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

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

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

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

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

 

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

 

 

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

 

Вначале решим задачу без всякого динамического программирования. Сначала кажется, что она настолько проста, что решение получится, если действовать так: оптимизировать решение на каждом этапе и тогда получится общее оптимальное решение. Эта мысль действительно очень проста, но и настолько же неверна. В соответствии с ней «оптимальным» решением будет путь от 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%. Однако с ростом числа состояний и этапов экономия в вычислительной работе с применением динамического программирования становится ощутимой настолько, что только его применение позволяет получить решения. Более ощутимые преимущества метода показан на примере следующей задачи.

 

Планирование использования супертраулеров при автономном ведении промысла в отдаленных районах

 

Рассмотрим типичную для современного промысла задачу использования шести супертраулеров в автономном промысле в Юго-Западной Атлантике со сдачей продукции в портах прибрежных государств. Перспективными считаются четыре района промысла. Предварительные экономические расчеты, основанные на математическом ожидании улова, его породном составе, видах готовой продукции, рыночных и контрастных ценах, расстояниях до портов, где продукция реализуется, эксплуатационных расходах и прочем, сведены в таблицу. Она представляется лицу, уполномоченному принять окончательное решение: как распределить супертраулеры по районам промысла, чтобы прибыль от этой операции была максимальной.

Естественно, что вначале приходит решение послать все шесть супертраулеров в район № 1, что дает валютную прибыль 204 десятка тысяч. Это решение можно условно записать в таком виде (6, 0, 0, 0). Но после небольшого раздумья управляющий увидит, что решение (1, 1, 2, 2) лучше: оно дает прибыль 56+50+50+66=222 десятка тысяч. Попытка получить еще лучшее решение увенчалась успехом. Решение (1, 2, 1, 2)дает прибыль 234 десятка тыс. ед. Проверка еще одного решения (2, 1, 2, 1) показывает, что оно хуже предыдущего (90+50+40=230). Другие варианты решения также уступают решению (1, 2, 1, 2). Казалось бы, что это решение наилучшее: по сравнению с самым первым оно дает на 300 тысяч больше. Возможно поискать другое решение или просчитать все 256 вариантов.

 

Таблица ожидаемой прибыли

(в десятках тысяч единиц СКВ)

Число траулеров в районе №	Район промысла
	1	2	3	4
0	0	0	0	0
1	56	50	30	40
2	90	82	50	66
3	130	110	80	84
4	156	130	100	86
5	180	150	124	106
6	204	160	146	112

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

Этап	Распределение супертраулеров
I	по району № 1
II	по районам № 1 и 2
III	по районам № 1, 2,3
IV	по всем четырем районам

Общее число состояний на первом этапе будет равно семи: можно послать в этот район 0, 1, 2, 3, 4, 5 и 6 супертраулеров. Ясно, что оптимум для этих решений (управлений) определится первым столбцом ожидаемой прибыли. На втором этапе число состояний также будет равно семи, но эти состояния, генерализованы, т.е. обобщены. Действительно, посылка двух супертраулеров в район № 2 соответствует следующему распределению в обоих районах: (0, 2), (1, 2), (3, 2), (4, 2).

На третьем и четвертом этапах число состояний на каждом этапе также равно семи, но эти состояния еще более генерализованы: посылка четырех супертраулеров в район № 3 на третьем этапе охватывает следующие состояния в целом: (0, 0, 4), (1, 0, 4), (2, 0, 4), (0, 1, 4), (0, 2, 4), (1, 1, 4).

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

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

Этап I

Расчет прибыли от распределения супертраулеров в районе № 1

Число траулеров	Прибыль	Оптимум прибыли	Оптимальное распределение траулеров
0	0	0	(0)
1	56	56	(1)
2	90	90	(2)
3	130	130	(3)
4	156	156	(4)
5	180	180	(5)
0	204	204	(6)

Результаты расчетов на этапе I несколько банальны и приводятся лишь в методических целях.

Этап II

⇐ Предыдущая18192021222324252627Следующая ⇒

Поделиться: