Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

Таким образом, уже при не слишком больших р* перебор с по­ мощью соотношений (5) по сравнению с полным перебором дает существенную экономию памяти ЭВМ и машинного времени. Такая

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

Сначала берут небольшое число шкал с небольшим количе­ ством точек на них и по описанной выше схеме поиска находят кратчайший путь 1\, соединяющий крайние шкалы Н0 и HN. Затем уменьшают шаг сетки на каждой шкале, путь U окружают некото­ рой «трубкой» из путей, проходящих вблизи 1\ по точкам новой сетки. Для построения трубки вокруг 1\ на каждой шкале обычно берут небольшие окрестности точки, через которую прохо­ дит 1\, и рассматривают пути, проходящие через выбранные точки. С помощью описанной выше схемы перебора находят кратчайший путь в полученной трубке; все пути вне этой трубки в переборе пока не участвуют. Таким образом получают новый улучшенный путь k, длина которого не превышает длины 1\. Далее, сохраняя прежние шкалы и точки на них, окружают путь 12 новой трубкой и находят следующее приближение /3 и т. д., продолжая процесс

§ 2] Схема Н. Н. Моисеева 197

до тех пор, пока трубка не перестанет «блуждать» и впервые по­ лучится равенство l s — l s+ и После этого измельчают сетку на каж ­ дой шкале, окружают путь ls новой трубкой и продолжают поиск кратчайшего пути описанным приемом блуждающих трубок. Про­ цесс измельчения сетки на шкалах и поиска кратчайшего пути указанным способом повторяют, пока два кратчайших пути, полу­ ченные после двух последовательных измельчений сетки, не совпа­ дут с удовлетворительной точностью. Затем увеличивают число шкал, т. е. сгущают сетку по времени, и повторяют процесс поиска методом блуждающих трубок с постепенным измельчением сетки на шкалах состояний до удовлетворительного совпадения двух по­ следовательных приближений. Попеременно измельчая сетку на шкалах состояния и сетку по времени, поиск с помощью блуждаю­ щих трубок продолжают до получения приближенного решения исходной задачи с достаточной точностью. Изменение шагов сеток на шкалах состояния и по времени должно быть согласованным; например, в случае равномерных сеток эти шаги должны удовлет­ ворять соотношению |Ал:| = о (А^) [169].

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

элементарная операция представляет собой экстремальную задачу той же трудности, что и исходная задача. Однако малость отрезка **^ *< A + i позволяет здесь сделать ряд упрощающих предположе­ ний. Прежде всего, если, шаг сетки по времени достаточно мал, то элементарную операцию строят исходя из условий (1), (2), (4), полагая, что дуги траекторий, соединяющих точки соседних шкал, или не нарушают фазовых ограничений (3), или этим нарушением

тригонометрические многочлены с коэффициентами С\, ..., ст, или кусочно-постоянные функции со значениями сь ст и т. п. Зна­ чения этих параметров затем можно определить из системы п уравнений с т неизвестными

. . .

используя для этого различные методы [19]. Если т > п , то пара­ метры С], ..., ст отсюда будут определяться, вообще говоря, неод­ нозначно, и свободные параметры можно использовать для мини­ мизации функционала (1). Для упрощения системы (8) дифферен­ циальное уравнение (2) часто заменяют более простыми уравне­ ниями

или другими более точными разностными уравнениями [171]; здесь возможно использование линеаризованной системы

x{t) = f (х, и (/), t) + (fx {х, и (<), t), х (/) — х).

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

[169, 171].

§3. ДИФФЕРЕНЦИАЛЬНОЕ УРАВНЕНИЕ Р. ВЕЛЛМАНА

Вэтом параграфе будет введена функция Веллмана для .ис­ ходной задачи оптимального управления и получено дифференци­ альное уравнение Веллмана, являющееся предельным для уравне­ ния (1.13) при неограниченном измельчении сетки по времени. Ограничимся рассмотрением частного случая задачи (1.1— 4 ): ми­ нимизировать функционал