§ 2. Построение целочисленного правильного отсечения. Третий алгоритм Гомори

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

2.1. Основой для построения целочисленного прапт но отсечения служит следующая Теорема 2.1. Пусть

где — конечное множество;

где обозначает целую часть числа х;

Тогда

Доказательство. Целочисленность непосредственно следует из определения целой части и из целочисленности Допустим теперь, что

Тогда из целочисленное следует, что

С другой стороны,

так что

Из (2.1) и (2.2) получаем

что невозможно ввиду неотрицательности и дробных частей Теорема 2.1 доказана.

2.2. Используя теорему 2.1, построим целочисленное правильное отсечение (удовлетворяющее условиям (1.5) — (1.10)). Пусть задана целочисленная, недопустимая и -нормальная таблица

и пусть для некоторого

Положим

так что

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

Ниже (в ходе изложения алгоритма) будет произведен более рациональный выбор К.

2.3. Выше было упомянуто, что третий алгоритм Гомори начинается с получения исходной таблицы То — целочисленной и -нормальной. Прежде чем переходить непосредственно а изложению алгоритма, покажем, как в некоторых случаях можно получить исходную таблицу с нужными свойствами.

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

при условиях

Здесь все числа целые.

Введем новые переменные и получим эквивалентную задачу с уравнениями вместо неравенств. Максимизировать

при условиях

целое,

Примем переменные за небазисные и выпишем таблицу То (см. стр. 173).

а) Если таблица То является -нормальной (например, в случае то принимаем ее за исходную таблицу

б) Допустим, что таблица не является -нормальной, но множество планов задачи ограничено. Решаем задачу линейного программирования с целевой функцией 2; при условиях и находим

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

Очевидно, что для всех планов задачи (2.3) — (2.6) заведомо

Следовательно, можно ввести новую переменную

Строку приписываем снизу к таблице и принимаем за направляющую. За направляющий столбец принимаем

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

2.4. Переходим к изложению третьего алгоритма Гомори.

0-я итерация. Строится исходная таблица

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

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

итерация Задана целочисленная и -нормальная, но недопустимая таблица

Столбцы обозначаем через Находим первую по номеру компоненту нарушающую допустимость таблицы

Если числа для всех то задача неразрешима. Если же среди чисел есть отрицательные, то выбираем ведущий столбец

и строим целочисленное правильное отсечение (направляющую строку)

Правило выбора числа указано ниже (см. п. 2.5). Строку приписываем снизу к таблице и принимаем за направляющую. Проделываем одну итерацию -метода (из базиса выводится в базис вводится Строку вычеркиваем. Если то строку не восстанавливаем. Получаем таблицу

целочисленную и -нормальную.

Здесь

Если таблица окажется допустимой, то вектор

является расширенным оптимальным планом задачи Если таблица недопустима, то переходим к итерации.

Блок-схема третьего алгоритма Гомори приведена на рис. 7.2.1.

(кликните для просмотра скана)

2.5. Число к выбирается с соблюдением следующих условий:

I. Направляющий элемент равен

II. Таблица должна быть -нормальной:

III. Столбец должен быть -минимальным:

Замечание 2.1. Так как направляющий элемент равен и (в силу -нормальности таблицы то т. е. -положительность гарантирована. Положительность следует из (2.14) и отрицательности (см. (2.10)).

2.6. Поясним, как находить X из условий (2.14) — (2.16). Условие (2.14) можно переписать следующим образом:

или, что то же самое,

Условие (2.15) также можно упростить. Если то и условие (2.15) выполняется при любом (положительном)

Таким образом, достаточно рассматривать те для которых

Далее, пусть для всех

Из (2.10) следует:

Ясно, что если то при любом

Следовательно, достаточно рассматривать лишь те для которых

и

Обозначим множество таких через

Теперь условие (2.15) можно переписать следующим образом:

Если множество пусто, то условие (2.150 не кладывает никаких ограничений на (положительное) Допустим, что множество не пусто. Тогда для каждого можно найти такое натуральное что

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

Но это невозможно, поскольку направляющие элементы у нас все время равны Поэтому получим

Возможны четыре случая:

В этом случае

Здесь натуральные,

В этом случае

Здесь натуральное В этом случае

Здесь натуральное В этом случае

Вычислив можно переписать (2.150 следующим образом:

или, что то же самое

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

Наконец, так как то условие (2.16) можно переписать следующим образом:

Из получаем

2.7. Приведем численный пример. Максимизировать

при условиях

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

Рис. 7.2.2.

правильному отсечению Направляющие элементы везде отмечены звездочками. Таблице соответствует решение задачи Геометрическая иллюстрация процесса решения задачи дана на рис. 7.2.2. Расширенные -псевдопланы , последний из которых является решением задачи (2.18) — (2.21), выписаны отдельно в виде табл. 2.1. В этой же таблице выписаны числа

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

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

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

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

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

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