Динамическое программирование. Уравнение Беллмана

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

Системы поддержки принятия решений

Тема :Динамическое программирование. Уравнение Беллмана

Содержание

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

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

3. Уравнение Беллмана

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

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

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

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

Одной из особенностей метода динамического программирования является то, что принятие решения по отношению к многошаговым процессам рассматривается не как единичный акт, а как целый комплекс взаимосвязанных решений. Эта последовательность взаимосвязанных решений называется стратегией. Цель оптимального планирования - выбрать такую стратегию, которая обеспечивала бы получение наилучшего результата с точки зрения заранее выбранного критерия. Такую стратегию называют оптимальной. Если, например, рассматривается работа станции с точки зрения её рентабельности, то критерием оптимальности будет прибыль, получаемая станцией за хозяйственный год, а оптимальной будет стратегия, состоящая из всех тех решений, которые приведут к получению максимальной прибыли.

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

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

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

Математически это можно записать следующим образом:

,

где Fk(uk) - значение искомой целевой функции на k-м этапе; Fk+1(uk+1) - значение целевой функции на k+1 этапе; Z(xk ,uk ) - оценочная функция данного k-го этапа; x, u - выбранные параметры функции.

Выражение (29) представляет собой математическую запись принципа оптимальности. Его называют основным функциональным уравнением динамического программирования или функциональным уравнением Беллмана.

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

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

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

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

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

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

В течение нескольких последних десятилетий сформировалась новая область науки и знаний - управление проектами (ProjectManagement). Под термином «проект» понимают ограниченное во времени целенаправленное предприятие, имеющее требования к привлекаемым ресурсам и качеству конечных результатов и предназначенное для создания уникальных продуктов, услуг или результатов. Таким образом, управление проектами - это приложение знаний, опыта, инструментов и методов к операциям проекта для удовлетворения требований, предъявляемых к проекту .

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

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

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

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

Во-первых, это - модели календарно-сетевого планирования и управления (КСПУ), с появления которых и зародилось управление проектами.

Во-вторых, это - "качественный" подход к управлению проектами, близкий по своей методологии к менеджменту организаций и развиваемый, в основном, зарубежными учеными.

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

Развитие общества, экономики, организации, да и жизни отдельного человека можно представить себе как совокупность дискретных процессов с заданными конечными целями, протекающими в условиях ограниченного времени и ограниченных ресурсов. Человеку удобно делить процесс своей деятельности на локальные процессы, которые требуют для своей реализации специальных методов управления . В основу методов управления проектами заложено представление проекта в виде сетевого графика, отражающего зависимость между различными операциями проекта. Сложностью решения дискретных задач управления проектами (задач дискретной оптимизации) заключается в том, что число допустимых решений экспоненциально растет с ростом размерности задачи n. Поэтому простой перебор всех решений невозможен при больших n. В то же время эти задачи относятся, как правило, к классу NP-полных задач, для которых не существует методов их точного решения, отличных от перебора.

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

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

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

Требуется выбрать подмножество работ M так, чтобы их суммарная полезность

была максимальной при ограничении на общее время выполнения T:

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

Способ построения сети рассмотрим на примере из пяти работ, данные о полезности и времени которых приведены в таблице 1.

Таблица 1 - Данные примера.

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

Рисунок 1. Метод динамического программирования.

Очевидно, что любой путь в сети, из начальной вершины 0 в одну из конечных вершин соответствует некоторому набору работ. И наоборот, любому набору работ, с общим временем выполнения не более 10 однозначно соответствует путь в сети, соединяющей начальную вершину с одной из конечных. Значение координаты по второй оси равно суммарному времени выполнения работ. Примем длины горизонтальных дуг равными 0, а длины наклонных равными полезности соответствующей работы. В этом случае длина пути, соединяющего начальную вершину с одной из конечных, равна суммарной полезности соответствующего набора работ. Таким образом, задача свелась к определению пути, имеющего максимальную длину. Путь максимальной длины выделен на рис. 1 жирными дугами; суммарная полезность U равна 14.

При решении данной задачи методом динамического программирования число допустимых решений равно 2ⁿ. Таким образом, для данного примера число путей в сети равно 32, а при большом n перебор всех возможных вариантов решений становится весьма трудоемким.

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

Шаг 1. Введем понятие коэффициента полезности работы K^u_-, определяемого следующим образом:

(3)

Вычислим K^u_- для каждой работы и ранжируем работы по убыванию K^u_-. Из получившейся последовательности выбираем первые kработ, сумма t_i которых удовлетворяет формуле (2). Таким образом, множество D возможных решений разбивается на два подмножества: одно D₁ - в котором, одновременно не используются работы, не попавшие в набор из k работ; второе подмножество D₂ содержит все остальные варианты решений.

Очевидно, что полученный набор из k работ (табл. 2) является оптимальным решением в D₁ и локально-оптимальным решением в D, а с некоторой долей вероятности - оптимальным в D (в данном примере полученное локально-оптимальное решение из 2-й и 4-й работ с суммарной полезностью равной 14 по случайности является оптимальным, в чем можно убедиться, отыскав его на рис. 1).

Таблица 2 - Локально-оптимальное решение.

Шаг 2. Предположим, что в отброшенных работах есть комбинации, которые дают более оптимальное решение, чем решение в D₁. Рассмотрим подмножество решений D₂, применяя метод динамического программирования для всех комбинаций, где работы 1, 5 и 3 не исключаются одновременно (рис. 2). Для наглядности работы 1, 5 и 3 были перемещены в начало оси работ.

Рисунок 2. Улучшенный метод динамического программирования.

Оптимальные решения множества D₂ выделены жирными дугами на рис. 2; при этом полезность оптимальных решений равна 13, что меньше полезности оптимального решения множества D₁. Следовательно, набор из 2-й и 4-й работ является оптимальным решением задачи. При этом стоит отметить, что число допустимых решений множества D₂ на 2^k меньше, чем число решений в D. Таким образом, использование метода динамического программирования в комбинации с вышеизложенным эвристическим алгоритмом позволяет:

· во-первых, без использования рутинных операций по перебору сразу получить как минимум локально-оптимальное решение задачи;

· во-вторых, сократить количество переборов до 2ⁿ-2^k при поиске оптимального решения.

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

1. Показано применение метода динамического программирования Беллмана к решению задачи о выборе приоритетных работ.

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

3. Дана оценка сокращения количества комбинаций для перебора при поиске точного решения за счет использования эвристических алгоритмов в методе динамического программирования.

3. Уравнение Беллмана

Метод динамического программирования состоит в том что оптимальное управление строится постепенно. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учётом последствий, так как управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. Это основное правило динамического программирования, сформулированное Беллманом, называется принципом оптимальности.

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

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

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

Назовем величину условным максимумом. Если мы теперь выберем на k-м шаге некоторое произвольное управление , то система придет в состояние . Согласно принципу оптимальности, необходимо выбирать управление так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1)-го) приводило бы к общему показателю эффективности на шагах, начиная с k-uго и до конца. Это положение в аналитической форме можно записать в виде следующего соотношения:

,

, (1)

получившего название основного функционального уравнения динамического программирования, или основного рекуррентного уравнения Беллмана.

Из уравнения (1) может быть получена функция , если известно функция . Аналогично можно получить , если известно и т. д., пока не будет определена величина , представляющая по определению максимальное значение показателя эффективности процесса в целом:

.

Решая уравнение (1) для определения условного максимума показателя эффективности за шагов, начиная с k-го, мы определяем соответствующее оптимальное управление , при котором этот максимум достигается. Это управление также зависит от ; будем обозначать его через и называть условным оптимальным управлением на k-м шаге. Основное значение уравнения (1), в котором реализована идея динамического программирования, заключается в том, что решение исходной задачи определения максимума функции n переменных сводится к решению последовательности n задач, задаваемых соотношениями (1), каждое из которых является задачей максимизации функции одной переменной .

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

Если начальное состояние задано , то непосредственно определяют максимум целевой функции

,

а затем - искомое безусловное оптимальное управление по цепочке

. (2)

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

,

откуда находят , а затем по цепочке (2) - безусловное оптимальное управление.

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

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

.

Введем в рассмотрение условные максимумы показателя эффективности за k шагов, от 1-го до k-го включительно, - величину . Повторив приве-денные рассуждения, придем к следующей системе уравнений Беллмана:

;

.

В результате решения этих уравнений получим последовательности

; .

Далее определим безусловное оптимальное управление по цепочке

.

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

1. Руководство к Своду знаний по управлению проектами. (Руководство PMBOK®). Третье издание. Издание на русском языке. - Project Management Institute, Inc., 2004.

2. Коновальчук Е.В., Новиков Д.А. Модели и методы оперативного управления проектами. - М.: ИПУ РАН, 2004. - 63 с.

3. Бурков В.Н., Квон О.Ф., Цитович Л.А. Модели и методы мультипроектного управления. М., Препринт / ИПУ РАН, 1997. - 62 с.

4. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. - М.: Наука, 1969.

5. Математическое основы управления проектами: Учеб. пособие / Баркалов С.А., Воропаев В.И., Секлетова Г.И. и др. Под ред. В.Н. Буркова. - М.: Высш. шк., 2005. - 423 с.

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