Метод отсекающих плоскостей

Идея этого метода предложена Данцингом и поэтому этот метод называют иногда методом Данцинга.

Пусть необходимо решить задачу ЦП:

Отбросив на время условие целочисленности, найдем оптимальный опорный план. Если он удовлетворяет условию целочисленности, то данный план искомый. В противном случае нужно сформулировать дополнительное ограничение, которому заведомо удовлетворяет любой целочисленный план, но не удовлетворяет найденный оптимальный план. Такое ограничение называют правильным отсечением. Геометрически правильное отсечение означает гиперплоскость, отсекающую от выпуклого многогранника соответствующей задачи ЛП некоторый многогранник, содержащий все целочисленные планы.

Таким образом, исходную систему ограничений дополняют правильным отсечением, после чего разыскивают оптимальное решение новой ЛП – задачи.

Если дополнительное ограничение сформировано правильно, то можно полагать, что через конечное число итераций будет найдено искомое решение задачи ЦП либо будет обнаружена несовместимость ее условий.