Краткая теория
Динамическое программирование (иначе - динамическое планирование) - это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой. Многие экономические процессы расчленяются на шаги естественным образом. Это все процессы планирования и управления, развиваемые во времени. Естественным шагом в них может быть год, квартал, месяц, декада, неделя, день и т. д. Однако метод динамического программирования может использоваться при решении задач, где время вообще не фигурирует; разделение на шаги в таких задачах вводится искусственно. Поэтому «динамика» задач динамического программирования заключается в методе решения.
В экономической практике встречается несколько типов задач, которые по постановке или способу решения относятся к задачам динамического программирования. Это задачи оптимального перспективного и текущего планирования во времени. Их решают либо путем составления комплекса взаимосвязанных статических моделей для каждого периода, либо путем составления единой динамической задачи оптимального программирования с применением многошаговой процедуры принятия решений. К задачам динамического программирования следует отнести задачи многошагового нахождения оптимума при размещении производительных сил, а также оптимального быстродействия.
Типичные особенности многошаговых задач.
1. Рассматривается система, состояние которой на каждом шаге определяется вектором . Дальнейшее изменение ее состояния зависит только от данного состояния и не зависит от того, каким путем система пришла в него. Такие процессы называются процессами без последействия.
2. На каждом шаге выбирается одно решение , под действием которого система переходит из предыдущего состояния в новое . Это новое состояние является функцией состояния на начало интервала и принятого в начале интервала решения т. е.
3. Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
4. На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений .
5. Требуется найти такое допустимое управление для каждого шага , чтобы получить экстремальное значение функции цели за все шагов.
Любую многошаговую задачу можно решать по-разному. Во-первых, можно считать неизвестными величинами щ и находить экстремум целевой функции одним из существующих методов оптимизации, т. е. искать сразу все элементы решения на всех шагах. Отметим, что этот путь не всегда приводит к цели, особенно когда целевая функция задана в виде таблиц или число переменных очень велико. Второй путь основан на идее проведения оптимизации поэтапно. Поэтапность отнюдь не предполагает изолированности в оптимизации этапов. Наоборот, управление на каждом шаге выбирается с учетом всех его последствий. Обычно второй способ оптимизации оказывается проще, чем первый, особенно при большом числе шагов. Идея постепенной, пошаговой оптимизации составляет суть метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса в целом. Лучше много раз решать сравнительно простую задачу, чем один раз - сложную.
С первого взгляда идея может показаться тривиальной: если трудно оптимизировать сложную задачу, то следует разбить ее на ряд более простых. На каждом шаге оптимизируется задача малого размера, что уже нетрудно. При этом принцип динамического программирования вовсе не предполагает, что каждый шаг оптимизируется изолированно, независимо от других. Напротив, пошаговое управление должно выбираться с учетом всех его последствий.
Можно сформулировать следующие принципы, лежащие в основе динамического программирования: принцип оптимальности и принцип погружения.
Оптимальное управление на каждом шаге определяется состоянием системы на начало этого шага и целью управления. Или в развернутой форме: оптимальная стратегия обладает таким свойством, что, каковы бы ни были начальное состояние и начальные решения, последующие решения должны приниматься исходя из оптимальной стратегии с учетом состояния, вытекающего из первого решения. Этот принцип имеет довольно простую математическую интерпретацию, выражающуюся в составлении определенных рекуррентных соотношений (функциональных уравнений Р. Беллмана).
Природа задачи, допускающей использование метода динамического программирования не меняется при изменении количества шагов , т. е. форма такой задачи инвариантна относительно . В этом смысле всякий конкретный процесс с заданным числом шагов оказывается как бы погруженным в семейство подобных ему процессов и может рассматриваться с позиции более широкого класса задач.
Реализация названных принципов дает гарантию того, что решение, принимаемое на очередном шаге, окажется наилучшим относительно всего процесса в целом, а не узких интересов данного этапа. Последовательность пошаговых решений приводит к решению исходной -шаговой задачи.
Дадим математическую формулировку принципа оптимальности для задач с аддитивным критерием оптимальности (сепарабельная функция цели). Для простоты будем считать, что начальное и конечное состояния системы заданы. Обозначим через значение функции цели на первом этапе при начальном состоянии системы и при управлении , через -соответствующее значение функции цели только на втором этапе, …., через - на этапе, …, через - на -м этапе. Очевидно, что
Надо найти оптимальное управление такое, что доставляет экстремум целевой функции при ограничениях .
Для решения этой задачи погружаем ее в семейство подобных. Введем обозначения. Пусть - соответственно области определения для подобных задач на последнем этапе, двух последних и т.д.; - область определения исходной задачи. Обозначим через
соответственно условно-оптимальные значения функции цели на последнем этапе, двух последних и т.д., на последних и т.д., на всех этапах.
Начинаем с последнего этапа. Пусть - возможные состояния системы на начало -го этапа. Находим:
Для двух последних этапов получаем:
Аналогично:
…………………….
…………………….
Выражение (5) представляет собой математическую запись принципа оптимальности. Выражение (4) - общая форма записи условно-оптимального значения функции цели для оставшихся этапов. Выражения (1)-(5) называются функциональными уравнениями Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т.е. для нахождения оптимального управления на шагах нужно знать условно-оптимальное управление на предшествующих этапах и т.д. Поэтому функциональные уравнения часто называются рекуррентными (возвратными) соотношениями Беллмана.
Пример решения задачи
Производственное объединение выделяет четырем входящим в него предприятиям кредит в сумме 100 млн.ден.ед. для расширения производства и увеличения выпуска продукции. По каждому предприятию известен возможный прирост выпуска продукции (в денежном выражении) в зависимости от выделенной ему суммы . Для упрощения вычислений выделяемые суммы кратны 20 млн.ден.ед. При этом предполагаем, что прирост продукции на предприятии не зависит от суммы средств, вложенных в другие предприятия, а общий прирост выпуска в производственном объединении равен сумме приростов, полученных на каждом предприятии объединения.
Требуется найти оптимальное решение распределения кредита между предприятиями, чтобы общий прирост выпуска продукции на производственном объединении был максимальным.
| Выделяемые средства , млн.ден.ед. | Предприятие | №1 | №2 | №3 | №4 | Прирост выпуска продукции на предприятиях млн.ден.ед. | 20 | 10 | 12 | 11 | 16 | 40 | 31 | 24 | 36 | 37 | 60 | 42 | 36 | 45 | 46 | 80 | 62 | 52 | 60 | 63 | 100 | 76 | 74 | 77 | 80 |
Если сроки со сдачей контрольной работы поджимают, на сайте всегда можно заказать cрочное решение задач по методам оптимальных решений .
Динамическое программирование представляет собой многоэтапный поиск оптимального решения. Оптимизация многошагового процесса базируется на принципе оптимальности Р. Беллмана.
Вычисления в динамическом программировании выполняются рекуррентно - оптимальное решение одной подзадачи используется в качестве исходных данных для поиска оптимального решения следующей подзадачи. Решив последнюю подзадачу, мы получим оптимальное решение исходной задачи.
| Выделяемые средства | 0 | 0 | 0 | 0 | 0 | 20 | 10 | 12 | 11 | 16 | 40 | 31 | 24 | 36 | 37 | 60 | 42 | 36 | 45 | 46 | 80 | 62 | 52 | 60 | 63 | 100 | 76 | 74 | 77 | 80 |
В соответствии с вычислительной схемой динамического программирования рассмотрим сначала случай , т.е. предположим, что все имеющиеся средства выделяются на реконструкцию и модернизацию одного предприятия. Обозначим через максимально возможный дополнительный доход на этом предприятии, соответствующий выделенной сумме . Каждому значению отвечает вполне определенное (единственное) значение дополнительного дохода, поэтому можно записать, что:
Пусть теперь , т.е. средства распределяются между двумя предприятиями. Если второму предприятию выделена сумма , то дополнительный доход на нем составит . Оставшиеся другому предприятию средства в зависимости от величины (а значит, и ) позволят увеличить дополнительный доход до максимально возможного значения . При этом условии общий дополнительный доход на двух предприятиях:
Пусть теперь , т.е. средства распределяются между тремя предприятиями. Если третьему предприятию выделена сумма , то дополнительный доход на нем составит . Оставшиеся средства в зависимости от величины (а значит, и ) позволят увеличить дополнительный доход до максимально возможного значения . При этом условии общий дополнительный доход на трех предприятиях:
Пусть теперь , т.е. средства распределяются между четырьмя предприятиями. Если четвертому предприятию выделена сумма , то дополнительный доход на нем составит . Оставшиеся средства в зависимости от величины (а значит, и ) позволят увеличить дополнительный доход до максимально возможного значения . При этом условии общий дополнительный доход на четырех предприятиях:
Оптимальный план распределения между 4 предприятиями 100 единиц ресурса:
| 0 | 20 | 40 | 40 |
При этом суммарный прирост продукции достигнет максимальной величины, равной 85.
Средняя стоимость решения контрольной работы 700 - 1200 рублей (но не менее 300 руб. за весь заказ). На цену сильно влияет срочность решения (от суток до нескольких часов). Стоимость онлайн-помощи на экзамене/зачете - от 1000 руб. за решение билета.
Все вопросы по стоимости можете задать прямо в чат, предварительно скинув условие задач и сообщив необходимые вам сроки решения. Время ответа - несколько минут.
Примеры близких по теме задач
Основная модель управления запасами
На примере решения задачи рассмотрена основная модель управления запасами (модель Уилсона). Вычислены такие показатели модели как оптимальный размер партии заказа, годовые затраты на хранение, интервал между поставками и точка размещения заказа.
Задача квадратичного программирования
Приведен образец решения задачи квадратичного выпуклого программирования графическим методом.
Игры в смешанных стратегиях
Содержит изложенные в краткой и доступной форме теоретические сведения о матричной игре без седловой точки и способе сведения такой задачи к задаче линейного программирования, для отыскания ее решения в смешанных стратегиях. Приведен пример решения задачи.
Инструкция . Выберите количество предприятий.
Пример №1 . Планируется работа двух предприятий на n лет. Начальные ресурсы равны s0. Средства x, вложенные в 1-е предприятие в начале года, дают в конце года прибыль f1(x), и возвращаются в размере g1(x). Средства y, вложенные в 2-е предприятие в начале года, дают в конце года прибыль f2(y) и возвращаются в размере g2(y). В конце года возвращенные средства заново перераспределяются между отраслями. Определить оптимальный план распределения средств и найти максимальную прибыль.
Задачу решим методом динамического программирования. Операцию управления производственным процессом разобьём на этапы. На каждом из них управление выберем так, чтобы оно приводило к выигрышу как на данном этапе, так и на всех последующих до конца операции. В этом состоит принцип оптимальности
, сформулированный американским математиком А. Беллманом.
Разобьём весь период на три этапа по годам и будем нумеровать их, начиная с первого.
Обозначим через x k
и y k
количество средств выделяемых каждому предприятию на k-ом этапе, а через x k
+ y k
= a k
- общее количество средств на этом этапе. Тогда первое предприятие приносит на этом этапе 3 x k
, а второе 4 y k
единиц дохода. Общий доход на k-ом этапе 3x k
+ 4y k
.
Обозначим через f
k (a
k) - максимальный доход, который получает отрасль от обоих предприятий на k-ом и всех последующих. Тогда функциональное уравнение, отражающее принцип оптимальности Беллмана, принимает вид:
f k (a k)=
max{3
x k + 4
y k +
f k +1 (a k +1)}.
(1)
Так как x k + y k = a k , то
y k = a k - x k и
3x k + 4y k = 3x k + 4(a k - x k) = - x k + 4a k . Поэтому
f k (a k) = max{-x k + 4a k + f k+1 (ak+1)}
. (2)
0 ≤ x k ≤ a k
Кроме того, ak - это средства выделяемые обои предприятиям на k-ом этапе, и они определяются остатком средств, получаемых на предыдущем (k-1)-ом этапе. Поэтому по условию задачи оптимальное управление на каждом этапе
a k = 0,5
x k -1 + 0,2
y k -1 = 0,5
x k -1 +0,2(a k -1 -
x k -1) = 0,3
x k -1 +0,2
a k -1 .
(3)
I.Условия оптимизации
Планирование начинаем с последнего третьего этапа
При k
=
3
получаем из (2)
f 3 (a 3) = max {- x 3 + 4a 3 + f 4 (a 4)}
0 ≤ x 3 ≤ a 3
Так как четвёртого этапа нет, то f 4 (a 4)=0
и
f 3 (a 3) = max {- x 3 + 4a 3 }=4a 3
0 ≤ x 3 ≤ a 3
(максимум выражения (-
x 3 + 4
a 3
) будет при x 3 =0)).
Итак, для третьего последнего этапа имеем: f 3 (a 3) = 4
a 3 ,
x 3 = 0,
y 3 =
a 3 -
x 3 =
a 3 ,
где a
3 = 0,3x 2
+ 0,2a 2 ,
что следует из формулы (3).
При k = 2
из (2) и (3) получаем:
f(a 2) = max {-x 2 + 4a 2 + f 3 (a 3)}=
0 ≤ x ≤ a 2
= max {-x 2 + 4a 2 + 4a 3 }= max {-x 2 + 4a 2 + 4(0,3x 2
+ 0,2a 2)} max{0,2x 2 + 4,8a 2 } 5a
0 ≤ x ≤ a
2
т. к. максимум выражения (0,2
x 2 + 4,8
a 2
) будет при x 2 =
a 2
.
То для второго этапа имеем: f 2 (a 2) = 5a 2 , x 2 = a 2 , y 2 = a 2 x 2 = 0 , при этом
a 2 = 0,3x 1 + 0,2a 1 с учетом (3).
При k = 1
с учетом (2) и (3) получаем:
f 1 (a 1) = max {-x 1 + 4a 1 + f 2 (a 2)}=
0 ≤ x ≤ a 1
= max {-x 1 + 4a 1 + 5a 2 }= max {-x 1 + 4a 2 + 5(0,3x 1 + 0,2a 2)}= max {0,5x 1 + 5a 1 }=5,5a 1
0 ≤ x ≤ a
1
при x 1 = a 1
.
Итак, для первого этапа f 1 (a 1) = 5,5
a 1 ,
x 1 =
a 1 ,
y 1 = 0.
Процесс закончен. На первом этапе общее количество распределяемых средств известно -a 1
= 900 ед. Тогда максимальный доход, получаемый обоими предприятиями за три года составит f 1 (a 1) = 5,5*900 = 4950 ден. ед.
II. Безусловная оптимизация
Выясним, каким должно быть оптимальное управление процессом выделения средств между первым и вторым предприятиями для получения максимального дохода в количестве 4950 ден. ед.
1-й год.
Так как x 1 =
a 1
и ,
y 1 = 0,
то все средства в количестве 900 ден. ед. отдаются первому предприятию.
2-й год.
Выделяются средства a 2 = 0,3x 1 + 0,2a 1 = 0,5 a 1
=450 ед., x 2 = a 2 , y 2 = 0.
Все они передаются первому предприятию.
3-й год
. Выделяются средства a
3 = 0,3x 2
+ 0,2a 2
= 0,5 a 2
= 225 ед., x 3 = 0,
y 3 =
a 3
. Все они передаются второму предприятию.
Результаты решения представим в виде таблицы.
| Период | Средства | Предприятие №1 | Предприятие №2 | Остаток | Доход |
| 1 | 900 | 900 | 0 | 450 | 2700 |
| 2 | 450 | 450 | 0 | 225 | 1350 |
| 3 | 225 | 0 | 225 | 45 | 900 |
| 4950 |
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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
Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.
Дадим математическую
формулировку принципа оптимальности.
Для простоты будем считать, что
начальное 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 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотношениями Беллмана.
На основании выше сказанного можно выделить следующие особенности задач динамического программирования.
Любую допустимую последовательность действий для каждого шага, переводящую систему из начального состояния в конечное, называют стратегией управления. Стратегия управления, в результате которой можно получить экстремальное значение функции цели, называется оптимальной.
Геометрическая интерпретация задачи динамического программирования состоит в следующем. Пусть n – размерность пространства состояний. В каждый момент времени координаты системы имеют вполне определенное значение. С изменением времени t могут изменяться значения координат вектора состояния. Назовем переход системы из одного состояния в другое траекторией ее движения в пространстве состояний. Такой переход осуществляется воздействием на координаты состояния. Пространство, в котором координатами служат состояния системы, называется фазовым. Особенно наглядно задачу динамического программирования можно интерпретировать в случае, если пространство состояний двухмерно. Область возможных состояний в этом случае изобразится некоторой фигурой, начальное и конечное состояния системы – точками х 0 , (рис. 1). Управление – это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X 0 или X T , которой эти точки принадлежат.
Рисунок 1
Тогда допустимые управления переводят точки из области Х 0 в X T . Задача динамического программирования геометрически может быть сформулирована следующим образом: найти такую фазовую траекторию, начинающуюся в области Х 0 и оканчивающуюся в области Х T , для которой функция цели достигает экстремального значения. Если в задаче динамического программирования известны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конечные области, то говорят о задаче со свободными концами.
2.1 Общая постановка задачи
Рассмотрим применение метода динамического программирования на примере распределения средств между шестью объектами реконструкции предприятия горводоканала:
1. Центральная насосно- фильтровальная станция;
2. Восточная насосно- фильтровальная станция;
3. Водопроводная насосная станции перекачки;
4. Центральная станция аэрации;
5. Восточная станция аэрации;
6. Загородная станция аэрации.
Общая сумма средств, предоставленная на развитие составляет не более 195 тысяч гривен. На основе технико-экономических расчетов установлено, что в результате реконструкции в зависимости от количества потраченных средств объекты будут иметь производительность, приведенную в таблице 1.1. Необходимо определить оптимальное распределение средств между объектами реконструкции, которая обеспечит максимальное увеличение производительности этих объектов. Таким образом, в этой задаче используется критерий оптимизации - суммарная производительность предприятий объектов реконструкции.
Таблица 1.1 Входные данные продуктивности объектов реконструкции
Порядковый номер объекта |
Объем ресурсов, выданных на развитие объектов (тыс. грн.) |
|||||||||||||
Продуктивность объектов результате развития (тыс. м3) |
||||||||||||||
Рисунок 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
Переменные члены класса.
//вектор для хранения объема ресурсов
std::vector
//матрица производительности объектов
int** effMatrix;
//функция перевода строки в число
int StringToInt(CString);
//функция проверки корректности введенных данных
BOOL FillMatrix();
//функция очистки ресурсов, после закрытия окна
virtual BOOL DestroyWindow();
//функция инициализации диалога
virtual BOOL OnInitDialog();
Переменные члены класса
int Value; //значение производительности
int MaxIndex;// максимальный индекс в векторе ресурсов
int Facility;//предприятие
int Recource;//выделенный ресурс
Item ** outMatrix; //матрица максимума цели
std::vector
void BuildOutMatrix(int **,std::vector
afx_msg void OnBnClickedButton1();// обработчик нажатия на кнопку «Вычислить», который запускает процесс вычислений.
virtual BOOL DestroyWindow();//очистка ресурсов программы
Назначение данного класса – это вывод вектора результата в табличной форме.
2.4 Результаты работы программы
Начальный ввод данных
Корректный ввод данных
Показ результата
Результат работы программы
Начальный ввод данных
Ввод продуктивности объектов
Приложение.
Листинг программы
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
Блок схема программы
Структура алгоритма программы
Результат работы программы
Заключение
Список используемой литературы
Инструкция . Выберите количество предприятий и количество строк (количество вариантов эффективного вложения), нажмите Далее (см. Пример заполнения). Если доход и остатки предприятий задан в виде функций f(x) и g(x) , задача решается через этот калькулятор .
Пример №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 |
Пример №2 . Имеются 4 предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятии в зависимости от выделенных средств Х представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.
