21. Особенности задач целочисленного программирования методом Гомори

Сначала задача решается без требования целочисленности. При этом может получиться целочисленный оптимальный план. В этом случае задача решена.

Если план не целочисленный, то выбирается дробная компонента (координата) плана и строится дополнительное линейное ограничение. Это ограничение должно обладать следующими свойствами:

- Ограничение не выполняется для нецелочисленного оптимального плана.

- Ограничение выполняется для любого целочисленного плана.

Далее решается расширенная задача с добавленным ограничением. В результате получается либо целочисленный план, либо не целочисленный.

Если план не целочисленный, то опять вводится новое линейное ограничение и т.д. до тех пор, пока не будет найден оптимальный план или показано что таких планов нет.

Комбинаторные методы.

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