Автор работы: Пользователь скрыл имя, 16 Апреля 2012 в 08:25, реферат
За последние десятки лет, в прикладной математике большое внимание уделяется ново-му классу задач оптимизации, заключающихся в нахождении в заданной области, опреде-ляемой линейными и нелинейными ограничениями (равенствами и неравенствами), точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, применяемые в самых разнообразных областях человеческой деятельности, в которых необходим выбор одного из возможных образов действий, прежде всего в экономических исследованиях, при решении проблем управления и планирования производственных процессов, в проектирова-нии и перспективном планировании и т. д.
Введение 3
Принцип оптимальности Беллмана 4
Основной принцип динамического программирования 5
Примеры задач динамического программирования 7
Список используемых источников: 10
При решении поставленной задачи методом динамического программирования в качестве функции состояния управляемой системы Λk(ξ) логично взять минимальный объем затрат, возникающих за первые k периодов при условии, что в k-й период имеется запас ξ . Тогда можно записать основное рекуррентное соотношение
поскольку
Система рекуррентных соотношений (5.27)-(5.28) позволяет найти последовательность функций состояния Λ1(ξ), Λ2(ξ), …, Λn(ξ) и условных оптимальных управлений 1(ξ), 2(ξ), …, n(ξ). На n-м шаге с помощью начального условия (5.26) можно определить х*n = n (yn+1). Остальные значения оптимальных управлений x*k определяются по формуле:
Особый интерес представляет частный случай задачи (5.24)-(5.25), при котором предполагается, что функции затрат на пополнение запаса сk(хk) являются вогнутыми по хk , а функции затрат на хранение sk(ξk) являются линейными относительно объема хранимого запаса, т. е. sk(ξk) = skξk . Параллельно заметим, что обе предпосылки являются достаточно реалистичными.
Обозначим функцию затрат в течение k-ro периода через
или, что то же самое,
В силу сделанных предположений все функции затрат fk (xk , yk+1) являются вогнутыми (как суммы вогнутой и линейной функций). Данное свойство значительно упрощает процесс решения, так как для поиска минимума вогнутых функций fk (xk , yk+1) достаточно рассмотреть только две крайние точки множества, на котором отыскивается минимум. С учетом введенного обозначения задачу (5.24)-(5.25) можно записать в виде:
при условиях
Рассмотрим процедуру решения (5.32)-(5.33). Так как ищется минимум суммы вогнутых функцийfk(xk , yk+1), то решение будет достигаться на одной из крайних точек множества, определяемого условиями (5.33). Общее число переменных xk и yk в системе (5.33) равно 2п. Однако, учитывая то, что в ней только п уравнений, в оптимальном плане будет не более п ненулевых компонент, причем для каждого периода k значения xk и yk не могут равняться нулю одновременно (в силу необходимости удовлетворения спроса либо за счет заказа, либо за счет запаса). Формально это утверждение можно представить в виде условия дополняющей нежесткости:
где
С точки зрения содержательной интерпретации условия (5.34)-(5.35) означают, что приоптимальном управлении заказ поставщику на новую партию не должен поступать, если в начале периода имеется ненулевой запас, или размер заказа должен равняться величине спроса за целое число периодов. Отсюда следует, что запас на конец последнего периода должен равняться нулю: у*n+1=0. Последнее позволяет решать задачу в прямом направлении, применяя рекуррентное соотношение
где ξ = уk+1= хk + уk - dk .
Учитывая (5.34)-(5.35) и вогнутость fk (xk, ξ), заключаем, что минимум (5.36) достигается в одной из крайних точек xk =0 или xk = ξ + dk поэтому
тогда
для предыдущего периода
на oснове чего в общем виде получаем модифицированную форму для рекуррентного соотношения
При дальнейших конкретизирующих предположениях о виде функций fk (xk , уk+1) можно получить еще более компактные формы для рекуррентных соотношений. Однако эти вопросы носят достаточно частный характер, и мы их рассматривать не будем. Отметим лишь, что приведенные в данном пункте преобразования неплохо иллюстрируют общие подходы, применяемые в динамическом программировании, а также те свойства задач, которые открывают возможности, для эффективного и плодотворного использования соответствующих методов.