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

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