Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Общая постановка задачи динамического программирования.

Дадим общую постановку задач динамического программирования и сформулируем принципы их решения.

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

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

Очевидно, выигрыш зависит от управления: W = W(U). Мы хотим найти такое управление (оптимальное) U = U*, при котором выигрыш максимален:

W(U*) = max {W(U)}

^u

Таким образом, поставлена общая задача оптимизации управления физической системой. Однако она поставлена еще не полностью. Обычно в таких задачах должны быть учтены некоторые условия, накладываемые на начальное состояние системы S_o и конечное состояние S_ω.

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

Например, если состояние системы характеризуется двумя параметрами P₁ и P₂ (например, скоростью и высотой), то процесс будет изображаться перемещением точки из S_оÎ в точку S_ωÎ по определенной траектории на фазовой плоскости P₁OP₂. Траектория эта и будет изображать управление (рис. 5.2).

Общая задача оптимизации управления в геометрических терминах может быть сформулирована так:

Найти такое оптимальное управление U*, под влиянием которого точка S фазового пространства переместится из начальной области в конечную область так, что при этом выигрыш W обратится в максимум.

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

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

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