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

Построив первую таблицу, проверяем ее на оптимальность, то есть в последней строке таблицы ищем максимально отрицательный элемент, в нашем случае – это -8. Из этого следует, что столбец х2 становится ключевым. Далее в столбце х2 ищем ключевую строку: свободный член делим на элемент столбца х2, находящийся в этой же строке. Из полученных делений выбираем минимальное, у нас это будет 25. То есть строка, в которой получилось минимальное частное, будет являться ключевой (строка х5). А элемент, стоящий на пересечении ключевого столбца и ключевой строки будет являться ключевым элементом, в нашей задаче это будет 1.

Строим новую таблицу, следуя алгоритму, приведенному выше.

Таблица 3 – Итерация 2

Таблицу 3 проверяем на оптимальность таким же способом, что и изначальную таблицу. Находим ключевой элемент в таблице 3, и затем заново пересчитываем новую таблицу.

Таблица 4 – Итерация 3

В нашем случае таблица 4 стала окончательным решением, так как в последней строке нет отрицательных чисел, из этого следует, что мы нашли оптимальный способ решение поставленной задачи.

X 1=15; X 2=25; Fmax=305.

Для достижения максимальной прибыли, равной 305 руб., необходимо производить 15 изделий первого вида и 25 изделий второго вида в день.

4. Алгоритм программы

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

Вычислительная процедура симплекс-метода является итерационным процессом. Если задача содержит несколько переменных и ограничений, то этот процесс очень громоздок. Во многие практические задачи входят десятки переменных и ограничений (иногда намного больше), и ясно, что неразумно решать эти задачи вручную. Симплекс-метод – это метод для электронно-вычислительных машин. Не случайно развитие теории линейного программирования совпало по времени с развитием электронно-вычислительных машин. Без них теория имела бы весьма узкую область приложений.

5. Программа для общего случая

#include ”stdafx.h”

#include ”iostream”

#include “locale”

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{ int a,b,d,stl,str,baz[10],f,g=0,i,j,l=0,q=0,z=0,y=0,xx,z1[10];

float m,tab[10][10],min=1000,c[10],tab1[10][10],x=1000;

setlocale(LC_ALL, ”russian”);

cout<<“Введите количество строк и столбцов”<<endl;

cin>>a>>b;

//заполнение начальной матрицы

for (i=0;i<a;i++)

{

for (j=0;j<b;j++)

{cout<<”Введите [”<<i<<”][”<<j<<“] элемент таблицы”<<endl;

cin>>tab[i][j];

}}

cout<<”первая итерация”<<endl;

for (i=0;i<a;i++)

{

for (j=0;j<b;j++){cout<<tab[i][j]<<" ";}cout<<endl;}

//проверка на оптимальность

k:

l=0;

for (i=0;i<b;i++){

if (tab[a-1][i]<0) {l=l+1;}}

if (l==0){

for (j=1;j<b-a+1;j++){

int kol=0,nol=0,ind;

for (i=0;i<a-1;i++){

if (tab[i][j]==1) {kol++;ind=i;}

else nol++;

}

if ((kol==1) && (a-nol==2))

cout<<”x=”<<j<<”=”<<tab[ind][0]<<endl;

}cout<<”Решение оптимально”<<endl;

for (i=0;i<a;i++)

{ for (j=0;j<b;j++)

{cout<<tab[i][j]<< ” “;}cout<<endl;}

cout<<”F(x)=”<<tab[a-1][0];

return 0;}

x=1000;

//поиск ключевого столбца

for (i=1;i<b;i++)

{ if (tab[a-1][i]<=x)

{x=tab[a-1][i];

stl=i;

}}

//поиск ключевой строки

for (j=0;j<a-1;j++)

{ if (tab[j][stl]>0)

c[j]=tab[j][0]/tab[j][stl];

else

c[j]=1000;}

cout<<endl;

cout<<”Массив для нахождения ключевой строки”<<endl;

for (j=0;j<a-1;j++){

cout<<c[j]<< “ “;

}

cout<<endl;

for (i=0;i<(a-1);i++)

if (c[i]<min){

min=c[i];

str=i;

}

cout<<endl;

cout<<”Kлючевой столбец и ключевая строка”<<endl;

cout<<stl<<” ”<<str<<” “<<endl;

cout<<endl;

cout<<“Ключевой элемент:”<<tab[str][stl]<<endl;

cout<<endl;

//пересчет новой таблицы

for (i=0;i<a;i++)

{ for (j=0;j<b;j++)

{tab1[i][j]=tab[i][j]-(tab[i][stl]*tab[str][j]/tab[str][stl]);

tab1[i][stl]=0;

tab1[str][stl]=1;

tab1[str][j]=tab[str][j]/tab[str][stl];

}}

//переприсвоенние матриц и вывод их на экран

for (i=0;i<a;i++)

{ for (j=0;j<b;j++)

{ tab[i][j]=tab1[i][j];

}}

goto k;

return 0;

}

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

Введите количество строк и столбцов

4

6

Введите [0][0] элемент таблицы

150

Введите [0][1] элемент таблицы

5

Введите [0][2] элемент таблицы

3

Введите [0][3] элемент таблицы

1

Введите [0][4] элемент таблицы

0

Введите [0][5] элемент таблицы

0

Введите [1][0] элемент таблицы

20

Введите [1][0] элемент таблицы

1

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

1

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

25

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

1

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

1

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

-7

Введите [1][0] элемент таблицы

-8

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

0

Первая итерация

150 5 3 1 0 0

20 1 0 0 1 0

25 0 1 0 0 1

0 -7 -8 0 0 0

Массив для нахождения ключевой строки

50 1000 25

Ключевой столбец и ключевая строка

2 2

Ключевой элемент:1

Массив для нахождения ключевой строки

15 20 1000

Ключевой столбец и ключевая строка

1 0

Ключевой элемент:5

Решение оптимально!

х1=15

х2=25

F(x)=305

15 1 0 0.2 0 -0.6

5 0 0 -0.2 1 0.6

25 0 1 0 0 1

305 0 0 1.4 0 3.8

Заключение

Целью курсового проекта было решение задач линейного программирования симплекс-методом, составление алгоритма, составление программы по алгоритму и вывод результата на экран.

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

Он основан на пересчёте коэффициентов в системе уравнений и целевой функции при перемене мест свободной и базисной переменных можно формализовать и свести к преобразованию симплекс-таблицы.

Симплекс-метод является вычислительной процедурой представленной в алгебраической форме. Он непосредственно применяется к общей задаче линейного программирования в стандартной форме.

В данном проекте был составлен оптимальный план выпуска продукции каждого вида, обеспечивающий максимальную прибыль.

Список использованных источников

1.      Ашихмин В.Н. «Введение в математическое моделирование». Москва: Логос, 2005.

2.      Банди Б. «Основы линейного программирования». Москва: Радио и связь, 1989.

3.      Большакова И.В. «Линейное программирование». Минск: БНТУ, 2004.