Динамическое программирование.

Это метод разработки оптимального решения в динамике с учётом времени. В основе метода положен принцип Беллмана:

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

Задача.

Имеем фрагмент сети ЭС, количество узлов 10 ОС в 5ти зонах. Каждая ветвь сети характеризуется величиной затрат на организацию связи.

Требуется выбрать траекторию из начального узла i = 1 к конечному i = 10 с минимальными затратами на организацию связи.

По принципу Беллмана: на каждом этапе (шаге) принимается такое решение, которое обеспечивает оптимальность из данного состояния (в начале 1го шага) до конца развития процесса. Реализацию такого принципа из 1го узла в 10ый (в нашей задаче) целесообразно выполнять в привязке к 10му последнему узлу.

Рассмотрим два способа. 1ый способ реализации на рисунке:

1 – 3 – 7 – 9 – 10 – оптимальная траектория.

2ой способ реализации – по таблице. По принципу Беллмана решение надо начинать при условии, что находимся в 4ой зоне (в узлах 8 и 9) и организуем связь из узлов 4ой зоны в узел 5ой зоны.

Из пунктов 4 зоны	Затраты, С							Комментарии
	В пункт 5 зоны						Минимальные затраты
8	1						1	Управление (траектория) из 8 в 9 – вынужденное с ценой 1 и 4 тыс. руб., эти показатели одновременно минимальные.
9	4						4
Из пунктов 3 зоны	Из пунктов						Минимальные затраты
	8			9
5	7 + 1			5 + 4			8	7 – из исходных данных 1 – из данных 1го шага
6	3 + 1			4 + 4			4
7	7 + 1			1 + 4			5
Из пунктов 2 зоны	Из пунктов						Минимальные затраты
	5		6			7
2	10 + 8		12 + 4			-	16
3	5 + 8		10 + 4			7 + 5	12
4	-		15 + 4			13 + 5	18
Из пункта 1 зоны	Из пунктов						Минимальные затраты
	2	3			4
1	2 + 16	5 + 12			1 + 18		17

Цена вопроса 17 тыс. руб., оптимальное решение 1 – 3 – 7 – 9 – 10.