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

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

В основе метода динамического программирования лежит принцип оптимальности, формулировка которого дана Р. Беллманом.

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

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

Рассмотрим управляемую систему, которая под влиянием управления переходит из начального состояния ε ₀ в конечное состояние ε _n. Пусть процесс управления можно разбить на n шагов и ε ₁, ε ₂, _... , ε _n – состояния системы после первого, второго и т.д. шага.

Последовательное преобразование системы на каждом шаге осуществляется с помощью управление u₁, u₂, …, u_n.. Предполагается, что состояние системы в конце k-го шага зависит только от предшествующего состояния системы ε _k-1 и управления u_k на данном шаге.

Варьируя управление u=(u₁, u₂, …, u_n), можно изменять эффективность процесса, которую будем оценивать количественно целевой функцией, зависящей от начального состояния и выбранного управления.

Z=Z(ε ₀; u) (8.1)

В рассматриваемой задаче целевая функция разбивается на сумму показателей эффективности каждого этапа.

(8.2)

Задача пошаговой оптимизации формулируется следующим образом: определить совокупность допустимых управлений u₁, u₂, …, u_n, переводящих систему из начального состояния ε ₀ в конечное состояние ε _n и максимизирующих или минимизирующих показатель эффективности (8.2). Управление, при котором достигается экстремум целевой функции (1.3), называется оптимальным управлением и обозначается через u*=(u*₁, u*₂, …, u*_n).

Сущность метода динамического программирования заключается в следующем. Если система в начале k-го шага находится в состоянии ε _k-1 и мы выбираем управление u_k, то система придет в новое состояние и дальнейшие управления u_k+1, …, u_n должны выбираться оптимальными относительно состояния ε _k. Это означает, что при таких управлениях оптимизируется показать эффективности на последующих до конца процесса шагах k+1, …, n, то есть величина

.

Обозначим через Z_k показатель, характеризующий суммарную эффективность от данного k-го до последнего n-го шага, то есть

(8.3)

Если мы выберем оптимальное управление u*_k на всех этапах, начиная с k-го, то получим величину

, (8.4)

которая зависит только от ε _k-1. Величина Z_k* ( ε _k-1 ) называется условным максимумом (минимумом). Согласно принципу оптимальности, какое бы u_k мы ни выбрали на последующих шагах, управление должно выбираться так, чтобы показатель эффективности Z_k+1, достигая экстремального значения Z*_k+1(ε _k), приводил бы к экстремуму показателя эффективности на всех шагах, начиная с k-го.

Это положение записывается в виде соотношения, называемого функциональным уравнением Беллмана

(8.5)

Уравнения Беллмана позволяют свести решение исходной задачи оптимизации функции и переменных (8.2) к решению последовательности n задач уравнениями (8.5), каждая из которых является задачей оптимизации функции переменной u_k.

Применим метод динамического программирования к решению задачи.

 

Дана ориентированная сеть, содержащая 10 узлов. Найти кратчайший путь из точки 1 в точку 10. Расстояния между узлами приведены на рисунке.

Рис. 8.1

Обозначим через Z_i* минимальный путь из узла i в конечный путь узел 10. Пусть из узла i можно перейти в узел l, расстояние между узлами равно a_il. Обозначим минимальный путь из l в десятый узел через Z_l *. Тогда согласно принципу Беллмана узел l выбирается из условия минимума суммы a_il+z_l*. В результате имеем уравнение Беллмана:

Очевидно, что из 1 в 10 можно попасть не более, чем за 5 шагов. Разделим все узлы сети на 5 множеств. К множеству ε ₀ отнесем все узлы, из которых можно попасть в десятый узел не более чем за 5 шагов. Оно включает начальный узел сети. В множество ε ₁ попадут узлы 2, 3 и 4, из которых можно попасть в конечный узел не более, чем за 4 шага. К ε ₂ отнесем точки из которых можно попасть в пункт 10 не более чем за 3 шага. Это узлы 5 и 6. Множество ε ₃ составляет узел 7, из которого можно достичь узла 10 не более чем за 2 шага. Из точек 8 и 9 в конечный пункт можно попасть не более, чем за один шаг. Они составляют множество ε ₄ .

Условные оптимальные маршруты, начинающиеся в узле i, будем изображать дополнительной стрелкой, идущей от узла i к узлу l, а условные минимальные пути от i до 10 записывать в скобках рядом с узлом. Будем обозначать через u_k*(i)- узел, в который осуществляется оптимальный переход из i. Сначала найдем , где узел s входит в ε _4. z₆*(l)=0 - оптимальный путь за 0 шагов. В 10 можно попасть из точек 8 и 9.

Тогда z₅*(8)=7, при u₅*(8)=10 z₅*(9)=4, при u₅*(9)=10

Далее определим z₄*(ε ₃). Рассмотрим точку . Из седьмого узла можно сразу попасть в 10, а можно сначала в 8. В одном случае путь равен 13, в другом 8+7=15.

Следовательно, z*4=13, u*4 (7)=10.

Найдем z₃*(ε ₂). Множество ε ₂ составляют узлы 5 и 6. Из пункта 5 можно переместиться в 7 и 8.

При этом уравнение Беллмана

; s ε ₂

принимает вид

Мы считаем z₄*(8)=z₅*(8)=7-минимальный путь из 8 узла в конечный. Таким образом, z₃*(5)=15; u₃*(5)=8.

Для узла 6 уравнение Беллмана записывается аналогично

Здесь также считаем z₄*(9)=z₅*(9)=4.

Тогда z₃*(6)=18; u₃*(6)=7 или u₃*(6)=9. На этом этапе получено два оптимальных управления u₃*(6).

На следующем этапе исследуем множество ε _l, состоящее из узлов 2, 3, 4. Из пункта 2 можно попасть только в пункт 5.

Значит .

Из узла 3 можно попасть в пункт 5 и 6.

Z*₂(3)=min .

Из узла 4 возможен переход в узел 6.

Следовательно, z₂*(4)=min =12+18; u₂*(4)=6.

На последнем этапе рассмотрим ε ₀. Оно состоит из одного элемента-узла 1, из которого можно попасть в 4 пункта-второй, третий, четвертый и пятый.

Z*₁(1) =min .

В окончательном виде задачу можно изображать на схеме.

(30)

(4)

Оптимальный маршрут проходит через узлы 1, 3, 5, 8, 10. При этом путь минимален и равен 29.

Решим с помощью метода динамического программирования задачу об оптимальном распределении ресурсов.

Пусть имеется некоторое количество ресурсов x, которое необходимо распределить между n различными предприятиями, объектами, работами и т.д. так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения.

Пусть x_i – количество ресурсов, выделенных i- му предприятию ;

g_i(x_i) – величина дохода от использования ресурса x_i, полученного i-м предприятием;

f_k (x) – наибольший доход, который можно получить при использовании ресурса x от первых k различных предприятий.

Запишем сформулированную задачу в математической форме:

при ограничениях:

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

Обозначим через x_k количество ресурса, используемого k-м способом , тогда для способов остается величина ресурсов, равная . Наибольший доход, который получается при использовании ресурса (x -x_k) от первых (k-1) способов, составит f_k-1 ( x – x_k ). Для максимизации суммарного дохода от k-го и первых способов необходимо выбрать x_k таким образом, чтобы выполнялись соотношения:

, , k=

Рассмотрим конкретную задачу по распределению инвестиций для эффективного использования потенциала предприятия.

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

Для модернизации предприятий совет директоров инвестирует средства в объеме 250 млн. р. с дискретностью 50 млн. р. Прирост выпуска зависит от выделенной суммы, его значения представлены предприятиями и содержатся в таблице.

Инвестиции, млн.р.	Прирост выпуска продукции, млн. р.
Предприятие 1	Предприятие 2	Предприятие 3	Предприятие 4

Найти распределение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить только одну инвестицию.

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

Рекуррентные соотношения будут иметь вид:

для предприятия № 1 , для всех остальных предприятий , .

1-й этап.

Инвестиции проводим только первому предприятию. Тогда f₁ (50)=12; f₁(100)=17; f₁(150)=23; f₁(200)=34; f₁(250)=42.

2-й этап.

Инвестиции выделяем первому и второму предприятиям. Рекуррентное соотношение для 2^го этапа имеет вид .

Тогда при x=50

,

при x=100

,

при x=150

,

при x=200

,

при x=250

 

.

Таким образом, получили

3-й этап.

Инвестиции выделяем только первому, второму и третьему предприятиям .

Тогда при x=50

,

при x=100

,

при x=150

,

при x=200

,

при x=250

.

 

Таким образом, f₃(50)=13; f₃(100)=25; f₃(150)=36; f₃(200)=41; f₃(250)=48.

4-й этап.

Инвестиции в объеме 250 млн.р. распределяем между четырьмя предприятиями .

при x=250

.

.

Вернемся от 4-го этапа к 1-му этапу. Максимальный прирост выпуска в 54млн.р. получен на 4-омэтапе как 18+36, т.е. прирост продукции 18 млн. р. соответствует выделению 100млн.р. четвертому предприятию (см.табл.).

Согласно 3-му этапу 36 млн. р. получено как 11 + 25, т.е. прирост продукции 11млн. р. соответствует выделению третьему предприятию 50 млн.р. Согласно 2-му этапу 25 млн. р. получено как 13 + 12, т.е. прирост 13 млн. р. соответствует выделению второму предприятию 50 млн. р, а прирост 12 млн. р. соответствует выделению первому предприятию 50 млн. р.

Таким образом, инвестиции в объеме 250 млн.р. целесообразно выделить первому, второму и третьему предприятиям по 50 млн.р., а четвертому -100 млн.р., при этом прирост продукции будет максимальным и составит 54 млн.р.

 

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Популярное:

1. АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ
2. АЛГОРИТМИЗАЦИЯИ ПРОГРАММИРОВАНИЕ.
3. Аэродинамическое сопротивление пароперегревателя.
4. Вопрос. Особенности творческого метода Л.Н. Толстого: «диалектика души», тема счастья, «человек- динамическое тождество»
5. Графическое программирование
6. ИНСТИНКТЫ И ПРОГРАММИРОВАНИЕ
7. МАТЕМАТИКА И ПРОГРАММИРОВАНИЕ
8. Нейролингвистическое программирование.
9. Нуклеиновые кислоты. Генетический код. Программирование синтеза белка в клетке.
10. Пассивное и динамическое расслабление
11. Программирование алгоритмов разветвляющейся структуры