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

Глава V

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

5.1. Введение

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

5.2. Азартная игра

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

Мы сформулируем задачу в виде модели ДП, используя следующие определения.

1. Этап i соответствует i-му вращению колеса, i = 1, 2, ..., m.

2. Альтернативы на каждом этапе состоят в следующем — либо покрутить колесо еще раз, либо прекратить игру.

Рекомендуемые материалы

3. Состояние системы j на каждом этапе i представляется одним из чисел от 1 до п, которое выпало в результате последнего вращения колеса.

Пусть f_i(j) — максимум ожидаемой прибыли при условии, что игра находится на этапe (вращении) i и исходом последнего вращения есть число j Имеем следующее.

Рекуррентное уравнение для f_i(j) можно записать следующим образом.

Обоснование рекуррентного уравнения сводится к следующему. При первом вращении колеса (i = 1) состоянием системы является j = 0, ибо игра только началась. Следовательно, f₁(0) = p₁f₂(l) + + ... + p_nf₂(n). После выполнения последнего вращения колеса (i = т) имеется лишь один выбор — закончить игру независимо от исхода j m – го вращения. Следовательно f_m+1(j) = 2j.

Рекуррентные вычисления начинаются с f_m+1, заканчиваются при f₁(0) и сводятся таким образом к т + 1 вычислительному этапу. Так как f₁(0) представляет собой ожидаемую прибыль от всех т вращений колеса, а игра обходится игроку в х долларов, имеем следующее.

Ожидаемая прибыль = f₁(0) – x.

Пример 5.2-1

Предположим, что по периметру колеса русской рулетки расставлены числа от 1 до 5. Вероятности р_i остановки колеса на числе i соответственно равны следующему: p₁ = 0.3,
 р₂ =0.25, p₃ = 0.2, p₄ = 0.15, р₅ = 0.1. Игрок платит 5 долларов за возможность сделать не более четырех вращений колеса. Определим оптимальную стратегию игрока для каждого из четырех вращений и найдем соответствующий ожидаемый выигрыш.

Этап 5.

Этап 4.

Этап 3.

Этап 2.

Этап.1.

В начале игры единственным выбором является вращение колеса.

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

Ожидаемая прибыль от игры составляет 7.31 – 5 = 2.31 доллара.

Упражнение 5.2, а

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

2. Я хочу продать свой подержанный автомобиль тому, кто предложит наивысшую цену. Изучая автомобильный рынок, я пришел к выводу, что с равными вероятностями мне за автомобиль могут предложить очень низкую цена (около 1050 долларов), просто низкую цену (около 1900 долларов), среднюю цену (около 2500 долларов) либо высокую цену (примерно 3000 долларов). Я решил помещать объявление о продаже автомобиля на протяжении не более трех дней подряд. В конце каждого дня мне следует решить, принять ли наилучшее предложение, поступившее в течение этого дня. Какой должна быть моя оптимальная стратегия относительно принятия предложенной цены за автомобиль?

5.3. Задача инвестирования

Некто планирует инвестировать С тысяч долларов через фондовую биржу в течение последующих п лет. Инвестиционный план состоит в покупке акций в начале года и продаже их в конце этого же года. Накопленные деньги затем могут быть снова инвестированы (все или их часть) в начале следующего года. Степень риска инвестиции представлена тем, что прибыль имеет вероятностный характер. Изучение рынка свидетельствует о том, что прибыль от инвестиции зависит от т условий рынка (благоприятных или неблагоприятных). При этом условие i приводит к прибыли r_i с вероятностью p_i, i = 1, 2, ..., т. Как следует инвестировать С тысяч долларов для наибольшего накопления к концу п лет?

Обозначим

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

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

Элементы модели ДП можно описать следующим образом.

1. Этап i представляет i-й год инвестирования.

2. Альтернативами на этапе i являются величины y_i.

3. Состояние системы на этапе i описывается величиной х_i.

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

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

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

,

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

Пример 5.3-1

Пусть в предыдущей модели инвестирования объем инвестиции составляет С =10 000 долларов на 4-летний период. Существует 40%-ная вероятность того, что вы удвоите деньги, 20%-ная — останетесь при своих деньгах и 40% — потеряете весь объем инвестиции. Необходимо разработать оптимальную стратегию инвестирования.

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

Этап 4.

.

Отсюда порлучаем

Этап 3.

Поэтому имеем

Этап 2.

Отсюда следует

Этап 1.

Имеем

Оптимальную инвестиционную политику можно сформулировать следующим образом. Так как  для i = 1, 2, 3, 4, то оптимальным решением является инвестирование всех наличных денежных средств в начале каждого года. Накопленные денежные средства к концу четырех лет составят 3.8416x₁ = 3.8416 3 10000 = 38416 долларов.

Упражнения 5.3,а

1. Определите оптимальную инвестиционную политику в примере 5.3-1 в предположении, что вероятности р_k и прибыли r_k для следующих 4 лет принимают такие значения.

2. Камера объемом 10 кубических метров предназначена для хранения изделий трех наименований. Одно изделие наименований 1, 2, 3 занимает соответственно 2, 1 и 3 кубических метра. Вероятности спроса на эти изделия приведены в следующей таблице.

Стоимость хранения единицы изделия наименований 1, 2, 3 равна 8, 10 и 15 дол­ларов соответственно. Сколько единиц изделий каждого наименования следует хранить в камере?

3. Фирма с высокотехнологичным производством начала выпуск самых современных суперкомпьютеров в расчете на трехлетний период. Годовой спрос D на новый суперкомпьютер описывается распределением

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

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

Как компании распределить восемь велосипедов между тремя спортивными центрами?

5.4. Максимизация вероятности достижения цели

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

Используя обозначения из раздела 5.3, оставим без изменения определение этапа i, альтернативы у_i и состояния х_i. Эти модели отличаются только определением критерия; здесь нашей целью является максимизация вероятности достижения некоторой накопленной денежной суммы S по истечении п лет. С этой точки зрения определим функцию f_i(x_i) – вероятность накопления суммы S, если в начале i-го года имеются денежные средства в сумме х_i и для последующих лет i, i + 1,..., п используется оптимальное инвестирование.

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

Рекуррентная формула основана на формуле условной вероятности

В нашем случае f_i+1 (x_i + r_k y_i) играет роль вероятности Р{А | B_j}.

Пример 5.4-1

Некий индивидуум планирует инвестировать 2 000 долларов. Имеющиеся варианты позволяют удвоить эту сумму с вероятностью 0.3 или потерять ее с вероятностью 0.7. Акции продаются в конце года, а в начале следующего года все деньги или их часть снова инвестируются. Этот процесс повторяется на протяжении трех лет. Целью является максимизация вероятности достижения суммы в 4 000 долларов в конце третьего года.

В соответствии с обозначениями данной модели, имеем r₁ = 1 с вероятностью 0.3
и r₂ = –1 с вероятностью 0.7.

Этап 3.

На этом этапе состояние х₃ может изменяться от 0 до 8 000 долларов. Минимальное значение возможно, когда вся инвестиция потеряна, а максимальное – когда инвестиция удваивается в конце каждого из двух первых лет. Следовательно, рекуррентное уравнение для этапа 3 записывается в следующем виде:

,

где, x₃ = 0, 1,..., 8.

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

.

В противном случае эти вероятности равны 1.

Хотя приведенная таблица и свидетельствует о том, что существуют альтерна­тивные оптимумы для х₃ = 1, 3, 4, 5, 6, 7 и 8, оптимальный (последний) столбец содержит лишь наименьшие оптимальные значения у₃. Это объясняется тем, что инвестор не собирается инвестировать больше того, что необходимо для достиже­ния поставленной цели.

Этап 2.

.

Этап 1.

.

Оптимальная стратегия определяется следующим образом. При заданной начальной сумме х₁ = 2000 долларов вычисления для первого этапа дают у₁ = 0. Это означает, что в первый год не следует делать инвестиций. Данное решение оставляет инвестора с 2000 долларов к началу второго года. Из таблицы, соответствующей второму этапу, при x₂ = 2 получаем у₂ = 0; это снова означает, что на протяжении второго года также не следует делать инвестиций. Далее использование значения х₃ = 2 на третьем этапе приводит к у₃ = 2, а это означает, что на третий год следует инвестировать всю имеющуюся в распоряжении сумму. Соответствующая максимальная вероятность достижения цели S = 4 равна f₁(2) = 0.3.

Упражнения 5.4,а

1. В примере 5.4–1 этап 1 решения задачи показывает, что существует два альтернативных оптимума: y₁ = 0 и у₁ = 2. Покажите, что применение стратегии у₁ = 2 (т.е. инвестировать все деньги в начале первого года) не изменяет результата инвестиционной политики на протяжении трех лет, а именно, соответствующая максимальная вероятность достижения цели сохраняется равной 0.3.

2. Решите задачу из примера 5.4-1, если целью инвестора является максимизация вероятности достижения, по меньшей мере, суммы в 6 000 долларов к концу третьего года. Инвестор имеет в своем распоряжении 1000 долларов, и вероятность удвоения суммы на протяжении каждого года равна 0.6.

3. Вы и ваш друг хотите сыграть в казино в следующую игру. Вы делаете определенную ставку, и каждый из вас независимо подбрасывает симметричную монету. За каждый доллар суммы ставки казино заплатит три доллара, (что дает чистую прибыль в 2 доллара), если в результате подбрасывания выпадут две решки. Иначе вы теряете сумму ставки. Если вы с другом имеете в сумме один доллар, определите стратегию игры, считая, что целью является максимизация вероятности окончания трех игр с суммой в 4 доллара.

Литература

Bertsekas D. Dynamic Programming: Deterministic and Stochastic Models, Prentice Hall, Upper Saddle River, N. J., 1987.

Cooper L. and Cooper M. Introduction to Dynamic Programming, Pergamon Press, N. Y., 1981.

Smith D. Dynamic Programming: A Practical Introduction, Ellis Horwood, London, 1991.

Комплексные задачи

5-1. Компания использует грузовые автомобили для доставки заказов покупателям и планирует заменить свои автомобили на протяжении последующих пяти лет. Годовые затраты, связанные с использованием нового грузовика, являются нормально распределенной случайной величиной с математическим ожиданием 300 долларов и среднеквадратическим отклонением 50 долларов. Математическое ожидание и среднеквадратическое отклонение годовых эксплуатационных затрат через год возрастают на 10%. Стоимость нового грузового автомобиля в настоящее время равна 20 000 долларов и через год возрастет, как ожидается, на 12%. Грузовые автомобили используются чрезвычайно интенсивно, поэтому существует вероятность того, что каждый из них может сломаться в любое время, после чего ремонту не подлежит. Имеется возможность сдать старый автомобиль при покупке нового. При этом стоимость старого автомобиля зависит от того, находится ли он в рабочем состоянии. В начале шестого года автомобиль подлежит продаже по цене, которая также зависит от его состояния (аварийное или рабочее). Приведенная ниже таблица содержит данные, описывающие ситуацию в зависимости от возраста автомобиля.

Если автомобиль использовался 1 год и находится в рабочем состоянии, то его стоимость равна 70% от начальной и за год уменьшается на 15%. Если же он находится в аварийном состоянии, то соответствующие показатели уменьшаются в два раза. Стоимость автомобиля в виде испорченного имущества в начале шестого года составляет 200 долларов, если он находится в рабочем состоянии, и 50 долларов, если он аварийный. Разработайте оптимальную политику замены автомобилей.