 |
 |
 |
 |
|
 |
 |
81
Индекс
i соответствует выбранной для формирования отсечения строке симплекс-таблицы,
содержащей нецелочисленное значение b
i
(?
(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), добавление
сформированного ограничения к системе ограничений текущей задачи, т. е. формирование новой
текущей задачи. Переход на начало следующей большой итерации.
Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать
новые дополнительные ограничения (правильные отсечения) и переходить от текущего псевдоплана к
новому оптимальному плану.
Можно доказать, что приведенный алгоритм конечен. Это означает, что на некотором шаге
(итерации) будет найден целочисленный оптимальный план или обнаружен факт отсутствия
допустимых целочисленных планов.
В качестве существенного замечания по поводу метода Гомори следует добавить, что при его
практической реализации на ЭВМ следует считаться с ошибками округления, т, к. в условиях
машинной арифметики практически ни один план не будет целочисленным. Кроме того,
накапливающиеся погрешности могут внести возмущения в алгоритм и «увести» от оптимального