§ 3. Применение третьего алгоритма Гомори

Универсальная схема применения алгоритма целочисленного линейного программирования для решения целочисленных задач вида (1.1) — (1.5) была дана в § 1. В этом параграфе эта схема будет расписана более подробно применительно к третьему алгоритму Гомори (поскольку именно для этого алгоритма возникает необходимость дать некоторые дополнительные разъяснения). Третий алгоритм Гомори следует использовать в модифицированном виде (см. § 4 гл. 7).

3.1. Рассматривается задача целочисленного линейного программирования с дополнительным условием (задачу обозначим через записанная в виде целочисленной и -нормальной таблицы

Через обозначаем расширенный псевдоплан

итерация. Задача записана в виде целочисленной -нормальной таблицы

К таблице применяем третий алгоритм Гомори. Если задача неразрешима, то неразрешима и задача Если задача разрешима (и ее решение — это то получаем целочисленную, -нормальную и допустимую таблицу

Здесь

Если удовлетворяет условию (1.5), то решение задачи Если же не удовлетворяет условию (1.5), то

(см. §§ 1 и 2) по выбранному способу строим исходное отсечение

Здесь

Если среди чисел нет отрицательных, то задача (1.1) — (1.5) не имеет решения. Если же среди чисел учесть отрицательные, то переходим к построению окончательного отсечения:

Здесь

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

После выбора направляющей строки и направляющего столбца переходим непосредственно к определению К (см. § 2 гл. 7) из условий

и вычисляем а по правилам, изложенным в п. 2.6 § 2 гл. 7. Затем выводим из базиса (и вычеркиваем соответствующую строку) и вводим в базис Если 1, то строка, соответствующая не восстанавливается. Получаем задачу в виде целочисленной, -нормальной симплексной таблицы.

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

при условиях:

выполнено по крайней мере одно из двух ограничений (3.7)

Условие (3.7) задает область дополнение которой — выпуклая область а замыкание это выпуклая область определяемая условиями

Сначала решим задачу по упрощенному методу, приведенному в § 1. Вычисления сведены в табл. 1—5. Табл. 1—4 не удовлетворяют условию (3.7). Переход от табл. 1 к табл. 2, от табл. 2 к табл. 3 и от табл. 3 к табл. 4 производится посредством отсечений вида (1.6). Табл. -нормальные и допустимые и обозначены через Табл. -нормальная и недопустимая) обозначена через Переход от к табл. производится посредством отсечения 3-го алгоритма Гомори (при Таблица -нормальная и допустимая; она удовлетворяет условию (3.7) и дает оптимальный план задачи (3.4) — (3.7). -псевдопланы, соответствующие таблицам обозначены через -псевдоплан, соответствующий таблице через Оптимальный расширенный план задачи (3.4) — (3.7) равен ). Геометрическая иллюстрация процесса решения задачи дана на рис. 8.3.1. Общее количество симплексных итераций равно 4.

Для сравнения та же задача решена с помощью другого способа построения отсечений (см. пп. 2.2 и 2.3), использующего выпуклость множества Вычисления приведены в табл. 6 и 7. Отсечение

построено согласно рекомендациям пп. 2.2 и 2.3.

Рис. 8.3.1.

Переход от произведен при значении параметра равном 2/3. Геометрическая иллюстрация хода решения дана на рис. 8.3.2.

Рис. 8.3.2.

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

(см. скан)