 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Общая постановка задачи ДП
|
|
Рассматривается управляемый процесс,
(например, • экономический процесс распределения средств между предприятиями, • использования ресурсов в течение ряда лет, • замены оборудования, • пополнения запасов и т.п.).
В результате управления система (объект управления) S переводится из начального состояния Sо в состояние S’.
Предположим, что управление можно разбить на п шагов, т.е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность п пошаговых управлений.
Обозначим через Xk управление на k -м шаге (k =1,2,..., n).
Переменные Хk отвечают некоторым ограничениям (требованиям) и в этом смысле называются допустимыми (Х k может быть числом, точкой в n -мерном пространстве, качественным признаком).
Пусть Х(Х1, X2,..., Хn) — управление, переводящее систему S из состояния S0 в состояние S’.
Обозначим через Sk состояние системы после k -го шага управления.
Получаем последовательность состояний
 |
S0, S 1 ,..., Sk -1,..., Sn- 1 ,Sn=S, которую изобразим кружками (рис. 1).
Рис. 12.1
Показатель эффективности рассматриваемой управляемой операции — целевая функция — зависит от начального состояния и управления:
Z=F(S0,X) (1)
Примим несколько предположений.
1. Состояние Sk системы в конце k -го шага зависит только от предшествующего состояния Sk- 1 и управления на k -м шаге Xk (и не зависит от предшествующих состояний и управлений).
Это требование называется "отсутствием последействия".
Сформулированное положение записывается в виде уравнений
Sk = φk(Sk-1,Xk), k = 1. 2,..., n, (2)
которые называются уравнениями состояний.
2. Целевая функция (1) является аддитивной от показателя эффективности каждого шага].
Обозначим показатель эффективности k -го шага через
Zk=fk(Sk-1,Xk), k =1,2,..., n, (3)
тогда Zk= 
fk(Sk-1,Xk) (4)
Задача пошаговой оптимизации (задача ДП) формулируется так:
Определить такое допустимое управление X, переводящее систему S из состояния SQ в состояние S ’, при котором целевая функция (12.4) принимает наибольшее (наименьшее) значение.
Выделим особенности модели ДП:
| На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние Sk — от конечного числа параметров (смысл замечания станет ясным из рассмотренных ниже примеров). |
Принцип оптимальности Беллмана.
Каково бы ни было состояние S -системы в результате какого–либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с остальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Замена решения исходной многомерной задачи последовательностью задач меньшей размерности возможна при выполнении основных требований к задаче:
· Объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями;
· Целевая функция равна сумме целевых функций каждого шага;
· Задача по своей природе должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из допустимых управлений, приводящих к изменению состояния системы;
· Задача не должна зависеть от количества шагов и быть определенной на каждом из шагов;
· Состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров;
· Последующее состояние Sk, в котором оказывается система после выбора решения на k -ом шаге, зависит только от предшествующего состояния (исходного состояния к началу k -го шага) и решения (управления Xk) на данном шаге.
· Данное свойство является основным с точки зрения идеологии динамического программирования и называется отсутствием последствия
· Выбор управления на k -м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (процесс управления должен быть без обратной связи).
Если изобразить геометрически оптимальную траекторию в виде ломаной линии, то любая часть этой ломаной будет являться оптимальной траекторией относительно начала и конца.
Дата публикования: 2014-11-02; Прочитано: 742 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
