Задача целочисленного линейного программирования

Рассмотрим задачу в канонической форме с дополнительным условием:

переменные должны быть целыми числами

Как правило, производственная задача, в которой продукция неделимая, является целочисленной. Однако при решении непрерывной задачи оптимальный план зачастую имеет дробные компоненты. Его округление до целых не всегда подходит. Метод ветвей и границ впервые был применён к целочисленной линейной задаче. На нулевой итерации решается непрерывная задача в канонической форме и получается оптимальный план для неё. Если он оказался целочисленным, то он естественно будет оптимальным и для целочисленной задачи. В противном случае число оценка сверху (задача максимизации).

Затем множество дробиться на два подмножества по некоторой компоненте , которая оказалась дробной в .

ясно, что не пересекаются, а в объединении дают множество . Переходим к первой итерации.

. Для нахождения верхней границы, решается задача , где – это , в котором отброшено условие целочисленности.

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

Разбиением множеств на два новых осуществляется таким же образом, как и на нулевой итерации (по оптимальному плану непрерывной задачи на этом множестве).

И так далее.