Кафедра маркетинга, коммерции и рекламы
Лабораторная работа
по курсу «Методы принятия управленческих решений»
Решение задач линейного программирования симплекс-методом
Решение задачи а)
Экономико-математическая модель
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 |
|
Невозможно выбрать разрешающий элемент – задача не имеет оптимального решения.
Скачать: