ГЛАВА 6. ВТОРОЙ АЛГОРИТМ ГОМОРИ И ДРУГИЕ ОБОБЩЕНИЯ ПЕРВОГО АЛГОРИТМА

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

В § 1 излагается логическая схема первого алгоритма Гомори, используемая во всех алгоритмах этой главы.

Параграфы 2, 3, 4 посвящены соответственно второму алгоритму Гомори [85], алгоритму Дальтона и Ллевелина [62], -алгоритму Финкельштейна [29].

Параграфы 2—4 построены по одной и той же схеме, включающей следующие пункты:

1) рассматриваемая задача;

2) способ построения правильного отсечения;

3) условия конечности алгоритма (без подробного доказательства, в значительной степени повторяющего доказательство конечности первого алгоритма Гомори);

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

Параграф 5 посвящен упрощенному алгоритму Данцига [67] и его исследованию, выполненному Гомори и Гофманом [91].

§ 1. Логическая схема первого алгоритма Гомори

В этом параграфе излагается логическая схема пер вого алгоритма Гомори, применяемая во всех алгоритмах данной главы.

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

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

при условиях

Здесь

Множество планов (1.2) — (1.4) обозначим через саму задачу через

Условие дискретности (1.4) может иметь различный вид в различных случаях. Предполагается (как и для первого алгоритма Гомори), что:

1) Целевая функция ограничена сверху на многогранном множестве планов

2) Если множество оптимальных планов задачи (1.1) — (1.3) не пусто, то оно ограничено.

1.2. Изложим логическую схему первого алгоритма Гомори.

Начальная большая итерация. Решаем -задачу Если она неразрешима, то неразрешима и задача (1.4)). Если задача разрешима и -оптимум

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

Если же не удовлетворяет условию дискретности, то переходим к 0-й большой итерации.

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

и получим симплексную таблицу

допустимую и -нормальную. Выберем наименьшую (по номеру) строку, которой соответствует компонента, не удовлетворяющая условию дискретности

и по некоторому правилу постройм правильное отсечение

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

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