без учета требования целочисленности симплекс-методом. Результаты пошагового решения приведены в табл. 12.1-12.3.
Таблица 12.1
|
|
|
1
|
-1
|
0
|
0
|
-М
|
|
|
|
|
|
|
|
|
|
|
-М
|
|
4
|
-1
|
[2]
|
-1
|
0
|
1
|
|
0
|
|
14
|
3
|
2
|
0
|
1
|
0
|
7
|
|
|
|
М
|
-2М
|
М
|
0
|
- М
|
|
|
|
|
1- М
|
-1+2М
|
- М
|
0
|
0
|
|
Вводим в базис переменную , выводим .
Таблица 12.2
|
|
|
1
|
-1
|
0
|
0
|
-М
|
|
|
|
|
|
|
|
|
|
|
-1
|
|
2
|
|
1
|
|
0
|
|
--
|
0
|
|
10
|
[4]
|
0
|
1
|
1
|
-1
|
|
|
|
|
|
-1
|
|
0
|
-
|
|
|
|
|
|
0
|
-
|
0
|
-M+
|
|
Вводим в базис переменную , выводим .
Таблица 12.3
|
|
|
1
|
-1
|
0
|
0
|
-М
|
|
|
|
|
|
|
|
|
|
|
-1
|
|
|
0
|
1
|
|
|
1
|
|
1
|
|
|
1
|
0
|
|
|
-
|
|
|
|
|
1
|
-1
|
|
|
-
|
|
|
|
|
0
|
0
|
-
|
-
|
-M+
|
|
Оптимальное решение (рис. 12.2) целочисленным не является, . Включаем в множество номеров задач, подлежащих ветвлению , и переходим к шагу 2.
20. Так как выбираем для ветвления задачу ЗЛП-0 , исключаем из множества и переходим к шагу 3.
30. Осуществим ветвление задачи ЗЛП-0. Выбираем координату , так как ее значение имеет наибольщую дробную часть, и сформируем:
а) дополнитльные ограничения
б) две задачи ЗЛП-
ЗЛП-1 ЗЛП-2
Перепишем их в расширенной форме (см.§11.1):
ЗЛП-1 ЗЛП-2
Полагаем и переходим к шагу 4.
40. Решаем задачу ЗЛП-1. Результаты пошагового решения задачи ЗЛП-1 приведены в табл. 12.4-12.6.
Таблица 12.4
|
|
|
1
|
-1
|
0
|
0
|
0
|
-М
|
|
|
|
|
|
|
|
|
|
|
|
-M
|
|
4
|
-1
|
[2]
|
-1
|
0
|
0
|
1
|
|
0
|
|
14
|
3
|
2
|
0
|
1
|
0
|
0
|
7
|
0
|
|
2
|
1
|
0
|
0
|
0
|
1
|
0
|
--
|
|
|
|
M
|
- 2M
|
M
|
0
|
0
|
- M
|
|
|
|
|
1- M
|
-1+ 2M
|
- M
|
0
|
0
|
0
|
|
Вводим в базис переменную , выводим .
Таблица 12.5
|
|
|
1
|
-1
|
0
|
0
|
0
|
-М
|
|
|
|
|
|
|
|
|
|
|
|
-1
|
|
2
|
|
1
|
|
0
|
0
|
|
--
|
0
|
|
10
|
2
|
0
|
1
|
1
|
0
|
-1
|
5
|
0
|
|
2
|
[1]
|
0
|
0
|
0
|
1
|
0
|
2
|
|
|
|
|
- 1
|
|
0
|
0
|
-
|
|
|
|
|
|
0
|
-
|
0
|
0
|
-M+
|
|
Вводим в базис переменную , выводим .
Таблица 12.6
|
|
|
1
|
-1
|
0
|
0
|
0
|
-М
|
|
|
|
|
|
|
|
|
|
|
|
-1
|
|
3
|
0
|
1
|
|
0
|
|
|
|
0
|
|
6
|
0
|
0
|
1
|
1
|
-2
|
-1
|
|
0
|
|
2
|
1
|
0
|
0
|
0
|
1
|
0
|
|
|
|
|
1
|
- 1
|
|
0
|
|
-
|
|
|
|
|
0
|
0
|
-
|
0
|
-
|
-M+
|
|
Оптимальное решение (точка на рис. 12.2) Переходим к шагу 5.
50. Решение -первое целочисленное. Полагаем - первое целочисленное. Полагаем и включаем решение в множество . Так как , то сравнивать значение не с чем. Перейдем к шагу 6.
60. Проверим вқполнение условия . Полагаем и переходим к шагу 4.
41. Решаем задачу ЗЛП-2. Результаты ее пошагового решения приведены в табл. 12.7-12.9.
Таблица 12.7
|
|
|
1
|
-1
|
0
|
0
|
0
|
-М
|
-М
|
|
|
|
|
|
|
|
|
|
|
|
|
-M
|
|
4
|
-1
|
[2]
|
-1
|
0
|
0
|
1
|
0
|
|
0
|
|
14
|
3
|
2
|
0
|
1
|
0
|
0
|
0
|
7
|
-M
|
|
3
|
1
|
0
|
0
|
0
|
-1
|
0
|
1
|
--
|
|
|
|
0
|
- 2M
|
M
|
0
|
M
|
- M
|
- M
|
|
|
|
|
1
|
-1+ 2M
|
- M
|
0
|
- M
|
0
|
0
|
|
Вводим в базис переменную , выводим .
Таблица 12.8
|
|
|
1
|
-1
|
0
|
0
|
0
|
-М
|
-М
|
|
|
|
|
|
|
|
|
|
|
|
|
-1
|
|
2
|
-
|
1
|
-
|
0
|
0
|
|
0
|
--
|
0
|
|
10
|
[4]
|
0
|
1
|
1
|
0
|
-1
|
0
|
|
-M
|
|
3
|
1
|
0
|
0
|
0
|
-1
|
0
|
1
|
3
|
|
|
|
-M+
|
1
|
|
0
|
M
|
-
|
- M
|
|
|
|
|
M+
|
0
|
-
|
0
|
- M
|
- M+
|
0
|
|
Вводим в базис переменную , выводим .
Таблица 12.9
|
|
|
1
|
-1
|
0
|
0
|
0
|
0
|
-М
|
|
|
|
|
|
|
|
|
|
|
|
|
-1
|
|
|
0
|
1
|
-
|
|
0
|
-
|
0
|
|
1
|
|
|
1
|
0
|
|
|
0
|
-
|
0
|
|
-M
|
|
|
0
|
0
|
-
|
-
|
-1
|
|
1
|
|
|
|
|
1
|
-1
|
|
|
M
|
-
|
- M
|
|
|
|
|
0
|
0
|
-
|
-
|
- M
|
-
|
0
|
|
Решение закончено , но из табл. 12.9 следует , что ограничения задачи ЗЛП-2 несовместны – множество допустимых решений пусто (рис.12.2) , потому что искусственная переменная в оптимальном решении не равна нулю. Исключаем задачу ЗЛП-2 из рассмотрения. Переходим к шагу 6.
61. Проверим выполнение условия . Переходим к шагу 2.
21. Так как множество , переходим к шагу 7.
70. Так как множество содержит единственное целочисленное решение, то решение исходной задачи. ■
Пример 12.2. Найти оптимальное решение задачи
□ 1. Положим . Решаем ЗЛП-0 , т.е. исходную задачу без учета требования целочисленности, графически. Как следует из рис. 12.3, , максимум достигается в точке . Решение не является целочисленным. Включаем номер в множество и переходим к шагу 2.
20. Так как , выбираем для ветвления задачу ЗЛП-0 , исключаем и из множества и переходим к шагу 3.
30. Осуществим ветвление задачи ЗЛП-0. Выберем нецелочисленную координату с наименьшим индексом: . Сформируем:
а) дополнительные ограничения:
б) две задачи ЗЛП-
ЗЛП-1 ЗЛП-2
Do'stlaringiz bilan baham: |