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

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

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

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

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

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

Сетевые модели могут оказать существенную помощь при изуче­нии метода построения моделей ДП. Имеющиеся различия в форму­лировках и вычислительных схемах не носят принципиального ха­рактера.

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

Наиболее важным при построении сетевой модели, по-видимому, является способ определения величин х_j, который позволяет авто­матически выводить из рассмотрения недопустимые проекты (дуги). В ДП используется аналогичный прием, приводящий к понятию со­стояния системы. Этот термин не представляется бесспорно удачным, поскольку он описывает «состояние» системы лишь с позиций нали­чия ограниченного количества некоторого ресурса, что обеспечивает взаимную увязку всех этапов.

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

f_j (x_j) = max {R_j (k_j) + f_j-1(x_j-1)}, j=1, 2, 3,

^{по допустимым проектам k}_j

где f₀(x₀)=0 по определению. Приведенное равенство действительно является рекуррентным, так как величина f_j (x_j) на этапе j вычис­ляется по известному значению f_j-1 (x_j-1) на этапе j-1 при f₀(x₀)=0.

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

Во-первых, заметим, что f_j(x_j) является функцией единственного аргумента x_j. Отсюда следует, что правая часть рекуррентного со­отношения должна быть выражена через x_j, а не через x_j-1. Вернем­ся к сетевой модели и вспомним, что разность между x_j и x_j-1 равна величине затрат (с_j) на реализацию проекта k_j на этапе j, т. е.

c_j (k_j) = x_j - x_j-1

Теперь можно выразить х_j-1 через x_j с помощью равенства x_j-1 = x_j – c_j(k_j). Такая замена обеспечивает более корректную мате­матическую запись рекуррентного соотношения.

Во-вторых, необходимо представить в математической форме условие, предписывающее рассмотрение только допустимых проек­тов. Как и в случае сетевой модели, можно воспользоваться равенст­вом c_j (k_j) = x_j – x_j-1. Однако это ограничение уже введено выше пу­тем замены x_j-1 = x_j – c_j (k_j) в функции f_j-1(x_j-1). Чтобы обеспечить полную корректность, следует в явном виде учесть не требующее пояснений неравенство x_j-1 ≥ 0, откуда x_j – c_j (k_j) ≥ 0 или c_j (k_j) ≤ x_j.

Таким образом, рекуррентное соотношение и ДП имеет следую­щий вид:

f₀(x₀) = 0,

f_j(x_j) = max {R_j (k_j) + f_j-1(x_j - c_j (k_j))}, j=1, 2, 3.

c_j (k_j) ≤ x_j

Ниже приводятся результаты поэтапных расчетов на основе рекуррентного соотношения для рассматриваемой задачи. Они представлены в виде таблиц, так как в ДП обычно используется таб­личная форма записи числовых результатов. Разумеется, весьма заманчивой выглядит перспектива проводить вычисления с исполь­зованием таблиц механически без четкого понимания, для чего вы­полняется та или иная операция. Однако такой путь приводит к це­лому ряду негативных последствий, и его ни в коем случае не следует выбирать тому, кто знакомится с основами динамического программирования. Следует придерживаться двух рекомендаций: (1) сравнивать результаты вычислений с использованием таблиц и расчетов с помощью сетевой модели и (2) всегда связывать исход­ные данные вычислений с использованием таблиц с соответствую­щими математическими символами в рекуррентном соотношении.

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

Этап 1

f₁(x₁) = max {R₁ (k₁)}.

c₁ (k₁) ≤ x₁, k₁ = 1, 2, 3

x1	R1(k1)			Оптимальное решение
	k1 = 1	k1 = 2	k1 = 3	f1(x1)	k1^*
0 1 2 3 4 5	0 0 0 0 0 0	- 5 5 5 5 5	- - 6 6 6 6	0 5 6 6 6 6	1 2 3 3 3 3

Этап 2

f₂(x₂) = max {R₂ (k₂) + f₁ (x₂ - c₂ (k₂))}.

c₂ (k₂ ) ≤ x₂, k₂ = 1, 2, 3, 4

x2	R2 (k2) + f1 (x2 - c2(k2))				Оптимальное решение
	k2 = 1	k2 = 2	k2 = 3	k2 = 4	f2(x2)	k2^*
0 1 2 3 4 5	0+0=0 0+5=5 0+6=6 0+6=6 0+6=6 0+6=6	- - 8+0=8 8+5=13 8+6=14 8+6=14	- - - 9+0=9 9+5=14 9+6=15	- - - - 12+0=12 12+5=17	0 5 8 13 14 17	1 1 2 2 2 или 3 4

Этап 3

f₃(x₃) = max {R₃ (k₃) + f₂ (x₃ – c₃ (k₃))}.

c₃ (k₃ ) ≤ x₃, k₃ = 1, 2

x3	R3 (k3) + f2 (x3 – c3 (k3))		Оптимальное решение
	k3 = 1	k3 = 2	f3(x3)	k3^*
5	0+17=17	3+14=17	17	1 или 2

Оптимальное решение можно найти непосредственно из приве­денных выше таблиц. Сначала рассматривается таблица, построен­ная на этапе 3. При х₃=5 оптимальный проект имеет либо k₃^*=1, либо k₃^*=2. Пусть сначала k₃^*=1. Так как с₃(1)=0, на этапах 2 и 1 х₂=х₃ – с₃(1)=5. Легко видеть, что на этапе 2 из

Рис. 7.3.

x₂ =5 следует k₂^* =4. Далее с₂(4)=4, откуда х₅ =5-4= 1. На этапе 1 из x₁= 1 вытекает k₁^* =2. Таким образом, (2, 4, 1) есть оптимальный набор проектов для этапов 1, 2 и 3. На рис. 7.3 изображена схема определения всех различных оптимальных наборов проектов.

69