§ 2. Первый алгоритм Гомори

В этом параграфе будет изложен алгоритм Гомори [88], дающий исторически первую реализацию метода отсечения, для которой:

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

2) доказана конечность алгоритма.

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

при условиях

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

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

Дробной частью числа х (обозначение {х}) называется число

Теорема 2.1. Пусть

2) X — план задачи Тогда

Доказательство. Из (2.5) получаем

Отсюда и из (2.6) получаем

Из определения целой части следует, что целые, а из условия 2) теоремы получаем, что должны быть целыми Следовательно, должно быть целым числом и так что формула (2.7) доказана.

Допустим теперь, что

Тогда, используя (2.6), получаем

Но из определения дробной части следует, что , а из условия 2), что откуда получаем

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

так что нецелое, а это противоречит только что доказанной формуле (2.7). Следовательно,

и формула (2.8) установлена. Теорема 2.1 доказана.

Замечание 2.1. Если гарантирована целочисленность целевой функции (например, в случае, когда все целые числа), то теорема 2.1 непосредственно переносится и на случай

Следствие 2.1 (из теоремы 2.1 и замечания 2.1). Пусть не удовлетворяет условию иелочисленности (2.4), так что для некоторого

Тогда соотношения (2.6), (2.8) задают правильное отсечение.

Доказательство следствия, а) Сначала проверим условие правильности. Все планы задачи удовлетворяют условиям (2.6) и (2.8) — это непосредственно видно из теоремы 2.1.

б) Теперь проверим условие отсечения. Подставляя в (2.6) нецелочисленный оптимальный план и учитывая, что получаем (используя

что противоречит (2.8).

Следствие 2.1 обосновано.

2.2. В схематичном изложении метода отсечения, данном выше, неоднозначно определялись оптимальные планы вспомогательных задач линейного программирования, поскольку задача может иметь много решений. Гомори предложил вместо задачи решать -задачу -оптимальный план С) является опорным (см. теорему 4.2 гл. 4) и определяется единственным образом. Все вычисления проводятся в соответствии с -методом (см. § 7 гл. 4).

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

Идея Гомори заключается в следующем:

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

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

2.4. Если задача не имеет решения в силу неограниченности сверху целевой функции на многогранном множестве планов , то первый алгоритм Гомори неприменим.

Первый алгоритм Гомори неприменим и в том случае, когда задача имеет решение, но не имеет решения -задача Это означает, что множество оптимальных планов задачи не пусто, но не ограничено. Будем предполагать в дальнейшем, что:

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

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

2.5. Переходим к формальному изложению первого алгоритма Гомори.

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

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

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

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

допустимую и -нормальную.

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

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

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

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

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

Рис. 5.2.2.

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

2.6. Решим с помощью первого алгоритма Гомори рассмотренный выше (см. § 1, п. 1.3) численный пример. Максимизировать

при условиях

или, что то же самое. Максимизировать

при условиях

Последовательность вычислений сокращенно записана в табл. 1 —10. Оптимальный расширенный план . Направляющий элемент везде отмечен звездочкой. Геометрическая иллюстрация дана на рис. 5.2.2.

(см. скан)

(см. скан)

Заметим, что оптимальный план (3, 2, 10, 2, 3) задачи не может быть получен с помощью округления из оптимального плана (40/9, 23/9, 1, 0, 0) соответствующей нецелочисленной задачи .

(см. скан)