Решение задач линейного программирования симплекс методом 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.

//



#include "stdafx.h"

#include <iostream>

using namespace std;

const int n=4;

const int 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) return true;

	}

	return false;

}

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);

}

	return 0 }