|
|
Динамическое программированиеДинамическое программирование, раздел математики, посвящённый теории и методам решения многошаговых задач оптимального управления. В Д. п. для управляемых процессов среди всех возможных управлений ищется то, которое доставляет наименьшее или наибольшее значение целевой функции — некоторой числовой характеристике процесса. Под многошаговостью понимают либо многоступенчатую структуру процесса, либо разбиение управления на ряд последовательных этапов (шагов), соответствующих, как правило, различным моментам времени. Т. о., в названии "Д. п." под "программированием" понимают "принятие решений", "планирование", а слово "динамическое" указывает на существенную роль времени и порядка выполнения операции в рассматриваемых процессах и методах. Методы Д. п. являются составной частью методов, используемых в исследовании операций, и применяются как в задачах оптимального планирования, так и при решении различных технических проблем (например, в задачах определения оптимальных размеров ступеней многоступенчатых ракет, в задачах оптимального проектирования прокладки дорог). Методы Д. п. находят применение не только в дискретных, но и в непрерывных управляемых процессах, например в таких процессах, когда решения надо принимать в каждый момент некоторого интервала времени. Д. п. дало новый подход к задачам вариационного исчисления. Хотя метод Д. п. существенно упрощает исходные задачи, однако непосредственное его применение, как правило, сопряжено с громоздкими вычислениями. Для преодоления этих трудностей разрабатываются приближённые методы Д. п. Динамическое программирование обычно придерживается двух подходов к решению задач: · нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач. · восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.
Области применения моделей динамического программирования см. вопрос 9 Задача о дилижансах см. вопрос 10. Задача управления запасами Постановка задачи Пусть месячная потребность предприятия в каком-либо материале (песок, щебень, цемент,...) составляет Q единиц (м^ т,...). Расход его во времени происходит равномерно. Необходимо определить, какова должна быть величина поставляемой партии материалов, чтобы суммарные затраты на создание и хранение запаса были минимальны. Можно выделить четыре основные причины, приводящие к необходимости образования запасов: • необходимость гарантирования бесперебойности питания производственного процесса с целью обеспечения его непрерывности; • периодичность производства отдельных видов ресурсов у поставщиков: • особенности доставки ресурсов от поставщика до потребителя (несо ответствие грузоподъемности транспортных средств и размеров по требления); • несовпадение ритма производства и поставок производственных ре сурсов с ритмом их потребления. Любая модель управления запасами, в конечном счете, должна дать ответ на два вопроса: 1. Какое количество продукции заказывать? 2. Когда заказывать? Ответ на первый вопрос выражается через размер заказа, определяющего оптимальное количество ресурсов, которое необходимо поставлять каждый раз, когда происходит размещение заказа. В зависимости от рассматриваемой ситуации размер заказа может меняться во времени. Ответ на второй вопрос зависит от типа системы управления запасами. Если система предусматривает периодический контроль состояния запаса через равные промежутки времени (например, еженедельно или ежемесячно), момент поступления нового заказа обычно совпадает с началом каждого интервала времени. Если же в системе предусмотрен непрерывный контроль состояние запаса, точка заказа обычно определяется уровнем запаса, при котором необходимо размещать новый заказ. Таким образом, решение обобщённой задачи управления запасами определяется следующим образом; 1. В случае периодического контроля состояния запаса следует обеспечивать поставку нового количества ресурсов в объеме размера заказа через равные интервалы времени. 2. В случае непрерывного контроля состояния запаса необходимо размещать новый заказ в размере объема запаса, когда его уровень достигает точки заказа. Размер и точка заказа обычно определяются из условий минимизации суммарных затрат системы управления запасами, которые можно выразить в виде функции этих двух переменных. Суммарные затраты системы управления запасами выражаются в виде функции их основных компонент
Рассмотрим достаточно типичную задачу, возникающую в процессе планирования деятельности системы снабжения, — так называемую динамическую задачу управления запасами. Пусть имеется некоторая система снабжения (склад, оптовая база и т. п.), планирующая свою работу на п периодов. Ее деятельность сводится к обеспечению спроса конечных потребителей на некоторый продукт, для чего она осуществляет заказы производителю данного продукта. Спрос клиентов (конечных потребителей) в данной модели рассматривается как некоторая интегрированная величина, принимающая заданные значения для каждого из периодов, и он должен всегда удовлетворяться (т. е. не допускаются задолженности и отказы). Также предполагается, что заказ, посылаемый производителю, удовлетворяется им полностью, и временем между заказом и его выполнением можно пренебречь (т. е. рассматривается система с мгновенным выполнением заказа). Введем обозначения: yk — остаток запаса после (k-1)-го периода; dk — заранее известный суммарный спрос в k-м периоде; хk — заказ (поставка от производителя) в k-м периоде; сk (хk) —затраты на выполнение заказа объема xk в k-м периоде; sk (ξk) — затраты на хранение запаса объема ξk в k-м периоде. После получения поставки и удовлетворения спроса объем товара, подлежащего хранению в период k, составит ξk = yk + хk - dk. Учитывая смысл параметра yk, можно записать соотношение:
Расходы на получение и хранение товара в период k описываются функцией
Планом задачи можно считать вектор х = (х1, х2,..., хn), компонентами которого являются последовательные заказы в течение рассматриваемого промежутка времени. Соотношение между запасами (5.24) в сочетании с некоторым начальным условием связывает состояния системы с выбранным планом и позволяет выразить суммарные расходы за все п периодов функционирования управляемой системы снабжения в форме аддитивной целевой функции:
Естественной в рамках сформулированной модели представляется задача нахождения последовательности оптимальных управлений (заказов) x*k и связанных с ними оптимальных состояний (запасов) ξ*k, которые обращают в минимум (5.25). В качестве начального условияиспользуем требование о сохранении после завершения управления заданного количества товара yn+1, а именно
При решении поставленной задачи методом динамического программирования в качестве функции состояния управляемой системы Λk(ξ) логично взять минимальный объем затрат, возникающих за первые k периодов при условии, что в k-й период имеется запас ξ. Тогда можно записать основное рекуррентное соотношение
поскольку
Система рекуррентных соотношений (5.27)-(5.28) позволяет найти последовательность функций состояния Λ1(ξ), Λ2(ξ), …, Λn(ξ) и условных оптимальных управлений
Особый интерес представляет частный случай задачи (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) можно получить еще более компактные формы для рекуррентных соотношений. Однако эти вопросы носят достаточно частный характер, и мы их рассматривать не будем. Отметим лишь, что приведенные в данном пункте преобразования неплохо иллюстрируют общие подходы, применяемые в динамическом программировании, а также те свойства задач, которые открывают возможности, для эффективного и плодотворного использования соответствующих методов. 101. Математическое описание задач динамического программирования Особенности математической модели динамического программирования заключаются в следующем: задача оптимизации формулируется как конечный многошаговый процесс управления; целевая функция является аддитивной и равна сумме целевых функций каждого шага
выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи); состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния:
на каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа переменных; оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений, число которых и определяет количество шагов задачи. X*=(X*1, X*2, …, X*k, …, X*n), Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как Fn(S)=max{Wn(S,Xn)}, где максимум ищется по всем возможным значениям Xn. Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге: Fk(S)=max{Wk(S,Xk)+Fk+1(S"(S,Xk))}. (1) Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X. Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S,x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага. 102. Алгоритм решения методом динамического программирования Очевидно, последний — после него других шагов нет. Этот шаг, единственный из всех, можно планировать так, чтобы он как таковой принес наибольшую выгоду. Спланировав оптимально этот последний шаг, можно к нему пристраивать предпоследний, к предпоследнему — предпредпоследний и т.д. Этапы построение алгоритма задач, решаемых методом динамического программирования · Найти такое разбиение задачи на две или более подзадач, чтобы оптимальное решение задачи содержало оптимальное решение всех подзадач, которые в нее входят. · Написать рекуррентное соотношение (если разбиваем задачу на подзадачи, значит, можем выразить качество решения задачи либо через ее подзадачи, либо элементарным образом). · Вычислить оптимальное значение параметра для всей задачи. · Если необходимо получить не только значение качества оптимального решения, но и найти само решение, то на шаге 3 нужно также запоминать некоторую дополнительную информацию о ходе решения – решение каждой подзадачи. Этот шаг иногда еще называют обратным ходом. Основную часть работы составляют шаги 1-3. Если нас интересует только оптимальное значение параметра, шаг 4 не нужен. Если же шаг 4 необходим, для построения оптимального решения иногда приходится получать и хранить дополнительную информацию в процессе выполнения шага 3.   ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
1(ξ), 
;
;