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

1. Экономико-математические методы и модели

к.э.н., доц. Косухина М.А.

2. Учебные вопросы

• Решение ЗЛП симплекс-методом:
•Метод искусственного базиса ( М-метод);
•Примеры.
27.02.2020
Лекция 4 ЭМММ
2

3. Метод искусственного базиса

• Последняя трудность, которую осталось преодолеть - это определение
исходного опорного плана и исходной симплекс-таблицы, с которой
начинаются все итерации.
• За счет чего мы так легко составили исходную симплекс-таблицу в
предыдущем примере из лекции 3 ? Легко видеть, что это произошло потому,
что среди переменных были такие, что входили лишь в одно уравнение
системы ограничений и не входили в другие.
• На искусственном введении таких переменных и основан метод
искусственного базиса.
27.02.2020
Лекция 4 ЭМММ
3

4. Метод искусственного базиса

• Итак, пусть мы имеем задачу линейного программирования в канонической
форме
• Можно считать, что все bi≥0, так как умножением соответствующего
ограничения на -1 всегда можно сменить знак.
• Возьмем ну очень большое число M и будем решать следующую
вспомогательную задачу.
27.02.2020
Лекция 4 ЭМММ
4

5. Вспомогательная задача

• В этой задаче сразу ясен исходный базис - в качестве него надо
взять переменные xn+1,…,xn+m.
• В качестве исходного опорного плана надо взять план
27.02.2020
Лекция 4 ЭМММ
5

6. Решение симплекс-таблицы

• А теперь начнем преобразования симплекс-таблицы, стараясь
выводить из базиса дополнительные переменные.
• Заметим, что если какая-то дополнительная переменная выведена
из базиса, то соответствующий столбец симплекс-таблицы можно
просто вычеркнуть и больше к нему не возвращаться.
• В конце концов возможны два варианта:
27.02.2020
Лекция 4 ЭМММ
6

7. Решение симплекс-таблицы

Вариант 1
•Все векторы, соответствующие введенным дополнительным
переменным, будут выведены из базиса.
•В этом случае мы просто вернемся к исходной задаче, попав в
какую-то вершину допустимой области.
•Все
столбцы
симплекс-таблицы,
соответствующие
дополнительным переменным, тогда исчезнут и дальше будет
решаться исходная задача.
27.02.2020
Лекция 4 ЭМММ
7

8. Решение симплекс-таблицы

Вариант 2
•Несмотря на то, что M очень велико, получающийся оптимальный план
будет все-таки содержать какую-то из дополнительных переменных.
•Это означает, что допустимая область исходной задачи пуста, то есть
ограничения исходной задачи противоречивы и поэтому исходная задача
вообще не имеет решений.
•Заметим в заключение, что величина M вообще не конкретизируется и
так и остается в виде буквы M.
•При решении учебных задач в дополнительную строку пишут
алгебраические выражения, содержащие M, а при счете на ПК вводится
еще одна дополнительная строка, куда пишутся коэффициенты при M.
27.02.2020
Лекция 4 ЭМММ
8

9. Пример 1

Введем дополнительные переменные:
27.02.2020
Лекция 4 ЭМММ
9

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

CБ
ХБ
M
х5
M
х6
1
х4
Инд. строка
Cj
-1
-2
-3
bi
x1
x2
x3
1
3
15
2
2
5
20
1
1
2
1
10
35M+10 3M+2 3M+4 8M+4
1
x4
0
0
1
M
x5
1
0
0
M
x6
0
1
0
0
0
0
Разрешающему столбцу соответствует наибольшая оценка = 8M+4 – столбец x3.
Разрешающую строку найдем по минимуму отношения:
Min {15/3; 20/5;10/1}=10 – строка х6
27.02.2020
Лекция 4 ЭМММ
10

11. Переходим к новой симплекс-таблице методом Жордана-Гаусса.

Cj
-1
CБ
ХБ
bi
x1
M
х5
3
1/5
-3
х3
4
2/5
1
х4
6
3/5
Инд. строка 3M-6 1/5M+8/5
-2
-3 1
x2
x3 x4
7/5
0 0
1/5
1 0
9/5
0 1
7/5M+16/5 0 0
M
x5
1
0
0
M
x6
-3/5
1/5
-1/5
0 -8/5M-4/5
Разрешающему столбцу соответствует наибольшая оценка = 7/5М+16/5 столбец x2 .
Разрешающую строку найдем по минимуму отношения: Min {15/7;
20;30/9}=15/7– строка х5
27.02.2020
Лекция 4 ЭМММ
11

12. Переходим к новой симплекс-таблице методом Жордана-Гаусса.

Cj
CБ
ХБ
bi
-2
х2 15/7
-3
х3 25/7
1
х4 15/7
Инд. строка -90/7
-1
x1
-1/7
3/7
6/7
6/7
-2
x2
1
0
0
0
-3
x3
0
1
0
1
x4
0
0
1
M
x5
5/7
-1/7
-9/7
0
0 -16/7-М
M
x6
-3/7
10/35
20/35
-М-4/7
Разрешающему столбцу соответствует наибольшая оценка = 6/7 - столбец x1 .
Разрешающую строку найдем по минимуму отношения: Min {-15;
25/3;15/6}=21/7– строка х4
27.02.2020
Лекция 4 ЭМММ
12

13. Переходим к новой симплекс-таблице методом Жордана-Гаусса.

Cj
CБ
ХБ
bi
-2
х2
5/2
-3
х3
5/2
-1
х1
5/2
Инд. строка -15
-1
x1
0
0
1
0
-2
x2
1
0
0
0
-3 1
x 3 x4
0 1/6
1 -3/6
0 7/6
0 -1
M
x5
M
x6
Ai-M
Ai-M
Полученный план оптимален.
Х* = (х1=5/2 ; x2=5/2 ; х3=5/2), F(x*)=-15
27.02.2020
Лекция 4 ЭМММ
13

14. Пример 2

max f(xi)=3x1+2x2+x3
2x1+x2=8
x1+x2+x3=6
X1,2,3>=0
Введем дополнительные переменные:
max f(xi)=3x1+2x2+x3-Mx4
2x1+x2+x4=8
x1+x2+x3=6
X1,2,3>=0
27.02.2020
Лекция 4 ЭМММ
14

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

CБ
ХБ
-M
х4
1
х3
Инд. строка
Cj
3
2
bi
x1
x2
2
8
1
1
1
6
-8M+6 -2M-2 -M-1
1
x3
0
1
-M
x4
1
0
0
0
Разрешающему столбцу соответствует наименьшая оценка = -2M-2 – столбец
x1.
Разрешающую строку найдем по минимуму отношения:
Min {8/2; 6/1;}=4– строка х4
27.02.2020
Лекция 4 ЭМММ
15

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

CБ
ХБ
3
х1
1
х3
Инд. строка
Cj
bi
4
2
14
3
x1
1
0
0
2
x2
1/2
1/2
0
1
x3
0
1
-M
x4
1/2
-1/2
0
M+1
Полученный план оптимален.
Х* = (х1=4 ; x2=0 ; х3=2), F(x*)=14
27.02.2020
Лекция 4 ЭМММ
16

17. Письменно ответить на вопросы

Решить методом искусственного базиса ЗЛП:
max f(xi)=x1+2x2+2x3
x1+2x2=6
x1+3x2+x3=12
х1,2,3>=0
Не забудьте указать ФИО и № группы!
27.02.2020
Лекция 4 ЭМММ
17