Главная / Математика / Оптимизация

Оптимизация

ЗАДАНИЕ

Целевая функция:

Система ограничений:

Найти максимум.

Теоретическая часть.

Решение задачи оптимизации линейной функции , используя симплекс-метод

Пусть задача состоит в том, что нужно найти такие неотрицательные значения x1, … xN, которые минимизируют линейную функцию при заданных ограничениях в виде системы уравнений :

Если в качестве ограничений заданы неравенства , то их можно преобразовать в равенство путём введения дополнительных отрицательных переменных, которые называются Балансовыми. Если уравнения системы линейно независимы, то число уравнений M Меньше числа переменных N , т. к. при M = N Система имеет единственное решение, что исключает оптимизацию. Выразим первые M Переменных X1, … , Xm Через остальные с помощью уравнений:

Переменные x1,…,xm называют Базисными , вектор { x1,…,xm } — Базисом ; xm+1,xm+2,…,xn — Свободные Переменные. Используя эту систему можно выразить линейную целевую функцию через свободные переменные:

(1)

Процесс оптимизации начинается с некоторого начального (опорного) решения; например при нулевых значениях свободных переменных. Тогда получим При этом целевая функция принимает значение (2) Дальнейшее решение задачи симплекс-методом распадается на ряд этапов, заключающихся в том, что от одного решения нужно перейти к другому с таким условием, чтобы целевая функция не возрастала. Это достигается выбором нового базиса и значений свободных переменных. Выясняется, является ли опорное решение оптимальным. Для этого проверяется, можно ли уменьшить соответствующее этому решению значение целевой функции при изменении каждой свободной переменной. Поскольку , то можно лишь увеличивать их значения.

Если коэффициенты в формуле (1) неотрицательны, то при увеличении любой свободной переменной целевая функция не может уменьшиться. В этом случае решение (2) окажется оптимальным.

Пусть среди коэффициентов формулы (1) хотя бы один отрицательный,

Например . Это означает, что при увеличении переменной целевая функция уменьшается по сравнению со значением , соответствующим решению (2). Поэтому в качестве нового опорного решения выбирается решение при следующих значениях свободных параметров:

(3)

При этом базисные переменные равны:

(4)

Если все коэффициенты неотрицательны, то можно увеличивать неограниченно; в этом случае не существует оптимального решения. Однако, на практике такого не бывает. Обычно среди коэффициентов имеются отрицательные, а это влечёт за собой угрозу сделать некоторые переменные в (4) отрицательными из-за большого значения . Следовательно, переменную можно увеличивать лишь до тех пор, пока базисные переменные остаются не отрицательными. Это является условием выбора значения . Его можно записать в виде:

(5)

Среди всех отрицательных коэффициентов находится наибольший по модулю. Пусть он равен , а соответствующее ему значение . Тогда из (5) получим максимально возможное значение переменной на данном шаге оптимизации: и новое опорное решение запишем в виде:

Новая целевая функция при этих значениях проектных параметров равна

Полученное значение целевой функции меньше предыдущего, поскольку в данной формуле второй член правой части больше нуля:

На этом заканчивается первый шаг оптимизации. Теперь необходимо сделать второй шаг, используя аналогичную процедуру. Для этого достаточно выбрать новый базис, принимая в качестве базисных переменных параметры . После второго шага либо находятся новые оптимальные значения переменных и соответствующее им значение целевой функции , либо окажется, что предыдущее решение является оптимальным. В любом случае после конечного числа шагов можно прийти к оптимальному решению.

Программа:

#include <stdio. h>

#include <conio. h>

#include <alloc. h>

#include <math. h>

#include <stdlib. h>

#include <stdarg. h>

Int n=4,m=3,gen_x, gen_y; float minx, miny; char * h,* v;

Struct item {

Float top;

Float bottom;

};

Void mprintf( char *fmt, … ){

va_list argptr;

va_start( argptr, fmt );

printf(fmt, argptr );

va_end( argptr );

}

Void out_matr(item * ptr, int x, int y, int fl){

Clrscr();

Printf(" ");

For(int j=0;j<m;j++) if(j) cprintf(" x:%-7c",h[j]); else cprintf(" ");

For(int i=0;i<n;i++){printf(" x%-4c ",v[i]);

For(int j=0;j<m;j++)

{

if((i==y||j==x)&&fl) {textcolor(15);textbackground(1);} else

{textcolor(7);textbackground(0);}

cprintf("%-10.2f¦",ptr[i*m+j].top);

}

Printf(" ");

For(j=0;j<m;j++)

{

if((i==y||j==x)&&fl) {textcolor(15);textbackground(1);} else

{textcolor(7);textbackground(0);}

cprintf("%10.2f¦",ptr[i*m+j].bottom);

}

Printf(" ");

For(j=0;j<m-1;j++)

{

if((i==y||j==x)&&fl) {textcolor(15);textbackground(1);} else

{textcolor(7);textbackground(0);}

cprintf("———-+");

}

if((i==y||j==x)&&fl) {textcolor(15);textbackground(1);} else

{textcolor(7);textbackground(0);}

Cprintf("———-+");

}

Printf(" ");

Textcolor(7);textbackground(0);

}

Void main(){

Printf("max->z=60*x1+50*x2 ");

Printf("4*x1+10*x2<=100 ");

Printf("2*x1+x2<=22 ");

Printf("3*x1+3*x2<=39 ");

H=(char *)malloc(m*sizeof(char));

V=(char *)malloc(n*sizeof(char));

For(int i=1;i<m;i++) h[i]=i+0x30;

For(i=1;i<n;i++) v[i]=i+m+0x30-1;

H[0]=’ ‘;

V[0]=’q’;

Item * matr=(item *)malloc(m*n*sizeof(item));

Item * temp=(item *)malloc(m*n*sizeof(item));

Matr[0].top=0;matr[1].top=-60;matr[2].top=-50;

Matr[3].top=100;matr[4].top=4;matr[5].top=10;

Matr[6].top=22;matr[7].top=2;matr[8].top=1;

Matr[9].top=39;matr[10].top=3;matr[11].top=3;

While(1){

Getch();

For(i=0;i<m;i++) if(matr[i].top<0) gen_x=i;

Miny=100000;

For( i=1;i<n;i++)

if(matr[i*m+gen_x].top>0)

if((matr[i*m].top/matr[i*m+gen_x].top)<miny)

{

miny=matr[i*m].top/matr[i*m+gen_x].top;

gen_y=i;

}

Matr[gen_y*m+gen_x].bottom=1.0/matr[gen_y*m+gen_x].top;

// Формируем главную строку и столбец

For(i=0;i<m;i++) if(i!=gen_x)

Matr[gen_y*m+i].bottom=matr[gen_y*m+i].top*matr[gen_y*m+gen_x].bottom;

For(i=0;i<n;i++) if(i!=gen_y)

Matr[i*m+gen_x].bottom=matr[i*m+gen_x].top*(-matr[gen_y*m+gen_x].bottom);

// Формируем остальные элементы матрицы

For(i=0;i<n;i++)

For(int j=0;j<m;j++)

If(i!=gen_y&&j!=gen_x){

Matr[i*m+j].bottom=matr[i*m+gen_x].bottom*matr[gen_y*m+j].top;

}

Int flag=0;

For(i=0;i<m;i++) if(matr[i].top<0) flag++;

If(!flag) {

Out_matr(matr, gen_x, gen_y,0);

Printf("Максимум найден!!!!!! ");

Printf("max=%.2f ",matr[0].top);

For(i=1;i<n;i++) printf("x[%c]=%.2f ",v[i],matr[i*m].top);

Printf(" ");

For(i=1;i<m;i++) printf("x[%c]=0 ",h[i]);

Exit(0);

}

Out_matr(matr, gen_x, gen_y,1);

Int t=h[gen_x];

H[gen_x]=v[gen_y];

V[gen_y]=t;

// Формируем дополнительную матрицу

For(i=0;i<m;i++) temp[gen_y*m+i].top=matr[gen_y*m+i].bottom;

For(i=0;i<n;i++) temp[i*m+gen_x].top=matr[i*m+gen_x].bottom;

For(i=0;i<n;i++)

For(int j=0;j<m;j++)

if(i!=gen_y&&j!=gen_x) temp[i*m+j].top=matr[i*m+j].top+matr[i*m+j].bottom;

For(i=0;i<m*n;i++) matr[i]=temp[i];

}

}

Результаты работы программы:

X1

X2

0.00

-60.0

-50.0

500.0

20.0

5.0

X3

100.0

4.0

10.0

10.0

0.4

0.1

X4

22.0

2.0

1.0

-10.0

-0.4

-0.1

X5

39.0

3.0

3.0

-30.0

-1.2

-0.3

X1

X3

500.0

-40.0

5.0

200.0

22.22

-6.67

X2

10.0

0.4

0.1

-2.0

-0.22

0.07

X4

12.0

1.6

-0.1

-8.0

-0.89

0.27

X5

9.0

1.8

-0.3

5.0

0.56

-0.17

X5

X3

700.0

22.22

-1.67

40.0

-8.89

10.0

X2

8.0

-0.22

0.17

-4.0

0.089

-1.0

X4

4.0

-0.89

0.17

24.0

-5.33

6.0

X1

5.0

0.56

-0.17

4.0

-0.89

1.0

X5

X3

740.0

13.33

10.0

-40.0

8.89

-1.67

X2

4.0

0.67

-1.0

4.0

-0.89

0.17

X4

24.0

-5.33

6.0

4.0

-0.89

0.17

X1

9.0

-0.33

1.0

-4.0

0.89

-0.17

Максимум : 740

X[2]=4.0 x[4]=24.0 x[1]=9.0

X[5]=0 x[3]=0