Динамическое программирование
Общая постановка задачи динамического программирования как метода оптимизации, приспособленного к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Принцип оптимальности и уравнения Беллмана. Задача распределения ресурсов.
| Рубрика | Математика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 30.01.2014 |
| Размер файла | 74,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
РЕФЕРАТ
Динамическое программирование
Введение
Динамическое программирование - метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми.
Начало развития динамического программирования относится к 50-м годам ХХ в. и связано с именем Ричарда Эрнеста Беллмана.
Если модели линейного программирования можно использовать в экономике для принятия крупномасштабных плановых решений в сложных ситуациях, то модели динамического программирования применяются при решении задач значительно меньшего масштаба:
ь при разработке правил управления запасами;
ь при распределении инвестиционных ресурсов между альтернативными проектами;
ь при составлении календарных планов текущего и капитального ремонта сложного оборудования и его замены и т.п.
1. Общая постановка задачи динамического программирования
динамический беллман уравнение программирование
Рассматривается управляемый процесс, например, процесс распределения средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования и т.п. В результате управления система (объект управления) S переводится из начального состояния s0 в состояние sn. Пусть, управление можно разбить на n шагов, т.е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность n пошаговых управленческих решений.
Обозначим через Xk управленческое решение на k-м шаге (k=1, 2, …, n). Переменные Xk удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Xk может быть числом, точкой в n-мерном пространстве или качественным признаком).
Пусть X=(X1, X2, …, Xn) - управление, переводящее систему S из состояния s0 в состояние sn. Обозначим через sk состояние системы (характеризуемое определенным набором параметров и конкретных их значений) после k-го шага управления. Причем состояние системы sk в конце k-го шага зависит только от предшествующего состояния sk-1 и управленческого решения на k-ом шаге Xk (т.е. не зависит напрямую от предшествующих состояний и управленческих решений). Данное требование называется «отсутствием последствия» и может быть выражено следующими уравнениями состояний:
. (1)
Таким образом, получаем последовательность состояний s0, s1, …, sk-1, sk, …, sn-1, sn. Тогда n-шаговый управленческий процесс схематично можно изобразить следующим образом:
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Пусть показатель эффективности k-го шага выражается некоторой функцией:
, (2)
а эффективность всего рассматриваемого многошагового процесса следующей аддитивной функцией:
, (3)
или
. (4)
Тогда задача пошаговой оптимизации (задача динамического программирования) формулируется следующим образом: определить такое допустимое управление Х, переводящее систему S из состояния s0 в состояние sn, при котором целевая функция Z принимает наибольшее (наименьшее) значение.
Задача динамического программирования обладает следующими особенностями:
1. Задача оптимизации интерпретируется как n-шаговый процесс управления.
2. Целевая функция равна сумме целевых функций каждого шага.
3. Выбор управления на k-ом шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (отсутствие обратной связи).
4. Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1 и управления Xk («отсутствие последствия»).
5. На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние sk - от конечного числа параметров.
2. Принцип оптимальности и уравнения Беллмана
Принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):
Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление таким образом, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Р.Э. Беллманом были сформулированы и условия, при которых принцип верен. Основное требование - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.
Рассмотрим общую задачу динамического программирования, приведенную выше. На каждом шаге кроме последнего для любого состояния системы sk-1 управленческое решение Xk необходимо выбирать «с оглядкой», так как этот выбор влияет на последующее состояние системы sk.
На последнем шаге исходя из состояния системы sn-1 управленческое решение Xn можно планировать локально-оптимально, т.е. исходя только из соображений этого шага.
Рассмотрим последний n-й шаг:
sn-1 - состояние системы к началу n-го шага;
sn - конечное состояние системы;
Xn - управление на n-ом шаге;
fn(sn-1, Xn) - целевая функция (выигрыш) n-го шага.
Согласно принципу оптимальности, Xn нужно выбирать таким образом, чтобы для любых состояний системы sn-1 получить оптимум целевой функции на этом шаге.
Обозначим через оптимум (для определенности примем максимум) целевой функции - показатель эффективности n-го шага при условии, что к началу последнего шага система S была в произвольном состоянии sn-1, а на последнем шаге управление было оптимальным.
называют условным максимумом целевой функции на n-ом шаге, и определяют по следующей формуле:
. (5)
Максимизация ведется по всем допустимым управлениям Xn.
Решение Xn, при котором достигается , также зависит от sn-1 и называется условным оптимальным решением на n-ом шаге. Обозначим его через .
Решив одномерную задачу локальной оптимизации по уравнению (5), определим для всех возможных состояний sn-1 две функции и .
Рассмотрим двухшаговую задачу: присоединим к n-му шагу (n-1) - й.
Для любых состояний sn-2, произвольных управленческих решений Xn-1 и оптимальном управлении на n-ом шаге значение целевой функции на двух последних шагах вычисляется по формуле:
. (6)
Согласно принципу оптимальности Беллмана для любых sn-2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем (n-ом) шаге приводило бы к оптимуму целевой функции на двух последних шагах. Следовательно, необходимо отыскать оптимум выражения (6) по всем допустимым управленческим решениям Xn-1:
. (6)
- называют условным максимумом целевой функции при оптимальном управлении на двух последних шагах. Необходимо отметить, что выражение в фигурных скобках в формуле (6), зависит только от sn-2 и Xn-1, так как sn-1 можно найти из уравнения состояний (1) при :
. (7)
Соответствующее управление Xn-1 на (n-1) - ом шаге обозначается через и называют условным оптимальным управлением на (n-1) - ом.
Аналогично определяются условные оптимумы целевой функции при оптимальном управлении на (n-k+1) шагах, начиная с k-го до конца, при условии, что к началу k-го шага система находилась в состоянии sk-1:
. (8)
Управление Xk на k-ом шаге, при котором достигается максимум по (8), обозначается и называется условным оптимальным управлением на k-ом шаге.
Уравнения (5) и (8) называют рекуррентными уравнения Беллмана (обратная схема). Процесс решения данных уравнений называют условной оптимизацией.
В результате условной оптимизации получаются две последовательности:
, , …, , - условные максимумы целевой функции на последнем, двух последних, …, на n шагах;
, , …, , - условные оптимальные управления на n-ом, (n-1) - ом, …, на 1-ом шагах.
Используя данные последовательности, можно найти решение задачи динамического программирования при данных n и s0:
В результате получаем оптимальное решение задачи динамического программирования: .
Аналогично рассуждая, можно выстроить и прямую схему условной оптимизации:
, (9)
. (10)
Оптимальное решение задачи в данном случае находится по следующей схеме:
Таким образом, построение модели динамического программирования и решение задачи на ее основе в общем виде можно представить в виде следующих этапов:
1. Выбирают способ деления процесса управления на шаги.
2. Определяют параметры состояния sk и переменные управления Xk на каждом шаге, записывают уравнения состояний.
3. Вводят целевые функции k-ого шага и суммарную целевую функцию, а также условные оптимумы и условное оптимальное управление на k-ом шаге ().
4. Записывают в соответствии с обратной или прямой схемой рекуррентные уравнения Беллмана и после выполнения условной оптимизации получают две последовательности: {} и {}.
5. Определяют оптимальное значение целевой функции и оптимальное решение .
3. Задача распределения ресурсов
Имеется определенное количество ресурсов s0, которое необходимо распределить между n хозяйствующими субъектами на текущую деятельность в течение рассматриваемого периода (месяц, квартал, полугодие, год и т.д.) с целью получения совокупной максимальной прибыли. Размеры вложений ресурсов xi (;) в деятельность каждого хозяйствующего субъекта кратны некоторой величине h. Известно, что каждый хозяйствующий субъект в зависимости от объема используемых средств xi за рассматриваемый период приносит прибыль в размере fi(xi) (не зависит от вложения ресурсов в другие хозяйствующие субъекты).
Необходимо определить, какой объем ресурсов нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.
Представим процесс распределения ресурсов между хозяйствующими субъектами как n-шаговый процесс управления (номер шага совпадает с условным номером хозяйствующего субъекта). Пусть sk () - параметр состояния, т.е. количество свободных средств после k-го шага для распределения между оставшимися (n - k) хозяйствующими субъектами. Тогда уравнения состояний можно записать в следующем виде:
(11)
Введем в рассмотрение функцию - условно оптимальная совокупная прибыль, полученная от k-го, (k+1) - го, …, n-го хозяйствующих субъектов, если между ними оптимальным образом распределялись ресурсы в объеме sk-1 (). Множество возможных управленческих решений относительно размера распределяемых ресурсов на k-ом шаге можно представить следующим образом: .
Тогда рекуррентные уравнения Р.Э. Беллмана (обратная схема) будут иметь вид:
(12)
Далее по полученным результатам условной оптимизации можно определить оптимальное распределение ресурсов по следующей схеме:
Пример. Имеется определенное количество ресурсов s0=100, которое необходимо распределить между n=4 хозяйствующими субъектами на текущую деятельность в течение рассматриваемого периода (месяц) с целью получения совокупной максимальной прибыли. Размеры вложений ресурсов xi (;) в деятельность каждого хозяйствующего субъекта кратны величине h=20 и заданы вектором Q. Известно, что каждый хозяйствующий субъект в зависимости от объема используемых средств xi за рассматриваемый период приносит прибыль в размере fi(xi) () (не зависит от вложения ресурсов в другие хозяйствующие субъекты):
;
Необходимо определить, какой объем ресурсов нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.
Решение. Составим рекуррентные уравнения Беллмана (обратную схему):
(13)
Определим условные максимумы в соответствии с (13), результаты расчетов представлены в таблице 1.
Таблица 1. Расчет условных оптимумов
|
sk-1 |
xk |
sk |
k=3 |
k=2 |
k=1 |
|||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
20 |
0 |
20 |
0+20=20 |
22 |
20 |
0+22=22 |
22 |
0 |
0+22=22 |
22 |
0 |
|
|
20 |
0 |
22+0=22 |
17+0=17 |
14+0=14 |
||||||||
|
40 |
0 |
40 |
0+33=33 |
42 |
20 |
0+42=42 |
42 |
0 |
0+42=42 |
42 |
0 |
|
|
20 |
20 |
22+20=42 |
17+22=39 |
14+22=36 |
||||||||
|
40 |
0 |
21+0=21 |
20+0=20 |
26+0=26 |
||||||||
|
60 |
0 |
60 |
0+46=46 |
55 |
20 |
0+55=55 |
59 |
20 |
0+59=59 |
59 |
0 |
|
|
20 |
40 |
22+33=55 |
17+42=59 |
14+42=56 |
||||||||
|
40 |
20 |
21+20=41 |
20+22=42 |
26+22=48 |
||||||||
|
60 |
0 |
37+0=37 |
32+0=32 |
35+0=35 |
||||||||
|
80 |
0 |
80 |
0+30=30 |
68 |
20 |
0+68=68 |
72 |
20 |
0+72=72 |
73 |
20 |
|
|
20 |
60 |
22+46=68 |
17+55=72 |
14+59=73 |
||||||||
|
40 |
40 |
21+33=54 |
20+42=64 |
26+42=68 |
||||||||
|
60 |
20 |
37+20=57 |
32+22=54 |
35+22=57 |
||||||||
|
80 |
0 |
67+0=67 |
61+0=61 |
52+0=52 |
||||||||
|
100 |
0 |
100 |
0+42=42 |
87 |
80 |
0+87=87 |
87 |
0 |
0+87=87 |
87 |
0 |
|
|
20 |
80 |
22+30=52 |
17+68=85 |
14+72=86 |
||||||||
|
40 |
60 |
21+46=67 |
20+55=75 |
26+59=85 |
||||||||
|
60 |
40 |
37+33=70 |
32+42=74 |
35+42=77 |
||||||||
|
80 |
20 |
67+20=87 |
61+22=83 |
52+22=74 |
||||||||
|
100 |
0 |
58+0=58 |
72+0=72 |
61+0=61 |
По результатам условной оптимизации определим оптимальное распределение ресурсов:
Таким образом, оптимальное распределение ресурсов:
,
которое обеспечит наибольшую прибыль в размере 87 усл. ден. ед.
Ответ: оптимальное распределение ресурсов: , которое обеспечивает наибольшую прибыль в 87 усл. ден. ед.
Вывод
Динамическое программирование - это область математического программирования, включающая совокупность приемов и средств для нахождения оптимального решения, а также оптимизации каждого шага в системе и выработке стратегии управления, то есть процесс управления можно представить, как многошаговый процесс. Динамическое программирование, используя поэтапное планирование, позволяет не только упростить решение задачи, но и решить те из них, которым нельзя применить методы математического анализа. Упрощение решения достигается за счет значительного уменьшения количества исследуемых вариантов, так как вместо того, чтобы один раз решать сложную многовариантную задачу, метод поэтапного планирования предполагает многократное решение относительно простых задач. Планируя поэтапный процесс, исходят из интересов всего процесса в целом, т.е. при принятии решения на отдельном этапе всегда необходимо иметь в виду конечную цель. Однако динамическое программирование имеет и свои недостатки. В отличие от линейного программирования, в котором симплексный метод является универсальным, в динамическом программировании такого метода не существует. Каждая задача имеет свои трудности, и в каждом случае необходимо найти наиболее подходящую методику решения. Недостаток динамического программирования заключается также в трудоемкости решения многомерных задач. Задача динамического программирования должна удовлетворять два условия. Первое условие обычно называют условием отсутствия последействия, а второе - условием аддитивности целевой функции задачи. На практике встречаются такие задачи планирования, в которых заметную роль играют случайные факторы, влияющие как на состояние системы, так и на выигрыш. Существует разница между детерминированной и стохастической задачами динамического программирования. В детерминированной задаче оптимальное управление является единственным и указывается заранее как жесткая программа действий. В стохастической задаче оптимальное управление является случайным и выбирается в ходе самого процесса в зависимости от случайно сложившейся ситуации. В детерминированной схеме, проходя процесс по этапам от конца к началу, тоже находится на каждом этапе целый ряд условных оптимальных управлений, но из всех этих управлений, в конечном счете осуществлялось только одно. В стохастической схеме это не так. Каждое из условных оптимальных управлений может оказаться фактически осуществленным, если предшествующий ход случайного процесса приведет систему в соответствующее состояние. Принцип оптимальности является основой поэтапного решения задач динамического программирования. Типичными представителями экономических задач динамического программирования являются так называемые задачи производства и хранения, задачи распределения капиталовложений, задачи календарного производственного планирования и другие. Задачи динамического программирования применяются в планировании деятельности предприятия с учетом изменения потребности в продукции во времени. В оптимальном распределении ресурсов между предприятиями в направлении или во времени. Описание характеристик динамического программирования и типов задач, которые могут быть сформулированы в его рамках, по необходимости должно быть очень общим и несколько неопределенным, так как существует необозримое множество различных задач, укладывающихся в схему динамического программирования. Только изучение большого числа примеров дает отчетливое понимание структуры динамического программирования.
Список литературы
Экономико-математические модели и методы. Линейное программирование: Учебное пособие для студентов экономических специальностей / Составители: Смирнов Ю.Н., Шибанова Е.В., Набережные Челны: Изд-во КамПИ, 2004, 81 с.
Исследование операций в экономике: Учебн. пособие для вузов/ Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2000. - 407 с.
Кузнецов А.В. и др. Высшая математика: Мат. программирование: Учеб./А.В. Кузнецов, В.А. Сакович, Н.И. Холод; Под общ. ред. А.В. Кузнецова. - Мн.: Высш. шк., 1994. - 286 с.: ил.
Размещено на Allbest.ru
Подобные документы
Понятие и виды задач математического линейного и нелинейного программирования. Динамическое программирование, решение задачи средствами табличного процессора Excel. Задачи динамического программирования о выборе оптимального распределения инвестиций.
курсовая работа [126,5 K], добавлен 21.05.2010Математическое программирование - область математики, в которой изучаются методы решения задач условной оптимизации. Основные понятия и определения в задачах оптимизации. Динамическое программирование – математический метод поиска оптимального управления.
презентация [112,6 K], добавлен 23.06.2013Задачи оптимального управления и ее разновидности. Вычислительные аспекты динамического программирования. Дифференциальное и интегральное исчисление в образах: функции, последовательности, ряды. Транспортная задача, модель-Леонтьева, задачи на повторение.
курсовая работа [1,5 M], добавлен 20.06.2012Теория математического программирования. Методы поиска глобального экстремума функции нескольких переменных. Угловые точки допустимых множеств. Постановка общей задачи нелинейного программирования. Решения уравнения f(x)=0 методом простой итерации.
контрольная работа [775,4 K], добавлен 05.01.2013Целочисленные задачи математического программирования. Постановка транспортной задачи по критерию стоимости в матричной форме. Задача о назначении (проблема выбора, задача о женихах и невестах). Алгоритм метода Гомори. Формирование правильного отсечения.
курсовая работа [868,8 K], добавлен 05.12.2012История зарождения и создания линейного программирования. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей. Методы составления начального опорного плана. Понятие потенциала и цикла. Задача, двойственная к транспортной.
курсовая работа [166,7 K], добавлен 17.07.2002Составление уравнения Эйлера, нахождение его общего решения. Нахождение с использованием уравнения Эйлера-Лагранжа оптимального управления, минимизирующего функционал для системы. Использование метода динамического программирования для решения уравнений.
контрольная работа [170,3 K], добавлен 01.04.2010Линейная производственная задача. Двойственная задача. Задача о "Расшивке узких мест производства". Транспортная задача. Распределение капитальных вложений. Динамическая задача управления запасами. Анализ доходности и риска.
курсовая работа [530,4 K], добавлен 29.05.2006Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Математическое моделирование и особенности задачи распределения. Обоснование и выбор метода решения. Ручное решение задачи (венгерский метод), а также с использованием компьютера. Формулировка полученного результата в сопоставлении с условием задачи.
курсовая работа [383,9 K], добавлен 26.05.2010
