7. Динамическое программирование и потоки в сетях

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

7.1. Задача оптимизации многошаговых процессов, задача о ранце.

Задача оптимизации многошаговых процессов имеет вид

	(7.1)
при ограничениях
x0=0X0={0},	(7.2)
xi=f i(xi–1, ui), i=1,2,3,...,n,	(7.3)
xiXi , i= 1,2,3,...,n,	(7.4)
uiUi , i=1,2,3,...,n,	(7.5)
где Xi, Ui , i=1,2,3,...,n, – конечные множества.

Обозначим через W_i(x_i) максимум в следующей задаче:

при ограничениях
xiXi,
xk=f k(xk–1, uk), k=i+1,2,3,...,n,
xkXk , k=i+1,2,3,...,n,
ukUk , k=i+1,2,3,...,n,
где Xk, Uk , k=i+1,2,3,...,n, – конечные множества.

Справедливо следующее функциональное соотношение Беллмана:

Для того, чтобы решение ((x_i) _{i=0,1,2,...,n}, (u_i)_{i=1,2,3,...,n}), удовлетворяющее ограничениям (7.1) – (7.5) было оптимальным, необходимо и достаточно, чтобы

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

Алгоритм.

Первый этап.

1. Для всехxX_n положить W_n(x)=0;

2. Последовательно дляi=n–1, n–2, n–3,…,0 выполнить:

     для всех xX_i положить:

Второй этап.

1. Положить x₀:=₀;

2. Последовательно для i=1, 2,3,…,n положить :

Полученное в результате работы алгоритма решение ((x_i) _{i=0,1,2,...,n}, (u_i)_{i=1,2,3,...,n}) будет оптимальным для задачи (7.1) – (7.5). Оптимальное значение функционала будет равноW₀(₀).

Задача о ранце имеет вид

	(7.6)
при ограничениях
	(7.7)

где u_i–целые числа i =1,2,3,...,n. Числаa_iтакже будем рассматривать целыми, i=1,2,3,...,n.

Введем переменные x₀=0, . Из задачи (7.6) – (7.7) получим эквивалентную задачу

,	(7.8)
при ограничениях
x0=0,	(7.9)
xi=f(xi–1, ui)=xi–1+ai  ui,    i=1,2,3,..., n,	(7.10)
xiXi={0,1,2,...,b}, i=1,2,3,..., n,	(7.11)
uiUi={0,1,2,...,b}, i=1,2,3,..., n.	(7.12)

Задача (7.8) – (7.12) имеет такой же вид, как и задача (7.1) – (7.5), поэтому для ее решения можно применить алгоритм, описанный выше. Легко показать, что для задачи о ранце

при ограничениях

Соотношение Беллмана примет вид

где [a] – целая часть числаa.

Пример. Решить задачу:

u1	+2u2		max
2u1	+u2		3
u1, u2 – целые.

В этой задаче n=2,b=3, поэтому таблица с результатами вычислений будет иметь вид:

		i
		0		1		2
		W0	u1	W1	u2	W2
x	0	6	0	6	3	0
	1			4	2	0
	2			2	1	0
	3			0	0	0

Приведем пояснения к заполнению этой таблицы в соответствии с выполнением алгоритма.

Первый этап.

Заполнение столбца W₂понятно, оно соответствует выполнению пункта 1 первого этапа алгоритма. Покажем, как заполнялась клетка (x,i)=(0,1). Ее заполнение соответствует вычислению

для x=0, i=0,

или

В соответствии с этим, Так какW₂(x)0 (см. таблицу), то

Аналогично получены все остальные элементы этого столбца.

Покажем вычисления для клетки (0,0). Для нее

При u=0,

При u=1,

Таким образом, W₀(0)=6,u₁(0)=0.

Остальные клетки столбца 0 не заполняем, так как X₀={0}.

Второй этап.

1. x₀=0. (в следующей таблице клетка (0,0) выделена )

2. u₁=u₁(x₀)= u₁(0)=0,x₁=x₀+2 u₁=0 (клетка (0,1) выделена )

3. u₂=u₂(x1)= u₂(0)=3,x₂=x₁+1 u₂=3 (клетка (3,2) выделена )

		i
		0		1		2
		W0	u1	W1	u2	W2
x	0	6	0	6	3	0
	1			4	2	0
	2			2	1	0
	3			0	0	0

Ответ.Максимальное значение функционала в задаче равно 6,u₁=0,u₂=3.