58. Марковские процессы. Выражение (основа) для формулировки марковской задачи в виде задачи линейного программирования.

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

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

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

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

59. Марковские процессы. Формулировка Марковской задачи в виде задачи линейного программирования. Постановка задачи.

Задача без дисконтирования.

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

Максимизировать

При ограничениях

Преобразование этой задачи в задачу линейного программирования:

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

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

Максимизировать

При ограничениях

,

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

Минимизировать

При ограничениях

Двойственной к приведенной задаче является задача

Максимизировать

При ограничениях

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

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

Максимизировать

При ограничениях

Оптимальным решением является , , , .Это означает, что . Таким образом, оптимальная стратегия требует выбора альтернативы 2 (k=2) при . Оптимальное значение равно 4,7(6/59)+3,1(31/59)+0,4(22/59)=2,256.

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

Обозначим:

x_i – сумма денежных средств, доступных для инвестирования в начале i-го года,

y_i – сумма реальной инвестиции в начале i-го года (x_i≤ y_i),

n – срок, на которой планируется провести инвестирование.

Прибыль от инвестиции зависит от m условий рынка.

Условие i приводит к прибыли r_i c вероятностью p_i, I = 1, 2, …, m.

Пусть f_i(x_i) – максимальная ожидаемая сумма поступления денежных средств за года от i до n при условии, что в начале i –го года имеется сумма x_i. Для k-го условия рынка имеем следующее.

Так как вероятность k- го условия рынка равна p_k, рекуррентное уравнение динамического программирования имеет следующий вид:

, так как после n-го года инвестиции нет. Отсюда следует, что

поскольку функция в фигурных скобках является линейной по y_n и, следовательно, достигает своего максимума при y_n=x_n.