7.3.Расчет оптимального перехода через океан в район промысла

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

На рис. 5 показаны исходная информация, необходимая для расчетов, и само решение.

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

Центральная линия кружков представляет собой кратчайший по расстоянию путь судна от пункта отхода (верхний кружок) до пункта прихода (нижний кружок). Кружки справа и слева от центральной линии представляют собой некоторые точки в стороне от кратчайшего по расстоянию пути судна. Курсы для перехода из кружка в кружок известны, но на чертеже не нанесены, чтобы не затемнять его лишними подробностями. Пути, кратчайшие по расстоянию и по времени, не совпадают между собой: часто обход циклона с удлинением пути на 200-300 миль занимает меньше времени, чем попытка пробиться через него напрямик, не говоря уже о возможных повреждениях судна во время шторма.

В этой задаче в соответствии с пунктами 1 и 2 общего порядка решения задачи S – управляемый объект (судно), а за этапы решения задачи естественно принять перевод судна последовательно с одной линии кружков на другую (всего таких этапов в задаче четыре); число состояний на каждом этапе, кроме конечного и нулевого (начальное место судна), по три. Выбор управления на каждом этапе эквивалентен выбору курсов для перемещения из кружка в кружок. Оценка каждого из управлений на этапе дается временем перехода, указанным на рис. 5 (цифры на линиях). Сам рис. 5 есть не что иное, как графическое представление задачи со всей необходимой информацией для решения – граф задачи.

Рис. 5. Геометрическое представление задачи динамического программирования

Вначале решим задачу без всякого динамического программирования. Сначала кажется, что она настолько проста, что решение получится, если действовать так: оптимизировать решение на каждом этапе и тогда получится общее оптимальное решение. Эта мысль действительно очень проста, но и настолько же неверна. В соответствии с ней «оптимальным» решением будет путь от S₀ (пункт отхода) до кружка с цифрой 38, далее до кружка с цифрой 28, затем до кружка с цифрой 11 и, наконец, до кружка с цифрой 0 (пункт прихода). Этот путь займет 9+12+17+11=49 ед. времени.

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

Перед четвертым заключительным этапом судно могло быть в одном из трех кружков (состояниях) нижнего ряда на рис. 5 . В каком именно - неизвестно, но если в левом, то в конечное состояние S₄ оно может быть переведено единственным курсом (управлением). Оценка этого управления – 11 ед. времени. Эту цифру запишем в кружке, отметив ромбиком соответствующее ему управление. Рассуждая так же в отношении среднего и правого кружков, поставим там цифры 9 и 10 и нарисуем ромбики.

Переходим к третьему этапу. Перед третьим этапом судно могло быть в одном из трех кружков (состояний) среднего ряда. Если судно было в левом кружке, то его можно переместить в левый нижний кружок с затратой времени 11+13=24 ед., в средний нижний – с затратой времени 9+14=23 ед., в правый нижний – с затратой времени 10+18=28 ед.

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

Повторив аналогичную процедуру для второго этапа, получим единственный этап. Перед ним судно занимало вполне определенное положение S₀ (верхний кружок). Управление, которое мы получили на этом этапе, будет уже не условным, а безусловным. Это управление соответствует курсу в крайний правый кружок первого ряда. Но раз судно там окажется, то условное оптимальное управление, заготовленное для этого кружка ранее, превращается в безусловное. Далее надо следовать до кружка с цифрой 23, затем до кружка с цифрой 9 и, наконец до кружка с цифрой 0. Этот путь, отмеченный на рис. 5 пунктиром, является оптимальным, а цифра 44, стоящая в самом верхнем кружке, является его оценкой. Ее легко проверить по исходным для задачи данным.

Этот пример иллюстрирует лишь суть метода динамического программирования. Задача может быть решена простым перебором всех возможных путей судна, которых здесь немного, - всего 27. Экономия в вычислениях, которую мы получили, применяя динамическое программирование для этой задачи, действительно невелика – всего лишь около 10%. Однако с ростом числа состояний и этапов экономия в вычислительной работе с применением динамического программирования становится ощутимой настолько, что только его применение позволяет получить решения. Более ощутимые преимущества метода показан на примере следующей задачи.