Задача динамического программирования

Узел (1,2) - г. Вологда, (2,1) - г. Великий Новгород

Для г. Вологды, г. Вел. Новгорода следует рассмотреть по 2 варианта маршрута.

Из узла г. Вологды можно продолжить дорогу к пункту В либо через (1,3) г. Ярославль, либо через (2,2) г. Тверь.

Путь из г. Вологды в г. Самару через г. Ярославль складывается из суммы работ:

Путь из г. Вологды в г. Самару через г. Тверь складывается из суммы работ:

Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Ярославль

Из узла (2,1) г. Вел. Новгорода можно продолжить дорогу к пункту В либо через (2,2) г. Тверь, либо через (3,1) г. Смоленск.

Путь из г. Вел. Новгорода в г. Самару через г. Тверь складывается из суммы работ:

Путь из г. Вел. Новгорода в г. Самару через г. Смоленск складывается из суммы работ:

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

При выборе оптимального маршрута достаточно знаний прокладывания маршрута в пункт В из (1,2), (2,1).

Рисунок 3.10 - Сетевая модель шага 9

Шаг 10

В вектор состояния входит 1 узел:

- пункт А (г. Санкт-Петербург)

Для г. Санкт-Петербурга следует рассмотреть 2 варианта маршрута.

Из узла (1,1) г. Санкт-Петербурга можно продолжить дорогу к пункту В либо через (1,2) г. Вологду, либо через (2,1) г. Вел. Новгород.

Путь из г. Санкт-Петербурга в г. Самару через г. Вологду складывается из суммы работ:

Путь из г. Санкт-Петербурга в г. Самару через г. Вел. Новгород складывается из суммы работ:

Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Вологду

Найдем минимальное значение функции цели (оптимальный маршрут) при i=1, используя основное функциональное уравнение Беллмана (3.1):

Рисунок 3.11 - Сетевая модель шага 10

Проведенные расчеты позволяют сделать вывод о том, что условная оптимизация привела к минимальному значению функции цели: Fmin = 269д.е. Данный маршрут по доставки автомобилей из Санкт-Петербурга (пункт А) в Самару (пункт В) будет оптимальным.

Безусловная оптимизация:

Необходимый маршрут определяется непрерывным следованием стрелок, соединяющих А и В (рисунок 3.12).

Минимальные затраты соответствуют следованию оптимальному пути (вектору управления) -

Вектору соответствует затраты (целевая функция):

2. Задача о распределении ресурсов

Таблица 3.2 -Эффективность от вложений в каждое предприятие