Решение задач линейного программирования симплекс методом 2

СОДЕРЖАНИЕ: Министерство образования и науки Российской Федерации Федеральное агентство по образованию Государственное образовательное учреждение ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Государственное образовательное учреждение

ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Математический факультет

Кафедра математического обеспечения информационных систем

Отчет

по лабораторной работе № 3

по дисциплине «Методы оптимизации»

Решение задач линейного программирования симплекс – методом

Руководитель:______Луговскова Ю.П.

«___»_______________________2010 г.

Исполнитель:

студент гр. 08МОС(у)

___________________Ледовского А.С.

«___»_______________________2010 г.

Оренбург 2010

Постановка задачи:

Найти максимум функции

Приограничениях

Дана функция:


Графический метод:

Точка максимума является (0;7)

Значение функции в данной точке = (0*(-1)+1*7) = 7

Симплекс – метод

Приведём данную функцию к каноническому виду

Матрица A =

Б={}

0 x3 2 1.00 -1.00 1.00 0.00 2.00

0 x4 7 2.00 1.00 0.00 1.00 2.00

--------------------------------------------

-1.00 1.00 0.00 0.00

-2.00 -1.00 1.00 -1.00 -0.00

--------------------------------------------

-1 x1 -2 -1.00 1.00 -1.00 -0.00 -2.00

0 x4 9 3.00 0.00 1.00 1.00 -2.00

--------------------------------------------

-2.00 2.00 -1.00 0.00

-2.00 -1.00 1.00 -1.00 -0.00

--------------------------------------------

1 x2 -2 -1.00 1.00 -1.00 -0.00 9.00

0 x4 9 3.00 0.00 1.00 1.00 9.00

--------------------------------------------

0.00 0.00 1.00 0.00

9.00 3.00 0.00 1.00 1.00

--------------------------------------------

1 x2 7 2.00 1.00 0.00 1.00

0 x3 9 3.00 0.00 1.00 1.00

-3.00 0.00 0.00 -1.00

б.п. {0 7 9 0 }

(.)max = (0;7)

function(.)max = 7

Код программы:


// lab3.cpp : Defines the entry point for the console application.

//

#includestdafx.h

#includeiostream

usingnamespace std;

constint n=4;

constint nn=2;

double A[2][n];

double A1[2][n];

int bp[2];

double Y0[2];

double mini;

double delta[n];

double e[n+1];

double C[4];

int bp_[n];

int maxi(double mas[n])

{

double mm=-1000;

int no;

for (int i=0;in;i++)

{

if (mas[i]mm) {mm=mas[i];no=i;}

}

return no;

}

bool exitt(double mas[n])

{

for (int i=0;in;i++)

{

if (mas[i]0.001) {return 0;}

}

return 1;

}

bool neogr(double mas[nn][n])

{

int k=0;

for (int i=0;inn;i++)

{

k=0;

for (int j=0;jn;j++)

{

if (mas[i][j]1) {k++;}

}

if (k==n) returntrue;

}

returnfalse;

}

int bp_free()

{

for (int i=0;in;i++)

{

if (bp_[i]==0) return i;

}

cout konec!!!endl;

for (int i=0;in;i++)

{bp_[i]=0;}

return 0;

}

void update(double mas[nn][n],double mas1[nn][n])

{

for (int i=0;inn;i++)

for (int j=0;jn;j++)

{mas[i][j]=mas1[i][j];}

}

int main()

{

freopen(input.txt,r,stdin);

freopen(output.txt,w,stdout);

cin C[0];

cin C[1];

C[2]=0;

C[3]=0;

// считали матрицу А

for (int i=0;inn;i++)

{

for (int j=0;jn;j++)

{cin A[i][j];bp_[j]=0;}

cin Y0[i];

}

bp[0]=3;

bp_[2]=0; // помечаем что в 3 были

bp[1]=4;

bp_[3]=0; // помечаем что в 4 были

int nomer=0;

// находимминимум

if (((Y0[0]/A[0][0])0)((Y0[0]/A[0][0])(Y0[1]/A[1][0]))) {mini=(Y0[0]/A[0][0]);}

else {mini=(Y0[1]/A[1][0]);nomer=1;}

// находимдельта

for (int i=0;in;i++)

{delta[i]=C[i]-(C[bp[0]-1]*A[0][i]+C[bp[1]-1]*A[1][i]);}

int s=maxi(delta); // номер ведущего столбца

double v_e=A[nomer][s];

// вычмсление строки ебсилон

e[0]=Y0[nomer]/v_e;

for (int i=0;in;i++)

{

e[i+1]=A[nomer][i]/v_e;

}

// вывод

for (int i=0;inn;i++)

{

printf(%2.0f,C[bp[i]-1]);

cout x;

printf(%1i,bp[i]);

cout ;

printf(%2.0f,Y0[i]);

cout ;

for (int j=0;jn;j++)

printf(%7.2f,A[i][j]);

printf(%7.2f,mini);

cout endl;

}

cout--------------------endl;

cout ;

for (int j=0;jn;j++)

printf(%7.2f,delta[j]);

cout endl ;

for (int j=0;jn+1;j++)

printf(%7.2f,e[j]);

coutendl---------------endl;

while (exitt(delta)==false) // смотримвсёлиэлементывеотрицательны

{

if (neogr(A)==true) {coutno ogran;return 0;} // проверяем есть ли столбцы со всеми отрицательными элементами

if (((bp[nomer])!=(bp_free()+1))((bp[1-nomer])!=(bp_free()+1)))

{

bp[nomer]=bp_free()+1;

bp_[bp_free()]=1;

}

else {bp[nomer]=bp_free()+2;bp_[bp_free()+1]=1;}

//пересчитываем матрицу А

Y0[nomer]=e[0];

Y0[1-nomer]=Y0[1-nomer]-e[0]*A[1-nomer][s];

for (int i=0;in;i++)

{

A1[nomer][i]=e[i+1];

A1[1-nomer][i]=A[1-nomer][i]-e[i+1]*A[1-nomer][s];

}

for (int i=0;in;i++)

{delta[i]=C[i]-(C[bp[0]-1]*A1[0][i]+C[bp[1]-1]*A1[1][i]);}

if (exitt(delta)==true)

{

cout endlendl;

for (int i=0;inn;i++)

{

printf(%2.0f,C[bp[i]-1]);

cout x;

printf(%1i,bp[i]);

cout ;

printf(%2.0f,Y0[i]);

cout ;

for (int j=0;jn;j++)

{printf(%7.2f,A1[i][j]);}

cout endl;

}

cout ;

for (int j=0;jn;j++)

printf(%7.2f,delta[j]);

cout endl endlendl;

double aa[n];

for (int i=0;in;i++) aa[i]=0;

aa[bp[0]-1]=Y0[0];

aa[bp[1]-1]=Y0[1];

coutб.п. {;

for (int i=0;in;i++) cout aa[i] ;

cout }endl;

if (aa[0]0.0001) C[0]=0;

cout(.)max = (C[0]*aa[0];C[1]*aa[1])endl;

coutfunction(.)max = C[0]*aa[0]+C[1]*aa[1];

return 0;

}

s=maxi(delta); // ведущийстолбец

// находимминимум

nomer=0;

if (((Y0[1]/A1[1][s])0)||(A1[1][s])==0)

{mini=(Y0[0]/A1[0][s]);nomer=0;}

else {mini=(Y0[1]/A1[1][s]);nomer=1;}

if ((A1[0][s])==0)

{mini=(Y0[1]/A1[1][s]);nomer=1;}

v_e=A1[nomer][s];

e[0]=Y0[nomer]/v_e;

for (int i=0;in;i++)

{

e[i+1]=A1[nomer][i]/v_e;

}

// вывод

for (int i=0;inn;i++)

{

printf(%2.0f,C[bp[i]-1]);

cout x;

printf(%1i,bp[i]);

cout ;

printf(%2.0f,Y0[i]);

cout ;

for (int j=0;jn;j++)

printf(%7.2f,A1[i][j]);

cout ;

printf(%5.2f,mini);

cout endl;

}

cout-------------------endl;

cout ;

for (int j=0;jn;j++)

printf(%7.2f,delta[j]);

cout endl ;

for (int j=0;jn+1;j++)

{printf(%7.2f,e[j]);}

coutendl--------------endl;

update(A,A1);

}

return 0 }

Скачать архив с текстом документа