Полная версия

Главная arrow Математика, химия, физика arrow Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Принцип оптимальности и уравнение Р. Беллмана

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

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

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

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

Схема поэтапного поиска оптимального пути

Рис. 3.3. Схема поэтапного поиска оптимального пути

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

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

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

В отличие от рассмотренной нами простой задачи поиска оптимального пути на двумерной сетке в сложных задачах каждое промежуточное состояние может определяться не двумя, а многими координатами, то есть каждому состоянию может соответствовать вектор многомерного пространства. От того как формально определено понятие «состояние», зависит не только формализация понятия «переход в другое состояние», но и, как мы увидим в дальнейшем, сама возможность применения метода Р. Веллмана.

Итак, пусть в каждом из состояний, в котором может находиться система в начале очередного этапа, известны все возможные воздействия на неё. И для каждого такого воздействия известны его последствия, то есть и состояние, в которое перейдёт система, и затраты на этот переход. Воздействие на i-ом шаге обозначим через Xi. Эти воздействия называются шаговыми управлениями. Если число этапов обозначить через п, то задача состоит в поиске последовательности шаговых управлений, то есть вектора x(xi,X2,...,xn). Поскольку начальное состояние системы задано, то последовательность шаговых управлений однозначно определяет последовательность переходов системы из одного состояния в другое, то есть траекторию движения (в широком смысле слова). В сложных задачах xi,X2,...,xn не обязательно числа. Это могут быть векторы или функции.

Обозначим затраты на i-ом этапе через z. Требуется найти такую последовательность шаговых управлений Xi, при которой суммарные затраты Z минимальны.

Ту последовательность шаговых управлений, при которой достигается минимум затрат Z, будем называть оптимальным управлением и обозначать через

[6]. Соответствующие ей минимальные по всем возможным последовательностям х затраты

Z* min Z(x).

Затраты на i-ом шаге (этапе) зависят не только от Xi, но и от состояния S, в котором была система до воздействия Xi, то есть фактически от всех предшествующих шаговых управлений. Состояние S', в которое перейдёт система, зависит только от S и Xi, если нет влияния предыстории. Формально это можно записать в виде S' =f(S, Xi), где f заданная функция, так как известны последствия воздействия Xi на систему, находящуюся в состоянии S. В соответствии с принципом оптимальности Xi надо выбирать так, чтобы суммарные затраты на все последующие этапы были минимальны. Эти суммарные затраты зависят от состояния S и складываются из затрат на i-ом шаге Zi(S, Xi) и на всех последующих шагах. Суммарные затраты на все шаги (этапы), начиная с i-ro и до конца, обозначим Zi. Тогда Zi=Zi + Zi+i и оптимальные управления надо на каждом шаге выбирать так, чтобы

Это и есть основное рекуррентное уравнение динамического программирования, выражающее затраты на все оставшиеся шаги из любого состояния S через затраты на данном шаге Zi и на всех последующих шагах Zi+i(S'). Только на последнем шаге из любого состояния S можно легко найти оптимальный переход в конечное состояние. Если конечное состояние единственное, то и для каждого из состояний S на последнем шаге этот переход (то есть шаговое управление хп) единственное. В общем случае для последнего шага уравнение (3.1) приобретает вид

так как п+1 шага просто нет. Это означает, что для каждого из возможных состояний на последнем шаге мы определяем и запоминаем затраты на этот последний шаг. Если конечных состояний несколько (рис. 3.6), то на последнем шаге придётся сравнивать варианты переходов из каждого состояния 1,2,...,к в конечные состояния Bi,B2,...,Bm, то есть шаговые управления хп, обеспечивающие переходы 1 Bi, 1В2,___, 1 Bm, и запоминать наилучшее управление и соответствующие ему минимальные затраты на последний шаг для состояния 1, затем все переходы из состояния 2 и т.д. В результате для каждого состояния S на последнем шаге станут известны затраты Zn(S) и управление хп, обеспечивающее оптимальный переход в конечное состояние.

Последний шаг при нескольких конечных состояниях

Рис. 3.6 Последний шаг при нескольких конечных состояниях

Запишем теперь уравнение для предпоследнего шага i = n -1.

Здесь затраты уже известны, а найти надо xn-i для каждого

состояния S на п-1 шаге. Это задача полностью аналогична той, что мы решали для последнего шага. Последовательно, рассматривая шаги от п-1 до 2, определим для каждого из состояний наименьшие затраты на все последующие этапы и управления (переходы на следующий этап). На первом шаге теперь известны последствия любого из возможных переходов (управлений), что и даёт возможность сделать окончательный выбор управления xi, то есть перехода из точки А.

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

Отметим, что поиск оптимального перехода из заданного состояния на i-ом шаге (в том числе и на последнем) может быть сложнее, чем выборка чисел из заданного массива, суммирование и сравнение. В сложных задачах использование принципа оптимальности Р. Веллмана может приводить к разностным, дифференциальным и др. уравнениям.

Часто принцип оптимальности Р.Веллмана формулируют следующим образом: «Оптимальная траектория состоит из оптимальных частей.» Эта формулировка относится не только к траекторным задачам, но ко всем задачам, решаемым с помощью метода динамического программирования, если под траекторией понимать последовательность переходов из одного состояния в другое в результате решений (управлений), принимаемых на последовательных этапах. Если под частью траектории понимать любую последовательность состояний, в которой начальное и конечное состояния фиксированы (аналог кривой, соединяющей две фиксированные точки), то для оптимальной траектории в задачах «без предыстории» это безусловно так. Но это не означает, что для двух состояний ( на этапах р и q рис. 3.7 состояния С и D), которые не содержатся в оптимальной последовательности, то есть не принадлежат оптимальной траектории, не может быть последовательности переходов с меньшими затратами, чем для оптимальной последовательности на тех же промежуточных этапах с р-го по q -ый. На рис. 3.7 для части С* D* оптимальной траектории (показана стрелками) на этапах с р-го по q-ый затраты (4+1+2) больше, чем для части неоптимальной траектории CD на тех же этапах (3+1+1), но в целом суммарные затраты на все этапы для оптимальной траектории меньше (10 против 15).

Смысл метода в том, что из начального состояния в любое промежуточное состояние (точку) нужно идти по оптимальному пути (остальные отбраковываются) и до конечной точки тоже нужно идти по оптимальному пути.

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

Сравнение траекторий

Рис. 3.7. Сравнение траекторий

Еще раз подчеркнём, что метод оптимизации Р. Веллмана и соответственно уравнение 3.1 не универсальны и рассмотрим более подробно условия их применимости.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>