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

РЕФЕРАТ

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

Введение

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

Начало развития динамического программирования относится к 50-м годам ХХ в. и связано с именем Ричарда Эрнеста Беллмана.

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

ü  при разработке правил управления запасами;

ü  при распределении инвестиционных ресурсов между альтернативными проектами;

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

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

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

Рассматривается управляемый процесс, например, процесс распределения средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования и т.п. В результате управления система (объект управления) S переводится из начального состояния s₀ в состояние s_n. Пусть, управление можно разбить на n шагов, т.е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность n пошаговых управленческих решений.

Обозначим через X_k управленческое решение на k-м шаге (k=1, 2, …, n). Переменные X_k удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (X_k может быть числом, точкой в n-мерном пространстве или качественным признаком).

Пусть X=(X₁, X₂, …, X_n) - управление, переводящее систему S из состояния s₀ в состояние s_n. Обозначим через s_k состояние системы (характеризуемое определенным набором параметров и конкретных их значений) после k-го шага управления. Причем состояние системы s_k в конце k-го шага зависит только от предшествующего состояния s_k-1 и управленческого решения на k-ом шаге X_k (т.е. не зависит напрямую от предшествующих состояний и управленческих решений). Данное требование называется «отсутствием последствия» и может быть выражено следующими уравнениями состояний:

.                         (1)

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

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

,                        (2)

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

,                              (3)

или

.                                     (4)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f_n(s_n-1, X_n) - целевая функция (выигрыш) n-го шага.

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

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

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

.                    (5)

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

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

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

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

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

.              (6)

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

.    (6)

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

.                                    (7)

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

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

.     (8)

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

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

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

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

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

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

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

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

,                                  (9)

.      (10)

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

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

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

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

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

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

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

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

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

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

                                   (11)

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

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

                  (12)

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

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

;

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

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

                  (13)

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

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

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

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

,

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

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

Вывод

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

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

1. Экономико-математические модели и методы. Линейное программирование: Учебное пособие для студентов экономических специальностей / Составители: Смирнов Ю.Н., Шибанова Е.В., Набережные Челны: Изд-во КамПИ, 2004, 81 с.

2. Исследование операций в экономике: Учебн. пособие для вузов/ Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2000. - 407 с.

3. Кузнецов А.В. и др. Высшая математика: Мат. программирование: Учеб./А.В. Кузнецов, В.А. Сакович, Н.И. Холод; Под общ. ред. А.В. Кузнецова. - Мн.: Высш. шк., 1994. - 286 с.: ил.