ГЛАВА 5. ИДЕЯ МЕТОДА ОТСЕЧЕНИЯ. ПЕРВЫЙ АЛГОРИТМ ГОМОРИ

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

§ 1. Идея метода отсечения

В § 1 гл. 1 отмечались принципиальные трудности, возникающие при решении задач дискретного программирования и, в частности, при решении задач целочисленного линейного программирования. С другой стороны (и об этом также говорилось выше), при решении задач линейного программирования принципиальных трудностей в настоящее время нет. Нельзя ли аппарат линейного программирования каким-то образом применить для решения задач целочисленного линейного программирования?

1.1. Сформулируем вопрос более конкретно. Нельзя ли по задаче целочисленного линейного программирования найти такую задачу линейного программирования чтобы решение сводилось крещению

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

Теорема 1.1. Пусть многогранник, множество его целых точек, выпуклая линейная оболочка множества Тогда:

1) - целочисленный многогранник.

3) Множество опорных планов многогранника содержится во множестве

Прежде чем доказывать теорему, заметим, что из (1.2) сразу получается

Следствие 1.1. Пусть -оптимальный опорный план задачи Тогда является также оптимальным планом задачи .

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

Доказательство теоремы

а) Докажем, что целочисленный многогранник. Так как многогранник, т. е. ограниченное множество, то — конечное множество, т. е. является выпуклой линейной оболочкой конечного множества точек. Следовательно, многогранник, причем множество опорных планов многогранника удовлетворяет условию

т. е. многогранник целочисленный.

б) Из определения выпуклой линейной оболочки следует, что

а следовательно,

в) Докажем, что

Пусть

Заметим, что так как то

Следовательно,

Из (1.6) и (1.7) получаем

откуда и следует (1.5).

г) Сравнивая (1.4) и (1.5), получаем

д) Из (1.3) и (1.8) следует (1.2). Теорема 1.1 доказана.

1.2. Покажем, что единственный целочисленный многогранник, для которого множество его целочисленных точек совпадает с

Теорема 1.2. Пусть — многогранник, целочисленный многогранник и

Тогда

Доказательство теоремы 1.2.

а) Из (1.9) непосредственно следует, что

б) Покажем, что

Так как многогранник целочисленный, т. е. все его опорные планы целочисленные, то

Из (1.9) и (1.13) следует, что

откуда получаем

т. е.

в) Сравнивая (1.11) и (1.12), заключаем, что

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

1.3. Приведем простой пример.

(см. скан)

На рис. 5.1.1 многогранник (многоугольник) выделен штриховкой, а точки целочисленной решетки, входящие в множество выделены черным цветом. Оптимальное значение целевой функции для задачи равно 7. Оптимум достигается во всех точках грани (отрезка) т. е. в точках отрезка, соединяющего два опорных плана (вершины) многогранника (13/3, 8/3) и (40/9, 23/9). Оптимальное значение целевой функции для задачи С) равно 5; оптимум достигается в точках (2,3) и (3,2). На рис. 5.1.2 отдельно показано множество (его точки выделены черным цветом). На рис. 5.1.3 многогранник (многоугольник) выделен штриховкой. Оптимальное значение целевой функции для задачи равно 5, оптимум достигается во всех точках грани (отрезка) т. е. в точках отрезка, соединяющего два опорных плана (вершины) многогранника и

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

Рис. 5.1.1.

Рис. 5.1.2.

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

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

Рис. 5.1.3

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

Нельзя ли по задаче целочисленного линейного программирования найти такую задачу линейного программирования что:

1) Оптимальные значения целевых функций для задач и совпадают:

2) Множество целочисленных точек многогранника совпадает с множеством целочисленных точек многогранника

3) Все оптимальные опорные планы задачи удовлетворяют условию целочисленности

Напомним, что через обозначается множество оптимальных планов задачи а через множество вершин (опорных планов) многогранника

Задачу построить можно, но мы не останавливаемся на этом более подробно, поскольку проблема построения многогранника удовлетворяющего условиям (1.14) — так же как и проблема построения многогранника оказывается достаточно сложной, и в настоящее время неизвестны эффективные алгоритмы ее решения.

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

I. При любом С оптимальные значения целевых функций для задач и совпадают.

II. Множество целочисленных точек многогранника А совпадает с множеством целочисленных точек многогранника При любом С все оптимальные опорные планы задачи удовлетворяют условию целочисленности.

На рис. 5.1.4 штриховкой выделен один из многогранников удовлетворяющих условиям (1.14) -(1.16) для задачи п. 1.3.

Рис. 5.1.4.

1.6. Две неудачные постановки проблемы линейной аппроксимации задачи С), рассмотренные выше, имели между собой много общего.

I. Множество целочисленных точек многогранника А аппроксимирующей задачи должно было совпадать с множеством целочисленных точек исходной задачи С)

II. Каждый оптимальный опорный план аппроксимирующей задачи должен был удовлетворять условию целочисленности

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

По-видимому, неудачными оказались условия II и III. Условие же I фигурирует во всех известных реализациях метода отсечения.

1.7. Введем понятие правильного отсечения, которое систематически используется в дальнейшем.

Пусть некоторая задача целочисленного линейного программирования и опорный оптимальный

план соответствующей задачи линейного программирования не удовлетворяет условию целочисленности

Неравенство

(или в векторной записи ) называется правильным отсечением, если оно удовлетворяет следующим двум условиям:

I. Условие отсечения. не удовлетворяет неравенству (1.17), т. е.

II. Условие правильности. Если X — план задачи , то X удовлетворяет неравенству (1.17), т. е.

1.8. Изложим теперь идею метода отсечения в том виде, в котором она впервые была предложена (см. Данциг, Фулкерсон, Джонсон [68] и Данциг [65]).

I. Предлагается решать задачу с помощью не двухэтапного, а, вообще говоря, многоэтапного процесса, причем

1-1) На этапе решается вспомогательная задача линейного программирования

Здесь

1-2) Множество целочисленных точек — одно и то же для всех многогранников

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

оказывается также и оптимальным планом исходной задачи и процесс решения завершается.

1-3) Если не удовлетворяет условию целочисленности, то не является планом задачи

II. Переход от этапа к этапу, т. е. переход от задачи к задаче (с соблюдением условий 1-2), в случае нецелочисленности осуществляется с помощью правильного отсечения

добавление которого к линейным условиям задачи превращает многогранник в многогранник

1.9. Итак, в основе метода отсечения лежат две основные идеи: Многоэтапная линейная аппроксимация задачи II. Переход от этапа к этапу с помощью правильного отсечения.

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

Один из таких способов будет изложен в следующем параграфе.

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