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

В-алгоритм Ю. Ю. Финкельштейна предназначен для решения задач целочисленного линейного программирования с булевыми переменными. Это отражено и в его названии: В-алгоритм. Специфика задачи с булевыми переменными существенно используется при построении правильных отсечений.

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

Найти -максимум вектора

при условиях

целые,

Здесь

4.2. Теорема 4.1. Пусть есть -опти-мальный опорный план задачи не целое, Тогда неравенство

задает правильное отсечение.

4.3. Доказательство теоремы 4.1. Сначала проверим условие отсечения. Действительно,

так что условие отсечения выполняется.

Переходим к проверке условия правильности. Так как вектор является -максимальным (при условиях задачи то (при тех же условиях) является -максимальным и вектор Следовательно, для любого плана X задачи С) имеем

(равенство невозможно, ибо не целое). Возможны два случая:

В случае 1)

и неравенство (4.6) выполняется. В случае 2)

и из (4.7) следует, что

так что для некоторого

Имеются две возможности:

и какая бы из них ни реализовалась, всегда

так что неравенство (4.6) верно и в этом случае.

4.4. Перепишем теперь неравенство (4.6) в форме, удобной для вычислений по -методу, считая, что оптимальному нецелочисленному плану соответствует таблица

4.5. Для доказательства конечности -алгоритма используется лексикографическое убывание векторов (как и для первого алгоритма Гомори) и тот факт, что существует лишь конечное число ограничений вида (4.6).

4.6. Любая частично целочисленная задача линейного программирования с целочисленной целевой функцией, целочисленными переменными и ограниченным множеством планов может быть сведена к задаче вида с помощью введения новых булевых переменных. Для каждой переменной определяются границы ее изменения Числа можно считать целыми.

Тогда представляется в виде

где булевы переменные. Вместо максимума следует искать лексикографический максимум вектора

Если же целевая функция не обязана быть целой, то можно получить приближенное решение с любой наперед заданной точностью (по значению целевой функции). Для этого условие максимизации целевой функции заменяется на условие -максимизации вектора и последовательно добавляются ограничения вида (более подробно см. Ю. Ю. Финкельштейн [29]).