Целочисленное линейное программирование

Постановка задачи ЦЛП. Задача Линейного программирования в постановке

Где , называется задачей целочисленного линейного программирования. Причем, если , то задача частично целочисленная, а если ,то полностью.

Отдельным случаем задач ЦЛП являются задачи ЛП с булевыми переменными. К этом случае дополнительные условия записываются так: , при этом остаются целыми. Это означает, что неизвестные принимают только значения 0 или 1.

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