x₁£20

x₂£25

x1, x2≥0

F(x) = 7x₁+8x₂®max

Приведем заданную модель к каноническому виду, введя свободные переменные x3, x4, x5, превращающие неравенства в равенства. Переменные x3, x4, x5 входят в уравнение с коэффициентом единица и только один раз:

5x₁+ 3x₂+x₃=150

x₁+x₄=20

x₂+x₅=25

x1, x2, x3, x4, x5≥0

F(x)= 7x₁+8x₂+x₃+x₄+x₅

x_3,x_4,x₅– базисные переменные; x_1,x₂– свободные переменные.

Составим симплекс – таблицу, соответствующую каноническому виду:

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

Базис	Свободные чл.	X₁	X₂	X₃	X₄	X ₅
X ₃	150	5	3	1	0	0
X ₄	20	1	0	0	1	0
X ₅	25	0	1	0	0	1
F(x)	0	-7	-8	0	0	0

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

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

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

Базис	Свободные	X₁	X₂	X₃	X₄	X₅
X₃	75	5	0	1	0	-3
X₄	20	1	0	0	1	0
X₂	25	0	1	0	0	1
F(x)	200	-7	0	0	0	8

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

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

Базис	Свободные	X₁	X₂	X₃	X₄	X₅
X₁	15	1	0	0,2	0	-0,6
X₄	5	0	0	-0,2	1	0,6
X₂	25	0	1	0	0	1
F(x)	305	0	0	1,4	0	3,8

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

X₁=15; X₂=25; F_max=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;}

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

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. Результаты работы программы

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

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

150

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

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

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

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

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

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

-7

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

-8

Введите [1][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.

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

Заключение