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

0

Кафедра маркетинга, коммерции и рекламы

 

 

 

Лабораторная работа

 

по курсу «Методы принятия управленческих решений»

 

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

 

Решение  задачи а)

Экономико-математическая модель

 F=5x1+4x2→max

 

x1+x2≤18                               

5x1-x2≤20   

х1-х2≤8                           

 

x1≥0                                       

x2≥0                                       

                    

Каноническая форма:

F=5x1+4x2→max

 

x1+x2+х3=18                               

5x1-x2+х4=20   

х1-х2+х5=8                           

 

x1≥0,   x2≥0,    x3≥0,    x4≥0,     x5≥0                                       

                            

А1=                А2=             А3=               А4=            А5=                В=                                 

                               

Базис образуют вектора А3, А4, А5                                    

 

Строим симплекс-таблицу

Базис

С баз

В

А1

А2

А3

А4

А5

Q

A3

0

18

1

1

1

0

0

18/1=18

A4

0

20

5

-1

0

1

0

20/5=4

A5

0

8

1

2

0

0

1

8/1=8

 

F(x)

0*18+

0*20+

0*8=0

0*1+

0*5+

0*1-5=-5

0*1+

0*(-1)+0*(-1)-4=-4

0*1+

0*1

+0*0=0

0*0+

0*1+

0*0=0

0*0+

0*0+

0*1=0

 

А1 войдет в базис, А4 – уйдет из базиса. Cтроим новую симплекс-таблицу.

Базис

С баз

В

А1

А2

А3

А4

А5

Q

A3

0

18-(20*1)/5=14

0

1-1*(-1)/5=6/5

1-(1*0)/5=1

0-(1*1)/5=-1/5

0-(1*0)/5=0

14/(6/5)=

70/6

A1

5

20/5=4

1

-1/5

0

1/5

0

-

A5

0

8-(20*1)/5=4

0

1-(1*(-1)/5=-4/5

0-0*1/5=0

0-(1*1)/5=-4/5

1-(1*0)/5=1

-

 

F(x)

0*14+5*4

+0*4-0=20

0*0+5*1

+0*0-5= 0

0*6/5+5*(-1/5)+0*(-4/5)-4= -5

0*1+5*0

+0*0-0=0

0*(1/5)+

(5*1)/5

+0*(-4/5)-0=1

0*0+5*0

+0*1-0=0

 

 

Получаем:

Базис

С баз

В

А1

А2

А3

А4

А5

Q

A3

0

14

0

6/5

1

-1/5

0

70/6

A1

5

4

1

-1/5

0

1/5

0

-

A5

0

4

0

-4/5

0

-4/5

1

-

 

F(x)

0

0

-5

0

1

0

 

А3 уйдет из базиса, А2 – войдет в базис.

Следующая симплекс-таблица:

Базис

С баз

В

А1

А2

А3

А4

А5

Q

A2

4

6 1/3

0

1

5/6

-1/6

0

 

A1

5

11 2/3

1

0

1/6

1/6

0

 

A5

0

13 1/3

0

0

2/3

2/15

1

 

 

F(x)

78 1/3

0

0

4 1/6

1/6

0

 

 

Все оценки больше либо равны нуля, поэтому решение оптимальное.

Ответ: F(max)=78 1/3, x1=6 1/3, x2=11 2/3

Решение задачи а) с помощью программы SIMP.

 

Задача в)

Решение задачи на максимум

 

F= x1-2x2→max

 

2x1+x2≥13

x1+x2≤11

 

x1≥0, x2≥0

 

Каноническая форма:

 

F=x1-2x2→max

 

2x1+x2-x3=13

x1+x2+x4=11

 

x1…4≥0

 

Ставим вспомогательную задачу:

 

G(y1)=-y1→max

 

2x1+x2-x3+y1=13

x1+x2+x4=11

 

x1…4≥0  y1≥0

 

Решаем вспомогательную задачу:

 

Базис

С баз

В

А1

А2

А3

А4

Ау1

Q

Ау1

-1

13

2

1

-1

0

1

6 ½

А4

0

11

1

1

0

1

0

11

 

 

-13

-2

-1

1

0

0

 

 

 

Базис

С баз

В

А1

А2

А3

А4

Ау1

Q

А1

0

6 ½

1

1/2

-1/2

0

1/2

6 1/2

А4

0

4 ½

0

1/2

1/2

1

-1/2

11

G(y1)

 

6 ½

0

0

0

0

1

 

 

Все ∆j≥0, вспомогательная задача решена

 

Х*вспом=(6 ½ ,0,0,4 ½ ,0)

 

Т.к. все у=0, переходим к решению основной задачи

 

F=x1-2x2→max

 

Базис

С баз

В

А1

А2

А3

А4

Q

А1

1

6 ½

1

1/2

-1/2

0

-

А4

0

4 ½

0

1/2

1/2

1

9

F(х)

 

6 1/2

0

2 1/2

-1/2

0

 

 

Базис

С баз

В

А1

А2

А3

А4

А1

1

11

1

1

0

1

А3

0

9

0

1

1

2

F(х)

 

11

0

3

0

1

 

Все ∆j≥0,  оптимальное решение найдено

 

Х*=(11,0,9,0,0)

F max = 11

 

Ответ: F max =11

 

 

 

Решение задачи в программе SIMP

 

 

Задача в) минимум

F= x1-2x2→min

 

2x1+x2≥13

x1+x2≤11

 

x1≥0, x2≥0

 

Каноническая форма:

 

F=-x1+2x2→max

 

2x1+x2-x3=13

x1+x2+x4=11

 

x1…4≥0

 

Ставим вспомогательную задачу:

 

G(y1)=-y1→max

 

2x1+x2-x3+y1=13

x1+x2+x4=11

 

x1…4≥0  y1≥0

 

Решаем вспомогательную задачу:

 

Базис

С баз

В

А1

А2

А3

А4

Ау1

Q

Ау1

-1

13

2

1

-1

0

1

6 ½

А4

0

11

1

1

0

1

0

11

 

 

-13

-2

-1

1

0

0

 

 

 

Базис

С баз

В

А1

А2

А3

А4

Ау1

Q

А1

0

6 ½

1

1/2

-1/2

0

1/2

6 1/2

А4

0

4 ½

0

1/2

1/2

1

-1/2

11

G(y1)

 

6 ½

0

0

0

0

1

 

 

Все ∆j≥0, вспомогательная задача решена

 

Х*вспом=(6 ½ ,0,0,4 ½ ,0)

 

Т.к. все у=0, переходим к решению основной задачи

 

F=-x1+2x2→max

 

Базис

С баз

В

А1

А2

А3

А4

Q

А1

-1

6 ½

1

1/2

-1/2

0

13

А4

0

4 ½

0

1/2

1/2

1

9

F(х)

 

-6 1/2

0

-2 1/2

1/2

0

 

 

Базис

С баз

В

А1

А2

А3

А4

Q

А1

-1

2

1

0

1

-1

 

А2

2

9

0

1

1

2

 

F(x)

 

16

0

0

1

5

 

 

Все ∆j≥0,  оптимальное решение найдено

 

Х*=(2,9,0,0,0)

F max = 16

 

Ответ: F min =16

 

 

Задача с) максимум

 

F=2x1+x2→max

 

-2х1+х2≥1

х1-2х2≥1

 

х1≥0, х2≥0

 

Каноническая форма

 

F=2x1+x2→max

 

-2х1+1х2-х3=1

х1-2х2-х4=1

 

х1…4≥0

 

Ставим вспомогательную задачу

 

G(y1,y2)=-y1-y2→max

 

-2х1+1х2-х3+у1=1

х1-2х2-х4+у2=1

 

х1…4≥0  y1,2≥0

 

 

Базис

С баз

В

А1

А2

А3

А4

Ay1

Ay2

 

Аy1

-1

1

-2

1

-1

0

1

0

-

Аy2

-1

1

1

-2

0

-1

0

1

-

F(x)

 

-2

1

1

1

1

0

0

 

 

Невозможно выбрать разрешающий элемент – задача не имеет оптимального решения.

 

Скачать:   У вас нет доступа к скачиванию файлов с нашего сервера. КАК ТУТ СКАЧИВАТЬ

 

Категория: Лабораторные работы / Лабораторные работы по математике

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.