Раздел IV. Динамическое программирование.

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

Лучше много раз решить одну простую задачу, чем один раз сложную.

ЗАДАЧА 1. О наивыгоднейшем пути между двумя пунктами.

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

ПРИМЕР 4.1. Найти минимальный путь от А до В.

2 4 В

3 1 3

2 3

2 5 2

2 3

А

Последний шаг – достижение т.В. Перед последним шагом мы могли находиться в точках, откуда за один шаг можно достичь т.В. Таких точки две (система могла находиться в одном из двух состояний). Для каждой из них существует единственный вариант достижения т.В: для одной – двигаться на восток; для другой – на север. Запишем затраты 4 и 3 в каждом случае.

4

3

Теперь оптимизируем предпоследний шаг. После предыдущего шага мы могли оказаться в одной из трех точек: С₁, С₂, С₃.

Для т. С₁ существует единственное управление (пометим его стрелкой) – двигаться на восток, при этом затраты составят 2(на данном шаге)+4(на следующем шаге)=6. Аналогично для т. С₃ затраты составят 2+3=5. Для т.С₂ существует два управления: идти на восток или на север. В первом случае затраты составят 3+3=6, а во втором случае – 1+4=5. Значит условное оптимальное управление – идти на север. Пометим его стрелкой и занесем соответствующие затраты.

6

4

2 4

С₁

1 3

5

3

3

С₂

2

5

С₃

Далее «пятясь» от предпоследнего шага к первому, найдем оптимальные управления на каждом шаге (обозначим их стрелкой) и условный оптимальный расход (запишем его). Теперь прочитаем рекомендации на каждом шаге (куда указывают стрелки), начиная с первого (от т.А) и получим оптимальный путь. Затраты на его сооружение W=9

2 4

3 1 3

2 3

2 5 2

2 3

ЗАДАЧА 2. О загрузке машины (о рюкзаке).

Имеется N предметов. Известны вес a_i и ценность φ_i каждого предмета. Требуется заполнить рюкзак, способный вместить вес ≤ R, таким набором предметов, который обладал бы наибольшей ценностью.

Процесс загрузки рюкзака можно разбить на N шагов. На каждом шаге мы решаем вопрос: брать данный предмет или не брать? На каждом шаге имеется всего 2 управления: управление =1, если мы берем данный предмет; и 0 – если не берем.

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

АЛГОРИТМ.

1. Начнем с последнего шага. Сделаем различные предположения о свободном пространстве в рюкзаке: S=0,1,…R. Положим последний предмет в рюкзак, если в нем сводного пространства достаточно.

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

3. На первом шаге рассмотрим только единственно возможное состояние S=R.

4. Найдем решение, «пятясь назад», т.е. взяв оптимальное управление на первом шаге, изменим состояние системы на втором шаге: S=R–x₁ a₁ и выберем оптимальное управление х₂ для этого состояния. И т.д.

ПРИМЕР 4.2.

N=4, R=10

Исходные данные

	П1	П2	П3	П4
вес ai	1	3	5	7
стоимость i	2	5	7	10

Основная таблица

S	i=4		i=3		i=2		i=1
	x4	W4	x3	W3	x2	W2	x1	W1
0	0	0	0	0	0	0
1	0	0	0	0	0	0
2	0	0	0	0	0	0
3	0	0	0	0	1	5
4	0	0	0	0	1	5
5	0	0	1	7	0	7
6	0	0	1	7	0	7
7	1	10	0	10	0	10
8	1	10	0	10	1	12
9	1	10	0	10	1	12
10	1	10	0	10	1	15	0	15

Вспомогательная таблица.

состояния	x	а	S-а	i(x)	Wi+1(S-а)	i(x)+ Wi+1(S-а)
i=3 S=5	0 1	0 5	5 0	0 7	0 0	0 7
S=6	0 1	0 5	6 1	0 7	0 0	0 7
S=7	0 1	0 5	7 2	0 7	10 0	10 7
S=8	0 1	0 5	8 3	0 7	10 0	10 7
S=9	0 1	0 5	9 4	0 7	10 0	10 7
S=10	0 1	0 5	10 5	0 7	10 0	10 7
i=2 S=5	0 1	0 3	5 2	0 5	7 0	7 5
S=6	0 1	0 3	6 3	0 5	7 0	7 5
S=7	0 1	0 3	7 4	0 5	10 0	10 7
S=8	0 1	0 3	8 5	0 5	10 7	10 12
S=9	0 1	0 3	9 6	0 5	10 7	10 12
S=10	0 1	0 3	10 7	0 5	10 10	10 15
i=1 S=10	0 1	0 1	10 9	0 2	15 10	15 12

Ответ: x₄ =0; x₃ =1; x₂ =0; x₁ =1; W=15

ЗАДАЧА 3. О распределении ресурсов.

Имеется N предприятий П₁, П₂,… П_N, каждое из которого дает доход φ_k (x), если ему выделен ресурс в количестве x. Требуется имеющийся в количестве А ресурс распределить между объектами так, чтобы суммарный доход был максимальным.

Пусть x_k – количество ресурса, выделенное k-ому предприятию. Тогда рассматриваемая задача сводится к обычной задаче нелинейного программирования.

Сформулируем задачу, как задачу динамического программирования.

За первый шаг примем вложение средств в предприятие П₁, за второй – в П₂ и т.д. Управляемая система в данном случае – средства, которые распределяются. Состояние системы перед каждым шагом характеризуется одним параметром – наличным запасом еще не вложенных средств. В этой задаче шаговыми управлениями являются средства, выделяемые предприятиям. Требуется найти оптимальное управление (х₁, х₂,…х_N), при котором суммарный доход максимален:

ПРИМЕР 4.3.

N=3 R=5

x	1(x)	2(x)	3(x)
0	0	0	0
1	0,5	0,1	1
2	1	0,5	1
3	1	2	2
4	1,5	2	3
5	3	2,5	3

S	i=3		i=2		i=1
	x3	W3	x2	W2	x1	W1
0	0	0	0	0
1	1	1	0	1
2	2	1	1	1,1
3	3	2	0	2
4	4	3	0	3
5	5	3	1	3,1	1	3,5

состояния	x	S-x	i(x)	Wi+1(S-x)	i(x)+ Wi+1(S-x)
i=2 S=1	0 1	1 0	0 0,1	1 0	1 0,1
S=2	0 1 2	2 1 0	0 0,1 0,5	1 1 0	1 1,1 0,5
S=3	0 1 2 3	3 2 1 0	0 0,1 0,5 2	2 1 1 0	2 1,1 1,5 2
S=4	0 1 2 3 4	4 3 2 1 0	0 0,1 0,5 2 2	3 2 1 1 0	3 2,1 1,5 3 2
S=5	0 1 2 3 4 5	5 4 3 2 1 0	0 0,1 0,5 2 2 2,5	3 3 2 1 1 0	3 3,1 2,5 3 3 2,5
i=1 S=5	0 1 2 3 4 5	5 4 3 2 1 0	0 0,5 1 1 1,5 3	3,1 3 2 1,1 1 0	3,1 3,5 3 2,1 2,6 3

Ответ: x₁ =1; x₃ =0; x₃ =4; W=3,5

ОБОБЩЕННЫЙ АЛГОРИТМ

1. Описать систему. Т.е выяснить, какими параметрами характеризуется состояние управляемой системы перед каждым шагом. Важно уметь правильно и “скромно” поставить задачу, не переобременяя ее лишними подробностями, упрощая сколько возможно описание управляемой системы.

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

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

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

w_i=f_i (S, x_i)

5. Определить, как изменяется состояние системы под влиянием управления x_i на I-м шаге, т.е. записать функции изменения состояния.

S^/=φ_i (S, x_i)

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

W_i (S)= max{f_i (S,x_i)+W_i+1 (φ_i (S, x_i))}

x_i

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

W_m (S)= max{f_m (S, x_m)}

x_m

8. Произвести условную оптимизацию, начиная с предпоследнего и кончая первым шагом(пятясь назад).

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

ПРИНЦИП ОПТИМАЛЬНОСТИ. Каково бы ни было состояние системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

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

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