2.3 Получение целочисленного решения путем введения дополнительных ограничений по методу Гомори
Решение задачи без условия целочисленности приведено в пункте 1.1. Выбираем строку, в которой находится наибольшая дробная часть оптимального плана
БП |
Своб. члены |
НП |
|
x1 |
x4 |
||
x2 |
0,6 |
-0,8 |
0,4 |
x3 |
3,6 |
0,2 |
-0,6 |
x5 |
3,6 |
1,2 |
-3,6 |
x6 |
10,8 |
2,6 |
2,2 |
F |
-16,8 |
0,4 |
0,8 |
M |
0 |
0 |
0 |
x2 = 0,6 = {0,6}
Составим дополнительное ограничение по строке по алгоритму Гомори для полностью целочисленной задачи:
([-1]+ {0,2}) * x1 + {0,4} * x4 >= {0,6}
или
0,2 * x1+0,4* x4 >= 0,6
Приведем к виду равенства, введя дополнительную переменную x7 и домножим обе части неравенства на «-1»:
-0,2 * x1 - 0,4 * x4 + x7 = -0,6
Выражение представляет дополнительное линейное ограничение или отсечение Гомори, которое определяет гиперплоскость, отсекающую нецелочисленные решения задачи вместе с частью ОДЗП и сохраняющую при этом все целые решения.
Расширенная симплекс-таблица выглядит следующим образом:
БП |
Своб. члены |
НП |
|
x1 |
x4 |
||
x2 |
0,6 |
-0,8 |
0,4 |
x3 |
3,6 |
0,2 |
-0,6 |
x5 |
3,6 |
1,2 |
-3,6 |
x6 |
10,8 |
2,6 |
2,2 |
x7 |
-0,6 |
-0,2 |
-0,4 |
F |
-16,8 |
0,4 |
0,8 |
Осуществляем оптимизацию, так как решение не является допустимым, в столбце свободных членов есть отрицательный элемент произведем перерасчет симплекс-таблицы.
БП |
Своб. члены |
НП |
|
x7 |
x4 |
||
x2 |
3 |
-4 |
2 |
x3 |
3 |
1 |
-1 |
x5 |
0 |
6 |
-6 |
x6 |
3 |
13 |
-3 |
x1 |
3 |
-5 |
2 |
F |
-18 |
2 |
0 |
Получим целочисленное решение:
x 1=3
x 2=3
x 3=3
x 4=0
x 5=0
x 6=3
x7=0
F(X)=-18
Fmax =18