|
Читайте также: |
Сформулируем общий принцип, лежащий в основе решения всех задач динамического программирования («принцип оптимальности»):
«Каково бы ни было состояние системы S перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным».
Динамическое программирование – это поэтапное планирование многошагового процесса, при котором на каждом этапе оптимизируется только один шаг. Управление на каждом шаге должно выбираться с учетом всех его последствий в будущем. При постановке задач динамического программирования следует руководствоваться следующими принципами:
1. Выбрать параметры (фазовые координаты), характеризующие состояние управляемой системы перед каждым шагом.
2. Расчленить операцию на этапы (шаги).
3. Выяснить набор шаговых управлений xi для каждого шага и налагаемые на них ограничения.
4. Определить какой выигрыш приносит на i-ом шаге управление xi, если перед этим система была в состоянии S, т.е. записать «функцию выигрыша»:
5. Определить, как изменяется состояние S системы S под влиянием управление xi на i-ом шаге: оно переходит в новое состояние
6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш Wi(S)
(начиная с i-го шага и до конца) через уже известную функцию Wi+1(S):
Этому выигрышу соответствует условное оптимальное управление на i-шаге xi(S) (причем в уже известную функцию Wi+1(S) надо вместо S подставить измененное состояние [pic])
7. Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыша по формуле [pic]
8. Произвести условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле (1.2), полагая в ней i=(m-1),(m-2),…, и для каждого из шагов указать условное оптимальное управление xi(S), при котором максимум достигается.
Заметим, что если состояние системы в начальный момент известно (а это обычно бывает так), то на первом шаге варьировать состояние системы не нужно - прямо находим оптимальный выигрыш для данного начального состояния. Это и есть оптимальный выигрыш за всю операцию
9. Произвести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге [pic]; изменить состояние системы по формуле (1.1); для вновь найденного состояния найти оптимальное управление на втором шаге х2* и т.д. до конца. Данные этапы рассматривались для аддитивных задач, в которых выигрыш за всю операцию равен сумме выигрышей на отдельных шагах. Метод динамического программирования применим также и к задачам с так называемым «мультипликативным» критерием, имеющим вид произведения:
(если только выигрыши wi положительны). Эти задачи решаются точно так же, как задачи с аддитивным критерием, с той единственной разницей, что в основном уравнении (1.2) вместо знака «плюс» ставится знак «умножения»:
Дата добавления: 2015-09-10; просмотров: 68 | Поможем написать вашу работу | Нарушение авторских прав |