5.1 Общая характеристика методов отсечения

Предположим, что мы решили ЛП-релаксацию данной зада­чи ЦЛП, например, с помощью какого-либо варианта симплекс-метода и нашли оптимальное базисное решение ж0. Если полу­ченное решение удовлетворяет условию целочисленности, то оно и является оптимальным решением рассматриваемой задачи ЦЛП. Если же не все компоненты ж0 целочисленны, то формируется новая задача ЛП путем добавления нового ограничения. Доба­вляемое ограничение (называемое отсечением) выбирается так, что ж0 этому ограничению не удовлетворяет (отсекается), в то время как все допустимые решения задачи ЦЛП остаются допу­стимыми решениями новой задачи ЛП. Затем решается новая за­дача ЛП и выше указанные шаги повторяются до тех пор, пока не будет получено решение задачи ЦЛП, либо не обнаружится ее неразрешимость. В общем случае конечность такого процесса не гарантируется. Исторически первым алгоритмом рассматрива­емого типа, конечность которого при достаточно общих предпо­ложениях установлена, был первый (или циклический) алгоритм Гомори. Сама идея метода принадлежит Данцигу.