Динамическое программирование
ЛЕКЦИЯ 7
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Постановка задачи динамического программирования. Принцип оптимальности. Рекуррентные вычисления в динамическом программировании. Задача о кратчайшем пути. Задача распределения ограниченных ресурсов.
Динамическое программирование – метод оптимизации, используемый для решения задач, в которых процесс принятия решений может быть разбит на отдельные этапы (шаги).
В названии динамического программирования под программированием понимают принятие решения, а слово динамическое указывает на существенную роль времени и порядка выполнения операций в рассматриваемых процессах и методах. В основу метода динамического программирования положен принцип оптимальности, сформулированный в начале 50 годов XX столетия американским математиком Р.Беллманом.
Принцип оптимальности. Каково бы ни было начальное состояние на любом шаге и решение, выбранное на этом шаге, последующие решения должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага.
Использование этого принципа гарантирует, что решение, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения задачи в целом.
Оптимальное решение в динамическом программировании строится постепенно, шаг за шагом. На каждом шаге оптимизируется решение только этого шага, но решение выбирается с учетом последствий, так как решение, оптимальное для этого шага, может привести к неоптимальному решению всей задачи, т.е. оптимальное решение задачи содержит оптимальные решения ее подзадач.
Рекомендуемые материалы
Вычисления в динамическом программировании выполняются рекуррентно в том смысле, что оптимальное решение одной подзадачи используется в качестве исходных данных для следующей. Решив последнюю подзадачу, мы получим оптимальное решение исходной задачи. Способ выполнения рекуррентных вычислений зависит от того, как выполняется декомпозиция исходной задачи. В частности, подзадачи обычно связаны между собой некоторыми общими ограничениями. Если осуществляется переход от одной подзадачи к другой, то должны учитываться эти ограничения.
Динамическое программирование позволяет резко сократить объем переборов вариантов и объем вычислений. Методику решения задач методом динамического программирования рассмотрим на примерах.
При рассмотрении каждого примера особое внимание необходимо обратить на три основных элемента моделей динамического программирования.
1. Определение этапов.
2. Определение на каждом этапе вариантов решения.
3. Определение состояний на каждом этапе.
Из перечисленных выше элементов понятие состояния, как правило, представляется весьма
Самым сложным для восприятия является понятие состояния. Рассмотренные в этом разделе приложения последовательно показывают, что определение состояния меняется в зависимости от моделируемой ситуации. При рассмотрении каждого приложения полезно ответить на следующие вопросы.
1. Какие соотношения связывают этапы вместе?
2. Какая информация необходима для того, чтобы получить допустимые решения на текущем этапе без повторной проверки решений, принятых на предыдущих этапах?
Пример 6.1. Пусть требуется найти путь минимальной стоимости неориентированной ациклической сети, показанной на рис. 6.1. Обозначим через cij стоимость проезда из пункта i в пункт j. Численные значения величин cij приведены непосредственно на рисунке.
Цель – найти путь из п. 1 в п. 10, для которого общая стоимость проезда является минимальной. Сложность решения подобных задач сострит в том, что они по своей природе являются комбинаторными: необходимо перебрать все возможные маршруты и подсчитать общую стоимость проезда по каждому из них.
Для того, чтобы решить эту комбинаторную задачу, используем метод динамического программирования, позволяющий получить искомое решение, не прибегая к полному перебору вариантов. При решении задачи будем рассматривать такие процессы принятия решений, которые позволяют ограничиться рассмотрением стратегий, зависящих только от наилучшего состояния.
Для сетевой модели (см. рис. 6.1) узлы являются «состоянием». Дуги, выходящие из какого-либо узла, указывают направления возможных переходов, определяющих соответствующие решения, которые можно принимать в данном узле (состоянии). Такое толкование соответствует тому, что переход происходит из состояния в состояние, а состояния представляют собой узлы, в которых принимаются решения. Процедуру принятия решения будем называть стратегией. Оптимальная стратегия – стратегия оптимальная одновременно для каждого состояния. Теперь можно формулировать лежащий в основе динамического программирования принцип оптимальности.
Принцип оптимальности. Оптимальная стратегия обладает тем свойством, что, каков бы ни был путь достижения некоторого состояния (пункта), последующие решения должны принадлежать оптимальной стратегии для части пути, начинающегося из этого состояния.
Это означает, что оптимальный путь в примере 6.1 из п. 7 не зависит от того, каким маршрутом мы пришли в этот пункт. Следуя этой идее, можно сделать вывод, что если известны оптимальные пути из пп. 5–7, то достаточно легко определить и оптимальный путь из п. 2. Для этого достаточно суммировать стоимость переезда из п. 2 (будь то c2,5 или c2,6 ) с ранее вычисленной стоимостью оптимального пути из п. 5 или п. 6 соответственно, а затем сравнить полученные суммы и выбрать тот пункт, для которого эта сумма минимальная.
Для того, чтобы практически использовать принцип оптимальности и его вычислительный смысл, введем следующие обозначения: fn(s) – стоимость, отвечающая стратегии минимальных затрат для пути от пункта s, если до конечного пункта остается n этапов: in(s) – решение, позволяющее достичь fn(s).
Для успешного усвоения последующего материала этой главы очень важно понять систему обозначений, используемую в моделях динамического программирования. В принятых обозначениях все буквы и индексы несут важную смысловую нагрузку: f означает, что данное число есть значение целевой функции; s – что это значение зависит от состояния системы; для условий нашего примера это номер пункта сети. И, наконец, индекс n показывает, сколько этапов остается до конца пути. Конкретная запись, такая, например, как f2(5) будет обозначать стоимость минимальных затрат, необходимых на перемещение из пункта 5 до конечного пункта (пункт 10), когда для достижения поставленной цели остается 2 этапа.
В примере 6.1 конечная цель, стоящая перед нами: достижение п. 10. Используя принятые обозначения, можно записать
для 
что соответствует ситуации, когда поставленная цель достигнута (мы находимся в конечном пункте 10) и, следовательно, дальнейшие затраты равны нулю. В соответствии с изложенными выше рассуждениями легко определить f1(8) и f1(9): к f0(10) достаточно прибавить 
или 
. Выполнив эти действия, мы определим стоимость стратегии минимальных затрат для всех случаев, когда до конечного пункта остается один шаг (рис 2)
| n = 1 csj + f0(j) | n = 2 csj + f1(j) | ||||||||
| 10 | i1(s) | f1(s) | 8 | 9 | i2(s) | f2(s) | |||
| 8 | 1+0 | 10 | 1 | 5 | 7+1 | 5+4 | 8 | 8 | |
| 9 | 4+0 | 10 | 4 | 6 | 3+1 | 4+4 | 8 | 4 | |
| 7 | 7+1 | 1+4 | 9 | 5 | |||||
| Рис. 2. | Рис. 3. |
На следующем этапе, когда до конечного пункта остается два шага, мы можем находиться в пунктах 5, 6 или 7. Нашей задачей на этом этапе является определение f2(5), f2(6), f2(7). Эти величины можно определить исходя из следующих соображений Если, например, мы находимся в пункте 5, то из него можно попасть либо р пункт 8, либо в пункт 9. Величины c5,8 и c5,9 известны из условия задачи, функции f1(8) и f1(9) определены на предыдущем этапе. Следовательно, искомая функция f2(5) может быть определена как меньшая из сумм c5,8 + f1(8) или c5,9 +f1(9) (рис. 3). Как видим, начинает просматриваться определенная закономерность, которая может быть представлена в виде так называемого рекуррентного соотношения:
(1)
Выражение (1) означает, что необходимо вычислить все возможные значения стоимости, отвечающие различным стратегиям, суммируя соответствующую стоимость для очередного шага пути (перемещение из пункта s в пункт j) и стоимость, отвечающую оптимальной стратегии выбора пути из пункта j до конечного пункта.
Характерной особенностью вычислительного процесса с использованием (1) является использованием результатов полученных на предыдущем этапе.
| n = 3 csj + f2(j) | n = 4 csj + f3(j) | |||||||||||
| 5 | 6 | 7 | i1(s) | f1(s) | 2 | 3 | 4 | i2(s) | f2(s) | |||
| 2 | 10+8 | 12+4 | 6 | 16 | 1 | 2+16 | 5+12 | 1+18 | 3 | 7 | ||
| 3 | 5+8 | 10+4 | 7+5 | 7 | 12 | |||||||
| 4 | 15+4 | 13+5 | 7 | 18 | ||||||||
| Рис. 4. | Рис. 5. |
На рис. 2, 3, 4 и 5 приводятся результаты поэтапных расчетов на основе рекуррентного соотношения (1) для рассматриваемого примера Они представлены в виде таблиц, так как это наиболее распространенная форма записи числовых результатов в динамическом программировании.
Нетрудно заметить, что изложенная процедура расчетов является итеративной и состоит в выполнении одних и тех же операций на каждом шаге, чтобы по известному fn-1(s) вычислить .fn(s)
Несмотря на возможные большие объемы вычислений алгоритм расчетов, как правило, несложен и легко программируется нa ЭВМ. Проблема заключается в том, что рекуррентные соотношения имеют различный вид для разных задач Вид этих соотношений определяется структурой решаемой задачи. Это обстоятельство не дает возможности создать общую программу дли решения на ЭВМ всех задач динамического программирования, как это делается, например, в линейном программировании.
Общим для задач динамического программирования является то, что переменные рассматриваются не вместе, а последовательно, одна за другой. Сущность состоит в том, что строится такая вычислительная схема, когда вместо одной задачи со многими переменными строится много задач с малым числом (обычно даже одной) переменных в каждой. Это значительно сокращает объем вычислений. Однако такое преимущество достигается лишь при двух условиях: когда критерий оптимальности аддитивен, т.е. общее оптимальное решение является суммой оптимальных решений каждого шага, и когда будущие результаты не зависят от предыстории того состояния системы, при котором принимается решение. Все это вытекает из принципа оптимальности Беллмана, лежащего в основе теории динамического программирования. Из него же вытекает основной прием — нахождение правил доминирования, на основе которого на каждом шаге производится сравнение вариантов будущего развития и заблаговременное отсеивание заведомо бесперспективных вариантов. Когда эти правила обращаются в формулы, однозначно определяющие элементы последовательности один из других, их называют разрешающими правилами. Несмотря на выигрыш в сокращении вычислений, их объем остается очень большим. Поэтому размерность практических задач динамического программирования всегда незначительна, что ограничивает его применение.
Можно выделить два наиболее общих класса задач, к которым в принципе мог бы быть применим этот метод, если бы не «проклятие размерности» (на самом деле на таких задачах, взятых в крайне упрощенном виде, пока удается лишь демонстрировать общие основы метода и анализировать экономико-математические модели). Первый — задача планирования деятельности экономического объекта (предприятия, отрасли и т.п.) с учетом изменения потребности в производимой продукции во времени. Второй класс задач — оптимальное распределение ресурсов между различными направлениями во времени. Сюда можно отнести, в частности, такую интересную задачу: как распределить урожай зерна каждого года на питание и на семена, чтобы за ряд лет получить наибольшее количество хлеба?
Задача распределения ограниченных ресурсов
Постановка задачи. Для развития отрасли на плановый период выделены капитальные вложения в размере X. Имеется n объектов вложений, по каждому из которых известна ожидаемая прибыль, получаемая от вложения определенной суммы средств. Необходимо распределить капитальные вложения между n объектами таким образом, что бы получить максимально возможную суммарную прибыль
Задача управления запасами предприятия
Постановка задачи. Предприятие должно разработать календарную программу выпуска некоторого вида изделия на плановый период, состоящий из N отрезков. Предполагается, что для каждого из этих отрезков имеется точный прогноз спроса на выпускаемую продукцию Время изготовления партии изделия настолько мало, что им можно пренебречь. Соответственно продукция, изготавливаемая в течение отрезка t может быть использована для полного и частичного покрытия спроса в течение этого отрезка времени. Для разных отрезков спрос не одинаков. Кроме того, ни экономические показатели производства влияют размеры изготавливаемых партий, поэтому предприятию нередко бывает выгодно изготовлять в течении некоторого месяца продукцию в объеме, превышающем спрос в пределах этого отрезка, и хранить излишки, используя их для удовлетворения последующего спроса. Вместе с тем хранение возникающих при этом запасов связано с определенными затратами. В зависимости oт обстоятельств затраты обусловлены такими факторами, как проценты на капитал, взятый взаймы для создания запасов; арендная плата за складские помещения; страховые взносы и расходы по содержанию запасов. Эти затраты необходимо учитывать и при установлении программы выпуска.
Задача о рюкзаке
Постановка задачи. Имеется рюкзак заданной грузоподъемности; также имеется некоторое множество предметов различного веса и различной стоимости (ценности); требуется упаковать рюкзак так, чтобы он закрывался и сумма стоимостей упакованных предметов была бы максимальной.
Люди также интересуются этой лекцией: Дескриптивные исследования, опрос и наблюдение.
Задача планирования рабочей силы
Постановка задачи. Число рабочих, необходимых для выполнения проекта регулируется путем найма и увольнения. Как наем так и увольнение рабочих связано с дополнительными затратами. Требуется определить, каким образом должна регулироваться численность рабочих в период выполнения проекта, чтобы дополнительные затраты, связанные с наймом и увольнением рабочих были минимальными.
Задача замены оборудования
Постановка задачи. Необходимо определить оптимальную стратегию использования оборудования в период времени длительностью n лет, если для оборудования возраста t лет известны прибыль от использования оборудования, годовые затраты на обслуживание, остаточная стоимость оборудования и стоимость нового оборудования. Суть оптимальной стратегии использования оборудования заключается в том, чтобы в начале каждого года принять решение либо об эксплуатации оборудования еще один год, либо о замене его новым.
Задача инвестирования
Постановка задачи. В начале каждого из следующих n лет необходимо сделать инвестиции P1, P2,…, Pn соответственно. Есть возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент r1, а второй - r2. Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы. Премиальные меняются от года к году, и для і-ого года равны qi1 и qi2 в первом и втором банках соответственно. Они выплачиваются к концу года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находится там до конца рассматриваемого периода. Необходимо разработать стратегию инвестиции на следующие n лет.
