Динамическое программирование

ГПП

0,0

ГПП

4 5 7

Рисунок 10. Кратчайшая связующая сеть для исходной схемы

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

Нижняя оценка постоянных затрат для исходной схемы (“нулевой группы вариантов”):

= 0,5 + 0,5 + 1 + 1,5 +1,5 = 5 млн тг

Определение минимально возможных переменных затрат начинается с построения начального опорного плана (рис. 11), который должен удовлетворять следующим требованиям:

1) к каждой вершине, кроме вершины I, должна подходить одна стрелка; из вершины I должно выходить не менее одной стрелки;

2) общее количество стрелок должно быть на единицу меньше числа вершин;

3) стрелки не должны образовывать замкнутый контур.

В результате получаем следующий опорный план:

0,0

13 МВт

11 МВт

0,3 0,4

0,3 0,5 0,4

2 МВт P₁ 4 МВт P₂ 10 МВт

0,1 0,3

0,2 0,4

0,4 0,8

0,6 0,5 0,1

P₃ P₄ P₅

Рисунок 11 – Начальный опорный план

На опорном плане рядом со стрелками указаны нагрузки ветвей (МВт), определенные по заданным значениям нагрузок P₁ … P₅, передаваемых по данным ветвям. Кроме того, для каждой ветви указывается значение удельных затрат С_i .

Проверим составленный опорный план на оптимальность. С этой целью вычислим потенциалы вершин, приняв предварительно потенциал вершины I равным нулю.

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

Найденные потенциалы вершин выделены на плане жирным шрифтом.

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

данному незагруженному ребру.

= 0,5 -(0,4 – 0,3) = 0,4 > 0

= 0,6 – (0,5 – 0,4) = 0,5 > 0

= 0,3 – (0,5 – 0,4) = 0,2 > 0

= 0,1 – (0,8 – 0,5) = -0,2 < 0

Если все ребра без стрелок имеют неотрицательные характеристики, то составленный план является оптимальным.

Так как < 0, план не оптимален. Для улучшения плана необходимо “загрузить” то ребро без стрелки, которому соответствует отрицательная характеристика. Новая стрелка направляется от вершины с меньшим потенциалом к вершине с большим потенциалом (на рис. 11 показана пунктиром). При этом образуется замкнутый контур из стрелок.

Для определения величины загрузки ребра 9 необходимо рассмотреть все стрелки контура, имеющие направление, противоположное направлению новой стрелки, и среди них выбрать стрелку с наименьшей “поставкой” (10 МВт на ребре 8).

Выбранная таким образом величина прибавляется ко всем “поставкам ” в стрелках, имеющих то же направление, что и новая стрелка и вычитается из “поставок” в стрелках, имеющих противоположное направление. “Поставки” в стрелках, не входящих в контур, сохраняются неизменными (см. рис. 12).

Новый опорный план проверяется на оптимальность подобно предыдущему плану. Он оказывается оптимальным.

Определяем нижнюю оценку переменных затрат для исходной схемы:

= 0,3*21+0,4*3+0,1*2+0,2*14+0,1*10 = 11,5 млн тг

Нижняя оценка расчетных затрат для исходной схемы:

= += 5 + 11,5 = 16,5 млн тг.

3 МВт

21 МВт

0,3 0,4

0,3 0,5 0,4

,

2 МВт P₁ 14 МВт P₂

0,1 0,3 0,4

0,1

0,2

0,4 0,6

0,6 0,5 10 МВт

P₃ P₄ P₅

Рисунок 12 – Новый опорный план

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

Дальнейшее решение задачи производится с помощью метода “ветвей и границ”. Сравним полученные схемы электроснабжения (см. рис. 10 и рис. 12). В пер­вой схеме отсутствует ребро 2, во второй – остается незагруженным ребро 7. Первое ветвление произведем по ветви 2, т.е. выделим две группы вариантов, одна из которых содержит ветвь 2 (группа А), а вторая – не содержит ее (группа В).

Построим кратчайшую связующую сеть для группы вариантов А, имея в виду, что ветвь 2 в ней обязательно должна присутствовать. Остальные ветви выбираются аналогично построению кратчайшего дерева для исходной схемы.

1 2

4 5

9

Рисунок 13 – Кратчайшая связующая сеть для группы вариантов А

Нижняя оценка постоянных затрат по группе вариантов А:

= 1,5 + 2,0 + 0,5 + 1 +0,5 = 5,5 млн тг

Составленный ранее оптимальный план для исходной схемы (рис. 12) удовлетворяет требованиям к группе вариантов А. Следовательно, нижние оценки переменных затрат для исходной схемы и группы вариантов А совпадают:

= = 11,5 млн тг

Схемы электроснабжения, изображенные на рис.12 и 13 совпадают. Следовательно, получена оптимальная схема для группы вариантов А.

Нижняя оценка расчетных затрат для группы вариантов А составляет:

= + = 5,5+11,5 = 17 млн тг

Произведем определение минимально возможных затрат для группы вариантов В.

Кратчайшая связующая сеть для исходной схемы (рис. 10) отвечает требованиям к группе вариантов В. Следовательно, нижняя оценка постоянных затрат для этой группы составит:

= = 5 млн тг

Для определения минимально возможных переменных затрат по группе вариантов В составим новый опорный план

0,0

24 МВт

0,3

0,3 0,5 0,8

,

0,4

2 МВт P₁ 17 МВт 0,3 P₂

0,1

0,6

0,1

0,2 3 МВт

0,4

0,6 0,5 10 МВт

P₃ P₄ P₅

Рисунок 14 - Опорный план для группы вариантов В

Определим характеристики незагруженных ребер:

= 0,5 -(0,8 – 0,3) = 0

= 0,4 – (0,8 – 0,6) = 0,2 > 0

= 0,6 – (0,5 – 0,4) = 0,5 > 0

Отрицательные характеристики отсутствуют. Следовательно, этот план оптимален.

Определяем нижнюю оценку переменных затрат по группе вариантов В:

= 0,3*24+0,2*17+0,1*2+0,3*3+0,1*10 = 12,7 млн тг

Обе схемы совпадают. Следовательно, найдено оптимальное решение для группы вариантов В.

Нижняя оценка расчетных затрат по группе вариантов В:

= += 5 + 12,7 = 17,7 млн тг

Эта сумма больше, чем нижняя оценка для группы вариантов А. Следовательно, схема, оптимальная для группы вариантов А, является оптимальной для

всех возможных вариантов.

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

Типичные особенности задач, решаемых методом динамического программирования, состоят в следующем:

1. Процесс перехода производственно-экономической системы из одного состояния в другое должен быть марковским (процессом с отсутствием последействия). Это значит, что если система находится в некотором состоянии, то дальнейшее развитие процесса зависит только от данного состояния и не зависит от того, каким путем система приведена в это состояние.

2. Процесс длится определенное число шагов N. На каждом шаге осуществляется выбор одного управления uⁿ, под воздействием которого система переходит из состояния Sⁿ в состояние Sⁿ⁺¹. Поскольку процесс марковский, то управляющее воздействие uⁿ зависит только от текущего состояния системы.

3. Каждый шаг связан с определенным эффектом, который зависит от текущего состояния и принятого решения.

4. Общий эффект за N шагов равен сумме эффектов на отдельных шагах, т.е. критерий оптимальности должен быть аддитивным (или приводящимся к нему).

Любая возможная допустимая последовательность решений называется стратегией управления. Стратегия управления, приводящая к максимальному (или минимальному) значения критерия оптимальности, называется оптимальной.

В основе концепции метода динамического программирования лежит принцип оптимальности Р. Беллмана: “Независимо от того, каким образом система оказалась в рассматриваемом конкретном состоянии, последующие решения должны составлять оптимальную стратегию, привязывающуюся к этому состоянию”.

Благодаря принципу оптимальности удается при последующих переходах испытывать не все возможные варианты, а лишь оптимальные выходы каждого этапа. Метод ДП позволяет заменить трудоемкое вычисление оптимума по N переменным решением N задач, в каждой из которых оптимум находится лишь по одной переменной.

Имеется очень много практических задач, которые ставятся и решаются как задачи ДП (задачи о замене оборудования, распределении ресурсов, выборе конфигурации сети и т. д.).

Пример 7. Определить методом динамического программирования оптималь­ный вариант прокладки кабельной линии 10 кВ от источника питания к потреби-

телю для схемы, приведенной на рисунке 15.

Рисунок 15 – Исходная схемы для выбора трассы кабельной линии

Решение задачи состоит в том, чтобы из множества возможных путей выбрать вариант, обеспечивающий минимум затрат на прокладку кабельной линии.

По переменной x₁ процесс решения можно разделить на 4 шага, по переменной x₂ – на три. Общее число шагов равно семи.

Выбор оптимального пути начинается с конечной точки К (рис. 15). В эту точку кабель может быть проложен либо из точки А₁, либо из точки А₂.

Если на предпоследнем (шестом) шаге мы оказались в точке А₁, то для прокладки кабеля из точки А₁ в точку К необходимо затратить 3 единицы стоимости, а если в точке А₂ – 9 единиц. Запишем эти значения в кружках, соответствующих точкам А₁ и А₂ (рис. 16, а) и обозначим оптимальные управления стрелками. Седьмой шаг спланирован.

Рисунок 16 - Этапы решения задачи методом динамического программирования

Переходим к шестому шагу (рис. 16, б). Рассмотрим возможные переходы из точек В₁, B₂, B₃. Для точки B₁ есть единственное управление из точки A₁ (З_min = 7), а из точки В₂ возможны два пути – через А₁ и А₂. Для точки В₂ расходы на прокладку кабеля через точку А₁ составляют 6 + 3 = 9 единиц, а через точку А₂ - 17 единиц (8 +9). Выбираем путь через точку А₁, записываем в кружок точки В₂ число 9 и отмечаем стрелкой путь от точки В₂ к точке А₁. Для точки В₃ наименьшая стоимость прокладки кабеля – через точку А₂ (З_min = 14). Таким образом, шестой шаг спланирован.

Переходим к планированию 5 шага (рис. 16, в) и т.д. Продолжая процесс, приходим в точку Н. В результате получаем З_опт = 30 единиц (рис. 17).

Оптимальное управление показано на рисунке 17 дополнительными стрелками.

Дата добавления: 2014-01-06