Изложение метода Гомори-1

Метод Гомори-1 является одним из методов отсечения, идея которых заключается в следующем.

Решается вспомогательная ЗЛП (9.1)–(9.3), которую получают из исходной ЦЗЛП (9.1)–(9.4) отбрасыванием условия целочисленности переменных (9.4). Если оптимальное решение вспомогательной ЗЛП — целочисленный, то он будет и решением исходной ЦЗЛП. Если же полученное решение вспомогательной задачи не является целочисленным, то от развязанной ЗЛП переходят к новой вспомогательной ЗЛП присоединением линейного ограничения, которое удовлетворяют целочисленные развязки исходной ЦЗЛП и которое не удовлетворяет полученное нецелочисленное решение вспомогательной ЗЛП. Упомянутое дополнительное линейное ограничение определяет некоторую отрезающую плоскость и называется правильным відтином (ограничением). Присоединение новых правильных ограничений рассмотрена к начальной вспомогательной ЗЛП осуществляется до тех пор, пока на некотором шаге не будет получено целочисленное решение вспомогательной задачи, которое, очевидно, будет оптимальным решением исходной ЦЗЛП. В методе Гоморi-1 правильный ограничение строится таким образом.

Пусть на последней итерации симплекс-метода при решении вспомогательной ЗЛП непрямые ограничения этой задачи приобрели вид:

xi + а¢і,m+1 xm+1 +...+ а¢in xn = а¢i0, i=1...,m

и, таким образом, решением вспомогательной ЗЛП будет вектор

x = (а¢10..., а¢m0,0...,0).

Пусть существует номер r такой, что а¢r0 — дробь, и, как всегда {z} — дробная часть z. Тогда правильный відтин методу Гомори-1 задается неравенством:

{ а¢r,m+1 } xm+1 +...+ { а¢rn } xn ³ { а¢r0 }.