§ 4. Модификация третьего алгоритма Гомори

Выше была доказана конечность третьего алгоритма Гомори, но лишь при условии, что задача (2.3) — (2.6) имеет хотя бы один план. Следует отметить, что в общем случае ответить на вопрос, есть ли хотя бы один план у задачи (2.3) — (2.6), так же трудно, как и решить задачу (2.3) — (2.6). Возникает естественный вопрос — является ли предположение о существовании планов у задачи (2.3) — (2.6) необходимым условием конечности третьего алгоритма Гомори или же просто несовершенна техника доказательства?

Здесь будет дан ответ на этот вопрос (см. Финкелыитейн [32]). Будет построен пример задачи вида (2.3) — (2.6), не имеющей планов, для которой третий алгоритм Гомори не является конечным. Кроме того, будет указана модификация третьего алгоритма Гомори, для которой конечность гарантируется без предположения о существовании планов у задачи

4.1. Приведем пример задачи, для которой третий алгоритм Гомори не является конечным. Условия задачи выпишем в виде таблицы

Таблица Т (см. скан)

Отметим, что в данном случае не только задача но и нецелочисленная задача заведомо не имеет планов, поскольку

условия задачи противоречивы.

4.2. Покажем, что применение алгоритма Гомори к таблице приводит к бесконечному процессу.

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

Теорема 4.1. Для любого

Доказательство проведем по индукции. При формулы (4.1) и (4.2) верны. Допустим, что они верны при и докажем их при Поскольку

то

Далее, так как

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

Далее, очевидно, получим

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

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

4.3. Модифицируем теперь третий алгоритм Гомори так, чтобы его конечность была гарантирована при соблюдении следующих условий: 1) Построена исходная целочисленная и -нормальная таблица и 2) множество планов задачи ограничено.

Доказательство конечности для модифицированного алгоритма почти не изменяется и здесь не приводится.

В силу ограниченности множества можно (методами линейного программирования) найти

Если задача минимизации на неразрешима, то неразрешима и задача

Если же эта задача разрешима, то для любого плана задачи получаем

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