практикум по математике часть 3

4. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

4.1 Краткие сведения из теории

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

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

“Динамика” динамического программирования заключена в методе решения.

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

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

Динамическое программирование основывается на использовании принципа оптимальности, разработанного Р.Беллманом.

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

Этот принцип можно выразить рекуррентной формулой – уравнением Беллмана:

Fi (s)= min{[Сs,k + Fi−1(k )];[Сs,l + Fi−1(l)]}.

Здесь Fi (s) – целевая функция (стоимость, затраты, расстояние, тариф

и т.д.), на i– том этапе, начиная с которого до конца процесса осталось i этапов;

s – одно из начальных состояний системы на i– том этапе;

k, l – конечные состояния, системы на i–том этапе, или начальные состояния системы на ( i–1) этапе;

Сs,k , Сs,l – решения (тариф, затраты, расстояние и т.д.), принимаемые

на i– том этапе и переводящие систему из начального состояния s в конечное состояние k или l на данном этапе; Fi−1(k ), Fi−1(l) – целевые функции на (i–1)

этапе, соответствующие начальному состоянию системы k или l на этом этапе.

70

Согласно принципа оптимальности независимо от принятых решений Сs,k или Сs,l на i– м этапе последующие управления должны быть

оптимальными относительно состояний k или l, к которым придет система в конце данного этапа, т.е. целевые функции на последующем (i–1)-м этапе Fi−1(k ) и Fi−1(l) должны быть минимальными.

Т.к. буквой F в рекуррентной формуле обозначаются целевые функции всех этапов, то принцип оптимальности обязывает их быть оптимальными всюду. Для обеспечения оптимальности целевой функции Fi (s) на i–м этапе

в условиях s-го начального состояния ее необходимо минимизировать. Это значит из двух сумм в фигурных скобках выбрать наименьшую.

Уравнение Беллмана показывает, что оптимальная целевая функция Fi (s) на i–м этапе зависит не только от принятого решения Сs,k или Сs,l на

этом этапе, но и от последствий данного решения ( Fi−1(k ) или Fi−1(l)).

Но на данном i– том этапе существует не одно начальное состояние s, а несколько. Поэтому определяют оптимальные целевые функции Fi для

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

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

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

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

Если на последнем этапе i=1 (до конца процесса остался один этап) имеется три начальных состояния системы P, M, N и одно конечное состояние W (оно же конечное состояние системы в целом), то при естественном отсутствии последствий уравнения Беллмана принимают вид:

F1(P)=CP,W ; F1(M)= CM,W ; F1(N)=CN,W ;

Данные решения известны по условию задачи и они одновременно становятся условно-оптимальными целевыми функциями последнего этапа i=1.

71

На предпоследнем этапе i=2 (до конца процесса остается два этапа) составляют условно-оптимальные решения для каждого начального состояния этого этапа на основе уравнения Беллмана. Например, если на этапе i=2 одно из начальных состояний системы будет s, то для этого состояния уравнения Беллмана примет вид:

F2 (s)= min{[Сs,P + F1(P)];[Сs,M + F1(M)];[Сs,N + F1(N)]}.

Решения Сs,P ; Сs,M ; Сs,N известны по условию задачи, условно-

оптимальные целевые функции этапа i=1 определены в исследовании последнего этапа. Условно-оптимальная целевая функция этапа i=2 для начального условия s определяется по минимуму из трех сумм, стоящих в фигурных скобках. Здесь же определяется условно-оптимальное решение для начального состояния s этапа i=2.

Двигаясь от конца к началу, проводя аналогичные исследования, находят условно-оптимальные решения для каждого начального состояния

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

целевую функцию этапа i = n , а значит и безусловно оптимальное решение этапа i = n . Это будет одно из трех решений СA,B , СA,C или СA,D . Это решение позволяет однозначно определить начальное состояние следующего i = n −1 этапа, для которого ранее определены условно-оптимальные решения. Выбрав одно из них для получившегося однозначного начального состояния превращаем это условно-оптимальное решение в безусловнооптимальное.

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

72

оптимальное решение уже определены исследованиями при движении от конца к началу.

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

4.2.Решение типовой задачи

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

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

Пусть таких этапов будет пять (диаграмма на рис.4.1). Обозначим их индексом i и пронумеруем в обратном порядке: последний этап i=1, а начальный этап i=5.

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

Скорости движения в начале и конце каждого этапа обозначают латинскими буквами A, B, C, D, E, …., L, M, N, W. Не трудно видеть, что для режима ведения поезда, как исследуемой системы, эти буквы обозначают начальные и конечные состояния системы на соответствующих этапах.

73

i= 2 F2 (H)= min{[СH,L + F1(L)];[СH,M + F1(M)];[СH,N + F1(N)]}=

=min{[60 + 70];[50 + 60];[40 + 50]}= min{130;110;90}= 90

На этапе i = 2 в начальном состоянии Н условно-оптимальное решение на движение можно сформулировать так: нужно двигаться со скоростью Н в

74

начале и со скоростью N в конце этапа (СH,N ), при этом расходы на

передвижение с учетом оптимального решения на последнем этапе составят 90 единиц.

Условно-оптимальное решение (СH,N ). Соответствующая целевая функция F2 (H)= 90.

F2 (I)= min{[СI,L + F1(L)];[СI,M + F1(M)];[СI,N + F1(N)]}=

= min{[50 + 70];[40 + 60];[30 + 50]}= min{120;100; 80}=80

Условно-оптимальное решение– СI,N , F2 (I)=80.

F2 (K)= min{[СK,L + F1(L)];[СK,M + F1(M)];[СK,N + F1(N)]}=

= min{[70 + 70];[60 + 60];[50 + 50]}= min{140;120;100}=100

Условно-оптимальное решение– СK,N , F2 (K)=100.

Этап i =3

F3 (E)= min{[СE,H + F2 (H)];[СE,I + F2 (I)];[СE,K + F2 (K)]}=

= min{[40 + 90];[35 +80];[30 +100]}= min{130;115;130}=115

Условно-оптимальное решение– СE,I , F3 (E)=115 .

F3 (F)= min{[СF,H + F2 (H)];[СF,I + F2 (I)];[СF,K + F2 (K)]}=

= min{[60 + 90];[55 +80];[60 +100]}= min{150;135;160}=135

Условно-оптимальное решение– СF,I , F3 (F)=135

F3 (G)= min{[СG,H + F2 (H)];[СG,I + F2 (I)];[СG,K + F2 (K)]}=

= min{[70 + 90];[60 + 80];[50 +100]}= min{160;140;150}=140

Условно-оптимальное решение– СG,I , F3 (G)=140

Этап i = 4

F4 (B)= min{[СB,E + F3 (E)];[СB,F + F3 (F)];[СB,G + F3 (G)]}=

= min{[90 +115];[70 +135];[55 +140]}= min{205; 205;195}=195

Условно-оптимальное решение– СB,G , F4 (B)=195 .

F4 (C)= min{[СC,E + F3 (E)];[СC,F + F3 (F)];[СC,G + F3 (G)]}=

= min{[95 +115];[75 +135];[60 +140]}= min{210; 210; 200}= 200

Условно-оптимальное решение– СC,G , F4 (C)= 200.

F4 (D)= min{[СD,E + F3 (E)];[СD,F + F3 (F)];[СD,G + F3 (G)]}=

= min{[110 +115];[90 +135];[75 +140]}= min{225; 225; 215}= 215

Условно-оптимальное решение– СD,G , F4 (D)= 215.

На исходном этапе i = 5 начальное состояние одно, равное А. Поэтому уравнение Беллмана одно и решение из условно-оптимальных переходит в безусловно-оптимальное, т.к. выбора в условиях (начальных состояний) нет.

75