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

находить оптимальные решения, основанные на вычислении последствий каждого решения и

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

Процессы принятия решений, которые строятся по такому принципу, называются многошаговыми процессами.

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

(выигрыш) является аддитивной и равна сумме целевых функций каждого шага.
выбор

управления xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1, и не влияет на предшествующие шаги (нет обратной связи);
состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия xk (отсутствие последействия) и может быть записано в виде уравнения состояния: Sk = fk(Sk-1 , xk);
на каждом шаге управление xk зависит от конечного числа управляющих переменных, а состояние системы зависит Sk – от конечного числа параметров;
оптимальное управление представляет собой вектор , определяемый последовательностью оптимальных пошаговых управлений:
X= (x*1, x*2, ..., x*k, ..., x*n ), число которых и определяет количество шагов задачи.
Все это вытекает из принципа оптимальности

Особенности математической модели задачи ДП

г. американским математиком Р.Э.Беллманом
Формулировка принципа: каково бы ни было

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

Принцип оптимальности

специалистов в области математики и вычислительной техники.
Получил многочисленные результаты, связанные

с применением динамического программирования в разных областях математики.
В вариационном исчислении важную роль играет функциональное уравнение Беллмана. В математических методах оптимального управления известны функция и уравнение Беллмана.
Р. Беллман опубликовал 619 статей и 39 книг. Многие его работы переведены на русский язык.

привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда

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

Идея динамического программирования

рассматриваются не вместе, а последовательно, одна за другой.
Строится такая

вычислительная схема, когда вместо одной задачи со многими переменными строится много задач с малым числом переменных в каждой.
Это значительно сокращает объем вычислений.
ДП применяется для задач:
связанных с течением времени.
многошаговым процессом решения “статической” задачи.

Идея динамического программирования

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

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

Идея динамического программирования

шаги (этапы).
При распределении на несколько лет ресурсов деятельности предприятия

шагом целесообразно считать временной период;
при распределении средств между предприятиями — номер очередного предприятия.
В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на временные отрезки (шаги).
Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.

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

конечное Sn.
Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений.
На каждом шаге необходимо определить два типа переменных:
переменную состояния системы Sk - определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге;
переменную управления xk - в зависимости от состояния S на этом шаге можно применить управления, которые удовлетворяют определенным ограничениям и называются допустимыми.
X=(x1, x2, ..., xk, ..., xn) – общее управление, переводящее систему на состояния S0 в состояние Sn,
- последовательность пошаговых управлений xk

Схема решения задачи ДП

содержание, ремонт и покупку нового автомобиля.
В начале каждого года

владелец может принять одно из трех решений:
продать машину и заменить ее новой;
ремонтировать ее и продолжать эксплуатацию;
продолжать эксплуатацию без ремонта.

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

Пример

решению численное значение 1, второму 2, третьему 3.
Показатель эффективности

равен где – zi расходы в i-м году.
Величину Z требуется обратить в минимум.
Управление в целом представляет собой комбинацию чисел 1, 2, 3; например:   
Это означает, что первые два года следует эксплуатировать машину без ремонта, последующие три года ее ремонтировать, в начале шестого года продать, купить новую, затем снова эксплуатировать без ремонта и т. д.

Пример

использовании рабочей силы,
задача управления запасами.

Классические задачи ДП

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

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

Оптимальная стратегия замены оборудования

на единице оборудования возраста t лет;
u(t) — ежегодные затраты на

обслуживание оборудования возраста t лет;
s(t) — остаточная стоимость оборудования возраста t лет;
Р — покупная цена оборудования.
Рассмотрим период N лет, в пределах которого требуется определить оптимальный цикл замены оборудования.
Обозначим через fN(t) максимальный доход, получаемый от оборудования возраста t лет за оставшиеся N лет цикла использования оборудования при условии оптимальной стратегии.

Оптимальная стратегия замены оборудования

0 соответствует случаю использования нового оборудования. Временные же стадии процесса

нумеруются в обратном направлении по отношению к ходу процесса. Так, N = 1 относится к одной временной стадии, остающей­ся до завершения процесса, а N = N — к началу процесса.





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

Оптимальная стратегия замены оборудования

N-стадийный процесс, а (2) — одностадийный. Оба уравнения состоят из

двух частей: верхняя строка определяет доход, получаемый при сохранении оборудования; нижняя — доход, получаемый при замене оборудования и продолжении процесса работы на новом оборудовании

Оптимальная стратегия замены оборудования

= 10, S(t) = 0, f(t) = r(t)-u(t), представленных в

таблице

Пример

п различными предприятиями, объектами, работами и т.д. так, чтобы получить

максимальную суммарную эффективность от выбранного способа распределения.
Введем обозначения:
xi — количество ресурсов, выделенных i-му предприятию;
gi(xi) — функция полезности, в данном случае это величи­на дохода от использования ресурса xi, полученного i-м предприятием;
fk(x) — наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприятий.

Оптимальное распределение ресурсов

необходимо получить рекуррентное соотношение, связывающее fk(x) и fk-1(x).
Обозначим через хk

количество ресурса, используемого k-м способом (0≤ xk ≤х), тогда для (k-1) способов остается величина ресурсов, равная (x-xk). Наибольший доход, который получается при использовании ресурса (x-xk) от первых (k-1) способов, составит fk-1(x-xk).
Для максимизации суммарного дохода от k-гo и первых (k-1) способов необходимо выбрать xk таким образом, чтобы выполнялись соотношения

Оптимальное распределение ресурсов

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

производства совет директоров выделяет средства в объеме 120 млн р. Траншами по 20 млн р. Прирост выпуска продукции на предприятиях зависит от выделенной суммы, его значения представлены предприятиями и содержатся в таблице.






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

Оптимальное распределение ресурсов

предприятий

Решение будем проводить согласно рекуррентным соотношениям в четыре этапа.
1-й этап.

Инвестиции производим только первому предприятию. Тогда

для 2-го этапа имеет вид

Тогда
при х = 20

f2(20) = max (8+0, 0+10) = max (8, 10) = 10,
при x = 40 f2(40) = max (16, 8+10, 20) = max (16, 18, 20) =20,
при х = 60 f2(60) = max (25, 16+10, 8+20, 28) = max (25, 26, 28, 28) =28,
при х = 80 f2(80) = max (36, 25+10,16+20, 8+28, 40) = max (36, 35, 36, 36, 40) = 40,
при х = 100 f2(100) = max (44, 36+10, 25+20,16+28, 8+40, 48) =
max (44, 46, 45, 44, 48, 48) = 48,
при х = 120 f2(120) = max (62, 44+10, 36+20, 25+28,16+40, 8+48, 62) = max (62, 54, 56, 53, 56, 56, 62) = 62.

по формуле

Тогда
при х = 20 f3(20) = mах (10,

12) = 12,
при x = 40 f3(40) = max (20,10+12, 21) = max (20, 22, 21) = 22,
при х = 60 f3(60) = max (28, 20+12,10+21, 27) = max (28, 32, 31, 27) = 32,
при х = 80 f3(80) = max (40, 28+12, 20+21, 10+27, 38) = max (40, 40, 41, 37, 38) = 41,
при x = 100 f3(100) = max (48, 40+12, 28+21, 20+27, 10+38, 50) =
max (48, 52, 49, 47, 48, 50) = 52,
при х = 120 f3(120) = max (62, 48+12, 40+21, 28+27, 20+38,10+50, 63) = max (62, 60, 61, 55, 58, 60, 63) = 63.

3-м этапом и четвертым предприятием.
При х = 120 f4(120) =

max (63, 52+11, 41+23, 32+30, 22+37, 12+51, 63) =
max (63, 63, 64, 62, 59, 63, 63) = 64.

Получены условия управления от 1-го до 4-го этапа. Вернемся от 4-го к 1-му этапу. Максимальный прирост выпуска продукции в 64 млн р. получен на 4-м этапе как 41+23, т.е. 23 млн р. соответствуют выделению 40 млн р. четвертому предприятию. Согласно 3-му этапу 41 млн р. получен как 20 + 21, т.е. 21 млн р. соответствует выделеник 40 млн р. третьему предприятию. Согласно 2-этапу 20 млн р. получено при выделении 40 млн р. второму предприятию.
Таким образом, инвестиции в объеме 120 млн р. целесообразно выделить второму, третьему и четвертому предприятиям по 40 млн р. каждому, при этом прирост продукции будет максимальным и составит 64 млн р.

В таким образом, чтобы суммарные затраты на его сооружение были

минимальные. Разделим расстояние между пунктами А и В на шаги (отрезки). На каждом шаге можем двигаться либо строго на восток, либо строго на север. Тогда путь от А в В представляет ступенчатую ломаную линию. Затраты на сооружение каждого из отрезков известны

Оптимизация затрат при строительстве транспортных артерий

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

МДП в ряде случаев сокращает объем при поиске оптимальных решений.
К недостаткам относятся:
Отсутствие универсального алгоритма, который был бы пригоден для решения всех задач (мы имеем только схему).
Трудности при решении задач большой размерности.

Преимущества и недостатки ДП