Модели динамического программирования
Постановка задачи динамического программирования, пошаговая оптимизация. Принцип оптимальности и уравнения Беллмана. Отсутствие обратной связи - основное условие. Задачи об оптимальном распределении средств между предприятиями и ресурсов между отраслями.
| Рубрика | Экономико-математическое моделирование |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 24.07.2009 |
| Размер файла | 131,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Модели динамического программирования
Общая постановка задачи динамического программирования
Динамическое программирование (ДП) - метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разбит на этапы (шаги).
Общая постановка задачи ДП. Рассматривается управляемый процесс, например, процесс распределения средств между предприятиями. В результате управления система (объект управления) переводится из начального состояния в состояние . Предполагается, что управление может быть разбито на шагов. Т.е. решения принимаются последовательно на каждом шаге. А управление, переводящее систему из начального состояния в конечное, является набором из пошаговых управлений.
Обозначим через управление на -м шаге (=1, 2, …,). Оно должно удовлетворять некоторым требованиям, т.е. быть допустимым. Пусть - управление, переводящее систему из начального состояния в состояние . Обозначим как состояние системы после -го шага. Показатель эффективности рассматриваемой операции - целевая функция - зависит от начального состояния и управления:
Сделаем ряд предположений.
1. Состояние системы зависит только от состояния на предыдущем шаге и управления (и не зависит от других предыдущих состояний и управлений). Или
.
2. Обозначим как эффективность -го шага. Целевая функция является суммой показателей эффективности каждого шага.
Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление переводится из начального состояния в состояние , при котором целевая функция принимает наибольшее (наименьшее) значение.
Принцип оптимальности и уравнения Беллмана
Принцип оптимальности был сформулирован Р. Беллманом в 1953 г. Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Основное условие, при котором принцип верен - процесс управления должен быть без обратной связи.
Уравнения Беллмана
На каждом шаге любого состояния системы решение нужно выбирать «с оглядкой», так как этот выбор влияет на последующее состояние и дальнейший процесс управления, зависящий от . Это следует из принципа оптимальности.
Рассмотрим -й шаг: - состояние системы к началу -го шага, - конечное состояние, - управление на -м шаге, - целевая функция (выигрыш) -го шага. Если бы управление состояло только из одного шага, то согласно принципу оптимальности, нужно выбирать так, чтобы для любых получить максимум целевой функции на этом шаге. Обозначим через условный максимум целевой функции на -м шаге. Очевидно, что
Обозначим решение , при котором достигается . Это решение называется условным оптимальным управлением. Таким образом, для всех возможных состояний можно найти и
Далее к -му шагу присоединим ()-й шаг. Если бы управление состояло из двух шагов, то целевая функция равна Согласно принципу оптимальности, нужно выбирать так, чтобы для любых получить максимум целевой функции на двух последних шагах. Обозначим его . Тогда
Это условный максимум целевой функции при оптимальном управлении на двух последних шагах. Причем, выражение в скобках зависит только от и , т.к. В результате максимизация по можно получить и условное оптимальное управление на ()-м шаге .
Обозначим условный максимум целевой функции, полученный при оптимальном управлении на шагах, начиная с -го до конца, при условии, что к началу -го шага система находилась в состоянии . Или
Тогда
Целевая функция на последних шагах при произвольном управлении на -м шаге и оптимальном управлении на последующих шагах равна
Согласно принципу оптимальности, выбирается из условия максимума этой суммы, т.е.
Это уравнение называют уравнением Беллмана.
В процессе решения находятся две последовательности функций:
…, - условные максимумы целевой функции и
, ,…, - условные оптимальные управления.
По определению - условный максимум целевой функции за шагов при условии, что к первому шагу система была в состоянии ,т.е. .
При фиксированном получаем . Далее находим , подставляем это выражение в , потом и т.д. по цепочке.
Задача об оптимальном распределении средств между предприятиями на один год
Постановка задачи.
Найти оптимальное распределение средств между четырьмя предприятиями на один год, при условии, что прибыль k-го предприятия fk (x), является функцией от вложенных в него средств x. Функции fk (x) задаются таблично. Начальные средства = 4. Выписать все оптимальные управления.
Таблица 1.
|
x |
f1(x) |
f 2(x) |
f 3(x) |
f 4(x) |
|
|
0 |
0 |
0 |
0 |
0 |
|
|
1 |
0.4 |
0.6 |
0.4 |
0.6 |
|
|
2 |
1 |
1.2 |
0.8 |
1.6 |
|
|
3 |
1.6 |
2.0 |
1.4 |
2.2 |
|
|
4 |
2.2 |
2.4 |
2.0 |
2.4 |
Решение задачи.
Введём обозначения:
количество средств, выделяемых -му предприятию (=1, 2, 3, 4). .
Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств = 4 рассматриваем как 4-шаговый, номера шагов совпадают с номерами предприятий, выбор , , , - управления на 1, 2, 3,4 шагах. - конечное состояние равно нулю, так как все средства должны быть распределены.
Уравнения состояний в данной задаче имеют вид:
,
где - параметр состояния - количество средств, оставшихся после k-го шага, т.е. средства, которые осталось распределить между предприятиями.
Введем условную оптимальную прибыль, полученную от -го, +1-го, …,4-го предприятий, если между ними распределялись оптимальным образом средства . Допустимые управления удовлетворяют условию . Т.е. либо -му предприятию ничего не идет, либо не более того, что остается к -му шагу.
Уравнение Беллмана и уравнение для максимума целевой функции на последнем шаге примут вид:
(a)
(б)
(в)
(г)
Решаем эти уравнения.
Рассмотрим 4-й шаг.
В таблице 1 прибыль (x) монотонно возрастает, поэтому все средства, оставшиеся к 4-му шагу, вкладываем в 4-е предприятие. При этом для возможных средств =0, 1,…, 5 получим:
и
Например, если , то Тогда
3-й шаг.
Делаются предположения для всех возможных остатков средств =0, 1,…, 5 на начало 3-го шага. Для каждого варианта перебираются , находятся и сравниваются при фиксированном и разных значения сумм . Для каждого наибольшее из этих значений есть - условная оптимальная прибыль. Оптимизация дана в таблице 2 при . Для каждого значения и помещены в графах 5 и 6 соответственно.
Например, если , то или или . В таблице 2 рассмотрены оба варианта. Если , то , и прибыль
Второй вариант распределения средств: если , то , и прибыль Из двух вариантов использования средств лучший: = 0,6. Он достигается при = 0.
2-й шаг.
Оптимизация, согласно уравнению (в), проведена в таблице 2 при =2. Делаются предположения для всех возможных значений =0, 1,…, 5 значения и помещены в графах 8 и 9 соответственно. Первые слагаемые в столбце 7 - значения , взяты из таблицы 1, а вторые из столбца 5 таблицы 2 при .
Поясним данное решение подробнее. Если , то возможны три варианта: , или . Если , то , и условная прибыль состоит из прибыли, полученной на втором предприятии из 0 ед. и условной оптимальной прибыли (прибыль от предприятий 3 и 4), рассчитанной на предыдущем шаге, = 1,6 (таблица 2, столбец 5, строка =2). Соответственно = 1,6.
Второй вариант: , то , = 0,6, прибыль = 0,6
(таблица 2, столбец 5, строка =1). Соответственно = 1,2.
Третий вариант: , то , = 1,2, прибыль = 0
(таблица 2, столбец 5, строка =0). Соответственно = 1,2.
Из двух вариантов использования средств лучший: = 1,6. Он достигается при = 0.
1-й шаг.
Оптимизация, согласно уравнению (г), проведена в таблице 2 при =1. Делаются предположения для всех возможных значений =0, 1,…, 5 значения и помещены в графах 8 и 9 соответственно. Первые слагаемые в столбце 7 - значения , взяты из таблицы 1, а вторые из столбца 5 таблицы 2 при .
В итоге получим 2,8. при = 0.
Далее, По таблице 2, столбцу 9, строке = 4 находим оптимальное управление для на втором шаге. Это = 1 или =2.
Для первого варианта = 1 получим По таблице 2, столбцу 6, строке = 3 находим оптимальное управление = 0. Остается
Для второго варианта = 2 получим По таблице 2, столбцу 6, строке =2 находим оптимальное управление = 0. Остается
Ответ: 2,8, (0, 1, 0, 3); (0, 2, 0, 2).
|
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 |
|
|
1 |
0 1 |
1 0 |
0 + 0,6 =0,6 0,4 + 0 =0,4 |
0,6 |
0 |
0 + 0,6 = 0,6 0,6 + 0 = 0,6 |
0,6 |
0 1 |
0 + 0,6 = 0,6 0,4 + 0 = 0,4 |
0,6 |
0 |
|
|
2 |
0 1 2 |
2 1 0 |
0 + 1,6 =1,6 0,4 + 0,6 =1 0,8 +0 =0,8 |
1,6 |
0 |
0 + 1,6 = 1,6 0,6 +0,6 = 1,2 1,2 + 0 = 1,2 |
1,6 |
0 |
0 + 1,6 = 1,6 0,4 + 0,6 =1 1,0 + 0 =1 |
1,6 |
0 |
|
|
3 |
0 1 2 3 |
3 2 1 0 |
0 + 2,2 = 2,2 0,4 +1,6 =2 0,8 +0,6 =1,4 1,4 +0 =1,4 |
2,2 |
0 |
0 + 2,2 = 2,2 0,6 + 1,6 =2,2 1,2 + 0,6 = 1,8 2,0 + 0 = 2 |
2,2 |
0 1 |
0 + 2,2 = 2,2 0,4 + 1,6 = 2 1,0 + 0,6 =1,6 1,6 + 0 = 1,6 |
2,2 |
0 |
|
|
4 |
0 1 2 3 4 |
4 3 2 1 0 |
0 + 2,4 = 2,4 0,4 + 2,2 = 2,6 0,8 + 1,6 = 2,4 1,4 + 0,6 = 2 2,0 + 0 = 2 |
2,6 |
1 |
0 + 2,6 =2,6 0,6 + 2,2 = 2,8 1,2 + 1,6 = 2,8 2,0 + 0,6 = 2,6 2,4 + 0 =2,4 |
2,8 |
1 2 |
0 + 2,8 = 2,8 0,4 + 2,2 = 2,6 1,0 +1,6 = 2,6 1,6 + 0,6 = 2,2 2,2 + 0 = 2,2 |
2,8 |
0 |
Задача об оптимальном распределении ресурсов между отраслями на n лет.
Постановка задачи.
Требуется распределить имеющиеся средства =50000 между двумя отраслями производства на 5 лет так, чтобы суммарная прибыль от обеих отраслей за 5 лет оказалось оптимальной. Средства , вложенные в I-ю отрасль в начале года, дают в конце года прибыль и возвращаются в размере ; аналогично для II-й отрасли функция прибыли , а возврата . В конце года все возвращенные средства заново перераспределяются между I и II отраслями, новые средства не поступают, прибыль в производство не вкладывается.
Решение задачи.
Процесс распределения средств между двумя отраслями разворачивается во времени, решения принимаются в начале каждого года, следовательно, осуществляется деление на шаги: номер шага номер года. Управление состоит в выделении средств каждой отрасли в очередном году. Параметры состояния к началу -го года (=1, 2, …,) количество средств, подлежащих распределению. Переменных управления на каждом шаге две: количество средств, выделенных I отрасли, и II отрасли. Но так как , то управление на -м шаге зависит от одной переменной , т.е..
Уравнения состояний
выражают остаток средств, возвращенных в конце -го года.
Показатель эффективности -го шага:
- прибыль, полученная в конце --го года от обеих отраслей:
Суммарный показатель эффективности - прибыль за лет:
.
Пусть условная оптимальная прибыль за лет, начиная с -го года до -го года включительно, при условии, что имеющиеся на начало -го года средства в дальнейшем распределялись оптимально. Тогда оптимальная прибыль за лет .
Уравнения Беллмана имеют вид:
Для приведенной задачи
Уравнения состояний примет вид:
.
Целевая функция -го шага
.
Целевая функция задачи
.
Функциональные уравнения
Далее проводим условную оптимизацию.
V шаг. Найдем
что достигается при = 0.
IV шаг.
Подставляем:
что достигается при = 0.
III шаг.
Подставляем:
что достигается при .
II шаг.
Подставляем:
что достигается при .
I шаг.
Подставляем:
что достигается при .
Используя полученные результаты, находим
(все средства выделяются I отрасли)
(все средства выделяются I отрасли)
(все средства выделяются I отрасли)
(все средства выделяются II отрасли)
(все средства выделяются II отрасли)
Ответ: 114406, I-я отрасль получает по годам (50000, 45000, 40500, 0, 0); II-я отрасль получает по годам (0, 0, 0, 36450, 21870).
Подобные документы
Многошаговые процессы в динамических задачах. Принцип оптимальности и рекуррентные соотношения. Метод динамического программирования. Задачи оптимального распределения средств на расширение производства и планирования производственной программы.
курсовая работа [129,8 K], добавлен 30.12.2010Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.
дипломная работа [845,3 K], добавлен 06.08.2013Оптимальный план распределения денежных средств между предприятиями. Разработка плана для каждого предприятия, при котором прибыль от вложенных денежных средств примет наибольшее значение. Использование методов линейного и динамического программирования.
курсовая работа [332,2 K], добавлен 16.12.2013Характерные черты задач линейного программирования. Общая постановка задачи планирования производства. Построение математической модели распределения ресурсов фирмы. Анализ чувствительности оптимального решения. Составление отчета по устойчивости.
презентация [1,1 M], добавлен 02.12.2014Общая характеристика и экономические показатели деятельности трех исследуемых предприятий. Решение задачи планирования производства, а также распределения инвестиций методом линейного и динамического программирования. Сравнительный анализ результатов.
курсовая работа [215,1 K], добавлен 25.04.2015Метод динамического программирования и его основные этапы. Оптимальная стратегия замены оборудования. Минимизация затрат на строительство и эксплуатацию предприятий. Оптимальное распределение ресурсов в ООО "СТРОЙКРОВЛЯ" и инвестиций ПКТ "Химволокно".
курсовая работа [1,6 M], добавлен 08.01.2015Графический метод решения задачи оптимизации производственных процессов. Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством. Метод динамического программирования для выбора оптимального профиля пути.
контрольная работа [158,7 K], добавлен 15.10.2010История создания средств цифровой вычислительной техники. Методы и модели линейного программирования. Экономическая постановка задачи. Выбор метода реализации задачи. Особенности выбора языка программирования. Решение задачи сетевым методом планирования.
курсовая работа [842,1 K], добавлен 19.02.2015Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Составление оптимальной схемы перевозок. Нахождение кратчайшего пути с использованием динамического программирования. Оптимизация математической модели с использованием ПК. Анализ параметров на их принадлежность к нормальному закону распределения.
курсовая работа [215,4 K], добавлен 21.12.2011
