Математические методы исследования операций в экономике (стр. 27 из 37)
Данному преобразованию условий задачи будет соответствовать преобразование симплекс-таблицы, показанное на рис. 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.
4.3.1. Общая схема метода «ветвей и границ». Другим широко применяемым для решения задач дискретного программирования методом является метод ветвей и границ. Впервые данный метод для решения ЦЗЛП предложили в 1960 г. Лэнг иДойг, а его «второе рождение» произошло в 1963г. в связи с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи о коммивояжере [33].
Вообще говоря, термин «метод ветвей и границ» является собирательным и включает в себе целое семейство методов, применяемых для решения как линейных, так и нелинейных дискретных задач, объединяемое общими принципами. Кратко изложим их.
Пусть стоит задача:
гдеD — конечное множество.
Алгоритм является итеративным, и на каждой итерации происходит работа с некоторым подмножеством множества D. Назовем это подмножество текущим и будем обозначать его как D(q), гдеq — индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все множество D (D(1)=D),и для него некоторым способом вычисляется значение верхней оценки для целевой функции maxf(x)≤ ξ( D(1)). Стандартная итерация алгоритма состоит из следующих этапов:
1°. Если можно указать планx(q)∊D(q), для которого f(x(q))≤ξ( D(q)), то x(q)=х* — решение задачи (4.29).
2°. Если такой план не найден, то область определенияD(q) некоторым образом разбивается на подмножества D1(q),D2(q), ..., Dlq(q), удовлетворяющие условиям:
Для каждого подмножества находятся оценки сверху (верхние границы) для целевой функции ξD1(q),ξD2(q), ..., ξDl1(q), уточняющие ранее полученную оценку ξD(q), то есть ξDi(q) ≤ ξD(q), i∊1:lq. Возможно одно из двух:
2.1. Если существует такой план х(q), что
то этот план оптимальный.
2.2. Если такой план не найден, то выбирается одно из множеств Di(q),i∊1:lq (как правило, имеющее наибольшую оценку
Все имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не подверглись процессу дробления, переобозначаются какD1(q+1),D2(q+1),...,Dl(q+1)(q+1),после чего процесс повторяется.
Схема дробления множества D представлена на рис. 4.3 в виде графа. Существуют и более сложные системы индексации подмножеств, при которых не требуется их переобозначение на каждом шаге.
Конкретные реализации метода ветвей и границ связаны с правилами разбиения на подмножества (правилами ветвления) и построения оценок значений целевых функций на данных подмножествах (границ).
4.3.2. Решение ЦЗЛП методом ветвей и границ. Рассмотрим применение алгоритма метода ветвей и границ для решения ЦЗЛП (4.2)-(4.3). Как уже упоминалось, черезD(q) обозначается подмножество множества допустимых планов задачи. Перед началом первой итерации (q = 1) в качестве текущего множества берется все множество D (D(1) = D), после чего решается стандартная задача линейного программирования (D(1), f). Нетрудно заметить, что она является непрерывным аналогом
исходной задачи (4.2)-(4.3). Если найденный оптимальный план 
(1)содержит только целочисленные компоненты, то он является и оптимальным планом для (4.2)-(4.3): (1)=x*. В противном случае значениеf( (1)) становится оценкой (верхней границей) значения целевой функции на множестве D(1), и мы переходим к выполнению стандартной итерации алгоритма. Опишем входящие в нее этапы.