Раздел 5. Целочисленное линейное программирова­ние

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

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

сх —т- шах (5-1) Ах = Ъ (5.2) х > 0 (5.3) хэ- — целое, ]' = 1,..., п. (5-4)

Под ЛП-релаксацией задачи (5.1)-(5.4) будем понимать зада­чу ЛП (5.1)—(5.3), получаемую из исходной задачи ЦЛП путем отбрасывания условий целочисленности переменных.

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

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