За последние десятки лет, в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области, определяемой линейными и нелинейными ограничениями (равенствами и неравенствами), точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, применяемые в самых разнообразных областях человеческой деятельности, в которых необходим выбор одного из возможных образов действий, прежде всего в экономических исследованиях, при решении проблем управления и планирования производственных процессов, в проектировании и перспективном планировании и т. д.
Математическое программирование в настоящее время является одной из наиболее часто используемых дисциплин прикладной математики, поэтому соответствующий курс под тем или иным названием и в том или ином томе включен в учебные планы почти каждого вуза.
Важным разделом математического программирования является динамическое программирование, которые применяются в разных областях науки.
Этот метод очень удобен для решения сложных задач, разбивая их на более простые подзадачи. это применимо к задачам с оптимальной подструктурой, которая представляет собой набор перекрывающихся подзадач, сложность которых немного меньше исходной.
Чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы.
В 40-х годах 20 века, Ричард Эрнст Беллман, американский математик, впервые использовал словосочетание «динамическое программирование» для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей.
Принцип оптимальности Беллмана
Суть подхода, реализованного в динамическом программировании, заключается в замене решения исходной многомерной задачи последовательностью задач меньшей размерности.
Основные требования к задачам, выполнение которых позволяет применить данный подход:
- объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями ;
- задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из допустимых управлений, приводящих к изменению состояния системы;
- задача не должна зависеть от количества шагов и быть определенной на каждом из них;
- состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров;
- последующее состояние, в котором оказывается система после выбора решения на k -м. шаге, зависит только от данного решения и исходного состояния к началу k -го шага. Данное свойство является основным с точки зрения идеологии динамического программирования и называется отсутствием последействия.
Проблемы применения модели динамического программирования в обобщенном виде.
Решение задачи оптимального управления
... линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр. Задачи линейного программирования - это задачи, в которых целевая функция и ... при этом равна 24. Заключение В задаче рассматриваются классические и программные методы решения задачи линейного программирования. Решение задачи во всех случаях было: произвести 6 ...
Пусть стоит задача управления некоторым абстрактным объектом , который может пребывать в различных состояниях . Текущее состояние объекта отождествляется с некоторым набором параметров, обозначаемым в дальнейшем ξ и именуемый вектором состояния . Предполагается, что задано множество Ξ всех возможных состояний. Для объекта определено также множество допустимых управлений (управляющих воздействий) X , которое, не умаляя общности, можно считать числовым множеством. Управляющие воздействия могут осуществляться в дискретные моменты времени k (k ∊ 1:n ) , причем управленческое решение заключается в выборе одного из управлений x k ∊ Х . Планом задачи или стратегией управления называется вектор х = (х 1 , х 2 , ..,x n -1 ), компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия между каждыми двумя последовательными состояниями объекта ξk и ξk +1 существует известная функциональная зависимость, включающая также выбранное управление: ξ k +1 = φ k (x k , ξ k ), k ∊ 1:п -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(ξ) должны удовлетворять рекуррентному соотношению:
Основное соотношение (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 описываются функцией
Планом задачи можно считать вектор х = (х 1 , х 2 , …, х n ), компонентами которого являются последовательные заказы в течение рассматриваемого промежутка времени. Соотношение между запасами (5.24) в сочетании с некоторым начальным условием связывает состояния системы с выбранным планом и позволяет выразить суммарные расходы за все п периодов функционирования управляемой системы снабжения в форме аддитивной целевой функции:
Естественной в рамках сформулированной модели представляется задача нахождения последовательности оптимальных управлений (заказов) x* k и связанных с ними оптимальных состояний (запасов) ξ*k , которые обращают в минимум (5.25).
В качестве начального условия используем требование о сохранении после завершения управления заданного количества товара y n +1 , а именно
