Черненко В.Д. Высшая математика в примерах и задачах (том 3)
Подождите немного. Документ загружается.
140
\по ^\
А,
^2
^3
^4
Заявки Ь.
^У
5
5
^2
5
5
^i
20
20
^.
10
25
35
^5
10
10
Гпава 24
Таблица 5.7
Запасы а.
10
30
25
10
75
Такие случаи «вырождения» могут иметь место не только
при составлении опорного плана, но и при его оптимизации.
Чтобы иметь в транспортной таблице m + п -
1
базисных
клеток, добавим и отнимем в соответствующие клетки беско-
нечно малое 8, что позволит от вырожденного плана перейти к
невырожденному. Для этого изменим запасы в первой и третьей
строках и положим их равными 10+8 и 25+8. Чтобы «свести
баланс», в четвертой строке ставим запасы 10-28 (табл. 5.8).
Таблица 5.8
\\пн
\по \^
А,
Аг
^3
^4
Заявки Ъ.
в,
5
5
В2
5
5
Вз
е
20-е
20
^4
10+е
25-е
35
Bs
Iz
10-2е
10
Запасы
а^
10+е
30
25+е
1(>-2е
75
ПИНЕИНОЕ И аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
141
Строя опорный план способом северо-западного угла, не-
трудно заметить, что в
табл.
5.8 содержится уже базисных пере-
менных столько, сколько нужно
m
+
«
-1 = 8. После нахождения
оптимального решения
£
следует положить равным нулю.
5.3.
Дана транспортная таблица 5.9. Найти оптимальный
план
Таблица 5.9
1Ю\
^'
^2
As
h
В,
10
5
8
22
^2
1
6
7
34
^3
6
5
6
41
^4
8
4
7
20
«,
31
48
38
117
Решение. Составим опорный план способом северо-
западного угла (табл.5.10). Стоимость этого плана равна
Lj = 2210+9-7+25-6+23-5+18-6+20-7=796.
Таблица 5.10
^1
^2
^3
Li_
^;
10
22
5
8
22
^2
1
9
6
25
7
34
^3
6
23 ,
18 -
5
i
6
1-
41
^4
8
'
2С
4
1+
г
7
»
20
«/
31
48
38
117
Попробуем улучшить план, заняв свободную клетку (2,4) с
минимальной стоимостью
4.
Цикл, соответствз^ощий этой клетке,
показан в
табл.5.10.
Цена этого цикла равна у=4- 7+6 -
5
= - 2.
142 Гпава 24
По этому циклу можно переместить только 20 единиц гру-
за, иначе в клетке (3,4) может быть отрицательная перевозка.
Новый, улучшенный план показан в
табл.5.11.
Стоимость этого
плана L^ = 22-10+9-7+25-6+3-5+20-4+38-6 = 756 .
Таблица 5.11
А,
^2
Аз
[Л
Bt
22,
-1
10
5
8
22
В,
+
'
—
7
9
6
'25
7
34
Bs
6
5
3
38 '
41
^4
8
4
20
7
20
«,•
31
48
38
117
Для дальнейшего улучшения плана рассмотрим свобод-
ную клетку (2.1) со стоимостью 5. Поставим знак «+» в этой
клетке и покажем в табл.5.11 новый цикл. Цена цикла бу-
дет у -1- 6+5 -10 = - 4. Переместим по циклу 22 единицы
груза, тогда стоимость перевозок сократится до
L^
= 31-6+22-5+3-6+3-6+20-4+38-6 = 668 (табл.5.12).
Таблица 5.12
\пн
^1
^2
^3
^-^
J
^;
10
5
22
8
22
^2
7
31
6
3
7
34
^3
6
5
3
6
38
41
^4
8
4
20
7
20
«/
31
48
38
117
Больше отрицательных циклов нет, следовательно, переста-
новки не могут улучшить плана.
ПИНЕЙНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 143
24.6.
Задачи динамического
программирования
1°.
Основные
определения.
Процедура оптимизации опера-
ций, развивающихся во времени, составляет суть решения задач
динамического программирования (планирования). Задачи ди-
намического программирования (управления), при которых по-
казатели эффективности обращаются в максимум, решаются
многошаговым (поэтапным) методом
с
учетом его будущих по-
следствий на еще предстоящих шагах.
Процесс оптимизации управления методом динамического
программирования «проходится»
дважды.
Сначала многошаго-
вый процесс динамического программирования проходится от
конца к началу,
в
результате чего находятся условные оптималь-
ные управления на каждом
шаге.
Затем, зная условные оптималь-
ные шаговые управления, находятся оптимальные шаговые уп-
равления от начала до конца, приводящие к максимально воз-
можному выигрышу.
2°.
Общая постановка задачи. Пусть имеется некоторая
физическая система 5, которая с течением времени меняет свое
состояние. Если мы можем управлять этим процессом, то систе-
ма S
и^зывз^стся
управляемой системой, а способ нашего воздей-
ствия—управлением U. Под t/понимается целая совокупность
величин, функций.
Процесс управления системой связан с выигрышем W, т. е.
выигрыш зависит от управления W
=
W(U).
Очевидно, нас интересует такое управление, при котором
выигрыш максимален
w„^=^^{w{u)}.
Обычно в таких системах должны быть учтены условия,
накладываемые на начальное состояние системы
SQ
И
конечное
144 Гпава 24
состояние S^. Тот факт, что начальное состояние системы S^
входит в область
SQ
, записывается в виде S^^ S^ , аналогично
для конечного состояния системы S^e S^ .
Таким образом, общая задача оптимального управления
формулируется так:
Из множества возможных управлений
С/найти
такое опти-
мальное управление, которое переводит физическую систему 5
из начального состояния S^^S^ в конечное состояние
S^ € S^ так, чтобы при этом выигрыш был максимальным.
3°.
Рассмотрим алгоритм решения задач динамического
программирования.
1.
Выбрать параметры, характеризующие состояние систе-
мы,
фазовое пространство и способ членения процесса на шаги.
2.
Записать выигрыш w. на / -том шаге в зависимости от
состояния S системы в начале этого шага и управления U.
w.(S,U-)
=
w-.
3.
Записать для /-того шага функцию, выражающую изме-
нение состояния системы от S к S' под влиянием управления f/.
4.
Записать основное функциональное уравнение
W,(S)
=
m^{w,(S,U,)
+
WU(p,(S,UJ)}.
При котором в соответствии
с
принципом оптимальности надо
выбрать такое управление U., чтобы выигрыш достигал макси-
мума.
5.
Найти функцию ^гп(^) — оптимальный выигрыш на
последнем шаге
WJS)
=
m^{wJS,Uj}
И
соответствующее условное оптимальное управление на после-
днем шаге
U^(S),
ПИНЕЙНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 145
6. Зная
W^(S)^^
пользуясь основным функциональным
уравнением, находим последовательно
И
соответствующие им управления
^a^i
^u^h -.
u,(S), u,(S).
7.
Если
SQ
задано, то находя по цепочке оптимальное уп-
равление, доходим до S^
8. Если начальное состояние не задано, а лишь ограничено
условием
SQ
6
SQ
,
находим максимальный выигрыш
lF_=ma2c{tt^(S)}
И
далее, по цепочке, безусловные оптимальные управления.
6.1.
Задача
распределения ресурсов. Имеется определенное
начальное количество средств К^, которое мы должны распре-
делять в течение
т
лет между двумя предприятиями I и II.
Средства, вложенные
в
каждое предприятие, приносят за год
определенный доход, зависящий от объема вложений. Если в I
предприятие вложены средства ^, то за год получен доход f(X),
при этом вложенные средства частично уменьшаются, тратятся
и к концу года их остается (р(Х)
<
X.
Аналогично, средства Y, вложенные во второе предприя-
тие,
приносят за год доход g(Y) и уменьшаются
Xj/fY) <
Y,
По истечении года оставшиеся средства /Сд заново распре-
деляются между предприятиями I и П. Доход в производство не
вкладывается, а накапливается.
Требуется найти такой способ управления ресурсами, при
котором суммарный доход от обоих предприятий за
т
лет будет
максимальным.
Решение. Решение будем проводить по схеме:
146 Гпава 24
1.
Система
в
нашем случае характеризуется двумя парамет-
рами X,Y— средства для предприятий. Шаг — это хозяйствен-
ный
год.
в процессе управления величины
X,
Г меняются в зави-
симости от:
а) перераспределения средств между отраслями в начале
каждого года;
б) уменьшения средств за год.
Управлением f/. на /-том шаге будут количества средств
X.,Y.,
вкладываемые в предприятия I, II на этом шаге. Необхо-
димо найти такое управление
V
=
(V„U, UJ,
при котором суммарный доход
т
был бы максимальным.
2.
Пусть/С — количество средств, сохранившихся после
/-1 шагов. Управление на U- на /-том шаге состоит в вьщеле-
нии X. средств I предприятию, тогда II будет иметь
Y-^K-X^
и
выигрыш будет
w,(K,X,)=^f(XJ
+
g(K-X,).
3.
Под влиянием этого управления система из состояния К
перейдет в состояние К'
К'
=
(р(Х,)+цг(К-Х,).
4.
Основное функциональное уравнение примет вид
W,(K)
=
mm,{f(X,)
+
g(K-X,)-vW,J(p(X,)+xif(K-X.,))]^
А,-
5.
Условный оптимальный выигрыш на последнем шаге
WJK)=^m2.x{f(XJ^-g(K-XJ}^
6. Зная функцию WJK)
,
по (4) находим выигрыши
ПИНЕЙНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 147
W^_,(K)=x^{f(X„_,)+g(K-X^_,)+W„J(p(X^_,)+xif(K-X^_,))l
^т-2
W,(K)
=
rmx{[(XJ
+
g(K-XJ
+
W,(cp(XJ
+
iif(K-XJ)}^
И
соответствующие им условные оптимальные управления
x„JK),
х,_,(К),
...,
х,(К).
7.
Начальное состояние
KQ
задано, поэтому максимальный
доход будет
Состояние системы после первого шага
K; =
(P(XJ+\I/(K^--XJ.
Оптимальное управление на втором шаге ^2 = Х2(К{) и
т.
д.
Состояние системы после / шагов
K:
=
(p(xJ+xif(Kl,-x,).
Оптимальное управление х-
=
х.(К'_^
^
и т. д. по цепочке:
K,-^X,(KJ-^K:-^X,(K:)->...^XJK:_J-^K:.
Величина К'^ — представляет количество
средств,
оставших-
ся после последнего шага. Совокупность средств, вложенных по
годам в I предприятие
будет представлять собой оптимальное управление
количество
средств,
вложенных во второе предприятие по годам.
6.2.
Пусть даны
два почтовых предприятия. Рассмотрим их
деятельность за
5
лет. Заданы функции дохода
148 Гпава 24
t(X)
=
\-e-\
g(Y) =
\-e-''
И
функции траты
(р(Х)
=
0Л5Х,
(p(Y)
=
0,3Y.
Требуется распределить средства в размере К^=2 между
предприятиями
по
годам,
исходя из
условрхя
максимального дохода.
Решение. Выигрыш на /-том шаге будет
2.
Поскольку K-X.=Y.,TO система под действием управ-
ления перейдет из состояния К в состояние
K'
=
0J5X,+0,3(K--X.).
3.
Основное функциональное уравнение
Ш^ГЛ:;
= тах{2-(в-'''+e-'^^-^'^)4-lJ^,, (0Л5Х^^
4.
Условный оптимальный выигрыш на последнем шаге
W,(K) = m^x{w,{K,X,)}=msix[2--(e-''^+e-'^^-'''^)].
При фиксированном К это есть функция аргумента Х^,
Продифференцируем по Х^ и приравняем нулю
^
=
е'-'^-2е''^'-'^^=0;
дХ,
-X,=\n2''2(K-XJ;
Х,=(2К-]п2)/3. (*)
Если К
> 1п2
/
2
- 0,347, то max достигается внутри отрез-
ка (О, К) в точке Х^(К)
=
(2К-Ы2)/3, если же Л:<1п2/2,то
max достигается в конце отрезка Х^(К) = О.
Отсюда следует, что, если К
> 1п2
/
2,
то первому почтово-
му предприятию следует выделить долю (*), если К
< 1п2
/
2,
то
все средства следует отдать второму предприятию, т. е.
ПИНЕЙНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 149
' \(2К-\п2)/Ъ К>\п1/2
Найдем теперь условный оптимальный выигрыш на пятом
шаге
W,(K)
=
2-{e-'^<'^-^e-'^'-^^<'^^}.
или
__ -2Л"
1-е"'"
К<\п2/1
5.
Далее переходят к 4-му шагу.
6.3.
Задача распределения ресурсов по неоднородным эта-
пам,
В
предыдущей задаче функции дохода f(X ) и g(Y) и фун-
кции траты (р(Х), y/fY) были одинаковы для всех шагов. Мо-
жет оказаться, что они меняются от шага к шагу и для /-того
шага равны
(р,(Х),
WY) (i
=
\,2....,m).
В этом случае стандартная схема почти не меняется и ос-
новное функциональное уравнение принимает вид
W,(K)
=
m^x{l(X,)
+
g,(YJ+W,^,{(p,(X,)+xif,(K-X,))}.
Условие оптимизации т-го шага будет
WJK) =
m^{fJXJ
+
gJK-XJ},
а
в
остальном процедура построения решения остается неизменной.
6.4. Задача
о резервировании
ресурсов.
Пусть имеется одно
предприятие
и
некоторый запас
средств
К^, который можно вкла-
дывать в производство не целиком, а частично резервировать.