Динамическое программирование

Июль 23, 2022

Главная
Информатика
Динамическое программирование

Содержание

2. 1. Основные понятия Динамическое программирование (иначе - динамическое планирование) - это метод нахождения оптимальных решений в
3. Естественным шагом в них может быть год, квартал, месяц, декада, неделя, день и т. д. Однако
4. В экономической практике встречается несколько типов задач, которые по постановке или способу решения относятся к задачам
5. Их решают либо путем составления комплекса взаимосвязанных статических моделей для каждого периода, либо путем составления единой
6. Рассмотрим несколько типичных задач, для решения которых естественным является применение метода динамического программирования.
7. Задача перспективного планирования. Планируется деятельность группы N промышленных предприятий Пi (i = 1,…, N) на период
8. Каждое предприятие за год приносит доход, зависящий от вложенных средств, часть которого отчисляется в фонд предприятий.
9. Здесь процесс принятия решения разбивается на Т шагов. Управление им заключается в начальном распределении и последующих
10. В свою очередь состояние каждого предприятия хit является вектором, компонентами которого служат трудовые ресурсы, основные фонды,
11. Целевой функцией будет суммарная прибыль объединения за Т лет. Если zt — прибыль за t-й год,
12. Задача об оптимальном управлении поставками. В различных областях народного хозяйства возникает задача определения момента подачи партии
13. Пусть Т - промежуток планирования. Обозначим через νt интенсивность потребления ресурса в t-м интервале. Состояние системы
14. Очевидно, что вектор управления есть функция состояния на начало интервала. Из множества возможных управлений требуется выбрать
15. 2.Особенности задач динамического программирования 1. Рассматривается система, состояние которой на каждом шаге определяется вектором xt. Дальнейшее
16. 2. На каждом шаге выбирается одно решение ut, под действием которого система переходит из предыдущего состояния
17. 3. Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят
18. 5. Требуется найти такое допустимое управление ut для каждого шага t, чтобы получить экстремальное значение функции
19. Любую допустимую последовательность действий для каждого шага, переводящую систему из начального состояния в конечное, называют стратегией
21. Скачать презентацию

Слайд 2

1. Основные понятия
Динамическое программирование (иначе - динамическое планирование) - это метод

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

Слайд 3

Естественным шагом в них может быть год, квартал, месяц, декада, неделя,

день и т. д. Однако метод динамического программирования может использоваться при решении задач, где время вообще не фигурирует; разделение на шаги в таких задачах вводится искусственно. Поэтому "динамика" задач динамического программирования заключается в методе решения.

Слайд 4

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

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

Слайд 5

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

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

Слайд 6

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

динамического программирования.

Слайд 7

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

= 1,…, N) на период в t (t = 1,…, Т) хозяйственных лет. В начале периода на развитие системы предприятий выделены какие-то средства К, которые должны быть распределены между предприятиями. В процессе деятельности предприятия вложенные в него средства частично амортизируются.

Слайд 8

Каждое предприятие за год приносит доход, зависящий от вложенных средств, часть

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

Слайд 9

Здесь процесс принятия решения разбивается на Т шагов. Управление им заключается

в начальном распределении и последующих перераспределениях средств иt = {иit}, где иit - объем средств, выделенных i-му предприятию в начале t-гo года. Для описания динамики системы вводится вектор состояния хt = {хit}, где хit - состояние i-го предприятия на начало t-гo года.

Слайд 10

В свою очередь состояние каждого предприятия хit является вектором, компонентами которого

служат трудовые ресурсы, основные фонды, финансовое положение и т.д., т.е. хit = { хikt }. Вектор управления - это функция состояния системы на начало соответствующего года: ut = ut(xt-1). Начальное состояние системы х° может быть заданным.

Слайд 11

Целевой функцией будет суммарная прибыль объединения за Т лет. Если zt

— прибыль за t-й год, то получим задачу

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

Слайд 12

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

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

Слайд 13

Пусть Т - промежуток планирования. Обозначим через νt интенсивность потребления ресурса

в t-м интервале. Состояние системы будем описывать величиной остатка нереализованной продукции на конец интервала xt. Начальное x0 и конечное xT состояния системы можно считать заданными. Для бесперебойности потребления поставками нужно управлять. Обозначим через u = {ut} вектор управления, координаты которого суть величины поставок в начале соответствующих интервалов.

Слайд 14

Очевидно, что вектор управления есть функция состояния на начало интервала. Из

множества возможных управлений требуется выбрать такое, при котором достигается минимум издержек на заказ и содержание материальных ресурсов. Если St — издержки содержания единицы продукции в t-м интервале, то функция цели примет вид:

Слайд 15

2.Особенности задач динамического программирования
1. Рассматривается система, состояние которой на каждом шаге

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

Слайд 16

2. На каждом шаге выбирается одно решение ut, под действием которого

система переходит из предыдущего состояния xt-1 в новое xt. Это новое состояние является функцией состояния на начало интервала xt-1 и принятого в начале интервала решения ut.

Слайд 17

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

или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
4. На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений u принадлежит Ω.

Слайд 18

5. Требуется найти такое допустимое управление ut для каждого шага t,

чтобы получить экстремальное значение функции цели за все Т шагов.

Слайд 19

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

состояния в конечное, называют стратегией управления. Допустимая стратегия управления, доставляющая функции цели экстремальное значение, называется оптимальной.
Управление — это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X0 или Хт которой эти точки принадлежат. Тогда допустимые управления переводят точки из области Хо в ХТ.