Симплексный метод решения задач ЗЛП

Интернет ресурсы

13. Задачи линейного программирования. Основные определения [Электронный ресурс]. – Режим доступа: http://stu.sernam.ru/book_sop.php?id=11, дата 10.12.2009.
14. Задачи линейного программирования. Теоретические основы ЗЛП – Режим доступа: http://ru.wikipedia.org/wiki, дата 15.01.2010.
15. Задачи линейного программирования. Примеры решения ЗЛП [Электронный ресурс]. – Режим доступа: http://www.matburo.ru/, дата 6.08.2011.
16. Задачи линейного программирования. Методы решения ЗЛП [Электронный ресурс]. – Режим доступа: http://math.semestr.ru/simplex/simplex.php, дата 15.05.2009.
17. Задачи линейного программирования. Симплекс метод решения – Режим доступа: http://mathminsk.com/sample/, дата 23.05.20010.

 

 

Приложение А

Блок-схема алгоритма симплекс-метода

 

Приложение B

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

int CSimpleks::iteration()

{

//Возвращаемые значения:

//1 - решение найдено

//-1 - решений нет

//0 - итерация закончилась  успешно

 

int o_Col=-1; //Опорный столбик

int o_Row=-1; //Опорная строка

float o_Col_temp=0; //Вспомогательная переменная

float o_Row_temp=-1; //Вспомогательная переменная

 

//Находим опорный столбик

for(int i=0; i<(size_small.x-1); i++)

{

if(!horzX[i].is_used) continue;   //Если базовая переменная сверху, пропустить

 

if( (matrix[size.y-1][i]<0) &&   //Элемент меньше нуля

(matrix[size.y-1][i]<o_Col_temp)) //Элемент меньше o_Col_temp

{

o_Col_temp=matrix[size.y-1][i];  //o_Col_temp равен текущему элементу

o_Col=i;       //Индекс столбика равен счетчику цикла

}

}

 

 

if(o_Col==-1) return 1; //Если отрицательных элементов нет, решение найдено

 

BOOL is_positive=FALSE; //Есть ли положительные значения в опорном столбике

 

//---Ищем положительные  значения в опорном столбике---

for(int i=0; i<size_small.y; i++)

{

if(matrix[i][o_Col]>0)

{

is_positive=TRUE;

o_Row_temp=matrix[i][size.x-1]/matrix[i][o_Col];

o_Row=i;

break;

}

}

 

if(!is_positive) return -1; //Положительных значений нет

 

 

//Находим опорную строчку

for(int i=0; i<size_small.y; i++)

{

if(matrix[i][o_Col]>0)

{

is_positive=TRUE; 

 

if((matrix[i][size.x-1]/matrix[i][o_Col])<o_Row_temp)

{

o_Row_temp=(matrix[i][size.x-1]/matrix[i][o_Col]);

o_Row=i;

}

}

}

 

if(o_Row==-1) return -1; //Если положительных элементов нет, решений нет

 

//Копируем bi в неиспользуемый более столбец matrix

 

for(int i=0; i<size.y; i++)

{

matrix[i][size_small.x-1]=matrix[i][size.x-1];

}

 

//Создаем новую таблицу

 

float ** chart=new float*[size.y];

 

for(int i=0; i<size.y; i++)

{

chart[i]=new float[size_small.x];

}

 

//Заполняем новую таблицу

 

for(int i=0; i<size.y; i++)

{

for(int j=0; j<size_small.x; j++)

{

if(i==o_Row && j==o_Col)  //Опорный элемент

{

chart[i][j]=1/matrix[o_Row][o_Col];

continue;

}

 

if(i==o_Row)     //Опорная строка

{

chart[i][j]=matrix[i][j]/matrix[o_Row][o_Col];

continue;

}

 

if(j==o_Col)     //Опорный столбик

{

chart[i][j]=-matrix[i][j]/matrix[o_Row][o_Col];

//chart[i][j]=0;

continue;

}

//В остальных  случаях вычисляем значение элемента  по формуле

chart[i][j]= ((matrix[i][j]*matrix[o_Row][o_Col]) - (matrix[i][o_Col]*matrix[o_Row][j]))/matrix[o_Row][o_Col];

 

}

}

 

//Делим все элементы  на опорный

 

for(int i=0; i<size.y; i++)

{

for(int j=0; j<size_small.x; j++)

{

//chart[i][j]=chart[i][j]/matrix[o_Row][o_Col];

 

//matrix[i][j]=chart[i][j];   //Копируем значения обратно в matrix

if(j==size_small.x-1)

{

//matrix[i][size.x-1]=chart[i][j];//Копируем bi в последний столбик matrix

}

}

}

 

//Копируем chart обратно в matrix

for(int i=0; i<size.y; i++)

{

 

for(int j=0; j<size_small.x; j++)

{

matrix[i][j]=chart[i][j];

 

if(j==size_small.x-1)

{

matrix[i][size.x-1]=chart[i][j];//Копируем bi в последний столбик matrix

}

}

}

 

//Меняем номера  переменных

 

var temp;

 

temp.num=horzX[o_Col].num;

temp.is_used=horzX[o_Col].is_used;

temp.type=horzX[o_Col].type;

 

horzX[o_Col].num=vertX[o_Row].num;

horzX[o_Col].is_used=vertX[o_Row].is_used;

horzX[o_Col].type=vertX[o_Row].type;

 

vertX[o_Row].num=temp.num;

vertX[o_Row].is_used=temp.is_used;

vertX[o_Row].type=temp.type;

 

//--------?--------//

if(horzX[o_Col].type==TRUE) horzX[o_Col].is_used=FALSE;

//--------?--------//

 

//Чистим память

 

delete[] chart;

 

 

//Итерация закончилась  успешно. Возвращаем 0

return 0;