В основе метода динамического программиро вания лежит идея разбиения исходной задачи на последователь ный ряд более простых задач. Основной областью приложения динамического программирования являются многошаговые про цессы, т.е. процессы, протекающие во времени (дискретном или непрерывном). Главным рабочим инструментом динамического программиро вания является метод рекуррентных соотношений, в основе которо го лежит необходимое условие оптимальности, выражаемое обыч но в виде так называемого принципа оптимальности и уравне ния Беллмана (по имени американского математика Р. Беллмана). 151 Принцип оптимальности Беллмана утверждает, что оптималь ный процесс (т.е. оптимальное управление и соответствующая ему оптимальная траектория) для всего периода управления облада ет тем свойством, что любая его часть, рассматриваемая на про межутке времени, входящем в исходный промежуток, также пред ставляет собой оптимальный процесс для этого частичного промежутка времени. Иными словами, любая часть оптимально го процесса необходимо является оптимальным процессом. Основные особенности дискретной модели динамического программирования состоят в следующем: 1) задача оптимизации интерпретируется как многошаговый процесс управления; 2) общая целевая функция равна сумме целевых функций для каждого шага; 3) выбор управлений Xf^ на /с-м шаге определяется только со стоянием системы 5^ J на предыдущем шаге и не зависит от со стояния системы на более ранних этапах управления; 4) состояние 5^ на к-и шаге зависит только от предшествую щего состояния 5^ J и управления х^, принимаемого на данном шаге, т.е. ^к ~fk^^k-{^^k)^ где /^ - заданная векторная функция соответствующих переменных, /: = 1, 2, ...,/7,... Схематически модель динамического программирования ил люстрируется следующей схемой: SQ >S\ >5*2 > ... S^^_x —'-^^—^ S,j и т.д. Число этапов п, как правило, считается фиксированным, од нако в некоторых задачах п может быть неограниченным, что соответствует задаче с бесконечным горизонтом управления. Следует иметь в виду, что принцип Беллмана справедлив толь ко для задач, у которых целевые функции можно описать в виде аддитивных функций от траектории, т.е. для процессов с опреде ленной структурой зависимости управлений. Это означает, что критерий оптимальности (целевая функция) F имеет вид 152 ^ ^ ' " k=\ где числовая функция фд, оценивает качество управленческого решения на /с-м шаге. Оптимальное управление удовлетворяет следующему прин ципу оптимальности Беллмана: предположим, что, осуществляя управление, уже выбрана последовательность оптимальных уп равлений Л',, -х^, ... , л'^на первых/; шагах, которой соответствует последовательность состояний (т.е. траектория) S^, S2, ... , S . Требуется завершить процесс, т.е. выбрать л: р ... , х,Да значит, и S ^р ... , S^j). Тогда если завершающая часть процесса не будет максимизировать функцию ^р+\ - S ^к(^к-\^ч)^ (\) к=р+\ ^ то и весь процесс управления не будет оптимальным. В част ности, прир =77-1 получаем требование максимизации функции ^п ~ ^n^'^n-v ^})' зависящей от переменной х^^. На основе принципа оптимальности Беллмана строится сис тема рекуррентных соотношений (уравнения Беллмана): w,.+ i(^,z) = 0' (2) а)/Д5'^_,) = тах[ф^(5'д,_р л-) + а)^^,(/;^ (5'/^_р х))1 к = п, п - 1, ... , 1, которым должен удовлетворять оптимальный процесс. Максимум в правой части равенства (2) берется по всем уп равлениям X, допустимым на шаге /с. Тем самым при вычислении ^k^^k-i^ "^ каждом шаге приходится решать семейство задач мак симизации функции переменной х, зависящих от состояния 5^, j на предыдущем (к-1)-м шаге. При этом величина CO,(5Q) есть оп тимальное значение критерия оптимальности. Вычисление оптимального процесса на основе уравнений Белл мана (2) в каждом конкретном случае может оказаться непрос той задачей, требующей навыка и изобретательности. 153 Модели динамического программирования применяются при распределении дефицитных капитальных вложений между пред приятиями, при составлении календарных планов текущего и ка питального ремонта оборудования и его замены и т.п.
Ви переглядаєте статтю (реферат): «ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
