Динамическое программирование: Дискретно динамическая модель оптимального распределения ресурсов

Размещено на http://www.allbest.ru/

Министерство образования РФ

Байкальский государственный университет экономики и права

Кафедра математики

Курсовая работа

по дисциплине "Исследование операций"

Динамическое программирование: Дискретно динамическая модель оптимального распределения ресурсов

Исполнитель

Литвинчук Константин

Чита- 2007

Оглавление

Введение

1.Общая постановка задачи динамического программирования

2.Принцип оптимальности и уравнения Беллмана

3.Стохастические задачи динамического программирования

4. Дискретно динамическая модель оптимального распределения ресурсов

Список использованной литературы

Введение

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

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

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

1. Общая постановка задачи динамического программирования

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

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

Если число решений очень велико, то можно построить относительные оценки состояний так, чтобы оценки, отвечающие каждой паре последовательных решений, отличались друг от друга на постоянную величину, представляющую собой средний "доход" на решение. Также можно выполнять дисконтирование доходов от будущих решений. Необходимость в этом иногда появляется в том случае, когда решение принимаются редко, скажем раз в году. Тогда уже не нужно рассматривать последовательно 1,2,3…решения, чтобы достичь решения с большим номером. Вместо этого можно непосредственно оперировать функциональным уравнением, что, как правило, дает существенную выгоду с точки зрения сокращения объема вычислений.

Для реализации такого метода необходимо выяснить все ситуации, в которых может происходить выбор последнего решения.

Рассматривается управляемый процесс например использование ресурсов в течении времени, замены оборудования, и т.п. в результате управления система S переводится из начального состояния S0 в Sn. Управления разбивается на N шагов, т.е. принимается на каждом шаге. Пусть xk управление на k-ом шаге, k=1,2,…n, переменные xk удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми. Пусть X (X1,X2,…Xn) - управление, переводящее систему S из начального состояния в конечное. Тогда обозначим через Sk состояние системы после k-ого шага управления. Получаем последовательность состояний S0,S1,…,Sk-1,Sk,…,Sn-1,Sn.

Показатель эффективности рассматриваемой управляемой операции - целевая функция - зависит от начального состояния и управления:

Z=F(S0,X)

Сделаем несколько предположений:

1.Состояние Sk системы в конце k-ого шага зависит только от предшествующего состояния Sk-1 и управления на k-ом шаге Xk (и не зависит от предшествующих состояний управлений). Это требование называется отсутствием последействия. Сформулированное положение записывается в виде уравнений

,

которые называются уравнением состояния

2. Целевая функция Z является аддитивной о показателей эффективности каждого шага. Обозначим показатель эффективности k-ого шага через

Тогда

.

Задача пошаговой оптимизации формулируется так: определить такое допустимое управление X, переводящее систему S из начального состояния в конечное, при котором целевая функция принимает наибольшее (наименьшее) значение.

2. Принцип оптимальности и уравнения Беллмана

Принцип оптимальности впервые был сформулирован Р.Беллманом в 1953г. Каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.

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

Уравнения Беллмана.

Обозначим через условный максимум целевой функции, полученной при оптимальном управлении на n-k-1 шагах, начиная с k-го до конца, при условии, что к началу k-го шага система находилась в состоянии .Фактически эта функция равна

.

Тогда

Целевая функция на n-k последних шагах при произвольном управлении Xk на k-ом шаге и оптимальном управлении на последующих n-k шагах равна

Согласно принципу оптимальности, Xk выбирается из условия максимума этой суммы, т.е.

(*)

k=n-1,n-2,…,2,1.

Управление Xk на k-м шаге, при котором достигается максимум в (*), обозначается через

и называется условным оптимальным управлением на k-м шаге(в правую часть уравнения (*) следует вместо Sk подставить выражение

найденное из уравнений состояния).

Уравнения (*) называются уравнениями Беллмана.Это рекуррентные соотношения, позволяющие найти предыдущее значение функции, зная последующие.

Естественно, что

(**)

Если найти , то при k=n-1 из (*) можно определить, решив задачу максимизации для всех возможных значений Sn-2, выражения для и соответствующее .Далее, зная , находим, используя (*) и , уравнения состояний.

В результате условной оптимизации получаются две последовательности:

,,…,,-

Условные максимумы целевой функции на последнем, на двух последних, на n шагах и

,,…,-

Условные оптимальные управления на n-м,(n-1)-м,..,1-м шагах. Используя эти последовательности, можно найти решение задачи при данных n и S0.

3. Стохастические задачи динамического программирования

В практике планирования довольно часто встречаются задачи, в которых на состояние системы и на значение критерия заметное влияние оказывают случайные факторы. В таких задачах управляемый процесс не полностью определяется начальным состоянием системы и выбранным управлением, а в какой-то мере зависит от случая. Такие задачи называются стохастическими и вероятностными.

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

Для стохастического процесса можно схематично записать последовательность преобразований:

,

,

.

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

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

Критерий

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

M(X1+X2+…+Xn)=M(X1)+M(X2)+…+M(Xn)

Позволяет упростить функциональное уравнение, описывающее процесс, а свойство линейности

M[M(X1)+M(X2)+…+M(Xn)]= M(X1)+M(X2)+…+M(Xn)

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

Пусть - максимум математического ожидания величины критерия по в N-этапном процессе, начинающемся с состояния , при использовании оптимальной стратегии; тогда

,

Откуда для дискретного случая получаем

Где (j=1,2,…,m) - вероятности m возможных дискретных состояний, которые может принимать случайный вектор

, 0<=<=1, .

4. Дискретно динамическая модель оптимального распределения ресурсов

Составить оптимальный план ежегодного распределения средств между двумя предприятиями в течении 3-летнего планового периода при следующих условиях:

1.Начальная сумма равна 400 (S0);

2. Вложенные средства в размере X приносят для предприятия 1 доход f1(x) и возвращаются в размере 60% от X;

3. На предприятии 2 доход f2(x) и возвращаются в размере 20% от X;

4.Ежегодно распределить все начальные средства, получаемые из возвращенных средств;

f1 и f2 заданы таблично.

Предположим, что все требования, предъявляемые к задаче методом ДП, выполнены. Построение модели ДП и применение метода ДП для решения сводиться к следующим моментам:

1.Выбирают способ деления процесса управления на шаги;

2.Определяют параметры состояния Sk и переменные управления Xk на каждом шаге;

3.Записывают уравнения состояний;

4.Вводят целевые функции k -го шага и суммарную целевую функцию;

5.Вводят в рассмотрение условные максимумы (минимумы) Zk(Sk-1) и условное оптимальное уравнение на k-ом шаге Xk(Sk-1), k=n, n-1, …,2,1;

6.Записывают основные для вычислительной схемы ДП уравнения Беллмана для Zn(Sn-1) и Zk(Sk-1), k=n-1,…,1;

7.Решают последовательно уравнения Беллмана (условная оптимизация) и получают две последовательности функций: { Zk(Sk-1) } и { Xk(Sk-1) };

8.После выполнения условной оптимизации получают оптимальное решение для конкретного начального состояния S0:

А) Zmax= Z1(S0)

Б) по цепочки S0-X1-S1-X2-S2-…-Xn-1-Sn-1-Xn-Sn оптимальное управление: X(X1, X2,…, Xn).

динамический программирование стохастический беллман

Список использованной литературы

1. Кузнецов Ю.Н. Математическое программирование. -М.: Наука,1976.

2. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. -М.: Наука,1965.

3. Кремер Н.Ш. Исследование операций в экономике. -М.: Юнити, 2004.

Размещено на Allbest.ru