5608.Учебная работа .Тема:Динамическое программирование

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...

Тема:Динамическое программирование»,»

РЕФЕРАТ

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

Введение

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

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

. (1)

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

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

, (2)

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

, (3)

или

. (4)

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

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

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

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

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

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

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

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

Принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):

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

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

Рассмотрим общую задачу динамического программирования, приведенную выше. На каждом шаге кроме последнего для любого состояния системы sk1 управленческое решение Xk необходимо выбирать «с оглядкой», так как этот выбор влияет на последующее состояние системы sk.

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

Рассмотрим последний nй шаг:

sn1 состояние системы к началу nго шага;

sn конечное состояние системы;

Xn управление на nом шаге;

fn(sn1, Xn) целевая функция (выигрыш) nго шага.

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

Обозначим через оптимум (для определенности примем максимум) целевой функции показатель эффективности nго шага при условии, что к началу последнего шага система S была в произвольном состоянии sn1, а на последнем шаге управление было оптимальным.

называют условным максимумом целевой функции на nом шаге, и определяют по следующей формуле:

. (5)

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

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

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

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

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

. (6)

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

. (6)

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

. (7)

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

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

. (8)

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

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

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

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

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

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

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

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

, (9)

.(10)

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

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

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

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

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

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

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

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

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

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

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

(11)

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

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

(12)

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

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

;

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

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

(13)

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

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

sk1xkskk=3k=2k=1123456789101112000000000000200200+20=20 22 200+22=222200+22=2222020022+0=2217+0=1714+0=14400400+33=33 42 200+42=424200+42=42420202022+20=4217+22=3914+22=3640021+0=2120+0=2026+0=26600600+46=46 55 200+55=55 59 20 0+59=59590204022+33=5517+42=5914+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=73404021+33=5420+42=6426+42=68602037+20=5732+22=5435+22=5780067+0=6761+0=6152+0=5210001000+42=42 87 800+87=878700+87=87870208022+30=5217+68=8514+72=86406021+46=6720+55=7526+59=85604037+33=7032+42=7435+42=77802067+20=8761+22=8352+22=74100058+0=5872+0=7261+0=61По результатам условной оптимизации определим оптимальное распределение ресурсов:

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

,

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

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

Вывод

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

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

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