1.6. Примеры

В этом разделе приводятся два численных примера и их решения с помощью итерационного алгоритма нахождения стратегий и алгоритма линейного программирования.

1. Описание примера дано во введении. Пусть где Тогда

где соответствует политике ускоренного ремонта, обычного ремонта. Решим задачу в предположении, что коэффициент переоценки

Сначала применим итерационный алгоритм. Выберем в качестве начальной политики процедуры определения весов имеем

Используя эти значения и процедуру улучшения решения, получим

откуда в качестве улучшенной получаем политику Применяя вновь процедуру определения весов, найдем

которые задают -оптимальную политику для

Теперь воспользуемся алгоритмом линейного программирования. При начальном распределении

получаем следующую задачу линейного программирования:

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

для которой оптимальное решение имеет вид

а целевая функция равна при этом 910/73. Значение целевой функции совпадает с

2. Задача водителя такси (см. [63]). Рассмотрим задачу водителя такси, в район обслуживания которого включены три города Если водитель находится в городе то у него есть три возможности: 1) курсировать в надежде поймать пассажира; 2) поехать на ближайшую стоянку такси и ждать в очереди; 3) ждать вызова по радио.

Если водитель находится в городе С, то у него есть такие же три возможности, но в городе В последняя из них отсутствует, поскольку в этом городе нет радиообслуживания автомобилей. Для данного города и данной возможности задаются вероятности того, что следующий рейс будет совершен в каждый из городов и задан доход в денежных единицах, соответствующий каждому рейсу. Этот доход представляет собой заработок от рейса за вычетом всех произведенных расходов. Например, в случае альтернатив 1 и 2 стоимость курсирования или проезда до ближайшей стоянки должна быть учтена при вычислении доходов. Вероятности переходов и доходы зависят от действия водителя, поскольку различные действия приводят к различным возможностям найти пассажира.

Отождествим города с состояниями 1, 2 и 3 соответственно. Условия задачи сведем в табл. 1.2.

Таблица 1.2 (см. скан) Данные задачи водителя такси

Положим Пусть начальная политика имеет вид

полученный из условия максимизации при каждом

Вычисления, сделанные с помощью итерационного алгоритма, сведены в табл. 1.3.

Таблица 1.3 (см. скан) Решение задачи водителя такси итерационным алгоритмом,

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