Динамическое программирование. Марковские процессы принятия решений (динамические модели стохастических процессов принятия решений)

Пусть некоторая система в любой фиксированный момент t может находиться в одном из n состояний и перейти из этого состояния в любое другое. Пусть вероятность P_t(i,j) перехода в момент t из i-го состояния в j-е не зависит от предыстории системы. Такая система называется Марковской.

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

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

Мы будем рассматривать задачу с конечным плановым периодом.

Задача о садовнике.

Некто берет в аренду земельный участок на n лет и собирается использовать его для выращивания сельскохозяйственных культур. Состояние почвы может быть хорошим (Х), удовлетворительным (У) и плохим (П). Состояние почвы может меняться. Нужно принимать решения о внесении удобрений.

Изменение состояния почвы при решении не вносить удобрения описывается следующей матрицей.

Буквы х у п по вертикали означают состояние почвы в начале года, по горизонтали – в конце года. Соответствующий элемент матрицы – вероятность того, что если не вносить удобрения состояние почвы изменится таким образом. Например, вероятность того, что без внесения удобрений почва из хорошей в начале года станет удовлетворительной в конце года равна 0.4. Соответствующая матрица дохода с учетом решения:

Аналогичными матрицами описывается состояние почвы и дохода при решении вносить удобрения:

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

Имеем систему с множеством состояний и множество управлений будем описывать их просто индексами . Рассматривается управление системой на шагах (шаги: ).

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

Нарисуем схему данной задачи:

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

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

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

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

Обратная прогонка:

N-й шаг:

…………………………………………………………………………..

n-й шаг:

…………………………………………………………………………..

1-й шаг:

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

Возможности усложнения:

· ­ матрицы переходов состояний и доходов меняются в зависимости от шага: ;

· учитывается влияние инфляции: – коэффициент инфляции, – коэффициент дисконтирования, тогда: ;

· , при бесконечном плановом периоде нужно ориентироваться на средние доходы по каким-то интервалам.

Динамическое программирование. Задача управления запасами.

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

Факторы, влияющие на систему управления запасами:

· спрос: детерминированный или стохастический. Детерминированный спрос может быть статическим или динамическим. Стохастический спрос может быть стационарным или нестационарным;

· задержки в поставках;

· период планирования;

· складирование;

· число видов продукции (однопродуктовые и многопродуктовые);

· вид поставок (дискретные или непрерывные);

· нехватка продукции (требование к гарантированному запасу).

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

· детерминированный динамический спрос;

· задержки равны нулю;

· конечный период планирования;

· 1 склад;

· один вид продукции;

· дискретные поставки;

· нехватка продукции недопустима.

Нарисуем схему данной задачи:

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

- потребление по шагам.

– поставки по шагам.

Функция переходов состояний: .

Стоимость поставки может описываться следующими моделями:

· ;

· ;

· , где – как в предыдущей модели, – разовые затраты, связанные с самим фактом поставки, .

Стоимость хранения может описываться следующими моделями:

· ;

· - будем рассматривать этот вариант;

· .

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

Обратная прогонка:

n-й шаг:

…………………………………………………………………………..

j-й шаг:

…………………………………………………………………………..

1-й шаг: аналогично – му.

39. Динамическое программирование. Задача о замене оборудования (2-я постановка).

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

2-я постановка предполагает наличие остаточной стоимости оборудования. Стоимость замены – это стоимость покупки нового оборудования минус стоимость от продажи заменяемого оборудования. В такой постановке затраты на замену и эксплуатацию должны быть разделены. Введем следующие обозначений:

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

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

Обратная прогонка:

n-й шаг:

УОУ – это эксплуатация или замена оборудования.

…………………………………………………………………………..

j-й шаг:

…………………………………………………………………………..

2-й шаг:

Прямая прогонка – восстановление последовательности замены/эксплуатации оборудования.

Динамическое программирование. Задача о рекламе.

Имеется фирма, которая распространяет свою продукцию в регионах . Для продвижения товаров используется два вида рекламы: стационарная реклама и рекламные агенты. Имеются запасы средств для использования рекламы каждого вида, причем средства для стационарной рекламы нельзя использовать для оплаты рекламных агентов и наоборот. В каждый регион вкладывается средств стационарной рекламы и средств оплаты работы агентов, причем выгода от рекламы рассчитывается по функции .

Функция перехода состояний:

Обратная прогонка:

m-й шаг:

…………………………………………………………………………..

i-й шаг:

…………………………………………………………………………..

1-й шаг:

Прямая прогонка:

Динамическое программирование. Задача о рюкзаке (контейнере, задача о загрузке).

Имеется контейнер грузоподъемностью . Имеются товары , которые могут быть загружены в контейнер. Товарам соответствуют веса и стоимости . Задача заключается в том, чтобы заполнить контейнер так, чтобы суммарная стоимость груза в контейнере была максимальной.

Если бы не требование целочисленности решения, то задача была бы обыкновенной задачей линейного программирования.

Нарисуем схему переходов состояний с отображением управлений и выигрышей:

Требование целочисленности решения не гарантирует того, что контейнер будет загружен «до упора», но тем не менее стоит отметить, что на последнем шаге следует потратить как можно больше оставшейся грузоподъемности. Функция перехода состояний в данной задачи: .

Обратная прогонка:

m-й шаг:

Квадратные скобки там, где дробь – целая часть числа.

…………………………………………………………………………..

i-й шаг:

…………………………………………………………………………..

1-й шаг:

Прямая прогонка:

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