ЧАСТЬ II. МЕТОД ОТСЕЧЕНИЯ

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

В гл. 4 кратко изложены необходимые предварительные сведения из теории выпуклых множеств и линейного программирования.

Главы 5—8 посвящены различным алгоритмам метода отсечения.

В гл. 5 излагается идея метода и первый алгоритм, реализующий эту идею, — алгоритм Гомори для полностью целочисленной задачи линейного программирования [88], [84].

В гл. 6 собран ряд алгоритмов, построенных по той же логической схеме, что и первый алгоритм Гомори, но отличающихся от него способом построения правильных отсечений. Это второй алгоритм Гомори [85] для частично целочисленной задачи линейного программирования, алгоритм Дальтона и Ллевелина [62] для частично дискретной задачи линейного программирования, - алгоритм Финкельштейна [29] для частично целочисленной задачи линейного программирования с булевыми переменными и упрощенный алгоритм Данцига [67].

В гл. 7 излагается третий алгоритм Гомори [86] для полностью целочисленной задачи линейного программирования (дискретный или полностью целочисленный алгоритм, как его называют в литературе) и его исследование и модификация, данные Финкельштейном [32].

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

Гл. 9 посвящена анализу эффективности алгоритмов метода отсечения; здесь приведены некоторые результаты вычислительных экспериментов.

Во второй части книги изложены не все алгоритмы метода отсечения. Например, не излагается здесь алгоритм Мартина [116], являющийся, судя по литературе (см., например, [50]), наиболее эффективной модификацией 1-го алгоритма Гомори. Этот алгоритм не рассмотрен здесь потому, что в литературе отсутствует достаточно полное его изложение. В работе Мартина [116] не только

отсутствует доказательство конечности, но и опущены некоторые существенные детали алгоритма.

Не изложены здесь также некоторые работы по выпуклому целочисленному программированию (см. начало гл. 8), эффективность которых пока неясна. Следует отметить, что новые приемы, изложенные в гл. 8, применимы к значительно более широкому классу задач.

Из-за недостатка места здесь не изложен и ряд других работ по методу отсечения, в частности работа Юнга [128] и некоторые другие работы, посвященные (практически пока мало испытанным) прямым алгоритмам метода отсечения. Прямые алгоритмы метода отсечения являются в некотором смысле переносом метода последовательного улучшения плана (прямого симплекс-метода) на задачи целочисленного линейного программирования, в то время как изложенные нами алгоритмы могут быть названы двойственными — в них к задачам целочисленного линейного программирования приспосабливается метод последовательного уточнения оценок (двойственный симплекс-метод).