Математические методы исследования операций в экономике (стр. 28 из 37)

1) Выбирается некоторая нецелочисленная компонента плана

_k^(q). Поскольку в оптимальном плане она должна быть целой, то можно наложить ограничения x_k ≤[

_k^(q)] и x_k ≥[

_k^(q)]+1. Таким образом,D^(q) разбивается на подмножества

Графическая интерпретация такого разбиения множестваD^(q) приведена на рис. 4.4.

2) Решаются задачи линейного программирования

Соответствующие максимальные значения целевой функции принимаются как ее оценки на этих множествах:

Если оптимальный план

для одной из решенных задач удовлетворяет условию

и содержит только целые компоненты, то, значит, найдено решение основной задачи (4.2)-(4.3). В противном случае среди всех концевых подмножеств, полученных как на предыдущих (D_i^(q)), так и на текущем (D₁^(q), D₂^(q)) этапе, выбирается область с наибольшей оценкой ξ(D_i^(q)). Она становится текущим рассматриваемым подмножеством (D^(q+1)). Далее производится перенумерация концевых множеств и вычислительный процесс итеративно повторяется.

При решении задач (D₁^(q), f) и (D₂^(q), f) можно воспользоваться результатами решения предыдущей задачи (D^(q),f). Рассмотрим вариант организации вычислительного процесса на примере задачи (

₁^(q), f) (для (

₂^(q), f) он выглядит аналогично с точностью до знаков неравенств).

Предположим, что на последнем шаге решения задачи (D^(q), f) был получен оптимальный базис β. Без ограничения общности можно считать, что он состоит из первых m столбцов матрицы задачи. Данное предположение делается исключительно для обеспечения наглядности дальнейшего изложения и очевидно, что его выполнения можно всегда добиться за счет простой перенумерации векторов а^j. По аналогии с предыдущим параграфом введем обозначения для элементов матрицы задачи (D^(q), f) и ее вектора ограничений относительно базиса

:

Тогда система ограничений задачи (D^(q), f) может быть представлена как

а получаемая на ее основе система ограничений задачи (

₁^(q), f) как

или

где х_n+1 ≥ 0 — фиктивная переменная, которой соответствует нулевой коэффициент в целевой функции, добавляемая для преобразования неравенства в строгое равенство.

Очевидно, что 1≤k≤m, т. к. небазисные компоненты оптимального плана (m+1≤j≤n) равны нулю, т. е. являются заведомо целочисленными. Тогда с учетом сделанных предположений о виде базиса

можно записать:

Как видно из (4.39), в k-м столбце имеется всего два отличных от нуля элемента: в k-й и (m+1)-й строках. Если вычесть из (m+1)-го уравненияk-e, то, учитывая, что [ά_k] – ά_k =-{ά_k}, получим эквивалентную систему:

Проведенные преобразования системы ограниченийD₁^(q) позволили явно выделить сопряженный базис, образуемый столбцами с номерами 1,..., m, n+1, и соответствующий ему псевдоплан (ά₁, ..., ά_m, 0,....,0, -{ά_k}), т.е. для решения задачи (D₁^(q), f) может быть применен алгоритм двойственного симплекс-метода. Практически вычислительный процесс для данного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис. 4.5.

Для случая задачи (D₂^(q), f) преобразование симплекс-таблицы, получаемое на базе аналогичных рассуждений, приведено на рис. 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. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

5.1. ОБЩАЯ СХЕМА МЕТОДОВ

ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

5.1.1. Основные идеи вычислительного метода динамического программирования. Некоторые задачи математического программирования обладают специфическими особенностями, которые позволяют свести их решение к рассмотрению некоторого множества более простых «подзадач». В результате вопрос о глобальной оптимизации некоторой функции сводится к поэтапной оптимизации некоторых промежуточных целевых функций. В динамическом программировании* рассматриваются методы, позволяющие путем поэтапной (многошаговой) оптимизации получить общий (результирующий) оптимум.

* Динамическое программирование как научное направление возникло и сформировалось в 1951-1953 гг. благодаря работам Р. Беллмана и его сотрудников.

Обычно методами динамического программирования оптимизируют работу некоторых управляемых систем, эффект которой оценивается аддитивной, или мультипликативной, целевой функцией. Аддитивной называется такая функция нескольких переменных f(х₁,x₂,...,х_n), значение которой вычисляется как сумма некоторых функцийf_j, зависящих только от одной переменной х_j:

Слагаемые аддитивной целевой функции соответствуют эффекту решений, принимаемых на отдельных этапах управляемого процесса. По аналогии, мультипликативная функция распадается на произведение положительных функций различных переменных: