<< Пред.           стр. 10 (из 13)           След. >>

Список литературы по разделу

 
 где - фиктивная переменная, добавляемая для преобразования неравенства в строгое равенство. Ей соответствует нулевой коэффициент в целевой функции.
  Данному преобразованию условий задачи будет соответствовать преобразование симплекс-таблицы, показанное на рис. 4.2. На нем по соображениям обеспечения наглядности использованы обозначения (4.17) и предполагается, что текущий базис состоит из первых т столбцов.
 
 
 
 
 
 
 
 
 
 
 
  Рис. 4.2
 
  Индекс i соответствует выбранной для формирования отсечения строке симплекс-таблицы, содержащей нецелочисленное значение .
  Как видно из рис. 4.2, технически преобразование таблицы сводится к дописыванию одной строки и одного столбца. При этом легко убедиться, что модифицированные столбцы
 
 
 
 совместно с добавленным столбцом
 
 
 образуют сопряженный (двойственно допустимый) базис для сформированной задачи, а являются ненулевыми компонентами соответствующего псевдоплана. Исходя из этого, приходим к тому, что для решения вновь полученной задачи может быть эффективно применена процедура двойственного симплекс-метода (см. параграф 1.7).
  Поскольку в начальном псевдоплане имеется только одна отрицательная компонента , то из базиса должен быть выведен соответствующий ей вектор an+l. Далее, следуя рекомендациям алгоритма двойственного симплекс-метода, находим оптимальный план. Если он не является целочисленным, то описанные действия итеративно повторяются.
  Если в ходе решения дополнительная переменная хп+1 вновь становится базисной, ее значение оказывается безразличным для основных переменных. Поэтому строку и столбец, отвечающие ей, вычеркивают. С геометрической точки зрения это можно обосновать так: если псевдоплан оказывается внутри полупространства хп+1?0, то дополнительное ограничение, определяемое гиперплоскостью хп+1=0, становится несущественным и опускается.
  4.2.2. Описание алгоритма. Приведем обобщенную схему алгоритма Гомори. Структурно он делится на так называемые большие итерации. Каждая большая итерация содержит этапы:
  1. Решение "текущей" задачи методами линейного программирования (малые итерации). На первой итерации в качестве "текущей" задачи выступает нецелочисленный аналог исходной ЦЗЛП.
  2. Определение первой нецелочисленной компоненты в оптимальном плане, полученном на этапе 1. Если все компоненты являются целочисленными, то алгоритм завершается.
  3. Построение для найденной компоненты условия отсечения согласно правилу (4.24), добавление сформированного ограничения к системе ограничений текущей задачи, т. е. формирование новой текущей задачи. Переход на начало следующей большой итерации.
  Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать новые дополнительные ограничения (правильные отсечения) и переходить от текущего псевдоплана к новому оптимальному плану.
  Можно доказать, что приведенный алгоритм конечен. Алгоритм приведен в упрощенном виде и не учитывает некоторых возможных вычислительных проблем. Для их преодоления применяется так называемый лексикографический симплекс-метод.
  В качестве существенного замечания по поводу метода Гомори следует добавить, что при его практической реализации на ЭВМ следует считаться с ошибками округления, т. к. в условиях машинной арифметики практически ни один план не будет целочисленным. Кроме того, накапливающиеся погрешности могут внести возмущения в алгоритм и "увести" от оптимального целочисленного плана.
  4.2.3. Пример решения ЦЗЛП методом Гомори. Рассмотрим особенности применения метода Гомори на конкретном примере. Пусть дана задача со следующими условиями:
 
  (4.26)
 
 
 
  (4.27)
 
 
 
  (4.28)
 
  Итерация 1. Используя обычный симплекс-алгоритм, решаем непрерывный аналог исходной задачи, в котором игнорируются условия целочисленности (4.28). В качестве исходного базиса можно взять первый и второй столбцы. На его основе заполняется таблица T(1,1) (первый индекс в обозначении таблицы соответствует "большой" итерации, а второй - "малой").
 
 
 
 
 
 
 
 
  Как видно из строки оценок, данный базис является оптимальным, однако соответствующий ему план х = (11/5, 17/5, 0) не является целочисленным, поэтому выбираем из таблицы T(1,1) строку, содержащую первый нецелый элемент, и согласно формуле (4.25) строим отсекающее ограничение:
 
 
 
 после чего переходим к следующей "большой" итерации.
  Итерация 2. С учетом сформированного отсекающего ограничения заполняем симплекс-таблицу T(2,1).
 
 
 
 
 
 
 
 
 
  В соответствии с алгоритмом двойственного симплекс-метода переходим к следующему базису = {1, 2, 3}.
 
 
 
 
 
 
 
 
 
 
 
 
  План, достигнутый в таблице T(2,2) , является не только оптимальным , но и полностью состоит из целочисленных компонент, т. е. решение задачи найдено: х* =(1, 2, 1) и f(x*)=7
 
  4.3. МЕТОД ВЕТВЕЙ И ГРАНИЦ
 
  4.3.1. Общая схема метода "ветвей и границ". Другим широко применяемым для решения задач дискретного программирования методом является метод ветвей и границ. Впервые данный метод для решения ЦЗЛП предложили в 1960 г. Лэнг и Дойг, а его "второе рождение" произошло в 1963г. в связи с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи о коммивояжере [33].
  Вообще говоря, термин "метод ветвей и границ" является собирательным и включает в себе целое семейство методов, применяемых для решения как линейных, так и нелинейных дискретных задач, объединяемое общими принципами. Кратко изложим их.
  Пусть стоит задача:
 
  (4.29)
 
 где D - конечное множество.
  Алгоритм является итеративным, и на каждой итерации происходит работа с некоторым подмножеством множества D. Назовем это подмножество текущим и будем обозначать его как D(q) , где q - индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все множество D (D(1) =D), и для него некоторым способом вычисляется значение верхней оценки для целевой функции . Стандартная итерация алгоритма состоит из следующих этапов:
  1°.Если можно указать план , для которого , то - решение задачи (4.29).
  2°. Если такой план не найден, то область определения D(q) некоторым образом разбивается на подмножества , удовлетворяющие условиям:
 
  (4.30)
  Для каждого подмножества находятся оценки сверху (верхние границы) для целевой функции , уточняющие ранее полученную оценку , то есть . Возможно одно из двух:
  2.1. Если существует такой план , что
 
 
 то этот план оптимальны.
 
 
 
 
 
 
 
 
 
 
 
 
  Рис. 4.3
 
  2.2. Если такой план не найден, то выбирается одно из множеств (как правило, имеющее наибольшую оценку
 
 
 
  Все имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не подверглись процессу дробления, переобозначаются как , после чего процесс повторяется.
  Схема дробления множества 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). Если найденный оптимальный план содержит только целочисленные компоненты, то он является и оптимальным планом для (4.2)-(4.3): . В противном случае значение становится оценкой (верхней границей) значения целевой функции на множестве D(1), и мы переходим к выполнению стандартной итерации алгоритма.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  Рис. 4.4
 
  Опишем входящие в нее этапы.
  1) Выбирается некоторая нецелочисленная компонента плана . Поскольку в оптимальном плане она должна быть целой, то можно наложить ограничения и . Таким образом, D(q) разбивается на подмножества
 
  (4.31)
 
  (4.32)
  Графическая интерпретация такого разбиения множества D(q) приведена на рис. 4.4.
  2) Решаются задачи линейного программирования
 
  и
 
  Соответствующие максимальные значения целевой функции принимаются как ее оценки на этих множествах:
 
  , (4.33)
 
  Если оптимальный план х для одной из решенных задач удовлетворяет условию
  (4.34)
  и содержит только целые компоненты, то, значит, найдено решение основной задачи (4.2)-(4.3). В противном случае среди всех концевых подмножеств, полученных как на предыдущих , так и на текущем этапе, выбирается область с наибольшей оценкой . Она становится текущим рассматриваемым подмножеством . Далее производится перенумерация концевых множеств и вычислительный процесс итеративно повторяется.
  При решении задач и можно воспользоваться результатами решения предыдущей задачи (D(q),f) . Рассмотрим вариант организации вычислительного процесса на примере задачи (для он выглядит аналогично с точностью до знаков неравенств).
  Предположим, что на последнем шаге решения задачи (D(q),f) был получен оптимальный базис . Без ограничения общности можно считать, что он состоит из первых т столбцов матрицы задачи. Данное предположение делается исключительно для обеспечения наглядности дальнейшего изложения и очевидно, что его выполнения можно всегда добиться за счет простой перенумерации векторов аj. По аналогии с предыдущим параграфом введем обозначения для элементов матрицы задачи (D(q),f) и ее вектора ограничений относительно базиса :
 
  (4.35)
 
  Тогда система ограничений задачи (D(q),f) может быть представлена как
 
  (4.36)
 
 а получаемая на ее основе система ограничений задачи как
 
  (4.37)
 или
 
  (4.38)
 где - фиктивная переменная, которой соответствует нулевой коэффициент в целевой функции, добавляемая для преобразования неравенства в строгое равенство.
  Очевидно, что , т. к. небазисные компоненты оптимального плана равны нулю, т. е. являются заведомо целочисленными. Тогда с учетом сделанных предположении о виде базиса можно записать:
 
 
 
 
 
  ...
 
 
 
  ...
 
 
 
 
 
  (4.39)
 
  Как видно из (4.39), в k-м столбце имеется всего два отличных от нуля элемента: в k-й и (m+1)-й строках. Если вычесть из (m+1)-го уравнения k-e, то, учитывая, что получим эквивалентную систему:
 
 
 
 
 
  ...
 
 
 
  ...
 
 
 
 
 
  (4.40)
 
  Проведенные преобразования системы ограничений позволили явно выделить сопряженный базис, образуемый столбцами с номерами 1, ..., т, п + 1, и соответствующий ому псевдоплан , т.е. для решения задачи может быть применен алгоритм двойственного симплекс-метода. Практически вычислительный процесс для данного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис. 4.5.
 
 
 
 
 
 
 
 
 
 
 
  Рис. 4.5
  Для случая задачи преобразование симплекс-таблицы, получаемое на базе аналогичных рассуждений, приведено на рис. 4.6.
 
 
 
 
 
 
 
 
 
 
 
  Рис. 4.6
 
  Очевидным недостатком алгоритма метода ветвей и границ при решении задач большой размерности является необходимость перебрать слишком большое количество вариантов перед тем, как будет найден оптимальный план. Однако он отчасти может быть преодолен, если ограничиться поиском не оптимального, а просто "хорошего" (близкого к оптимальному) плана. О степени такой близости и скорости приближения к экстремуму нетрудно судить по изменению значений оценок.
  Подчеркнем, что приведенная реализация метода ветвей и границ является одной из многих. Помимо нее, например, очень популярна версия метода решения задачи коммивояжера, в которой для ветвления и построения оценок используют специфические свойства данной модели. При желании о ней можно прочесть в [1, 14].
 
  КЛЮЧЕВЫЕ ПОНЯТИЯ
 
  > Задачи с неделимостями.
  > Экстремальные комбинаторные задачи.
  > Задачи с разрывными целевыми функциями.
  > Правильное отсечение.
  > Метод Гомори.
  > Методы ветвей и границ.
 
  КОНТРОЛЬНЫЕ ВОПРОСЫ
 
 4.1 Какие основные проблемы возникают при решении дискретных задач?
 4.2 Сформулируйте задачу о ранце.
 4.3 Какие экономико-математические модели могут быть сведены к задаче о коммивояжере?
 4.4 Приведите пример моделей с разрывными целевыми функциями.
 4.5 Какой принцип используется для построения правильного отсечения в методе Гомори?
 4.6 Перечислите основные этапы, входящие в "большую" итерацию метода Гомори.
 4.7 Какую роль играет алгоритм двойственного симплекс-метода при решении целочисленной линейной задачи методом Гомори?
 4.8 Перечислите принципиальные идеи, лежащие в основе методов ветвей и границ.
 4.9 Как производится построение отсечения мри решении целочисленной линейной задачи методом ветвей и границ?
 4.10 Опишите схему решения целочисленной задачи линейного программирования методом ветвей и границ.
 4.11 За счет каких преобразований удается построить сопряженный базис при добавлении отсекающего ограничения?
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  ГЛАВА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
 

<< Пред.           стр. 10 (из 13)           След. >>

Список литературы по разделу