Зенкевич Н.А. Практикум по исследованию операций
Подождите немного. Документ загружается.
4.2. ЗАДАЧА О КОММИВОЯЖЕРЕ 111
4.2.13
∞ 19 25 11 2 35
37 ∞ 26 58 21 43
10 50 ∞ 39 22 3
38 39 24 ∞ 38 45
27 9 32 9 ∞ 2
33 48 60 53 1 ∞
4.2.14
∞ 21 40 28 60 52
58 ∞ 11 39 22 56
22 12 ∞ 23 14 19
25 47 51 ∞ 20 54
47 43 18 42 ∞ 52
44 49 50 52 29 ∞
112 Глава 4. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ
Глава 5
Динамическое программирование
5.1 Многошаговый управляемый детерминированный
процесс принятия решения. Уравнение Беллмана
Методы динамического программирования применяются как в задачах оптимального
управления и планирования, так и при решении различных технических проблем (напри-
мер, в задачах определения оптимальных размеров ступеней м ногоступенчатых ракет, в
задачах оптимального проектирования прокладки дорог и др.).
Предположим, что процесс управления некоторой системой X продолжается n шагов.
Пусть задано пространство состояний P и пространство управлений Q с элементами p
и q соответственно. Предполагается, что начальное состояние p
0
процесса задано. Пусть
также задана функция T : P × Q → P , т.е. T (p, q) = p
′
, (p, q) ∈ P × Q, p
′
∈ P . Функция
T (·) часто называют функцией динамики управляемого процесса.
Многошаговый управляемый процесс реализуется следующим образом (см. рис. 5.1.1.):
Шаг 1. Система находится в состоянии p
0
∈ P . В этом состоянии выбирается управ-
ление q
1
∈ Q. Отображение T переводит систему в новое состояние T (p
0
, q
1
) = p
1
.
Шаг 2. Система находится в состоянии p
1
∈ P . В этом состоянии выбираем управле-
ние q
2
∈ Q поэтому T (p
1
, q
2
) = p
2
.
Шаг k. Система находится в состоянии p
k−1
∈ P . Выбирается управление q
k
∈ Q,
тогда T (p
k−1
, q
k
) = p
k
.
Шаг n. Система X в состоянии p
n−1
∈ P . При выборе управления q
n
∈ Q получаем
T (p
n−1
, q
n
) = p
n
. Процесс останавливается.
113
114 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
p
0
q
1
p
1
p
n-1
p
n
p
2
q
3
qq
q
2
q
n
Рис 5.1.1. Реализация многошагового управляемого процесса.
Обозначим через q = (q
1
, . . . , q
k
, . . . , q
n
), q
k
∈ Q, k = 1, n – программным управле-
нием многошагового процесса. Тогда данному начальному состоянию p
0
и управлению q
соответствует траектория p = (p
0
, . . . , p
k−1
, p
k
, . . . , p
n
), где p
k
= T (p
k−1
, q
k
), k = 1, n.
Предполагается, что на управлении q и траектории p задана аддитивная функция:
K(p, q) = f
1
(p
0
, q
1
) + . . . + f
i
(p
i−1
, q
i
) + . . . + f
n
(p
n−1
, q
n
) + f
n+1
(p
n
) =
=
n
P
i=1
f
i
(p
i−1
, q
i
) + f
n+1
(p
n
).
(5.1.1)
Обозначим через
K(p
0
, q) =
n
X
i=1
f
i
(p
i−1
, q
i
) + f
n+1
(p
n
) (5.1.2)
значение функции
K(p, q) на траектории управляемого процесса из начального состоя-
ния p
0
при управлении q.
Теперь можно сформулировать задачу дискретного оптимального управления. Най-
ти оптимальное управление q
∗
, которое является решением следующей задачи:
max
q
K(p
0
, q) = max
"
n
X
i=1
f
i
(p
i−1
, q
i
) + f
n+1
(p
n
)
#
(5.1.3)
при динамических ограничениях:
p
i
= T (p
i−1
, q
i
), q
i
∈ Q, i =
1, n,
p
0
= p
0
,
(5.1.4)
где p
0
– заданное начальное состояние процесса.
Заметим, что при выборе управления q
i
на шаге i нам известно состояние процес-
са p
i−1
на предыдущем шаге, причем знание (p
i−i
, q
i
) определяет будущее состояние
процесса и значение функционала. Поэтому естественно рассматривать функции q
i
=
q
i
(p
i−1
), i =
1, n и набор функций
5.2. ОБЩАЯ СХЕМА МЕТОДА 115
q(·) = (q
1
(·), . . . , q
k
(·), . . . , q
n
(·)), (5.1.5)
где q
k
(·) : q
k
= q
k
(p
k−1
). Этот набор функций q(·) - будем называть стратегией или
синтезирующим управлением процесса.
Принцип оптимальности Беллмана.
Оптимальная стратегия q
∗
(·) = (q
∗
1
(·), . . . , q
∗
n
(·)) обладает тем свойством, что ка-
ково бы ни было начальное состояние p
0
и начальное управление q
1
, она останется
оптимальной стратегией в (n − 1) шаговом процессе, начинающемся из реализовавше-
гося состояния p
1
= T (p, q).
Из принципа оптимальности Беллмана можно вывести реккурентное функциональ-
ное уравнение Беллмана, которое и лежит в основе вычислительных процедур динами-
ческого программирования.
Обозначим F
n
(p) – максимальное значение функционала в n-шаговой задаче (5.1.3),
(5.1.4) из начального состояния p. Функция F
n
(p) часто называется функцией Беллмана.
Из принципа оптимальности получаем следующее уравнение.
Уравнение Беллмана.
F
n
(p) = max
q
1
∈Q
[f
1
(p, q
1
) + F
n−1
(T (p, q
1
))] (5.1.6)
при граничном условии
F
0
(p) = f
n+1
(p). (5.1.7)
5.2 Общая схема метода
Рассмотрим суть метода динамического программирования на следующем примере за-
дачи динамического программирования. Найти:
max
x
1
,...,x
n
n
X
j=1
f
j
(x
j
), (5.2.1)
n
X
j=1
a
j
x
j
≤ b, (5.2.2)
x
j
≥ 0, x
j
− целые, j =
1, n.
Поскольку переменные x
j
, j =
1, n независимы, то
116 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
max
x
1
,...,x
n
n
X
j=1
f
j
(x
j
) = max
x
n
(
f
n
(x
n
) + max
x
1
,...,x
n−1
n−1
X
j=1
f
j
(x
j
)
)
. (5.2.3)
при условии
n−1
X
j=1
a
j
x
j
≤ b − a
n
x
n
. (5.2.4)
x
j
≥ 0, x
j
− целые, j =
1, n.
Обозначив max
x
1
,...,x
n−1
n−1
P
j=1
f
j
(x
j
) при условии (5.2.4) через F
n−1
(b − a
n
x
n
), получим
max
x
1
,...,x
n
n
X
j=1
f
j
(x
j
) = max
x
n
[f
n
(x
n
) + F
n−1
(b − a
n
x
n
)] . (5.2.5)
Обозначим также max
x
1
,...,x
k
k
P
j=1
f
j
(x
j
) = F
k
(ξ) при условии
X
j=1
a
j
x
j
≤ ξ.
x
j
≥ 0, x
j
− целые, j =
1, n.
После преобразований приходим к следующему основному рекуррентному соотноше-
нию динамического программирования
F
k
(ξ) = max
x
k
[f
k
(x
k
) + F
k−1
(ξ − a
k
x
k
)] , k =
1, n (5.2.6)
при условии 0 ≤ x
k
≤
ξ
a
k
.
Используем (5.2.6) для организации вычислительного процесса следующим образом.
Построение функции Беллмана.
Шаг 1. Вычисляем
F
1
(ξ) = max
x
1
f
1
(x
1
), x
1
≤ ξ, (5.2.7)
где ξ =
0, b – параметр процесса. Заполняем табл. 5.1.1 значениями F
1
(ξ), x
0
1
(ξ), для
ξ = 0, b, x
0
1
(ξ) – оптимальное решение задачи (5.2.7).
Шаг 2. Вычисляем
F
2
(ξ) = max
0≤x
2
≤
ξ
a
2
[f
2
(x
2
) + F
1
(ξ − a
2
x
2
), ] . (5.2.8)
5.2. ОБЩАЯ СХЕМА МЕТОДА 117
Значения F
1
(ξ − a
2
x
2
) при различных значениях аргумента ξ − a
2
x
2
выбираем из табл.
5.1.1. Заполняем табл. 5.1.2 следующими результатами: F
2
(ξ), x
0
2
(ξ), где x
0
2
(ξ) -оптимальное
решение задачи (5.2.8).
Шаг k. (1 ≤ k ≤ n − 1). Вычисляем
F
k
(ξ) = max
0≤x
k
≤
ξ
a
k
[f
k
(x
k
) + F
k−1
(ξ − a
k
x
k
), ] . (5.2.9)
Заполняем таблицу значениями F
k
(ξ), x
0
k
(ξ), ξ =
0, b, где x
0
k
(ξ) – оптимальное реше-
ние задачи (5.2.9).
Расчет оптимального решения.
Полагая ξ = b и k = n находим F
n
(b) и x
0
n
= x
0
n
(b).
Вычислив в (5.2.9) оптимальное значение x
0
n
= x
0
n
(b) и положив ξ
0
1
= b − a
n
x
0
n
, по
значению ξ
0
1
из таблицы шага n − 1 определяем оптимальные значения всех остальных
переменных x
0
n−1
(ξ
0
1
), потом аналогично значения x
0
n−2
(ξ
0
1
), . . . , x
0
1
(ξ
0
1
).
ξ F
1
(ξ) x
0
1
(ξ)
0 F
1
(0) x
0
1
(0)
1 F
1
(0) x
0
1
(1)
.
.
.
.
.
.
.
.
.
b
1
F
1
(b − 1) x
0
1
(b − 1)
b F
1
(b) x
0
1
(b)
ξ F
2
(ξ) x
0
2
(ξ)
0 F
2
(0) x
0
2
(0)
1 F
2
(0) x
0
2
(1)
.
.
.
.
.
.
.
.
.
b
1
F
2
(b − 1) x
0
2
(b − 1)
b F
2
(b) x
0
2
(b)
Табл 5.1.1. Таблица для первой итерации. Табл 5.1.2. Таблица для второй итерации.
Для применения метода динамического программирования необходимо, чтобы вы-
полнялись условия:
• процесс поиска оптимальных решений должен допускать интерпретацию как мно-
гошаговый процесс принятия решений;
• для каждого шага должно быть определено множество параметров состояния ξ,
которое не зависит от номера шага;
• оптимальное решение на шаге k зависит только от текущего состояния и не зависит
от предыстории процесса.
118 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
5.3 Задача распределения капиталовложений
Фирма располагает запасом капитала A, который она предполагает разместить по четы-
рем экономическим регионам. Пусть x
i
количество капитала, направленное в i-й эконо-
мический регион. В зависимости от экономических условий прибыль от вложение капи-
тала различна и составляет h
1
(x
1
), h
2
(x
2
), h
3
(x
3
), h
4
(x
4
). Требуется так распределить
капитал A чтобы получить максимальную прибыль. Математически задач а выглядит
следующим образом:
max
x
1
+ x
2
+ x
3
+ x
4
= A
x
i
≥ 0, x
i
− целые i = 1, 2, 3, 4.
(h
1
(x
1
) + h
2
(x
2
) + h
3
(x
3
) + h
4
(x
4
))
Пусть F
1234
(A) прибыль от распределения капитала A по четырем экономическим
регионам, при использовании оптимальной политики.
F
1234
(A) = max
0≤x
4
≤A
[h
4
(x
4
) + F
123
(A − x
4
)];
F
123
(A) = max
0≤x
3
≤A
[h
3
(x
3
) + F
12
(A − x
3
)];
F
12
(A) = max
0≤x
2
≤A
[h
2
(x
2
) + F
1
(A − x
2
)];
F
1
(A) = h
1
(x
1
).
(5.3.1)
Рассмотрим следующую задачу. Пусть имеется пять единиц капитала A = 5. В таб-
лице эффективностей заданы прибыли от распределения различного количества единиц
капитала по четырем экономическим регионам.
A h
1
(x
1
) h
2
(x
2
) h
3
(x
3
) h
4
(x
4
)
0 0 0 0 0
1 35 25 20 25
2 45 40 30 35
3 50 55 40 45
4 65 75 50 55
5 80 90 60 65
Используя формулы (5.3.1) построим оптимальное распределение капитала. На пер-
вой итерации F
1
= h
1
(A), строим F
12
следующим образом: предположим, что необходимо
распределить одну единицу капитала. Эту единицу капитала можно направить в первый
5.3. ЗАДАЧА РАСПРЕДЕЛЕНИЯ КАПИТАЛОВЛОЖЕНИЙ 119
или второй регион, и в зависимости от этого получить различную прибыль, то есть выби-
рается max{35; 25}. Получаемая прибыль больше при использовании единицы капитала
первым экономическим регионом F
12
= 35 и оптимальная политика распределения ка-
питала (1,0).
Распределение двух единиц капитала происходит по такой же схеме, предполагается,
что необходимо разместить две единицы капитала, это можно сделать тремя способа-
ми: по две единицы в первый или второй экономический регион, или по одной еди-
нице капитала в каждый, соответственно необходимо выбрать максимум из значений
max{45; 40; 35 + 25 = 60}. Максимальное значение 60, и следовательно оптимальная
политика распределения по одной единице в каждый экономический регион (1,1).
Подобным образом происходит дальнешее распределение капитала между двумя эко-
номическими регионами.
A h
1
(x
1
) h
2
(x
2
) F
12
(A) Оптимальная стратегия
0 0 0 0 0
1 35 25 35 (1,0)
2 45 40 60 (1,1)
3 50 55 75 (1,2)
4 65 70 90 (1,3)
5 80 90 105 (1,4)
1. max{35; 25; } = 35.
2. max{45; 40; 35 + 25 = 60} = 60.
3. max{50; 55; 45 + 25 = 70; 4 + 35 = 75; } = 75.
4. max{65; 70; 50 + 25 = 75; 55 + 35 = 90; 45 + 40 = 85; } = 90.
5. max{90; 80; 70 + 35 = 105; 65 + 25 = 90; 50 + 40 = 90; 55 + 45 = 100; } = 105.
На второй итерации сравниваем полученное значение F
12
(A) и h
3
(x
3
).
120 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
A h
3
(x
3
) F
12
(A) Оптимальная стратегия F
123
(A) Оптимальная стратегия
0 0 0 (0,0) 0 0
1 20 35 (1,0) 35 (1,0,0)
2 30 60 (1,1) 60 (1,1,0)
3 40 75 (1,2) 80 (1,1,1)
4 50 90 (1,3) 95 (1,2,1)
5 60 105 (1,4) 110 (1,3,1)
1. max{20; 35; } = 35.
2. max{30; 60; 35 + 20 = 55} = 60.
3. max{40; 75; 60 + 20 = 80; 30 + 35 = 65; } = 80.
4. max{50; 90; 75 + 20 = 95; 40 + 35 = 75; 60 + 30 = 90; } = 95.
5. max{60; 105; 90 + 20 = 110; 50 + 35 = 85; 75 + 30 = 105; 40 + 60 = 100.} = 110.
На третьей итерации сравниваем полученное значение F
123
(A) и h
4
(x
4
).
A h
4
(x
4
) F
123
(A) Оптимальная стратегия F
1234
(A) Оптимальная стратегия
0 0 0 (0,0,0) 0 (0,0,0,0)
1 25 35 (1,0,0) 35 (1,0,0,0)
2 35 60 (1,1,0) 60 (1,1,0,0) или (1,0,0,1)
3 45 80 (1,1,1) 85 (1,1,0,1)
4 55 95 (1,2,1) 105 (1,1,1,1)
5 65 110 (1,3,1) 120 (1,2,1,1)
1. max{25; 35; } = 35.
2. max{95; 60; 35 + 25 = 60} = 60.
3. max{45 80; 60 + 25 = 85; 35 + 35 = 70; } = 85.
4. max{55; 90; 80 + 25 = 105; 35 + 45 = 80; 35 + 60 = 95; } = 105.
5. max{65; 110; 55 + 35 = 90; 95 + 25 = 120; 80 + 35 = 105; 60 + 45 = 105; } = 120.