Исследование операций. Линейное, динамическое программирование




Исследование операций - часть 77


Прежде всего произведем условную оптимизацию последнего, 12-го шага. Рассмотрим отдельно правый верхний угол нашей прямоугольной сетки (рис. 13.3). Где мы можем находиться после 11-го шага? Только

        С1            11                       10         В

                                         13                14

                                 С2               14

                                                              8

                                                                     С3

там, откуда за один (последний) шаг можно попасть в В,

т. е. в одной из точек В1

или В2. Если мы находимся в точке В1,

у нас нет выбора (управление вынужденное): надо идти на восток, и это обойдется нам в 10 единиц. Запишем это число 10 в кружке у точки В1, а оптимальное управление покажем короткой стрелкой, исходящей из В1

и направленной на восток. Для точки В2

управление тоже вынужденное (север), расход до конца равен 14, мы его запишем в кружке у точки В2.

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

Теперь  давайте оптимизировать предпоследний (11-й) шаг. После предпредпоследнего (10-го) шага мы могли оказаться в одной из точек С1, С2, С3 (рис. 13.4). Найдем для каждой из них условное оптимальное управление и условный оптимальный выигрыш. Для точки С1 управление вынужденное: идти на восток;

обойдется это нам до конца в 21 единицу (11 на данном шаге, плюс 10, записанных в кружке при В1). Число 21 записываем в кружке при точке С1. Для точки С2 управление уже не вынужденное: мы можем идти как на восток, так и на север. В первом случае мы затратим на данном шаге 14 единиц и от В2 до конца — еще 14, всего 28 единиц. Если пойдем на север, затратим 13 + 10, всего 23 единицы. Значит, условное оптимальное управление в точке С2

— идти на север (отмечаем это стрелкой, а число 23 записываем в кружке у С2), Для точки С3 управление снова вынужденное («с»), обойдется это до конца в 22 единицы (ставим стрелку на север, число 22 записываем в кружке при С3).




Содержание  Назад  Вперед