Метод Гомори

Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:

оно должно быть линейным;

должно отсекать найденный оптимальный нецелочисленный план;

не должно отсекать ни одного целочисленного плана.

Дополнительное ограничение, обладающее указанными свойствами, называют правильным отсечением.

Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д.

Одним из методов отсечения является метод Гомори, который можно представить в виде следующих этапов:

1 этап: решение исходной задачи с ослабленными ограничениями симплекс-методом.

Пусть задана исходная задача линейного целочисленного программирования (6.1). Данная задача решается симплекс-методом без учета условий целочисленности проектных параметров (задача с ослабленными ограничениями). Если найденные оптимальные значения проектных параметров, обладающих условиями целочисленности, являются целыми числами, то данный план будет оптимальным и для исходной задачи линейного целочисленного программирования. Если задача с ослабленными ограничениями не разрешима, то и исходная задача линейного целочисленного программирования также не разрешима.