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

РЕФЕРАТ

Введение

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

Начало развития динамического программирования относится к 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 (т.е. не зависит напрямую от предшествующих состояний и управленческих решений). Данное требование называется «отсутствием последствия» и может быть выражено следующими уравнениями состояний:

Таким образом, получаем последовательность состояний s0, s1, …, sk-1, sk, …, sn-1, sn. Тогда n-шаговый управленческий процесс схематично можно изобразить следующим образом:

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

а эффективность всего рассматриваемого многошагового процесса следующей аддитивной функцией:

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

Задача динамического программирования обладает следующими особенностями:

Задача оптимизации интерпретируется как n-шаговый процесс управления.

Целевая функция равна сумме целевых функций каждого шага.

Выбор управления на k-ом шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (отсутствие обратной связи).

Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1 и управления Xk («отсутствие последствия»).

На каждом шаге управление 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-ом шаге, и определяют по следующей формуле:

Максимизация ведется по всем допустимым управлениям Xn.

Решение Xn, при котором достигается, также зависит от sn-1 и называется условным оптимальным решением на n-ом шаге. Обозначим его через.

Решив одномерную задачу локальной оптимизации по уравнению (5), определим для всех возможных состояний sn-1 две функции и.

Рассмотрим двухшаговую задачу: присоединим к n-му шагу (n-1) - й.

Для любых состояний sn-2, произвольных управленческих решений Xn-1 и оптимальном управлении на n-ом шаге значение целевой функции на двух последних шагах вычисляется по формуле:

Согласно принципу оптимальности Беллмана для любых sn-2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем (n-ом) шаге приводило бы к оптимуму целевой функции на двух последних шагах. Следовательно, необходимо отыскать оптимум выражения (6) по всем допустимым управленческим решениям Xn-1:

Называют условным максимумом целевой функции при оптимальном управлении на двух последних шагах. Необходимо отметить, что выражение в фигурных скобках в формуле (6), зависит только от sn-2 и Xn-1, так как sn-1 можно найти из уравнения состояний (1) при:

Соответствующее управление Xn-1 на (n-1) - ом шаге обозначается через и называют условным оптимальным управлением на (n-1) - ом.

Аналогично определяются условные оптимумы целевой функции при оптимальном управлении на (n-k+1) шагах, начиная с k-го до конца, при условии, что к началу k-го шага система находилась в состоянии sk-1:

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

Уравнения (5) и (8) называют рекуррентными уравнения Беллмана (обратная схема). Процесс решения данных уравнений называют условной оптимизацией.

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

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

, …, - условные оптимальные управления на n-ом, (n-1) - ом, …, на 1-ом шагах.

Используя данные последовательности, можно найти решение задачи динамического программирования при данных n и s0:

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

Аналогично рассуждая, можно выстроить и прямую схему условной оптимизации:

Оптимальное решение задачи в данном случае находится по следующей схеме:

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

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

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

3. Вводят целевые функции k-ого шага и суммарную целевую функцию, а также условные оптимумы и условное оптимальное управление на k-ом шаге ().

Записывают в соответствии с обратной или прямой схемой рекуррентные уравнения Беллмана и после выполнения условной оптимизации получают две последовательности: {} и {}.

Определяют оптимальное значение целевой функции и оптимальное решение.

3. Задача распределения ресурсов

Имеется определенное количество ресурсов s0, которое необходимо распределить между n хозяйствующими субъектами на текущую деятельность в течение рассматриваемого периода (месяц, квартал, полугодие, год и т.д.) с целью получения совокупной максимальной прибыли. Размеры вложений ресурсов xi (;) в деятельность каждого хозяйствующего субъекта кратны некоторой величине h. Известно, что каждый хозяйствующий субъект в зависимости от объема используемых средств xi за рассматриваемый период приносит прибыль в размере fi(xi) (не зависит от вложения ресурсов в другие хозяйствующие субъекты).

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

Введем в рассмотрение функцию - условно оптимальная совокупная прибыль, полученная от k-го, (k+1) - го, …, n-го хозяйствующих субъектов, если между ними оптимальным образом распределялись ресурсы в объеме sk-1 (). Множество возможных управленческих решений относительно размера распределяемых ресурсов на k-ом шаге можно представить следующим образом: .

Тогда рекуррентные уравнения Р.Э. Беллмана (обратная схема) будут иметь вид:

Пример. Имеется определенное количество ресурсов s0=100, которое необходимо распределить между n=4 хозяйствующими субъектами на текущую деятельность в течение рассматриваемого периода (месяц) с целью получения совокупной максимальной прибыли. Размеры вложений ресурсов xi (;) в деятельность каждого хозяйствующего субъекта кратны величине h=20 и заданы вектором Q. Известно, что каждый хозяйствующий субъект в зависимости от объема используемых средств xi за рассматриваемый период приносит прибыль в размере fi(xi) () (не зависит от вложения ресурсов в другие хозяйствующие субъекты):

Необходимо определить, какой объем ресурсов нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.

Решение. Составим рекуррентные уравнения Беллмана (обратную схему):

Определим условные максимумы в соответствии с (13), результаты расчетов представлены в таблице 1.

Таблица 1. Расчет условных оптимумов

sk-1xkskk=3k=2k=1123456789101112000000000000200200+20=20 22 200+22=22 2200+22=22 22020022+0=22 17+0=1714+0=14400400+33=33 42 200+42=42 4200+42=42 420202022+20=42 17+22=3914+22=3640021+0=2120+0=2026+0=26600600+46=46 55 200+55=55 59 20 0+59=59 590204022+33=5517+42=59 14+42=56402021+20=4120+22=4226+22=4860037+0=3732+0=3235+0=35800800+30=30 68 200+68=68 72 200+72=72 73 20206022+46=6817+55=7214+59=73 404021+33=5420+42=6426+42=68602037+20=5732+22=5435+22=5780067+0=6761+0=6152+0=5210001000+42=42 87 800+87=87 8700+87=87 870208022+30=5217+68=8514+72=86406021+46=6720+55=7526+59=85604037+33=7032+42=7435+42=77802067+20=87 61+22=8352+22=74100058+0=5872+0=7261+0=61По результатам условной оптимизации определим оптимальное распределение ресурсов:

Таким образом, оптимальное распределение ресурсов:

которое обеспечит наибольшую прибыль в размере 87 усл. ден. ед.

Ответ: оптимальное распределение ресурсов: , которое обеспечивает наибольшую прибыль в 87 усл. ден. ед.

Вывод

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

Список литературы

1. Экономико-математические модели и методы. Линейное программирование: Учебное пособие для студентов экономических специальностей / Составители: Смирнов Ю.Н., Шибанова Е.В., Набережные Челны: Изд-во КамПИ, 2004, 81 с.
2. Исследование операций в экономике: Учебн. пособие для вузов/ Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2000. - 407 с.
3. Кузнецов А.В. и др. Высшая математика: Мат. программирование: Учеб./А.В. Кузнецов, В.А. Сакович, Н.И. Холод; Под общ. ред. А.В. Кузнецова. - Мн.: Высш. шк., 1994. - 286 с.: ил.

Репетиторство

Нужна помощь по изучению какой-либы темы?

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

хорошую работу на сайт">

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

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

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

Для расширения производственных мощностей трех предприятий А, В и С выделяется некоторое количество единиц дополнительной электроэнергии в объеме х 0 =8 единиц. Электроэнергия может выделяться в виде 1, 2, 3, 4, 5, 6, 7 и 8 единиц. Вкладывая в развитие i-того предприятия х i единиц электроэнергии можно получить доход у i единиц на предприятии. Существуют разные варианты х i (к) выделения дополнительной электроэнергии. Они приносят доход у i (к), к=1,n. Возможные варианты развития предприятий приведены в табл.1. Суммарный доход по всем предприятиям должен быть максимальным, т.е у=? у i (к)>max

Табл. 1. Варианты развития предприятий

Вариант к	Предриятие А	Предприятие В	Предприятие С

Математическая постановка задачи:

у=? у i (к)> max

?х i (к)?х 0

Решение:

Начнем рассмотрение процедуры решения поставленной задачи с последнего (3 шага) этапа (Табл.2), на котором инвестиции выделяются предприятию С. Условно-оптимальное управление на третьем этапе ищется как решение уравнения

g C (S 2)=max k f c , x C (k)?S 2 , k=1,2,3,4

Табл. 2. Условно-оптимальные решения(шаг 3)

Состояние		Управление

Имеется четыре возможности вложения средств - четыре шаговых управления х С (1)=0ед., х С (2)=1ед., х С (3)=2ед., х С (4)=3ед. и девять теоретически возможных состояний системы S 2 , предшествующих выделению средств предприятию С, - объемы не распределенных к 3-му этапу инвестиций: 0,1,2,3,4,5,6,7,8.

Предположим, что система находилась в состоянии S 2 =2.Тогда, для шагового управления х С (2)=1 доход у С (2) будет равен 3ед. (Табл.3), а шаговое управление х С (3)=2 будет оптимальным для этого состояния, дающим условно-максимальный выигрыш g c (S 2)=5. Если система находилась в состоянии S 2 =3, то допустимы все шаговые управления х С (1)=0ед., х С (2)=1ед., х С (3)=2ед., х С (4)=3ед., а оптимальным будет управление х С (4)=3, которое обеспечивает условно максимальный выигрыш g c (S 2)=6.

Табл.3 динамический программирование распределение инвестиция

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

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

g А (S 1)=max k f А +g c ], x А (k)?S 1 , k=1,2,3,4

Так, для состояния S 1 =3 с шаговым управление х A (2)=1 получаем:

g А (S 1)=max k f А +g c ]

Max k 4+g c =4+5=9, где находим из таблицы 1, а g c из таблицы 3. Аналогично заполняются все состояния.

Табл. 4. Условно-оптимальные решения(шаг 2)

Состояние	f А +g c	Управление

Здесь возникают ситуации, при которых оптимальное решение будет не единственным, Так в состояние S 1 =3 условно оптимальными будут шаговые управления х A (2)=1 и х A (3)=2, дающие один и тот же выигрыш g A (S 1)=9

Табл. 5. Безусловно-оптимальные решения (шаг 1)

На первом этапе (Табл.5)-выделение инвестиций предприятию В - есть только одно предшествующее состояние системы, соответствующее начальному состоянию S 0 =8. Безусловно оптимальный выигрыш определяется выражением:

у * = g В (S 0)= max k {f А +g А } x в (k)?S 0 =x 0 , k=1,2,3,4,5

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

Схема нахождения всех оптимальных вариантов распределения инвестиций между предприятиями (Табл.6) представлена на рисунке 1.

Табл. 6. Оптимальные распределения инвестиций.

Рисунок 1. Схема оптимального распределения инвестиций между предприятиями

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

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

...

Подобные документы

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

курсовая работа , добавлен 25.04.2015


Многошаговые процессы в динамических задачах. Принцип оптимальности и рекуррентные соотношения. Метод динамического программирования. Задачи оптимального распределения средств на расширение производства и планирования производственной программы.

курсовая работа , добавлен 30.12.2010


Метод динамического программирования и его основные этапы. Оптимальная стратегия замены оборудования. Минимизация затрат на строительство и эксплуатацию предприятий. Оптимальное распределение ресурсов в ООО "СТРОЙКРОВЛЯ" и инвестиций ПКТ "Химволокно".

курсовая работа , добавлен 08.01.2015


Математическая модель планирования производства. Составление оптимального плана производственной деятельности предприятия методом линейного программирования. Нахождение оптимального способа распределения денежных ресурсов в течение планируемого периода.

дипломная работа , добавлен 07.08.2013


Расчет стоимости перевозок методом минимальных затрат. Нахождение условного оптимального равенства в процессе динамического программирования. Линейное алгебраическое уравнение Колмогорова для среднего времени безотказной работы резервированной системы.

курсовая работа , добавлен 14.01.2011


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

контрольная работа , добавлен 15.10.2010


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

курсовая работа , добавлен 16.12.2013


Характерные черты задач линейного программирования. Общая постановка задачи планирования производства. Построение математической модели распределения ресурсов фирмы. Анализ чувствительности оптимального решения. Составление отчета по устойчивости.

презентация , добавлен 02.12.2014


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

дипломная работа , добавлен 11.02.2017


Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.

Назначение сервиса . Данный сервис предназначен для решения задачи оптимального распределения инвестиций в онлайн режиме. Результаты вычислений оформляются в отчете формата Word (см. пример оформления).
Такого рода задачи основаны на функции Беллмана и при решении используется метод обратной прогонки (см. Типовые задания). Также можно воспользоваться сервисом Процедура прямой прогонки .

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

Количество предприятий 2 3 4 5 6 7 8 9 10
Количество строк (количество вариантов эффективного вложения) 2 3 4 5 6 7 8 9 10

Пример №1 . Определите оптимальный план расширения производства трех предприятий, если известна их прибыль в год при отсутствии вложений и при инвестировании 1, 2, 3 или 4 млн. Определите, при каком инвестировании будет максимальный процент прироста прибыли.

f1	f2	f3	x i
40	30	35	0
90	110	95	1
395	385	270	2
440	470	630	3
620	740	700	4

I этап. Условная оптимизация .
1-ый шаг. k = 3.

e 2	u 3	e 3 = e 2 - u 3	f 3 (u 3)	F* 3 (e 3)	u 3 (e 3)
1	0	1	35
	1	0	95	95	1
2	0	2	35
	1	1	95
	2	0	270	270	2
3	0	3	35
	1	2	95
	2	1	270
	3	0	630	630	3
4	0	4	35
	1	3	95
	2	2	270
	3	1	630
	4	0	700	700	4

2-ый шаг. k = 2.

e 1	u 2	e 2 = e 1 - u 2	f 2 (u 2)	F* 2 (e 1)	F 1 (u 2 ,e 1)	F* 2 (e 2)	u 2 (e 2)
1	0	1	30	95	125	125	0
	1	0	110	0	110
2	0	2	30	270	300
	1	1	110	95	205
	2	0	385	0	385	385	2
3	0	3	30	630	660	660	0
	1	2	110	270	380
	2	1	385	95	480
	3	0	470	0	470
4	0	4	30	700	730
	1	3	110	630	740	740	1
	2	2	385	270	655
	3	1	470	95	565
	4	0	740	0	740

3-ый шаг. k = 1.

e 0	u 1	e 1 = e 0 - u 1	f 1 (u 1)	F* 1 (e 0)	F 0 (u 1 ,e 0)	F* 1 (e 1)	u 1 (e 1)
1	0	1	40	125	165	165	0
	1	0	90	0	90
2	0	2	40	385	425	425	0
	1	1	90	125	215
	2	0	395	0	395
3	0	3	40	660	700	700	0
	1	2	90	385	475
	2	1	395	125	520
	3	0	440	0	440
4	0	4	40	740	780	780	0
	1	3	90	660	750
	2	2	395	385	780
	3	1	440	125	565
	4	0	620	0	620

Примечание : Столбцы 1 (вложенные средства), 2 (проект) и 3 (остаток средств) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация .
Из таблицы 3-го шага имеем F* 1 (e 0 = 4 млн.руб.) = 780 тыс.руб., то есть максимальная прибыль от инвестирования e 0 = 4 млн.руб. равна 780 тыс.руб.
Из этой же таблицы получаем, что первому предприятию следует выделить u* 1 (e 0 = 4 млн.руб.) = 0 млн.руб.
При этом остаток средств составит: e 1 = e 0 - u 1 , e 1 = 4 - 0 = 4 млн.руб.
Из таблицы 2-го шага имеем F* 2 (e 1 = 4 млн.руб.) = 740 тыс.руб., т.е. максимальная прибыль при e 1 = 4 млн.руб. равна 740 тыс.руб.
Из этой же таблицы получаем, что второму предприятию следует выделить u* 2 (e 1 = 4 млн.руб.) = 1 млн.руб.
При этом остаток средств составит: e 2 = e 1 - u 2 , e 2 = 4 - 1 = 3 млн.руб.
Последнему предприятию достается 3 млн.руб. Итак, инвестиции в размере 4 млн.руб. необходимо распределить следующим образом: первому предприятию ничего не выделять, второму предприятию выделить 1 млн.руб., третьему предприятию выделить 3 млн.руб., что обеспечит максимальную прибыль, равную 780 тыс.руб.

Пример №2 . Имеются 4 предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятии в зависимости от выделенных средств Х представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.

- 1.03 Мб

Дадим математическую формулировку принципа оптимальности. Для простоты будем считать, что начальное x 0 и конечное x T состояния системы заданы. Обозначим через z 1 (х 0 , u 1) значение функции цели на первом этапе при начальном состоянии системы x 0 и при управлении u 1 , через z 2 (х 1 ,u 2) – соответствующее значение функции цели только на втором этапе, ..., через
z i (х i -1 ,u i) – на i-м этапе, ..., через z N (х N -1 , u N) -на N-м этапе. Очевидно, что

Надо найти оптимальное управление u*= (; ;...;), такое, что доставляет экстремум целевой функции (1) при ограничениях.

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

определения для подобных задач на последнем этапе, двух последних и т. д.;
– область определения исходной задачи. Обозначим через F 1 (x N -1), F 2 (x N -2), …, F k (x N -k), …, F N (x 0) соответственно условно-оптимальные значения функции цели на последнем этапе, двух последних и т. д., на k последних и т. д., на всех N этапах.

Начинаем с последнего этапа. Пусть х N-1 – возможные состояния системы на начало N-го этапа. Находим:

F 1 (x N -1) = z N (x N -1 , u N). (2)

Для двух последних этапов получаем

F 2 (x N -2) = (Z N -1 (x N -2 , u N -1) + F 1 (x N -1)). (3)

Аналогично:

F 3 (x N -3) = (Z N -2 (x N -3 , u N -2) + F 2 (x N -2)). (4)

………………………………………………….

F k (x N -k) = (z N-k +1 (x N -k , u N-k +1) + F k- 1 (x N-k +1)). (5)

…………………………………………………..

F N (x 0) = (z 1 (x 0 , u 1) + F N -1 (x 1)). (6)

Выражение (6) представляет собой математическую запись принципа оптимальности. Выражение (5) – общая форма записи условно-оптимального значения функции цели для k оставшихся этапов. Выражения (2) – (6) называются функциональными уравнениями Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т. е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N – 1 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотношениями Беллмана.

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

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

• Рассматривается система, состояние которой на каждом шаге определяется вектором x t . Дальнейшее изменение ее состояния зависит только от данного состояния x t и не зависит от того, каким путем система пришла в это состояние. Такие процессы называются процессами без последействия.
• На каждом шаге выбирается одно решение u t , под действием которого система переходит из предыдущего состояния x t -1 в новое х t . Это новое состояние является функцией состояния на начало интервала x t -1 и принятого в начале интервала решения u t , т. е. x t = x t (x t -1 ,u t).
• Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
• На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений.
• Требуется найти такое допустимое управление u t для каждого шага t, чтобы получить экстремальное значение функции цели за все Т шагов.

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

Геометрическая интерпретация задачи динамического программирования состоит в следующем. Пусть n – размерность пространства состояний. В каждый момент времени координаты системы имеют вполне определенное значение. С изменением времени t могут изменяться значения координат вектора состояния. Назовем переход системы из одного состояния в другое траекторией ее движения в пространстве состояний. Такой переход осуществляется воздействием на координаты состояния. Пространство, в котором координатами служат состояния системы, называется фазовым. Особенно наглядно задачу динамического программирования можно интерпретировать в случае, если пространство состояний двухмерно. Область возможных состояний в этом случае изобразится некоторой фигурой, начальное и конечное состояния системы – точками х 0 , (рис. 1). Управление – это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X 0 или X T , которой эти точки принадлежат.

Рисунок 1

Тогда допустимые управления переводят точки из области Х 0 в X T . Задача динамического программирования геометрически может быть сформулирована следующим образом: найти такую фазовую траекторию, начинающуюся в области Х 0 и оканчивающуюся в области Х T , для которой функция цели достигает экстремального значения. Если в задаче динамического программирования известны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конечные области, то говорят о задаче со свободными концами.

1. ЗАДАЧА РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

2.1 Общая постановка задачи

Рассмотрим применение метода динамического программирования на примере распределения средств между шестью объектами реконструкции предприятия горводоканала:

1. Центральная насосно- фильтровальная станция;

2. Восточная насосно- фильтровальная станция;

3. Водопроводная насосная станции перекачки;

4. Центральная станция аэрации;

5. Восточная станция аэрации;

6. Загородная станция аэрации.

Общая сумма средств, предоставленная на развитие составляет не более 195 тысяч гривен. На основе технико-экономических расчетов установлено, что в результате реконструкции в зависимости от количества потраченных средств объекты будут иметь производительность, приведенную в таблице 1.1. Необходимо определить оптимальное распределение средств между объектами реконструкции, которая обеспечит максимальное увеличение производительности этих объектов. Таким образом, в этой задаче используется критерий оптимизации - суммарная производительность предприятий объектов реконструкции.

Таблица 1.1 Входные данные продуктивности объектов реконструкции

Порядковый номер объекта

Объем ресурсов, выданных на развитие объектов (тыс. грн.)

Продуктивность объектов результате развития (тыс. м3)

1. Блок схема программы

Рисунок 1. Основная программа

QtObj – количество объектов

QtRes – количество ресурсов

effMatrix - матрица производительности объектов,

distVector – вектор выделенных ресурсов

Шаг 1. Условная оптимизация

Шаг 2. Безусловная оптимизация

I = QtObj-1,0 формируем вектор результат

Рисунок 2. Ввод данных

distVector – вектор дистанций, effMatrix = матрица производительности

если все элементы матрицы введены

если вектор производительности- не

отрицательный

Рисунок 3. Условная оптимизация,

формируем мартицу выхода (максимум функции цели)

outMatrix – матрица максимума цели

QtObj – количество объектов

QtRes – количество ресурсов

Matrix – матрица производительности

distVect – вектор дистанций (вектор ресурсов)

нет да Если первое предприятие

Поиск максимума

да maxItem = temp; outMatrix[i][j] = maxItem

1. Структура алгоритма программы

1. Ввод данных – класс DataDlg.

Переменные члены класса.

//вектор для хранения объема ресурсов

std::vector distVector;

//матрица производительности объектов

int** effMatrix;

//функция перевода строки в число

int StringToInt(CString);

//функция проверки корректности введенных данных

BOOL FillMatrix();

//функция очистки ресурсов, после закрытия окна

virtual BOOL DestroyWindow();

//функция инициализации диалога

virtual BOOL OnInitDialog();

1. Вычисление результатов – основ ной класс программы courseWorkDlg

Переменные члены класса

int Value; //значение производительности

int MaxIndex;// максимальный индекс в векторе ресурсов

int Facility;//предприятие

int Recource;//выделенный ресурс

Item ** outMatrix; //матрица максимума цели

std::vector resVector; //вектор результатов

void BuildOutMatrix(int **,std::vector);//функция формирования матрицы цели (условная оптимизация)

afx_msg void OnBnClickedButton1();// обработчик нажатия на кнопку «Вычислить», который запускает процесс вычислений.

virtual BOOL DestroyWindow();//очистка ресурсов программы

1. Вывод результатов класс Report

Назначение данного класса – это вывод вектора результата в табличной форме.

2.4 Результаты работы программы

Начальный ввод данных

1. Ввод данных о продуктивности объектов реконструкции

1. Если не все поля заполнены

1. Если введен неправильный символ

Корректный ввод данных

Показ результата

1. Ввод данных

Результат работы программы

Начальный ввод данных

Ввод продуктивности объектов

Приложение.

Листинг программы

int DataDlg::StringToInt(CString str)

const wchar_t* s = T2CW(str);

int val = _wtoi(s);

// все поля заполнены?

BOOL DataDlg::FillMatrix()

bool flag = true;

for (int i = 0; i < Cells.GetSize(); i ++){

for (int j = 0 ; j < Cells.GetAt(i)->Edits.GetSize(); j ++){

CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;

if (temp->m_hWnd != NULL){

temp->GetWindowText(str);

if (str.IsEmpty()){

MessageBox(L"Нужно заполнить все поля", L"Ошибка", MB_ICONERROR | MB_OK);

Описание работы

Целью данной работы является реализация на ЭВМ решения задачи оптимального распределения средств на расширение производства.
Задачи курсовой работы:
Рассмотреть теоретические аспекты решения задач динамического программирования; рекуррентность природы задач данного типа; принципы оптимальности Беллмана.
Разработка алгоритма. Блок - схемы. Структура алгоритма.
Реализация на ЭВМ разработанного алгоритма на выбранном языке программирования.

Содержание

ВВЕДЕНИЕ ……………………………………………2
Динамическое программирование
Основные понятия …………………4
Принципы динамического программирования. Функциональные уравнения Беллмана …………………….5
Особенности задач динамического программирования……………….10
Задача распределения ресурсов……………………12
Общая постановка задачи ………………………….13
Блок схема программы
Структура алгоритма программы
Результат работы программы
Заключение
Список используемой литературы

План урока

Учебная дисциплина МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В ЭКОНОМИКЕ

Тема урока Решение различных практических задач ДП с применением математических методов.

Цели урока

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

Развитие качества ума, внимания, умений учебного труда студентов.

Воспитание дисциплинированности, целеустремленности студентов.

Оснащение урока конспект лекций, В.П.Агальцов «Математические методы в программировании».

Ход урока:

Организационный момент:

проверка отсутствующих, заполнение журнала.

Актуализация опорных знаний : ответы на контрольные вопросы

Какие задачи называются многошаговыми?

При помощи какого математического аппарата решаются многошаговые задачи?

Что такое оптимальное управление u*?

Каков алгоритм метода последовательных приближений в два круга?

Приведите примеры задач оптимального распределения ресурсов.

Изучение нового материала:

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

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

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

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

• Задача о вычислении чисел Фибоначчи

• Задача о порядке перемножения матриц: даны матрицы, …, требуется минимизировать количество скалярных операций для их перемножения.

• Задача о выборе траектории

• Задача последовательного принятия решения

• Задача об использовании рабочей силы

• Задача управления запасами

• Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.

• Алгоритм Флойда - Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.

• Алгоритм Беллмана - Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.

• Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

Пример: Оптимальное распределение ресурсов

Капитал 40 млн.руб. инвестор должен вложить в четыре инвестиционных проекта так, чтобы получить максимальный доход. Доходность проектов дана в таблице (вложения кратны 8 млн. руб.)

u

Прибыль от внедрения

f4 (u )

f3 (u )

f2 (u )

f1 (u )

55

39

120

115

10 0

120

135

134

14 0

145

158

147

Решение:

Это задача динамического программирования. Решение состоит из двух этапов. На первом этапе (от конца к началу) ищем условное оптимальное решение, на втором (от начала к концу) – ищем оптимальное решение задачи.

1 этап.

Распределяем капитал между четырьмя проектами и считаем получаемую прибыль L (i ), i = 8,16,24,32,40.

1 шаг : Денежные средства вкладываются в четвертый проект.

L (8)=55

L (16)=58

L (24)=90

L (32)=100

L (40)=140

2 шаг : Денежные средства вкладываются в четвертый и третий проекты.

u

Прибыль от внедрения

1 шаг

f3 (u )

55

39

10 0

120

14 0

145

3 шаг : Денежные средства вкладываются в четвертый, третий (2 шаг) и второй проекты.

u

Прибыль от внедрения

2 шаг

f 2(u )

94

108

120

135

135

175

158

175

134

214

147

2 этап:

На четвертом шаге выбираем максимальное из полученных значений прибыли L (40)=214.

И возвращаясь в обратном порядке от таблицы к таблице (от 4 шага к 1) выбираем такие значения доходов, при которых и получено значение 214.

Максимальный доход 214 млн. руб. от вложенных средств может быть получен при следующем распределении средств:

1 проект – 0 млн. руб.

2 проект – 24 млн. руб.

3 проект – 8 млн. руб.

4 проект – 8 млн. руб.

Закрепление нового материала:

5. Подведение итогов урока: выводы, оценки, домашнее задание:

(2) п.5.1

Ср12: формирование и усвоение содержания теоретического материала

Подпись преподавателя