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

x₂ = 0,6 = {0,6}

Составим дополнительное ограничение по строке по алгоритму Гомори для полностью целочисленной задачи:

([-1]+ {0,2}) * x₁ + {0,4} * x₄ >= {0,6}

или

0,2 * x₁+0,4* x₄ >= 0,6

Приведем к виду равенства, введя дополнительную переменную x₇ и домножим обе части неравенства на «-1»:

-0,2 * x₁ - 0,4 * x₄ + x₇ = -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

Таблица 1.9

Осуществляем оптимизацию, так как решение не является допустимым, в столбце свободных членов есть отрицательный элемент произведем перерасчет симплекс-таблицы.

БП	Своб. члены	НП
		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

Таблица 1.10

Получим целочисленное решение:

x ₁=3

x ₂=3

x ₃=3

x ₄=0

x ₅=0

x ₆=3

x₇=0

F(X)=-18

F_max =18

16