Элементы динамического программирования оптимизация непрерывных систем

Задача 1. На рис. 14.1 изображена сеть, соединяющая точки А и В. Сеть состоит из совокупности узлов S и соединяющих их дуг. Каждой дуге, соединяющей два каких-либо узла сети, приписано число, характеризующее продолжительность перехода по этой дуге. Необходимо отыскать кратчайший по времени путь из A в В, если разрешенным является только движение слева направо.

Решение. Составим таблицу, в которой будем хранить опти­мальное управление и соответствующее ему значение целевой функ­ции для всех возможных состояний системы после каждого шага. Число строк таблицы равно числу шагов N процесса управления

(в рассматриваемом примере N=4). Число столбцов таблицы равно числу возможных состояний (в рассматриваемом примере конечное состояние фиксировано, поэтому число столбцов на единицу меньше числа возможных состояний и равно 12).

k
	1	2	3	4	5	6	7	8	9	10	11	12
1	---	---	---	---	---	---	---	---	13/12	13/8	13/6	13/7
2	---	---	---	---	12/11	11/12	12/10	11/16	---	---	---	---
3	---	5/22	5/18	6/15	---	---	---	---	---	---	---	---
4	3/24	---	---	---	---	---	---	---	---	---	---	---

Клетки таблицы разбиты пополам, причем слева вверху будем хранить оптимальное управление, а справа внизу — соответствующее значение целевой функции. Для каждого узла сети управление однозначно определяется номером следующего на выбранном маршруте узла. В первой строке таблицы хранится информация о последнем шаге пути.

Поскольку перед последним (четвертым) шагом множество воз­можных состояний есть

и из каждого из этих состояний ведет лишь один путь в В, оптимальное управление очевидно. При этом

Перед предпоследним (третьим) шагом множество возможных состояний системы .

Как видно из рисунка