ГЛАВА 8. О РЕШЕНИИ ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПРОИЗВОЛЬНЫМИ ДОПОЛНИТЕЛЬНЫМИ УСЛОВИЯМИ

В последние годы выполнен ряд работ, посвященных переносу метода отсечения на задачи выпуклого целочисленного программирования (см. Куртийо [61], Кюнци и Этли [107], Витцгалл [127]).

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

Постановка задачи и идея метода изложены в § 1. Там же, в сущности, изложен простейший алгоритм. § 2 посвящен использованию специфики выпуклых и некоторых невыпуклых задач. В § 3 дано более подробное изложение применения третьего алгоритма Гомори и приведен численный пример.

§ 1. Постановка задачи и идея метода решения

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

Максимизировать

при условиях

Условие (1.5) совершенно произвольно. Многогранное множество ((1.2) -(1.3)) считаем ограниченным, так что множество (1.2)-(1.4) содержит лишь конечное множество точек. Числа считаем целыми,

1.2. Идея метода состоит в последовательном решении (с помощью метода отсечения) ряда вспомогательных полностью целочисленных задач линейного программирования: Переход от задачи к задаче также совершается с помощью метода отсечения. Если решение некоторой задачи удовлетворяет дополнительному условию (1.5), то процесс решения заканчивается и оказывается оптимальным планом задачи

1.3. Опишем переход от задачи к задаче Пусть оптимальный опорный план задачи не удовлетворяет дополнительному условию (1.5), причем множество индексов небазисных переменных, соответствующих .

Решение можно «отсечь», используя прием, аналогичный упомянутому выше приему Данцига

Теорема 1.1. Пусть

X — план задачи Тогда

Доказательство совершенно аналогично обоснованию приема Данцига. План X однозначно определяется значениями переменных причем набору значений соответствует , не являющийся планом (так как не удовлетворяется условие Следовательно, для плана X по крайней мере одна из переменных скажем, переменная должна быть положительной, а в силу целочисленности

откуда вследствие неотрицательности переменных получаем

Теорема 1.1 доказана.

1.4. Выберем алгоритм метода отсечения, с помощью которого будем решать вспомогательные задачи . Под подразумевается задача

шаг Решаем задачу . Если задача неразрешима, то неразрешима и задача Если задача разрешима и ее решение удовлетворяет дополнительному условию (1.5), то является одновременно решением задачи Если же решение неудовлетворяет условию (1.5), то вводим дополнительное ограничение (см. теорему 1.1), присоединяем его к условиям задачи и получаем задачу . Конечность процесса следует из конечности числа планов задачи

1.5. Этот метод можно распространить также и на за дачи с произвольной максимизируемой целевой функцией и ограничениями но в этом случае удается получить лишь приближенное решение.

Пусть максимально допустимое отклонение (по значению целевой функции) от точного решения.

Введем вспомогательную целевую функцию решим (указанным выше методом) задачу (1.1) — (1.5). Получим решение запомним его и перейдем к решению задачи (1.1) — (1.5) с дополнительным условием

Если новая задача (1.1) — (1.6) не имеет решения, то следует принять за приближенное решение задачи Если же задача имеет решение то вычеркнем из памяти запомним и перейдем к решению задачи (1.1) — (1.5) с дополнительным условием

Таким образом, за конечное число шагов получим искомое приближенное решение.

1.6. Изложенные выше методы носят универсальный характер, что связано с отсутствием каких-либо ограничений, наложенных на множество (входящее в условие и функцию Поэтому соответствующий вычислительный процесс может получиться весьма длительным. Например, при решении задачи (1.1) — (1.5) количество решаемых задач будет равно количеству планов X задачи , удовлетворяющих условию

где X — лексикографический оптимум задачи (1.1) — (1.5).

В следующем параграфе будут указаны некоторые приемы для использования специальных свойств