Принцип оптимальности Беллмана. Решение задач методом динамического программирования

 

Содержание

Введение 3

Принцип оптимальности Беллмана 4

Основной  принцип динамического  программирования 5

Примеры задач динамического  программирования 7

Список  используемых источников: 10 
 

 

Введение

   За  последние десятки лет, в прикладной математике большое внимание уделяется  новому классу задач оптимизации, заключающихся в нахождении в заданной области, определяемой линейными и нелинейными ограничениями (равенствами и неравенствами), точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, применяемые в самых разнообразных областях человеческой деятельности, в которых необходим выбор одного из возможных образов действий, прежде всего в экономических исследованиях, при решении проблем управления и планирования производственных процессов, в проектировании и перспективном планиро­вании и т. д.

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

   Важным  разделом математического программирования является динамическое программирование, которые применяются в разных областях науки.

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

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

   В 40-х годах 20 века, Ричард Эрнст Беллман, американский математик, впервые использовал словосочетание «динамическое программирование» для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. 
 

 

 
Принцип оптимальности Беллмана

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

Основные  требования к задачам, выполнение которых позволяет применить данный подход:

• объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями;
• задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из допустимых управлений, приводящих к изменению состояния системы;
• задача не должна зависеть от количества шагов и быть определенной на каждом из них;
• состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров;
• последующее состояние, в котором оказывается система после выбора решения на k-м. шаге, зависит только от данного решения и исходного состояния к началу k-го шага. Данное свойство является основным с точки зрения идеологии динамического программирования и называется отсутствием последействия.

Вопросы применения модели динамического программирования в обобщенном виде. Пусть стоит задача управления некоторым абстрактным объектом, который может пребывать в различных состояниях. Текущее состояние объекта отождествляется с некоторым набором параметров, обозначаемым в дальнейшем ξ и именуемый вектором состояния. Предполагается, что задано множество Ξ всех возможных состояний. Для объекта определено также множество допустимых управлений (управляющих воздействий) X, которое, не умаляя общности, можно считать числовым множеством. Управляющие воздействия могут осуществляться в дискретные моменты времени k (k∊1:n), причем управленческое решение заключается в выборе одного из управлений x_k∊Х. Планом задачи или стратегией управления называется вектор х = (х₁, х₂, ..,x_n-1), компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия между каждыми двумя последовательными состояниями объекта ξ_k и ξ_k+1 существует известная функциональная зависимость, включающая также выбранное управление: ξ_k+1 = φ_k(x_k , ξ_k), k∊1:п-1. Тем самым задание начального состояния объекта ξ₁∊Ξ и выбор плана х однозначно определяют траекторию поведения объекта, как это показано на рис. 5.1.

Эффективность управления на каждом шаге k зависит от текущего состояния ξk , выбранного управления xk и количественно оценивается с помощью функций fk(хk, ξk), являющихся слагаемыми аддитивной целевой функции, характеризующей общую эффективность управления объектом. (Отметим, что в определение функции fk(хk, ξk) включается область допустимых значений хk , и эта область, как правило, зависит от текущего состояния ξk .) Оптимальное управление, при заданном начальном состоянии ξ1 , сводится к выбору такого оптимального планах*, при котором достигается максимум суммы значений fk на соответствующей траектории.

 

Основной  принцип динамического  программирования

Основной  принцип динамического программирования заключается в том, что на каждом шаге следует стремиться не к изолированной оптимизации функции fk(хk, ξk), а выбирать

оптимальное управление хk* в предположении об оптимальности всех последующих шагов. Формально указанный принцип реализуется путем отыскания на каждом шаге k условных оптимальных управлений  k(ξ), ξ∊Ξ, обеспечивающих наибольшую суммарную эффективность начиная с этого шага, в предположении, что текущим является состояние ξ.

Λk(ξ) максимальное значение суммы функций fk на протяжении шагов от k до п(получаемое при оптимальном управлении на данном отрезке процесса), при условии, что объект в начале шага k находится в состоянии ξ . Тогда функции Λk(ξ) должны удовлетворять рекуррентному соотношению:

где ξk+1 = φk(xk, ξ)

Соотношение (5.14) называют основным рекуррентным соотношением динамического программирования. Оно  реализует базовый принцип динамического  программирования, известный также как принцип оптимальности Беллмана:

F - Оптимальная стратегия управления должна удовлетворять следующему условию: каково бы ни было начальное состояние ξk на k-м шаге и выбранное на этом шаге управление хk,, последующие управления (управленческие решения) должны быть оптимальными по отношению к состоянию ξk+1 = φk(xk, ξk), получающемуся в результате решения, принятого на шаге k.

Основное  соотношение (5.14) позволяет найти  функции Λk(ξ) только в сочетании с начальным условием, каковым в нашем случае является равенство:

 

Сравнение рекуррентной формулы (5.14) с аналогичными соотношениями в рассмотренных  выше примерах указывает на их внешнее  различие. Это различие обусловлено  тем, что в задаче распределения ресурсов фиксированным является конечное состояние управляемого процесса. Поэтому принцип Беллмана применяется не к последующим, а к начальным этапам управления, и начальное соотношение имеет вид:

 

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

В то же время, говоря о динамическом программировании как о методе решения оптимизационных задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения задачи (5.3)-(5.4) существенным образом используется тот факт, что система ограничений содержит только одно неравенство, и, как следствие, ее состояние задается одним числом — нераспределенным ресурсом ξ . При наличии нескольких ограничений состояние управляемого объекта на каждом шаге характеризуется уже набором параметров ξ1, ξ2, ..., ξm , и табулировать значения функций Λk (ξ1, ξ2, ..., ξm) необходимо для многократно большего количества точек. Последнее обстоятельство делает применение метода динамического программирования явно нерациональным или даже просто невозможным. Данную проблему его основоположник Р. Беллман эффектно назвал «проклятием многомерности». В настоящее время разработаны определенные пути преодоления указанных трудностей.

 

Примеры задач динамического  программирования

Одной из наиболее известных сфер приложения методов динамического программирования является такая область математической экономики, как теория управления запасами. Ее предметом является разработка и исследование математических моделей систем, занимающих промежуточное положение между источниками (производителями) тех или иных ресурсов и их потребителями. При математической формализации процессов управления запасами очень часто приходится использовать скачкообразные, не дифференцируемые и кусочно-непрерывные функции. Как правило, это обусловливается необходимостью учета эффектов концентрации, фиксированных затрат и платы за заказ. В связи с этим получаемые задачи с трудом поддаются аналитическому решению классическими методами, однако могут быть успешно решены с помощью аппарата динамического программирования. Рассмотрим достаточно типичную задачу, возникающую в процессе планирования деятельности системы снабжения, — так называемую динамическую задачу управления запасами.

Пусть имеется некоторая система снабжения (склад, оптовая база и т. п.), планирующая  свою работу на п периодов. Ее деятельность сводится к обеспечению спроса конечных потребителей на некоторый продукт, для чего она осуществляет заказы производителю данного продукта. Спрос клиентов (конечных потребителей) в данной модели рассматривается как некоторая интегрированная величина, принимающая заданные значения для каждого из периодов, и он должен всегда удовлетворяться (т. е. не допускаются задолженности и отказы). Также предполагается, что заказ, посылаемый производителю, удовлетворяется им полностью, и временем между заказом и его выполнением можно пренебречь (т. е. рассматривается система с мгновенным выполнением заказа). Введем обозначения:

y_k — остаток запаса после (k-1)-го периода;

d_k — заранее известный суммарный спрос в k-м периоде;

х_k — заказ (поставка от производителя) в k-м периоде;

с_k (х_k) —затраты на выполнение заказа объема x_k в k-м периоде;

s_k (ξ_k) — затраты на хранение запаса объема ξ_k в k-м периоде.

После получения поставки и удовлетворения спроса объем товара, подлежащего  хранению в период k, составит ξ_k = y_k + х_k - d_k . Учитывая смысл параметра y_k , можно записать соотношение:

Расходы на получение и хранение товара в  период k описываются функцией

Планом  задачи можно считать вектор х = (х₁, х₂, ..., х_n), компонентами которого являются последовательные заказы в течение рассматриваемого промежутка времени. Соотношение между запасами (5.24) в сочетании с некоторым начальным условием связывает состояния системы с выбранным планом и позволяет выразить суммарные расходы за все п периодов функционирования управляемой системы снабжения в форме аддитивной целевой функции:

Естественной  в рамках сформулированной модели представляется задача нахождения последовательности оптимальных управлений (заказов) x*_k и связанных с ними оптимальных состояний (запасов) ξ*_k , которые обращают в минимум (5.25). В качестве начального условияиспользуем требование о сохранении после завершения управления заданного количества товара y_n+1 , а именно