Что делать, если при решении ЗЛП методом искусственного базиса в оценках векторов остались штрафы?

Question

[Ntonk]

Решаю следующую задачу целочисленного программирования методом Гомори:

F(X) = 3x_1 + x_2 -> max;
4x_1 + x_2 <= 19,
5x_1 - 2x_2 <= 15,
x_1 + x_3 <= 10;
x_1, x_2 >= 0.

Решил ослабленную задачу обычным симплекс-методом, введя базисные переменные x_3, x_4 и x_5, - ничего сложного. Полученная симплексная таблица:



Поскольку решение не является целочисленным, нашел переменную с наибольшей дробной частью x_1: {65/17} = 14/17. Получив новое ограничение 3/17x_4 + 2/17x_5 >= 14/17, ввел свободную переменную x_6 с коэффициентом -1 и базисную x_7. Целевая функция приобрела вид:

F(X) = 3x_1 + x_2 -Mx_7 -> max.

Решил полученную задачу симплекс-методом с искусственным базисом и получил допустимое базисное решение. Однако, хотя все переменные со штрафами М и вышли из базиса, в дельте j=7 штраф М остался:



В правильности полученного решения уверен, даже перепроверил его двумя онлайн-решалками.

Хотя это и было бы допустимым, если бы решалась обычная ЗЛП, в моем случае это мешает перейти к следующей итерации метода Гомори. А она необходима, поскольку полученное значение целевой функции F(X) = 3*3 + 1*7/3 = 34/3 не является целочисленным. В принципе, можно было бы забить и решать двойственным симплексом, но хотелось бы докопаться до причин происходящего. Понимаю, что не вправе просить повторять все муторные итерации симплекс-метода, поэтому прошу лишь указать в общих чертах, где может крыться проблема.

Answer 1

[Ntonk]

Вопрос решился сам собой: просто продолжать решать, вводя новые базисные переменные со штрафами. Штрафы с предыдущих итераций на решение не повлияют.