Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Государственное образовательное учреждение
ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Математический факультет
Кафедра математического обеспечения информационных систем
Отчет
по лабораторной работе № 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.
//
#include"stdafx.h"
#include<iostream>
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;i<n;i++)
{
if (mas[i]>mm) {mm=mas[i];no=i;}
}
return no;
}
bool exitt(double mas[n])
{
for (int i=0;i<n;i++)
{
if (mas[i]>0.001) {return 0;}
}
return 1;
}
bool neogr(double mas[nn][n])
{
int k=0;
for (int i=0;i<nn;i++)
{
k=0;
for (int j=0;j<n;j++)
{
if (mas[i][j]<1) {k++;}
}
if (k==n) returntrue;
}
returnfalse;
}
int bp_free()
{
for (int i=0;i<n;i++)
{
if (bp_[i]==0) return i;
}
cout << "konec!!!"<<endl;
for (int i=0;i<n;i++)
{bp_[i]=0;}
return 0;
}
void update(double mas[nn][n],double mas1[nn][n])
{
for (int i=0;i<nn;i++)
for (int j=0;j<n;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;i<nn;i++)
{
for (int j=0;j<n;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;i<n;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;i<n;i++)
{
e[i+1]=A[nomer][i]/v_e;
}
// вывод
for (int i=0;i<nn;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;j<n;j++)
printf("%7.2f",A[i][j]);
printf("%7.2f",mini);
cout << endl;
}
cout<<"--------------------"<<endl;
cout << " ";
for (int j=0;j<n;j++)
printf("%7.2f",delta[j]);
cout << endl<< " ";
for (int j=0;j<n+1;j++)
printf("%7.2f",e[j]);
cout<<endl<<"---------------"<<endl;
while (exitt(delta)==false) // смотримвсёлиэлементывеотрицательны
{
if (neogr(A)==true) {cout<<"no 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;i<n;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;i<n;i++)
{delta[i]=C[i]-(C[bp[0]-1]*A1[0][i]+C[bp[1]-1]*A1[1][i]);}
if (exitt(delta)==true)
{
cout << endl<<endl;
for (int i=0;i<nn;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;j<n;j++)
{printf("%7.2f",A1[i][j]);}
cout << endl;
}
cout << " ";
for (int j=0;j<n;j++)
printf("%7.2f",delta[j]);
cout << endl<< " "<<endl<<endl;
double aa[n];
for (int i=0;i<n;i++) aa[i]=0;
aa[bp[0]-1]=Y0[0];
aa[bp[1]-1]=Y0[1];
cout<<"б.п. {";
for (int i=0;i<n;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;
cout<<"function(.)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;i<n;i++)
{
e[i+1]=A1[nomer][i]/v_e;
}
// вывод
for (int i=0;i<nn;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;j<n;j++)
printf("%7.2f",A1[i][j]);
cout <<" ";
printf("%5.2f",mini);
cout <<endl;
}
cout<<"-------------------"<<endl;
cout << " ";
for (int j=0;j<n;j++)
printf("%7.2f",delta[j]);
cout << endl<< " ";
for (int j=0;j<n+1;j++)
{printf("%7.2f",e[j]);}
cout<<endl<<"--------------"<<endl;
update(A,A1);
}
|