2.6. Примеры

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

1. Задача водителя такси (см. [63]). Данные для этой задачи приведены в табл. 1.2. Оптимальная стратегия находится за три итерации. Вычисления сведены в табл. 2.2. При решении задачи линейного программирования с той же самой начальной стратегией (начальным допустимым базисным решением), что и в итерационном алгоритме, оптимальное решение

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

находится за шесть шагов, если предположить, что для нахождения начального базисного допустимого решения требуется три шага.

Рассмотрим теперь новый алгоритм, являющийся комбинацией указанных выше двух алгоритмов. Напомним об особенностях этих алгоритмов. Как указывалось в разделе 1.4, итерационный алгоритм обладает с вычислительной точки зрения одним недостатком. Именно, даже в том случае, когда существует всего лишь одна пара удовлетворяющая (2.69), необходимо решать систему из линейных уравнений. Однако и стандартный подход линейного программирования также имеет недостаток, который особенно сказывается при рассмотрении задач большой размерности, так как на каждом шаге приходится использовать симплексный критерий. Но с помощью стандартной техники в допустимом базисном решении на каждом шаге может меняться лишь одна переменная. Из теорем 2.2 и 2.3 следует, что улучшенная стратегия увеличивает средний доход Другими словами, выполнение ведущих операций одновременно над многими переменными приводит к улучшению стратегии. Таким образом, можно сформулировать новый алгоритм, используя подход линейного программирования с той лишь разницей, что

симплексный критерий применяется как в итерационном алгоритме. Новый алгоритм состоит из следующих процедур.

1. Выбрать начальную стратегию и найти начальное допустимое базисное решение с помощью теоремы 2.3.

2. Для всех найти

где полагается

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

Этот новый алгоритм может с соответствующими изменениями применяться и к марковским моделям принятия решений с переоценкой, рассмотренным в гл. 1. Здесь этот вопрос не рассматривается.

Рис. 3. Сравнение трех алгоритмов для задачи водителя такси. (Итерационный алгоритм — новый алгоритм алгоритм линейного программирования ).

На рис. 3 показаны результаты работы трех алгоритмов в предположении, что одна итерация соответствует трем шагам линейного программирования. Как видно из рис. 3, новый алгоритм наиболее эффективен среди этих трех.

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

2. Задача о замене автомобиля (см. [63]). Рассмотрим задачу о замене автомобиля на временном отрезке в десять лет. Условимся пересматривать текущую ситуацию каждые три месяца и принимать при этом решение о том, продавать или нет автомобиль. Состоянием системы является возраст автомобиля, измеренный в трехмесячных периодах; величина пробегает значения от 1 до 40. Чтобы сохранить число состояний конечным, будем приписывать возраст 40 машине, проработавшей более 40 периодов (считается, что такая машина существенно изношена). В каждом состоянии могут приниматься следующие решения. Первое состоит в том, чтобы не менять данную машину в течение следующих трех месяцев. Другие -предполагают покупку автомобиля возраста где не превышает 39. Следовательно, имеются 40 состояний и в каждом состоянии возможно 41 решение. Таким образом, имеются 4140 возможных стационарных стратегий.

Заданы следующие величины: С — покупная цена машины возраста выручка от продажи машины возраста средний расход, связанный с эксплуатацией машины возраста вероятность того, что машина возраста достигнет возраста без капитального ремонта.

Такой выбор вероятностей обусловлен необходимостью иметь конечное число состояний. В случае безнадежной поломки машина любого возраста сразу же переводится в состояние 40. Естественно,

Величины и (в прежних обозначениях) могут быть записаны в виде

Конкретные данные, использованные в задаче, сведены в табл. 2.3 и изображены графически на рис. 4.

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

Оптимальная стратегия итерационным алгоритмом была найдена за семь итераций.

Рис. 4. Данные для задачи о замене автомобиля.

Рис. 5. Сравнение работы трех алгоритмов при решении задачи о замене автомобиля.

С помощью алгоритма линейного программирования оптимальная стратегия была найдена за 84 шага в предположении, что вычисления последней фазы I (получение допустимого базисного решения) занимают шагов. С помощью нового алгоритма оптимальное решение находится за 174 шага. При этом была выбрана та же начальная стратегия. Результаты работы этих трех алгоритмов показаны на рис. 5.

Новый алгоритм более эффективен, чем итерационный, поскольку требует для своего применения симплексный критерий того же объема, но на ведущих операциях экономит 174/280 времени вычислений (около 62%). Вопрос о сравнении с методом линейного программирования, в общем, открыт.