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

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

Рис. 13

а) Систему за n шагов нужно перевести из исходного состояния S₀ через несколько промежуточных состояний в конечное S_n под действием шаговых управлений.

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

в) Выбранное шаговое управление х_к оценивается частным критерием g_k, т.е. вычисляется значение g_k (х_к), называемое выигрышем на к-м шаге.

г) Требуется найти такой набор шаговых управлений (назовем его оптимальным), который обращает в максимум суммарный критерий G = g₁ + g₂ +…..g_n.

Замечание

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

Пример 1:

задача распределения средств.

Совет директоров фирмы рассматривает предложения по наращиванию производственных мощностей на четырех предприятиях фирмы. Для расширения производства совет директоров выделяет средства в объеме 200 млн. $.

Как же связаны дополнительные средства с наращиванием производственных мощностей?

Аналитиками фирмы составлена таблица, в которой указаны возможные приращения мощностей (в денежном выражении) в зависимости от выделенной предприятию суммы:

Табл.1

Клиент	g1	g2	g3	g4
Сумма

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

Рис. 14

Столбцы в табл. 1 это и есть частные критерии, оценивающие каждый шаг.

Следуя принципу Беллмана оптимизацию начинаем с последнего 4- го шага (почему?), затем 3-го и т.д.

1. Оптимизация 4-го шага, т.е. решение задачи:

max {g₄ (x₄) } = (обозначим)= Z ₄ (S₃) → табл. 2

Табл.2

x4							Z4 (S3)	x4^*
S3
		-	-	-	-	-
			-	-	-	-
				-	-	-
					-	-
						-

2. Оптимизация 3-го шага, т.е. решение задачи:

max {g₃ (x₃) + Z ₄ (S₂ - x₃) } = Z ₃ (S₂) → табл. 3

Табл.3

x3							Z3 (S2)	x3^*
S2
	0+0=0	-	-	-	-	-
	0+4=4	3+0=3	-	-	-	-
	0+6=6	3+4=7	4+0=4	-	-	-
	0+8=8	3+6=9	4+4=8	7+0=7	-	-
	0+13=13	3+8=11	4+6=10	7+4=11	11+0=11	-
	0+16=16	3+13=16	4+8=12	7+6=13	11+4=15	18+0=18

3. Оптимизация 2-го шага, т.е. решение задачи:

max {g₂ (x₂) + Z ₃ (S₁ - x₂) } = Z ₂ (S₁) → табл. 4

Табл.4

x2							Z2 (S1)	x2^*
S1
	0+0=0	-	-	-	-	-
	0+4=4	6+0=6	-	-	-	-
	0+7=7	6+4=10	9+0=9	-	-	-
	0+9=9	6+7=13	9+4=13	11+0=11	-	-
	0+13=13	6+9=15	9+7=16	11+4=15	13+0=13	-
	0+18=18	6+13=19	9+9=18	11+7=18	13+4=17	15+0=15

4. Оптимизация 1- го шага → табл.5

max {g ₁ (x₁) + Z ₂ (S₀ - x₁) } = Z ₁(S₀) → табл. 5

Табл.5

x1							Z1 (S0)	x1^*
S0
	0+19 =19	8+16=24	10+13=23	12+10=22	12+6=18	18+0=18

5. Обратный ход – окончательный оптимальный набор шаговых уравнений

40 80 40 40

S₀ → S₁ → S₂ → S₃ → S₄

200 160 80 40 0

ВЫВОД: ПЕРВОМУ КЛИЕНТУ ВЫДЕЛЯЕМ 40, ВТОРОМУ-

80, ТРЕТЬЕМУ- 40, ЧЕТВЕРТОМУ - 40.

Максимальная наращенная мощность 24.

Пример 2:

оптимизация на графе:

Транспортная сеть состоит 10 пунктов (рис. 7), некоторые из которых соединены магистралями. Стоимость проезда по каждой из магистралей отмечена на схеме. Найти оптимальный (самый дешевый) путь проезда от 1-го пункта в 10-й.(см. рис. на доске).

Решаем задачу методом динамического программирования.

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

Так пункты {7, 8, 9} S₁.

По аналогии пункты {5, 6} S₂, {2, 3, 4} S₃, {1} S₄.

Начинаем оптимизацию 1-го состояния (почему?).

В последний пункт можно попасть за один шаг из пунктов 7,8,9. Их стоимости (этих маршрутов) отмечены, а прямоугольниках. Так для пункта 5: min {6+9, 6+3} = 9. При этом ненужный путь зачеркиваем.

Далее оптимизируем 2-е состояние (с учетом принципа Беллмана).

В квадратных скобках пунктов 5, 6 отмечаем минимальную сумму попадания в конечный пункт с учетом оптимизации 1- го состояния (этого требует принцип Беллмана!). Продолжая оптимизацию, доходим до 4-го состояния.

Далее - обратный ход: отсекая бесперспективные ветви сети, прочитываем оптимальный путь:

1→ 4→ 6→ 8→ 10.

Рис. 15

Дата добавления: 2014-12-27