Г Л А В А  6 МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ (ДП).

К оглавлению1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
17 

       

Общее понятие ДП.

 

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

 

                                                                                      m

                                                                          W  =  å wi                 -  аддитивный критерий.

                                                                                     i=1

 

     Пусть операция (задача) является управляемой, т.е. выбираются какие-то параметры, которые влияют на ход и исход. На каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом, - шаговое управление. Совокупность всех шаговых управлений  есть управление операцией (задачей) в целом. Обозначив его Х, а шаговое управление х1, x2, ..., хm, имеем:

 

                                                                      Х = (х1, x2, ..., хm),

 

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

Требуется найти такое управление Х,  при котором выигрыш W обращается в максимум:

 

                                                                                 m

                                                                       W = å wi      max.

                                                                               i=1

 

То x = x*, при котором это случается, называется оптимальным управлением:

 

                                                                  x* = (х1*, x2*, ..., хm*).

 

Пусть  W* = max {W(x)},  максимум  берется  по  всем  управлениям  х  (возможным  в  данных

                           x

условиях), т.е. возможна запись:

 

                                                                  W*  = max { W ( x ) }                       

                                                                              xX

 

П р и м е р :

Пусть ставится задача планирования деятельности k предприятий А1, A2, ..., Ак на m  лет  (т.е. на период  m хозяйственных лет). В начале периода на развитие группы выделяются средства M, которые нужно распределить между  Аi,  i = 1, 2, ..., k. В процессе работы предприятия часть вложенных средств частично расходуется (амортизируется), а часть средств сохраняется для последующего перераспределения.

Каждое предприятие за год приносит доход W, зависящий от того, сколько средств в него вложено.

В начале каждого года имеющиеся в наличии средства перераспределяются между предприятиями.

Какое количество средств нужно выделить каждому предприятию, чтобы суммарный доход за m лет был максимальным?

Суммарный доход W (выигрыш) есть сумма дохода на отдельных шагах (годах):

 

                                                                                           m

                                                                               W  =   å wi,

                                                                                          i=1

т.е. в наличии свойство аддитивности.

Управление xi на i-ом шаге состоит в том , что в начале  i-го года предприятиям Аi (i = 1,....,k) выделяются какие-то средства  хi1, xi2, ..., xik, т.е. шаговое управление есть вектор с к  составляющими:

 

                                                                          xi = (xi1, xi2, ..., xik).

 

Величина wi зависит от количества вложенных в предприятие средств. Управление всей операцией есть совокупность всех шаговых управлений:

 

                                                                          х = (х1, x2, ..., хm).

 

Требуется найти такое распределение средств по Аi (i = 1, 2,..., k) и по годам (m = 1,2,..., m) (оптимальное управление х*),  при котором W обращается в максимум.

 

Принцип решения задачи ДП.

 

Любую многошаговую задачу можно решить следующими способами:

- либо искать все элементы решения сразу на m шагах;

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

Именно последний путь оптимизации лежит в основе метода ДП - пошаговая оптимизация.

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

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

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

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

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

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

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

Следовательно, процесс ДП обычно разворачивается от конца к началу, т.е. сначала планируется m-й шаг. Но как его спланировать, если не знаем чем кончается предпоследний шаг. Как быть?

Планируя последний шаг, нужно сделать разные предположения о том, чем кончится предпоследний (m-1)-й  шаг , и для каждого из этих предположений найти условное оптимальное управление на m-ом шаге [условное, так как оно выбирается, исходя из условия, что предпоследний шаг кончился так-то и так-то (каким-то образом)].

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

Теперь можно оптимизировать управление на предпоследнем (m-1)-ом шаге. Снова делаем возможные предположения о том, чем может кончиться предыдущий (m-2)-й шаг и для каждого из этих предположений находим такое управление на (m-1)-ом шаге, при котором выигрыш за последние два шага ( m-й уже оптимизирован) максимален. Так находятся для каждого исхода (m-2)-го шага условное оптимальное управление на (m-1)-м шаге и условный оптимальный выигрыш на двух последних шагах. И так, "пятясь назад", оптимизируем управление на (m-2)-м шаге и т.д., пока не дойдем до первого. Предположим, что все условные оптимальные управления и выигрыши за весь" хвост" процесса (на всех шагах, начиная от данного и до конца) известны. Теперь можно найти не условные оптимальные управления x*  и  w*.

Действительно, пусть известно, что в каком-то состоянии S0 управляемая система (объект управления S) была в начале первого шага. Тогда можно выбрать оптимальное управление х1* на первом шаге. Применив его, меняем состояние системы на некоторое новое S1*. В  этом состоянии подходим ко второму шагу. Тогда тоже известно условное оптимальное управление x2*, которое к концу второго шага переводит систему в состояние S2* и т.д. Оптимальный выигрыш w* за всю операцию известен, так как именно на основе его максимальности выбиралось управление на первом шаге.

Таким образом, в процессе оптимизации управления методом ДП многошаговый процесс "проходится" дважды:

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

     - от начала к концу - осуществляется "чтение" уже готовых рекомендаций и поиск безусловного оптимального управления x*, состоящего из оптимальных шаговых управлений x1*, x2*, ..., xm*.

                

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

 

Пусть имеем некий запас ресурсов (средств) К, который нужно распределить между   предприятиями А1,A2, ..., Аm. Каждое i-ое предприятие при вложении в него каких-то средств x приносит доход в виде функции ji(x)  i = 1,2,..., m. Все ji(x) заданы (пусть они неубывающие). Как распределить средства К между Ai (i=1,2, ..., m), чтобы в сумме они дали максимальный доход?

Здесь нет параметра времени. Однако, операцию распределения средств можно мысленно развернуть в какой-то последовательности, считая за первый шаг вложение в предприятие А1, за второй - вложение в предприяие А2  и  т.д.

Управляемая система S в данном случае - это ресурсы (средства). Состояние системы S перед каждым шагом характеризуется одним числом S -наличным запасом еще не вложенных средств.

Шаговыми управлениями являются средства x1, x2, ..., xm, выделяемые конкретным предприятиям.

Требуется найти оптимальное управление, т.е. совокупность x1, x2, ..., xm, при которой суммарный доход максимален:

                                                                                  m

                                                                      W  =  å  ji(xi)      max.

                                                                                 i=1  

 

Решение в общем виде.

 

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

Начинаем оптимизацию с последнего m-го шага.

Пусть подошли к этому шагу с остатком средств S. Вкладываем всю сумму S целиком в предприятие Аm. Следовательно, условное оптимальное управление на m-м шаге: отдать последнему предприятию все имеющиеся средства S:

 

                                                                            xm(S) = S,

 

а условный оптимальный выигрыш:

 

                                                                        wm(S) = m(S).

 

Задаваясь последовательностью значений S (располагая их достаточно тесно), для каждого значения S будем знать xm(S) и  wm(S). Последний шаг оптимизирован.

Переходим к предпоследнему (m-1)-му шагу. Пусть подошли к нему с запасом средств S. Обозначим wm-1(S)  условный оптимальный выигрыш на двух последних шагах: ( m-1)- ом и  m-ом (последний оптимизирован). Если на (m-1)-м шаге  (m-1)-му предприятию выделим средств x, то на последний останется S -x.  Выигрыш на двух последних шагах будет

 

                                                                    m-1(x) + wm(S-x)

 

и нужно найти такое x, при котором этот выигрыш максимален:

  

                                                  wm-1(S) = max { m-1(x) + wm(S-x) }

                                                                     x S

Знак  max означает, что берется максимальное значение по всем x,  какие только возможны:

 

x S

 

(вложить больше,  чем S нельзя) от выражения в { }. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а то значение x, при котором max достигается - условное оптимальное управление на (m-1)-ом шаге.

Далее оптимизируем (m-2)-й, (m-3)-й и  т.д. шаги. Для любого i-го шага условный оптимальный выигрыш за все шаги с этого и до конца находятся по формуле:

 

                                                   wi(S) = max { i(x) + wi+1(S-x) }

                                                                 x S

 

и соответствующее ему условное оптимальное управление xi(S) - то значение x, при котором  этот  максимум достигается.

Продолжая этот процесс, доходим до первого предприятия А1. Варьировать значениями S нет нужды, так как знаем, что запас средств перед первым шагом есть К,  т.е.:

 

                                                 w* = w1(K) = max { 1(x) + w2(K-x) }.

                                                                        x K

 

Итак, максимальный выигрыш(доход) от всех предприятий найден. Значение x, при котором достигается max в последнем соотношении и есть оптимальное управление x1* на первом шаге.

После того, как эти средства вложены в первое предприятие, остается К-x1*. Читая рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств:

 

                                                                Х2* = Х2 (К - x1*)

 

и т.д. до конца.

 

Числовой пример.

 

Пусть К=10, m =5. Вкладываются только целые количества средств. Функции ji(x) заданы таблицей:

      

x

1(x)

2(x)

3(x) 

4(x)

 5(x)

1

0.5

0.1

0.6

0.3 

1.0

2

1.0 

0.5

1.1

0.6

1.2

3

1.4

1.2

1.2

1.3

1.3

4

2.0

1.8

1.4

1.4

1.3

5

2.5

2.5

1.6

1.5

1.3

6

2.8

2.9

1.7

1.5

1.3

7

3.0

3.5

1.8

1.5

1.3

8

3.0

3.5

1.8

1.5 

1.3

 

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

Проводим условную оптимизацию, начиная с 5-го шага.

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

В следующей таблице даны результаты условной оптимизации по всем шагам. Таблица построена так:  в первом столбце - значение запаса средств S, с которым подходим к данному шагу. Далее пять пар столбцов  - соответствующие номеру шага значения xi и wi.

 

S

i = 5

i = 4

i = 3

i = 2

i = 1

 

x5(S)

w5(S)

x4(S)

w4(S)

x3(S)

w3(S)

x2(S)

w2(S)

x1(S)

w1(S)

1

1

1.0

0

1.0

0

1.0

0

1.0

 

 

2

2

1.2

1

1.3

1

1.6

0

1.6

 

 

3

3

1.3

2

1.6

2

2.1

0

2.1

 

 

4

4

1.3

3

2.3

2

2.4

0

2.4

 

 

5

5

1.3

3

2.5

1

2.9

0

2.9

 

 

6

6

1.3

4

2.6

2

3.4

5

3.5

 

 

7

7

1.3

5

2.7

2

3.6

5

4.1

 

 

8

8

1.3

5

2.8

4

3.7

5

4.6

 

 

9

9

1.3

6

2.8

5

3.9

7

5.1

 

 

10

10

1.3

7

2.8

5

4.1

7

5.6

2

5.6

 

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

В результате последовательной оптимизации 5-го, 4-го, ... и 1-го шагов получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W* за всю операцию - он равен 5.6.

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

Объяснение заполнения  предыдущей таблицы. Образец  расчета.

Пусть нужно оптимизировать решение x3(7) - как  поступить на

третьем шаге, если подошли к нему с запасом средств S = 7 и сколько максимум можно выиграть на всех оставшихся шагах, включая третий. Пусть все шаги после третьего ( 4 и 5-й) уже оптимизированы, т.е. заполнены две пары столбцов таблицы. Найдем x3(7) и  w3(7). Составляем вспомогательную таблицу:

 

x

7 - x

3(x)

w4(7 - x)

3(x) + w4(7 - x)

7

0

1.8

0

1.8

6

1

1.7

1.0

2.7

5

2

1.6

1.3

2.9

4

3

1.4

1.6

3.0

3

4

1.2

2.3

3.5

2

5

1.1

2.5

3.6

1

6

0.6

2.6

3.2

0

7

0

2.7

2.7

 

В первом столбце даны всевозможные вложения x на третьем шаге, не превосходящие S=7. Второй столбец - это то, что остается от S=7. Третий - это выигрыш на третьем шаге от вложения средств x в А3 по столбцу j3(x) из первой таблицы. Четвертый столбец - это оптимальный выигрыш на всех оставшихся шагах (4-м и 5-м) при условии, что подошли к четвертому шагу с оставшимися средствами (заполняется по столбцу i=4 второй таблицы). В пятом столбце - сумма двух выигрышей: шагового и оптимизированного  при данном вложении x в третий шаг.

Из всех выигрышей последнего столбца выбирается максимальный w3(7) = 3.6, тогда соответствующее управление x(7) = 2.  Вопрос: Если в третьей таблице max достигается не при одном x?

     Ответ: Все равно какое брать. Выигрыш от этого не зависит.

     Вообще в задачах ДП решение может быть не единственным.

 

 

 

Практические  рекомендации  по  постановке задач ДП.

 

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

2. Расчленить операцию (задачу) на этапы (шаги).

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

4. Определить, какой выигрыш приносит на i-м шаге управления xi, если перед этим система была в состоянии S,  т.е.  записать "функции выигрыша":

 

                                                                            wi = fi(S,xi )                                          (7.1)

 

5. Определить, как изменяется состояние S системы под влиянием управления xi на i-м шаге;  оно переходит в новое состояние:

 

                                                                            S = i(S,xi)                                          (7.2)

 

Эти функции изменения состояния тоже должны быть записаны.

6. Записать основное рекурентное уравнение ДП, выражающее условный оптимальный выигрыш wi(S) (начиная с i-го шага и до конца) через уже известную функцию wi+1(S):

 

                                                            wi(S) = max{fi(S,xi) + wi+1(i(S,xi))}            (7.3)

                                                                            xi

 

Этому выигрышу соответствует условное оптимальное управление на i-м шаге xi(S) (в уже известную функцию wi+1(S)  нужно вместо S подставить измененное состояние S = i(S,xi).

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

 

                                                                       wm(S) = max { fm(S,xm) },

                                                                                        xm

                                                                                                                                                                                                        и находя условное оптимальное управление xm(S) , для которого  этот максимум достигается.

8. Провести условную оптимизацию  (m - 1)-го, (m - 2)-го и т.д. шагов по  формуле (7.3), полагая в ней i = (m - 1), (m - 2), ... и для каждого из шагов указать условное оптимальное xi(S), при  котором достигается максимум. Если состояние системы в начальный момент известно (что является обычным), то на первом шаге варьировать состояние системы не нужно - сразу находится оптимальный выигрыш для данного начального состояния S0. Это и есть оптимальный выигрыш за всю операцию:

 

                                                                                    w* = w1(S)

 

9. Провести безусловную оптимизацию управления, "читая" соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге x1* = x1(S0), изменить состояние системы по формуле (7.2), для вновь найденного состояния найти оптимальное управление на втором шаге x2*  и т.д. до конца.

 

З А Д А Ч И   П О   Т Е М Е

ЗАДАЧА 6.1.

Судно грузоподъемностью 10 т должно быть загружено ящиками 3-х типов. Масса ящика первого типа 860 кг, а стоимость 516 руб., масса ящика второго типа 720 кг, стоимость - 360 руб., масса ящика третьего типа 600 кг, стоимость - 240 руб. Необходимо так выбрать количество ящиков каждого типа, чтобы стоимость груза на судне была наибольшей.

Ответ: u1 = 10, u2 = 1, u3 = 1, Fmax = 5760.

ЗАДАЧА 6.2.

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

начальная сумма x1 = 300 тыс. руб.;

вложенная сумма u на предприятии П1 приносит доход f1(u) и возвращается в конце года в сумме j1(u) = 0.6u, а на предприятии П2 приносит доход f2(u) и возвращается в конце года в сумме j2(u) = 0.4u;

ежегодно распределяются все наличные средства;

функции f1 и f2 определены в следующей таблице.

 

u  

50

100

150

200

250

300

f1

6

10

16

24

28

30

f2

10

16

24

28

30

32

 

Ответ: x1 = 300, x2 = 160, x3 = 64, u1 = 200, u2 = 0, u3 = 0, Fmax = 77.

ЗАДАЧА 6.3.     

Средства предприятия в количестве 100 единиц делятся между тремя цехами. Прибыль от  производства k-го цеха при выделении ему  u = uk средств оценивается функцией fk(u), где f1(u) = 0.2u, f2(u) = 0.3u, f3(u) = 0.4u. На вкладываемые средства накладывается ограничение

 

u1 + 2u2 + 3u3 = 150.

 

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

Ответ: Pmax = 25, u1 = 75, u2 = 0,  u3 = 25.

ЗАДАЧА 6.4.

Имеются два склада и три потребителя. На первом складе хранится 50 т продукции, на втором - 40 т. На первый пункт потребления должно быть доставлено 30 т продукции, на второй - 20 т, на третий - 40 т. Известно, что стоимость перевозки u т  продукции с i-го склада на j-ый пункт потребления равна fij(u) (i = 1, 2; j = 1, 2, 3), где

 

f11(u) = u,  f21(u) = 0.1u2,  f12(u) = 2u,  f22(u) = 0.2u2,  f13(u) = 0.1u2,  f23(u) = 1.2u.

 

Определить количество продукции yij (i = 1, 2; j = 1, 2, 3), которое нужно отправить с i-го склада на j-ый пункт потребления таким образом, чтобы суммарная стоимость перевозки была минимальной.

Ответ: y11 = 27, y21 = 3, y12 = 16, y22 = 4, y13 = 7, y23 = 33, Fmin = 101.

 

 

    

       

Общее понятие ДП.

 

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

 

                                                                                      m

                                                                          W  =  å wi                 -  аддитивный критерий.

                                                                                     i=1

 

     Пусть операция (задача) является управляемой, т.е. выбираются какие-то параметры, которые влияют на ход и исход. На каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом, - шаговое управление. Совокупность всех шаговых управлений  есть управление операцией (задачей) в целом. Обозначив его Х, а шаговое управление х1, x2, ..., хm, имеем:

 

                                                                      Х = (х1, x2, ..., хm),

 

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

Требуется найти такое управление Х,  при котором выигрыш W обращается в максимум:

 

                                                                                 m

                                                                       W = å wi      max.

                                                                               i=1

 

То x = x*, при котором это случается, называется оптимальным управлением:

 

                                                                  x* = (х1*, x2*, ..., хm*).

 

Пусть  W* = max {W(x)},  максимум  берется  по  всем  управлениям  х  (возможным  в  данных

                           x

условиях), т.е. возможна запись:

 

                                                                  W*  = max { W ( x ) }                       

                                                                              xX

 

П р и м е р :

Пусть ставится задача планирования деятельности k предприятий А1, A2, ..., Ак на m  лет  (т.е. на период  m хозяйственных лет). В начале периода на развитие группы выделяются средства M, которые нужно распределить между  Аi,  i = 1, 2, ..., k. В процессе работы предприятия часть вложенных средств частично расходуется (амортизируется), а часть средств сохраняется для последующего перераспределения.

Каждое предприятие за год приносит доход W, зависящий от того, сколько средств в него вложено.

В начале каждого года имеющиеся в наличии средства перераспределяются между предприятиями.

Какое количество средств нужно выделить каждому предприятию, чтобы суммарный доход за m лет был максимальным?

Суммарный доход W (выигрыш) есть сумма дохода на отдельных шагах (годах):

 

                                                                                           m

                                                                               W  =   å wi,

                                                                                          i=1

т.е. в наличии свойство аддитивности.

Управление xi на i-ом шаге состоит в том , что в начале  i-го года предприятиям Аi (i = 1,....,k) выделяются какие-то средства  хi1, xi2, ..., xik, т.е. шаговое управление есть вектор с к  составляющими:

 

                                                                          xi = (xi1, xi2, ..., xik).

 

Величина wi зависит от количества вложенных в предприятие средств. Управление всей операцией есть совокупность всех шаговых управлений:

 

                                                                          х = (х1, x2, ..., хm).

 

Требуется найти такое распределение средств по Аi (i = 1, 2,..., k) и по годам (m = 1,2,..., m) (оптимальное управление х*),  при котором W обращается в максимум.

 

Принцип решения задачи ДП.

 

Любую многошаговую задачу можно решить следующими способами:

- либо искать все элементы решения сразу на m шагах;

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

Именно последний путь оптимизации лежит в основе метода ДП - пошаговая оптимизация.

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

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

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

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

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

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

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

Следовательно, процесс ДП обычно разворачивается от конца к началу, т.е. сначала планируется m-й шаг. Но как его спланировать, если не знаем чем кончается предпоследний шаг. Как быть?

Планируя последний шаг, нужно сделать разные предположения о том, чем кончится предпоследний (m-1)-й  шаг , и для каждого из этих предположений найти условное оптимальное управление на m-ом шаге [условное, так как оно выбирается, исходя из условия, что предпоследний шаг кончился так-то и так-то (каким-то образом)].

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

Теперь можно оптимизировать управление на предпоследнем (m-1)-ом шаге. Снова делаем возможные предположения о том, чем может кончиться предыдущий (m-2)-й шаг и для каждого из этих предположений находим такое управление на (m-1)-ом шаге, при котором выигрыш за последние два шага ( m-й уже оптимизирован) максимален. Так находятся для каждого исхода (m-2)-го шага условное оптимальное управление на (m-1)-м шаге и условный оптимальный выигрыш на двух последних шагах. И так, "пятясь назад", оптимизируем управление на (m-2)-м шаге и т.д., пока не дойдем до первого. Предположим, что все условные оптимальные управления и выигрыши за весь" хвост" процесса (на всех шагах, начиная от данного и до конца) известны. Теперь можно найти не условные оптимальные управления x*  и  w*.

Действительно, пусть известно, что в каком-то состоянии S0 управляемая система (объект управления S) была в начале первого шага. Тогда можно выбрать оптимальное управление х1* на первом шаге. Применив его, меняем состояние системы на некоторое новое S1*. В  этом состоянии подходим ко второму шагу. Тогда тоже известно условное оптимальное управление x2*, которое к концу второго шага переводит систему в состояние S2* и т.д. Оптимальный выигрыш w* за всю операцию известен, так как именно на основе его максимальности выбиралось управление на первом шаге.

Таким образом, в процессе оптимизации управления методом ДП многошаговый процесс "проходится" дважды:

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

     - от начала к концу - осуществляется "чтение" уже готовых рекомендаций и поиск безусловного оптимального управления x*, состоящего из оптимальных шаговых управлений x1*, x2*, ..., xm*.

                

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

 

Пусть имеем некий запас ресурсов (средств) К, который нужно распределить между   предприятиями А1,A2, ..., Аm. Каждое i-ое предприятие при вложении в него каких-то средств x приносит доход в виде функции ji(x)  i = 1,2,..., m. Все ji(x) заданы (пусть они неубывающие). Как распределить средства К между Ai (i=1,2, ..., m), чтобы в сумме они дали максимальный доход?

Здесь нет параметра времени. Однако, операцию распределения средств можно мысленно развернуть в какой-то последовательности, считая за первый шаг вложение в предприятие А1, за второй - вложение в предприяие А2  и  т.д.

Управляемая система S в данном случае - это ресурсы (средства). Состояние системы S перед каждым шагом характеризуется одним числом S -наличным запасом еще не вложенных средств.

Шаговыми управлениями являются средства x1, x2, ..., xm, выделяемые конкретным предприятиям.

Требуется найти оптимальное управление, т.е. совокупность x1, x2, ..., xm, при которой суммарный доход максимален:

                                                                                  m

                                                                      W  =  å  ji(xi)      max.

                                                                                 i=1  

 

Решение в общем виде.

 

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

Начинаем оптимизацию с последнего m-го шага.

Пусть подошли к этому шагу с остатком средств S. Вкладываем всю сумму S целиком в предприятие Аm. Следовательно, условное оптимальное управление на m-м шаге: отдать последнему предприятию все имеющиеся средства S:

 

                                                                            xm(S) = S,

 

а условный оптимальный выигрыш:

 

                                                                        wm(S) = m(S).

 

Задаваясь последовательностью значений S (располагая их достаточно тесно), для каждого значения S будем знать xm(S) и  wm(S). Последний шаг оптимизирован.

Переходим к предпоследнему (m-1)-му шагу. Пусть подошли к нему с запасом средств S. Обозначим wm-1(S)  условный оптимальный выигрыш на двух последних шагах: ( m-1)- ом и  m-ом (последний оптимизирован). Если на (m-1)-м шаге  (m-1)-му предприятию выделим средств x, то на последний останется S -x.  Выигрыш на двух последних шагах будет

 

                                                                    m-1(x) + wm(S-x)

 

и нужно найти такое x, при котором этот выигрыш максимален:

  

                                                  wm-1(S) = max { m-1(x) + wm(S-x) }

                                                                     x S

Знак  max означает, что берется максимальное значение по всем x,  какие только возможны:

 

x S

 

(вложить больше,  чем S нельзя) от выражения в { }. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а то значение x, при котором max достигается - условное оптимальное управление на (m-1)-ом шаге.

Далее оптимизируем (m-2)-й, (m-3)-й и  т.д. шаги. Для любого i-го шага условный оптимальный выигрыш за все шаги с этого и до конца находятся по формуле:

 

                                                   wi(S) = max { i(x) + wi+1(S-x) }

                                                                 x S

 

и соответствующее ему условное оптимальное управление xi(S) - то значение x, при котором  этот  максимум достигается.

Продолжая этот процесс, доходим до первого предприятия А1. Варьировать значениями S нет нужды, так как знаем, что запас средств перед первым шагом есть К,  т.е.:

 

                                                 w* = w1(K) = max { 1(x) + w2(K-x) }.

                                                                        x K

 

Итак, максимальный выигрыш(доход) от всех предприятий найден. Значение x, при котором достигается max в последнем соотношении и есть оптимальное управление x1* на первом шаге.

После того, как эти средства вложены в первое предприятие, остается К-x1*. Читая рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств:

 

                                                                Х2* = Х2 (К - x1*)

 

и т.д. до конца.

 

Числовой пример.

 

Пусть К=10, m =5. Вкладываются только целые количества средств. Функции ji(x) заданы таблицей:

      

x

1(x)

2(x)

3(x) 

4(x)

 5(x)

1

0.5

0.1

0.6

0.3 

1.0

2

1.0 

0.5

1.1

0.6

1.2

3

1.4

1.2

1.2

1.3

1.3

4

2.0

1.8

1.4

1.4

1.3

5

2.5

2.5

1.6

1.5

1.3

6

2.8

2.9

1.7

1.5

1.3

7

3.0

3.5

1.8

1.5

1.3

8

3.0

3.5

1.8

1.5 

1.3

 

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

Проводим условную оптимизацию, начиная с 5-го шага.

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

В следующей таблице даны результаты условной оптимизации по всем шагам. Таблица построена так:  в первом столбце - значение запаса средств S, с которым подходим к данному шагу. Далее пять пар столбцов  - соответствующие номеру шага значения xi и wi.

 

S

i = 5

i = 4

i = 3

i = 2

i = 1

 

x5(S)

w5(S)

x4(S)

w4(S)

x3(S)

w3(S)

x2(S)

w2(S)

x1(S)

w1(S)

1

1

1.0

0

1.0

0

1.0

0

1.0

 

 

2

2

1.2

1

1.3

1

1.6

0

1.6

 

 

3

3

1.3

2

1.6

2

2.1

0

2.1

 

 

4

4

1.3

3

2.3

2

2.4

0

2.4

 

 

5

5

1.3

3

2.5

1

2.9

0

2.9

 

 

6

6

1.3

4

2.6

2

3.4

5

3.5

 

 

7

7

1.3

5

2.7

2

3.6

5

4.1

 

 

8

8

1.3

5

2.8

4

3.7

5

4.6

 

 

9

9

1.3

6

2.8

5

3.9

7

5.1

 

 

10

10

1.3

7

2.8

5

4.1

7

5.6

2

5.6

 

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

В результате последовательной оптимизации 5-го, 4-го, ... и 1-го шагов получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W* за всю операцию - он равен 5.6.

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

Объяснение заполнения  предыдущей таблицы. Образец  расчета.

Пусть нужно оптимизировать решение x3(7) - как  поступить на

третьем шаге, если подошли к нему с запасом средств S = 7 и сколько максимум можно выиграть на всех оставшихся шагах, включая третий. Пусть все шаги после третьего ( 4 и 5-й) уже оптимизированы, т.е. заполнены две пары столбцов таблицы. Найдем x3(7) и  w3(7). Составляем вспомогательную таблицу:

 

x

7 - x

3(x)

w4(7 - x)

3(x) + w4(7 - x)

7

0

1.8

0

1.8

6

1

1.7

1.0

2.7

5

2

1.6

1.3

2.9

4

3

1.4

1.6

3.0

3

4

1.2

2.3

3.5

2

5

1.1

2.5

3.6

1

6

0.6

2.6

3.2

0

7

0

2.7

2.7

 

В первом столбце даны всевозможные вложения x на третьем шаге, не превосходящие S=7. Второй столбец - это то, что остается от S=7. Третий - это выигрыш на третьем шаге от вложения средств x в А3 по столбцу j3(x) из первой таблицы. Четвертый столбец - это оптимальный выигрыш на всех оставшихся шагах (4-м и 5-м) при условии, что подошли к четвертому шагу с оставшимися средствами (заполняется по столбцу i=4 второй таблицы). В пятом столбце - сумма двух выигрышей: шагового и оптимизированного  при данном вложении x в третий шаг.

Из всех выигрышей последнего столбца выбирается максимальный w3(7) = 3.6, тогда соответствующее управление x(7) = 2.  Вопрос: Если в третьей таблице max достигается не при одном x?

     Ответ: Все равно какое брать. Выигрыш от этого не зависит.

     Вообще в задачах ДП решение может быть не единственным.

 

 

 

Практические  рекомендации  по  постановке задач ДП.

 

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

2. Расчленить операцию (задачу) на этапы (шаги).

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

4. Определить, какой выигрыш приносит на i-м шаге управления xi, если перед этим система была в состоянии S,  т.е.  записать "функции выигрыша":

 

                                                                            wi = fi(S,xi )                                          (7.1)

 

5. Определить, как изменяется состояние S системы под влиянием управления xi на i-м шаге;  оно переходит в новое состояние:

 

                                                                            S = i(S,xi)                                          (7.2)

 

Эти функции изменения состояния тоже должны быть записаны.

6. Записать основное рекурентное уравнение ДП, выражающее условный оптимальный выигрыш wi(S) (начиная с i-го шага и до конца) через уже известную функцию wi+1(S):

 

                                                            wi(S) = max{fi(S,xi) + wi+1(i(S,xi))}            (7.3)

                                                                            xi

 

Этому выигрышу соответствует условное оптимальное управление на i-м шаге xi(S) (в уже известную функцию wi+1(S)  нужно вместо S подставить измененное состояние S = i(S,xi).

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

 

                                                                       wm(S) = max { fm(S,xm) },

                                                                                        xm

                                                                                                                                                                                                        и находя условное оптимальное управление xm(S) , для которого  этот максимум достигается.

8. Провести условную оптимизацию  (m - 1)-го, (m - 2)-го и т.д. шагов по  формуле (7.3), полагая в ней i = (m - 1), (m - 2), ... и для каждого из шагов указать условное оптимальное xi(S), при  котором достигается максимум. Если состояние системы в начальный момент известно (что является обычным), то на первом шаге варьировать состояние системы не нужно - сразу находится оптимальный выигрыш для данного начального состояния S0. Это и есть оптимальный выигрыш за всю операцию:

 

                                                                                    w* = w1(S)

 

9. Провести безусловную оптимизацию управления, "читая" соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге x1* = x1(S0), изменить состояние системы по формуле (7.2), для вновь найденного состояния найти оптимальное управление на втором шаге x2*  и т.д. до конца.

 

З А Д А Ч И   П О   Т Е М Е

ЗАДАЧА 6.1.

Судно грузоподъемностью 10 т должно быть загружено ящиками 3-х типов. Масса ящика первого типа 860 кг, а стоимость 516 руб., масса ящика второго типа 720 кг, стоимость - 360 руб., масса ящика третьего типа 600 кг, стоимость - 240 руб. Необходимо так выбрать количество ящиков каждого типа, чтобы стоимость груза на судне была наибольшей.

Ответ: u1 = 10, u2 = 1, u3 = 1, Fmax = 5760.

ЗАДАЧА 6.2.

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

начальная сумма x1 = 300 тыс. руб.;

вложенная сумма u на предприятии П1 приносит доход f1(u) и возвращается в конце года в сумме j1(u) = 0.6u, а на предприятии П2 приносит доход f2(u) и возвращается в конце года в сумме j2(u) = 0.4u;

ежегодно распределяются все наличные средства;

функции f1 и f2 определены в следующей таблице.

 

u  

50

100

150

200

250

300

f1

6

10

16

24

28

30

f2

10

16

24

28

30

32

 

Ответ: x1 = 300, x2 = 160, x3 = 64, u1 = 200, u2 = 0, u3 = 0, Fmax = 77.

ЗАДАЧА 6.3.     

Средства предприятия в количестве 100 единиц делятся между тремя цехами. Прибыль от  производства k-го цеха при выделении ему  u = uk средств оценивается функцией fk(u), где f1(u) = 0.2u, f2(u) = 0.3u, f3(u) = 0.4u. На вкладываемые средства накладывается ограничение

 

u1 + 2u2 + 3u3 = 150.

 

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

Ответ: Pmax = 25, u1 = 75, u2 = 0,  u3 = 25.

ЗАДАЧА 6.4.

Имеются два склада и три потребителя. На первом складе хранится 50 т продукции, на втором - 40 т. На первый пункт потребления должно быть доставлено 30 т продукции, на второй - 20 т, на третий - 40 т. Известно, что стоимость перевозки u т  продукции с i-го склада на j-ый пункт потребления равна fij(u) (i = 1, 2; j = 1, 2, 3), где

 

f11(u) = u,  f21(u) = 0.1u2,  f12(u) = 2u,  f22(u) = 0.2u2,  f13(u) = 0.1u2,  f23(u) = 1.2u.

 

Определить количество продукции yij (i = 1, 2; j = 1, 2, 3), которое нужно отправить с i-го склада на j-ый пункт потребления таким образом, чтобы суммарная стоимость перевозки была минимальной.

Ответ: y11 = 27, y21 = 3, y12 = 16, y22 = 4, y13 = 7, y23 = 33, Fmin = 101.