Магазин реализует следующую стратегию: максимальный уровень запаса не должен превышать двух холодильников в течение любого месяца.
a) Определите переходные вероятности при различных альтернативах решения этой задачи.
b) Определите ожидаемые месячные затраты на хранение запаса как функцию состояния системы и альтернативных решений.
c) Определите оптимальную стратегию размещения заказов на последующие 3 месяца.
4. Выполните задания предыдущего упражнения, предполагая, что плотности вероятностей спроса на следующий квартал определяются значениями из следующей таблицы.
19.3. МОДЕЛЬ С БЕСКОНЕЧНЫМ ЧИСЛОМ ЭТАПОВ
Существует два метода решения задачи с бесконечным числом этапов. Первый метод основан на переборе всех возможных стационарных стратегий в задаче принятия решений. Этот подход, по существу, эквивалентен методу полного перебора, и его можно использовать только тогда, когда общее число стационарных стратегий с точки зрения практических вычислений достаточно мало. Второй метод, называемый методом итераций по стратегиям, как правило, более эффективен, так как определяет оптимальную стратегию итерационным путем.
19.3.1. Метод полного перебора
Предположим, что в задаче принятия решений имеется S стационарных стратегий. Пусть РиК - матрицы переходных (одношаговых) вероятностей и доходов, соответствующие применяемой стратегии, 8 = 1,2, S. Метод перебора включает следующие действия.
Шаг 1. Вычисляем v, - ожидаемый доход, получаемый за один этап при стратегии s для заданного состояния I, i = 1, 2.....т.
Шаг 2. Вычисляем п - долгосрочные стационарные вероятности матрицы переходных вероятностей Р, соответствующие стратегии s. Эти вероятности (если они существуют) находятся из уравнений
где я*=(я;,я2,...Х).
Шаг 3. Вычисляем по следующей формуле Е ожидаемый доход за один шаг (этап) при выбранной стратегии s.
Шаг 4. Оптимальная стратегия s* определяется из условия, что
Е =тах{Е}.
Проиллюстрируем этот метод на примере задачи садовника при бесконечном горизонте планирования.
Пример 19.3.1
В задаче садовника имеется восемь стационарных стратегий, представленных в следующей таблице.
Стационарная стратегия, s | Действия |
| Не применять удобрения вообще |
| Применять удобрения независимо от состояния почвы |
| Применять удобрения, если почва находится в состоянии 1 |
| Применять удобрения, если почва находится в состоянии 2 |
| Применять удобрения, если почва находится в состоянии 3 |
| Применять удобрения, если почве находится в состоянии 1 или 2 |
| Применять удобрения, если почва находится в состоянии 1 или 3 |
| Применять удобрения, если почва находится в состоянии 2 или 3 |
Матрицы Р5 и R1 для стратегий от 3 до 8 получаются из аналогичных матриц для стратегий 1 и 2. Таким образом, имеем
| | 0,5 0,3Ч | | | | | | |
| | 0,5 0,5 | | | | | | |
| | 0 1 , | | | | | | |
| | 0,6 0,1 | | | | | |
Р2 = | | 0,6 0,3 | , R2 | | | | |
| ,0,05 | 0,4 0,55, | | | | 3 • | |
| | 0,6 0,Г | | | | | | |
Р3 = | | 0,5 0,5 | | R3 = | | | | » |
| | | | | | | | |
| | 0,5 0,3N | | | | | | |
Р4 = | | 0,6 0,3 | | R4 = | | | | |
| | 0 1 , | | | | | | |
| | | 0,3 4 | | | | |
Р5 = | | | | , R5 = | | | |
| 0,05 | | 0,55, | | | | |
| | | | | | | | |
Р6 = | | | | | R6 = | | | |
| | | | | | | | |
| | | | | | | |
Р7 = | | | | , R7 = | | | |
| ,0,05 | | 0,55; | | | | |
| г 0,2 | | | | | | |
Р8 = | | | | , R8 = | | | |
| 0,05 | | 0,55, | | | | "2, |
Результаты вычислений значений v* приведены в следующей таблице.
| | | |
/= 1 | /= 2 | /= 3 |
| | | -1,0 |
| | | |
| | | -1,0 |
| | | -1,0 |
| | | |
| | | -1,0 |
| | | |
| | | |
Стационарные вероятности находятся из уравнений
я*Р*=я\
л, + л2+...+ л„, =1.
Для иллюстрации применения этих уравнений рассмотрим стратегию s = 2. Соответствующие уравнения имеют следующий вид.
0,3л, + 0,1л2 +0,057с3 =тс,, 0,6л, + 0,6л2 + 0,4л3 = л2, 0,1л, + 0,3л2 +0,55л3 = л3, л, + л2 + л3 = 1.
(Отметим, что одно из первых трех уравнений избыточно.) Решением системы будет
2 6 2 31 2 22 ~ 59 "2 ~59 * ~ 59