эти пределы превышаются в силу неожиданных задержек, экипаж должен быть заменен новым. Авиакомпании содержат резервные экипажи для таких случаев. Средняя годовая стоимость содержания члена резервного экипажа оценивается в 30 ООО долл. Задержка полета на одну ночь, обусловленная отсутствием резервного экипажа, может стоить 50 ООО долл. Член экипажа находится по вызову непрерывно 12 часов в сутки 4 дня в неделю и может не находиться по вызову три оставшихся дня недели. Самолет В-74 7 может обслуживаться двумя экипажами для самолета В-707.
Следующая таблица содержит вероятности вызова резервных экипажей, вычисленные на основании трехлетнего опыта.
| | Вероятность вызова |
Категория рейса | Рейс (время вылета) | В-747 | В-707 |
| 14:00 | 0,014 | 0,072 |
| 13:00 | 0,000 | 0,019 |
| 12:30 | 0,000 | 0,006 |
| 12:00 | 0,016 | 0,006 |
| 11:30 | 0,003 | 0,003 |
| 11:00 | 0,002 | 0,003 |
Приведенные данные свидетельствуют, например, что для 14-часового рейса вероятность вызова равна 0,014 для В-747 и 0,072 - для В-707.
Типичная пиковая часть расписания дня имеет следующий вид.
Время дня Самолет Категория рейса
8:00 | | |
9:00 | | |
| | |
10:00 | | |
11:00 | | |
| | |
15:00 | | |
16:00 | | |
19:00 | | |
Существующая политика относительно резервных экипажей состоит в использовании двух экипажей (по семь членов каждый) с 5:00 до 11:00, четырех - с 11:00 до 17:00 и двух - с 17:00 до 23:00.
Оцените эффективность существующей политики относительно резервных экипажей. В частности, является ли число резервных экипажей очень большим, очень малым или таким, как необходимо?
ГЛАВА 15
ВЕРОЯТНОСТНОЕ ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Вероятностное динамическое программирование (ДП) отличается от детерминированного, описанного в главе 10, тем, что состояния и прибыли на каждом этапе являются случайными1. Модели вероятностного ДП возникают, в частности, при рассмотрении стохастических моделей управления запасами и в теории марковских процессов принятия решений. Этим двум темам посвящены главы 16 и 19, поэтому в настоящей главе они не рассматриваются. В этой главе описываются некоторые примеры достаточно общего содержания, призванные показать стохастическую природу ДП.
15.1. АЗАРТНАЯ ИГРА
Одна из разновидностей игры в русскую рулетку состоит во вращении колеса, на котором по его периметру нанесены п последовательных чисел от 1 до п. Вероятность того, что колесо в результате одного вращения остановится на цифре i, равна рг Игрок платит х долларов за возможность осуществить т вращений колеса. Сам же игрок получает сумму, равную удвоенному числу, которое выпало при последнем вращении колеса2. Поскольку игра повторяется достаточно много раз (каждая до т вращений колеса), требуется разработать оптимальную стратегию для игрока.
Мы сформулируем задачу в виде модели ДП, используя следующие определения.
1. Этап i соответствует i-му вращению колеса, i- 1, 2, т.
2. Альтернативы на каждом этапе состоят в следующем - либо покрутить колесо еще раз, либо прекратить игру.
3. Состояние системы j на каждом этапе i представляется одним из чисел от 1 до п, которое выпало в результате последнего вращения колеса.
Пусть ffj) - максимум ожидаемой прибыли при условии, что игра находится на этапе (вращении) t и исходом последнего вращения есть число у. Имеем следующее.
1 Эта глава является продолжением главы 10, посвященной детерминированным моделям динамического программирования.
Здесь подразумевается, что игрок может прекратить игру (больше не вращать колесо) после любого г-го вращения колеса (i < m). В этом случае выигрыш определяется результатом последнего вращения колеса, на котором игра остановлена. - Прим. ред.
(Ожидаемая прибыль на этапе / при условии, [ что исходом последнего вращения есть j
2 j, если игра заканчивается,
L,Pkfi*\ (*)> если игРа продолжается.
Рекуррентное уравнение для /,(у) можно записать следующим образом.
/„-,(/) = 2у,
/(./) = max
конец игры:
продолжение игры: ptf,tt(k), / = 2,3,...,т,
y;(o)=Zft/,w
Обоснование рекуррентного уравнения сводится к следующему. При первом вращении колеса (£ = 1) состоянием системы является у = 0, ибо игра только началась. Следовательно, /,(0) = р,/2(1) + р2/2(2) + ... + pj2(n). После выполнения последнего вращения колеса (£ = т) остается лишь один выбор - закончить игру независимо от исхода у m-го вращения. Следовательно, fm ,,(;) = 2у.
Рекуррентные вычисления начинаются с /т + 1, заканчиваются при /ДО) и сводятся таким образом к т + 1 вычислительному этапу. Так как /,(0) представляет собой ожидаемую прибыль от всех т вращений колеса, а игра обходится игроку в х долларов, получаем следующее.
Ожидаемая прибыль = /,(0) - х.
Пример 15.1.1
Предположим, что по периметру колеса русской рулетки расставлены числа от 1 до 5. ВероятностиPi остановки колеса на числе / соответственно равны следующему: Pl = 0,3, р2 = 0,25, рз = 0,2, р4 = 0,15, р5 = 0,1. Игрок платит 5 долл. за возможность сделать не более четырех вращений колеса. Определим оптимальную стратегию игрока для каждого из четырех вращений и найдем соответствующий ожидаемый выигрыш.
Этап 5.
/*(/) = 2/.
Исход 4-го вращения, j | f5{j) | Оптимальное решение Решение |
| | Закончить |
| | Закончить |
| | Закончить |
| | Закончить |
| | Закончить |
Этап 4.
ftf) = max {2j, Plf5( 1) + р/5(2) + Pifs(3) + p/5(4) + p&5)} = = max{2/, 0,3x2+ 0,25x4 +0,2x6 +0,15x8+ 0,1 x 10} = = max{2/, 5}.