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

Постановка задачи целочисленного линейного программирования. В целом ряде случаев в задаче линейного программирования присутствует дополнительное условие о том, что все или некоторые переменные должны быть целочисленными. Эти условия возникают тогда, когда дробные значения переменных противоречат их физическому смыслу. С точки зрения математики это условие приводит к принципиально новому классу моделей — целочисленному программированию. Принципиальная особенность таких задач заключается в том, что X принадлежит дискретному множеству, а это в свою очередь требует пересмотра многих положений теории линейного программирования.

В общем случае задача целочисленного линейного программирования (ЦЛП) имеет вид.

На практике последнее условие в (15.1) часто заменяется условием булевости переменных, т. е. х_;— принимает одно из двух возможных значений: 0 или 1.

Задача (15.1) очень похожа на задачу линейного программирования. Однако требование целочисленное™ переменных вызывает необходимость отнести ее к совершенно другому классу задач — задачам оптимизации на дискретных множествах. Рассмотрим геометрическую иллюстрацию к такого рода задаче. Как показано на рис. 15.1, область возможных значений в ЦЛП — множество целочисленных точек, расположенных внутри ОДР соответствующей нецелочисленной задачи линейного программирования.

Рис. 15.1. Область допустимых значений в задаче целочисленного программирования.

Как решать задачи ЦЛП? Самый простой, на первый взгляд, способ — метод полного перебора: можно рассмотреть все целочисленные точки ОДР, подсчитать в них значения целевой функции и выбрать ту, где значение W (X) наибольшее. Однако для практики этот путь неперспективен, поскольку даже для самых скоростных компьютеров длительность такой процедуры решения будет неприемлемо большой.

Казался бы, естественным будет такой подход: решить соответствующую задачу линейного программирования, а затем округлить полученное решение. Однако такой путь так же неперспективен, поскольку во многих случаях размер получаемой ошибки будет неприемлем. В доказательство этому рассмотрим следующий пример.

Пример 15.1.

Найти минимум функции при условиях.

Решение. Если отбросить требование целочисленности и решать задачу как непрерывную, то получим решение х_г = 5,9, х₂=0 и W = -59. Простое округление этого результата приводит к недопустимому решению Xj = 6, х₂ = 0. Вместе с тем исследование области решений целочисленной задачи приводит к нахождению ее оптимального решения: Xi = 1, х*₂=4, W‘=-54.

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

Метод ветвей и границ. Среди применяемых сегодня методов решения задач ЦЛП наибольшее распространение получил метод ветвей и границ [18]. Идея метода заключается в следующем. Пусть имеется пара задач: ЦЛП и соответствующая ее непрерывная задача ЛП, т. е.

Очевидно, что всегда выполняется условие L (X) > W (X). Таким образом, решение соответствующей задачи ЛП обеспечивает получение оценки решения ЦЛП сверху (дает верхнюю границу для ЦЛП). Область допустимых решений R разбивается на непересекающиеся подмножества R = JR₍ /i, j Rif]Rj =0 (ветвление процесса). Для каждой подобласти R, решается непрерывная задача ЛП и определяется L (R,). Если.

3i: V/ L (X,) > L (Xj) л X, — е Z", (15.2).

то X, — решение ЦЛП. В противном случае подобласть с наибольшим значением L (X_;) вновь подвергается делению и проверяется выполнение условия (15.2), включая и все неразбитые на последнем шаге подобласти.

Проиллюстрируем вышеизложенное на следующем простом примере.

Пример 15.2 [14].

Максимизировать при условиях

Решение. После решения соответствующей исходной задачи линейного программирования (15.3)—(15.5) получим нецелочисленное решение: Xg = (Xj = 1,2, х₂=2,2) при значении целевой функции ЩХд) = 12,4.

Осуществим ветвление этой задачи на две посредством введения условий Xj 2 (рис. 15.2):

Решение этих задач дает следующие результаты: для I — Х_п = (xj = 1, х₂= 2,25), ЩХ_П) = 12; для II — Х₁₂ = (xj = 2, х₂ = 1), ЩХ₁₂) =10.

Решение Х₁₂ — целочисленное. Однако решение Х_п дает большее значение целевой функции и там может находиться искомый максимум, поэтому проводим разветвление задачи I. Поскольку х, в Х_и целое, то разветвление проводим пох₂, вводя условиях₂<2их₂>3. Вновь рассматриваем две нецелочисленные задачи:

Решение для III: Х₂₁ = (Xj = 1, x₂ = 2), W (X₂₁) = 11. Решение для IV не существует. Поскольку полученное решение целочисленное и соответствующие значение целевой функции наибольшее, тоХ₂₁ — решение исходной целочисленной задачи (15.3)—(15.6), т. е. X* =(х₁* = 1, х₂ =2), причем W (X) = 11.