Лабораторная работа №3
Тема: Управление запасами и вероятностное динамическое программирование.
Цель работы: знакомство с задачами управления запасами и вероятностными задачами динамического программирования, изучение различных методов решения в системе компьютерной математики.
1. Краткие теоретические сведения
1.1 Общая схема решения задач динамического программирования.
Для решения задач динамического программирования необходимо выполнить следующие действия:
1. Определить этапы.
2. Определить на каждом этапе вариантов решения (альтернатив).
3. Определить состояния на каждом этапе.
Из перечисленных выше элементов понятие состояния, как правило, представляется весьма сложным для восприятия. Рассмотренные в этом разделе приложения последовательно показывают, что определение состояния меняется в зависимости от моделируемой ситуации. При рассмотрении каждого приложения полезно ответить на следующие вопросы.
1. Какие соотношения связывают этапы вместе?
2. Какая информация необходима для того, чтобы получить допустимые решения на текущем этапе без повторной проверки решений, принятых на предыдущих этапах?
1.2. Азартная игра
Одна из разновидностей игры в русскую рулетку состоит во вращении колеса, на котором по его периметру нанесены п последовательных чисел от 1 доп. Вероятность того, что колесо в результате одного вращения остановится на цифреi, равнар,. Игрок платитх долларов за возможность осуществитьт вращений колеса. Сам же игрок получает сумму, равную удвоенному числу, которое выпало припоследнем вращении колеса. Поскольку игра повторяется достаточно много раз (каждая дот вращений колеса), требуется разработать оптимальную стратегию для игрока.
Мы сформулируем задачу в виде модели ДП, используя следующие определения.
Этап i соответствуетi-му вращению колеса,i= 1,2,...,т.
Альтернативы на каждом этапе состоят в следующем — либо покрутить колесо еще раз, либо прекратить игру.
3. Состояние системыj на каждом этапеiпредставляется одним из чисел от 1 доn, которое выпало в результатепоследнего вращения колеса.
Пусть fi(j) — максимум ожидаемой прибыли при условии, что игра находится на этапе (вращении)iи исходом последнего вращения есть число у. Имеем следующее.
Рекуррентное уравнение для fi(j) можно записать следующим образом.
Обоснование рекуррентного уравнения сводится к следующему. При первом вращении колеса (j=1) состоянием системы являетсяj=0, ибо игра только началась. Следовательно,f1(0)=p1f2(1)+p2f2(2)+...+ pnf2(n). После выполнения последнего вращения колеса (i=т) имеется лишь один выбор — закончить игру независимо от исходаj т-го вращения. Следовательно,fm+1(j)=2j.
Рекуррентные вычисления начинаются cfm+l, заканчиваются приf1(0) и сводятся таким образом кm+1 вычислительному этапу. Так какf1(0) представляет собой ожидаемую прибыль от всехm вращений колеса, а игра обходится игроку вх долларов, имеем следующее.
Ожидаемая прибыль = f1(0) –х.
1.3. Вероятностная задача инвестирования
Некто планирует инвестировать С тысяч долларов через фондовую биржу в течение последующих и лет. Инвестиционный план состоит в покупке акций в начале года и продаже их в конце этого же года. Накопленные деньги затем могут быть снова инвестированы (все или их часть) в начале следующего года. Степень риска инвестиции представлена тем, что прибыль имеет вероятностный характер. Изучение рынка свидетельствует о том, что прибыль от инвестиции зависит отm условий рынка (благоприятных или неблагоприятных). При этом условиеiприводит к прибылиri с вероятностьюрi, i=1, 2, ...,т. Как следует инвестироватьСтысяч долларов для наибольшего накопления к концуп лет?
Обозначим
xi — сумма денежных средств, доступных для инвестирования в началеi-го года (x1=C),
уi — сумма реальной инвестиции в началеi-го года (уi<хi).
Элементы модели ДП можно описать следующим образом.
Этап i представляетi-й год инвестирования.
Альтернативами на этапеi являются величиныyi.
Состояние системы на этапеiописывается величинойхi.
Пусть fi(xi) — максимальная ожидаемая сумма поступления денежных средств за года отiдоnпри условии, что в началеi-го года имеется суммахi. Дляk-го условия рынка имеем следующее.
хi+1=(1+rk)yi+(хi–уi)=rkyi+xi, k=1,2,...,m.
Так как вероятность k–го условия рынка равнарk, рекуррентное уравнение динамического программирования имеет следующий вид.
где fn+1(xn+1)= xn+1, так как послеn-го года инвестиции нет. Отсюда следует, что
поскольку функция в фигурных скобках является линейной по уn и, следовательно, достигает своего максимума приуn=хn.