4.2. МЕТОД ГОМОРИ
4.2.1. Основные идеи и принципы*. Данный метод, который также носит название метода отсекающих плоскостей, предназначен для решения ЦЗЛП в канонической форме (4.2)-(4.3). Кратко представим его основные идеи.
* Впервые был предложен Р.Гомори в 1957-1958 гг.
Отправной точкой для решения задачи (4.2)-(4.3) является решение ее непрерывного аналога, т.
е. КЗЛП без учета условий целочисленности. Если получаемый в результате оптимальный план х* содержит только целые компоненты, то мы автоматически получаем и соответствующее решение ЦЗЛП. В противном случае к системе ограничений задачи должно быть добавлено такое ограничение, для которого:>
найденный нецелочисленный оптимальный план х* не удовлетворяет вновь добавляемому ограничению; >
любой допустимый целочисленный план непрерывной задачи (4.2)-(4.3) удовлетворяет вновь добавляемому ограничению.
Такое ограничение называют правильным отсечением. В первой геометрической интерпретации правильному отсечению соответствует гиперплоскость, отсекающая от выпуклого многогранного множества допустимых планов D некоторый многогранник, не содержащий целочисленных планов.
Добавив сформированное отсекающее ограничение к уже существующим, мы получаем новую оптимизационную задачу, после чего вычислительный процесс итеративно повторяется.
Теперь необходимо несколько более подробно остановиться на принципах формирования отсекающих ограничений. Воспользуемся системой обозначений, применявшихся при изложении вычислительных методов линейного программирования. Пусть ?(q) — оптимальный базис, полученный на последней итерации решения нецелочисленной ЗЛП. Если обозначить через ?i,j и ?i коэффициенты матрицы задачи и вектора ограничений в текущем базисе (A(?(q)) и b(?(q)))
то i-ое уравнение в системе ограничений задачи примет вид:
Так как план x(?(q)) является базисным, то в каждом уравнении все коэффициенты ?i,j, соответствующие базисным столбцам (j?N(?(q))), равны нулю за исключением некоторого ?i,ji =1, на основе чего из (4.18) получаем:
Если представить каждый коэффициент ?i,j в виде суммы целой и дробной частей ?i,j =[?i,j]+{?i,j}, то получим
или
Из (4.21) следует, что если все хj, j?1: n являются целыми, то целым будет и выражение
стоящее в левой части (4.21), и, стало быть, правая часть данного уравнения:
также должна быть целой.
Предположим, что
тогда, в силу того, что 0 ? {?i} < 1, а {?i,j} ? 0, xj ? 0, должно выполняться неравенство
Однако неравенства (4.22) и (4.23) противоречат требуемой целочисленности правой части (4.21) xj(?(q)). Следовательно, для целочисленных решений должно выполняться условие, противоположное неравенству (4.22), или, что то же самое,
В то же время (4.24) не выполняется для любого нецелочисленного базисного плана х. Действительно, небазисные компоненты плана равны нулю: хj =0 , j?N(?(q)), и (4.24) приобретает вид {?i} ?0 <=> {?i} =0, но это противоречит предположению о нецелочисленности плана х, т. к. в базисном плане хi = ?i . Все сказанное позволяет утверждать, что ограничение (4.24) задает правильное отсечение.
Таким образом, с точки зрения организации техники, вычислений для осуществления правильного отсечения мы должны к системе ограничений нецелочисленной линейной задачи, решаемой на q-й итерации, добавить условие
где xn+1 ?0 — фиктивная переменная, добавляемая для преобразования неравенства в строгое равенство. Ей соответствует нулевой коэффициент в целевой функции.
Данному преобразованию условий задачи будет соответствовать преобразование симплекс-таблицы, показанное на рис. 4.2. На нем по соображениям обеспечения наглядности использованы обозначения (4.17) и предполагается, что текущий базис ?(q) состоит из первых m столбцов.
Индекс i соответствует выбранной для формирования отсечения строке симплекс-таблицы, содержащей нецелочисленное значение bi(?(q)).
Как видно из рис. 4.2, технически преобразование таблицы сводится к дописыванию одной строки и одного столбца. При этом легко убедиться, что модифицированные столбцы
совместно с добавленным столбцом
образуют сопряженный (двойственно допустимый) базис для сформированной задачи, а (?1, ..., ?m, -{?i}) являются ненулевыми компонентами соответствующего псевдоплана.
Исходя из этого, приходим к тому, что для решения вновь полученной задачи может быть эффективно применена процедура двойственного симплекс-метода (см. параграф 1.7).Поскольку в начальном псевдоплане имеется только одна отрицательная компонента (-{?i}), то из базиса должен быть выведен соответствующий ей вектор аn+1 . Далее, следуя рекомендациям алгоритма двойственного симплекс-метода, находим оптимальный план. Если он не является целочисленным, то описанные действия итеративно повторяются.
Если в ходе решения дополнительная переменная хn+1 вновь становится базисной, ее значение оказывается безразличным для основных переменных. Поэтому строку и столбец, отвечающие ей, вычеркивают. С геометрической точки зрения это можно обосновать так: если псевдоплан оказывается внутри полупространства хn+1 ?0, то дополнительное ограничение, определяемое гиперплоскостью хn+1=0, становится несущественным и опускается.
4.2.2. Описание алгоритма. Приведем обобщенную схему алгоритма Гомори. Структурно он делится на так называемые большие итерации. Каждая большая итерация содержит этапы:
1. Решение «текущей» задачи методами линейного программирования (малые итерации). На первой итерации в качестве «текущей» задачи выступает нецелочисленный аналог исходной ЦЗЛП.
2. Определение первой нецелочисленной компоненты в оптимальном плане, полученном на этапе 1. Если все компоненты являются целочисленными, то алгоритм завершается.
3. Построение для найденной компоненты условия отсечения согласно правилу (4.24), добавление сформированного ограничения к системе ограничений текущей задачи, т. е. формирование новой текущей задачи. Переход на начало следующей большой итерации.
Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать новые дополнительные ограничения (правильные отсечения) и переходить от текущего псевдоплана к новому оптимальному плану.
Можно доказать, что приведенный алгоритм конечен. Это означает, что на некотором шаге (итерации) будет найден целочисленный оптимальный план или обнаружен факт отсутствия допустимых целочисленных планов.
В качестве существенного замечания по поводу метода Гомори следует добавить, что при его практической реализации на ЭВМ следует считаться с ошибками округления, т, к.
в условиях машинной арифметики практически ни один план не будет целочисленным. Кроме того, накапливающиеся погрешности могут внести возмущения в алгоритм и «увести» от оптимального целочисленного плана.4.2.3. Пример решения ЦЗЛП методом Гомори. Рассмотрим особенности применения метода Гомори на конкретном примере. Пусть дана задача со следующими условиями:
Итерация 1. Используя обычный симплекс-алгоритм, решаем непрерывный аналог исходной задачи, в котором игнорируются условия целочисленности (4.28). В качестве исходного базиса можно взять первый и второй столбцы. На его основе заполняется таблица T(1,1) (первый индекс в обозначении таблицы соответствует «большой» итерации, а второй — «малой»).
Как видно из строки оценок, данный базис является оптимальным, однако соответствующий ему план х ={11/5,17/5, 0) не является целочисленным, поэтому выбираем из таблицы T(1,1) строку, содержащую первый нецелый элемент, и согласно формуле (4.25) строим отсекающее ограничение:
после чего переходим к следующей «большой» итерации.
Итерация 2. С учетом сформированного отсекающего ограничения заполняем симплекс-таблицу T(2,1).
В соответствии с алгоритмом двойственного симплекс-метода переходим к следующему базису N(?(2,2))={1, 2, 3}.
План, достигнутый в таблице T(2,2), является не только оптимальным (b(?(2,2))>0), но и полностью состоит из целочисленных компонент, т. е. решение задачи найдено: х* = (1, 2, 1) и f(x)=7.