1.4 Выводы к Главе 1
В первой главе на примере данных трех задач продемонстрированы основные этапы и приемы, применяемые при решении задач линейного программирования.
Сложность решения задач линейного программирования определяется количеством переменных и ограничений в исходной задачe. Количество итераций зависит от того, на сколько «далеко» находится начальное базисное решение от оптимального.
2. Целочисленное программирование
2.1 Решение полностью целочисленной задачи
Максимизировать целевую функцию:
Y=-4x1-x2+3x3-2x4 → max
При ограничениях:
x1+2x2+0x3+0x4 ≥ 3
-2x1+0x2+0x3+2x4 ≤ -9
-x1-x2+x3+2x4 ≤ -5
x1+0x2-2x3+x4 ≥ 2
x1,2,3,4 ≥ 0 и целые
2.1.1 Решение задачи методом отсекающих плоскостей (метод Гомори)
Для решения целочисленной задачи воспользуется решением линейной задачи без требования целочисленности. Перепишем симплекс-таблицу решённой задачи из пункта 1.3.
Таблица 2.1
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
|
X5 |
5 |
0 |
0 |
0 |
-5 |
1 |
0 |
-2 |
1 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
|
X2 |
7/4 |
0 |
1 |
0 |
-2 |
0 |
1/4 |
-1 |
1/2 |
|
X3 |
5/4 |
0 |
0 |
1 |
-1 |
0 |
-1/4 |
0 |
1/2 |
|
Y |
-16 |
0 |
0 |
0 |
5 |
0 |
1 |
1 |
1 |
На основе этой симплекс-таблицы для базисной переменной x1 (у нее наибольшая дробная часть) строим уравнение отсекающей плоскости по следующей формуле:
где f – дробная часть свободного члена;
fij – дробные части коэффициентов строки.
Представим новое ограничение в форме Куна-Таккера:
x9=-1/2-(-5/16*x3-7/8*x5-5/8*x7-13/16*x8)
Добавляем это ограничение к условиям оптимального решения и решаем новую расширенную задачу симплекс-методом.
Таблица 2.2
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X4 |
7/2 |
0 |
0 |
-3/4 |
1 |
1/2 |
0 |
1/2 |
-3/4 |
0 |
|
X6 |
229/8 |
0 |
0 |
21/16 |
0 |
23/8 |
1 |
29/8 |
-99/16 |
0 |
|
X2 |
5/8 |
0 |
1 |
13/16 |
0 |
-1/8 |
0 |
-3/8 |
5/16 |
0 |
|
X1 |
35/8 |
1 |
0 |
11/16 |
0 |
1/8 |
0 |
3/8 |
-13/16 |
0 |
|
X9 |
-5/8 |
0 |
0 |
-5/16 |
0 |
-7/8 |
0 |
-5/8 |
-13/16 |
1 |
|
Y |
-109/8 |
0 |
0 |
139/16 |
0 |
9/8 |
0 |
11/8 |
3/16 |
0 |
Используем двойственный симплекс-метод. Вводим в базис X8, выводим из базиса X9.
Таблица 2.3
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X4 |
53/13 |
0 |
0 |
-6/13 |
1 |
17/13 |
0 |
14/13 |
0 |
-12/13 |
|
X6 |
434/13 |
0 |
0 |
48/13 |
0 |
124/13 |
1 |
109/13 |
0 |
-99/13 |
|
X2 |
5/13 |
0 |
1 |
9/13 |
0 |
-6/13 |
0 |
-8/13 |
0 |
5/13 |
|
X1 |
5 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
-1 |
|
X8 |
10/13 |
0 |
0 |
5/13 |
0 |
14/13 |
0 |
10/13 |
1 |
-16/13 |
|
Y |
-179/13 |
0 |
0 |
112/13 |
0 |
12/13 |
0 |
16/13 |
0 |
3/13 |
Решение оптимально. Так как переменная X8, подчиненная требованию целочисленности, и имеет дробное значение, то необходимо ввести дополнительное сечение относительно этой переменной:
x10=-10/13-(-5/13*x3-1/13*x5-10/13*x7-10/13*x9)
Таблица 2.4
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X4 |
53/13 |
0 |
0 |
-6/13 |
1 |
17/13 |
0 |
14/13 |
0 |
-12/13 |
0 |
|
X6 |
434/13 |
0 |
0 |
48/13 |
0 |
124/13 |
1 |
109/13 |
0 |
-99/13 |
0 |
|
X2 |
5/13 |
0 |
1 |
9/13 |
0 |
-6/13 |
0 |
-8/13 |
0 |
5/13 |
0 |
|
X1 |
5 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
-1 |
0 |
|
X8 |
10/13 |
0 |
0 |
5/13 |
0 |
14/13 |
0 |
10/13 |
1 |
-16/13 |
0 |
|
X10 |
-10/13 |
0 |
0 |
-5/13 |
0 |
-1/13 |
0 |
-10/13 |
0 |
-10/13 |
1 |
|
Y |
-179/13 |
0 |
0 |
112/13 |
0 |
12/13 |
0 |
16/13 |
0 |
3/13 |
0 |
Используем двойственный симплекс-метод. Вводим в базис X9, выводим из базиса X10.
Таблица 2.5
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X4 |
5 |
0 |
0 |
0 |
1 |
7/5 |
0 |
2 |
0 |
0 |
-6/5 |
|
X6 |
41 |
0 |
0 |
15/2 |
0 |
103/10 |
1 |
16 |
0 |
0 |
-99/10 |
|
X2 |
0 |
0 |
1 |
1/2 |
0 |
-1/2 |
0 |
-1 |
0 |
0 |
1/2 |
|
X1 |
6 |
1 |
0 |
3/2 |
0 |
11/10 |
0 |
2 |
0 |
0 |
-13/10 |
|
X8 |
2 |
0 |
0 |
1 |
0 |
6/5 |
0 |
2 |
1 |
0 |
-8/5 |
|
X9 |
1 |
0 |
0 |
1/2 |
0 |
1/10 |
0 |
1 |
0 |
1 |
-13/10 |
|
Y |
-182/13 |
0 |
0 |
17/2 |
0 |
9/10 |
0 |
1 |
0 |
0 |
3/10 |
Полученное решение удовлетворяет поставленным ограничениям и требованиям целочисленности. Решение является оптимальным.
Ответ: Y=-14, X=(6;0;0;5;0;41;0;2;1;0).