Динамическое программирование. Романовская А.М - 19 стр.

UptoLike

ВУЗ: 

РЭУ им. Плеханова | Омск

Составители: 

Рубрика: 

18
каждом шаге, причем начальное состояние
0
фиксирова-
но, соответствует пункту 1;
3) под управлением на каждом шаге будем понимать
ребра, соединяющие соответствующие кружки данного
шага. Из рис. 5 видно, что при выбранных состояниях и
управлениях каждое состояние в начале k-го шага (k = 1, 2,
3, 4) и конкретное управление на этом шаге однозначно
определяет состояние к концу k-го шага.
II. Строим аддитивную целевую функцию.
Под величиной затрат на каждом шаге будем пони-
мать стоимость перевозки единицы груза между пунктами
сети. Они заданы для всех возможных состояний и всех
возможных управлений. Тогда под целевой функцией бу-
дем понимать суммарные стоимости перевозок при пере-
ходе от
0
к
;
4
очевидно, они равны сумме стоимостей
перевозок на каждом шаге, что означает аддитивность це-
левой функции. Решить данную задачу означает найти на-
бор управлений на каждом шаге, который доставляет ми-
нимум целевой функции
?,,,min
4321
uuuuS
Р е ш е ние.
1
2
5
3
4
6
7
8
9
10
7
8
6
8
4
6
9
7
5
3
5
6
10
9
4
11
20
19
15
9
7
12
15
21 11
Рисунок 6
Двигаясь последовательно от конца к началу находим ми-
нимальные потери из данного кружка и до конца при усло-

Страницы