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

Задание:

. Задача о выборе оптимального маршрута

Компании ОАО «АвиаМоторс» поступил заказ от филиала «Aldis», находящегося в Самаре ул. Демократическая 65, на покупку автомобилей марки BMW. Перед компанией встала задача о выборе оптимального маршрута из г. Санкт-Петербурга (пункт А) в г. Самару (пункт В), который обеспечивал бы минимальные транспортные расходы.

Известна стоимость дороги по участкам в западном и северном направлениях (таблица 3.1).Требуется, используя алгоритм Беллмана, определить оптимальный маршрут прокладки пути от пункта А (северо-западный угол) в пункт В (юго-восточный угол).

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

Компанию ОАО «АвиаМоторс» распределяет 600 млн. д.е. между 5 филиалами, находящихся в Екатеринбурге «Bayerhof» ул. Блохера 45, Перми «Верра- Моторс» ул. Героев Хасана 81, Самаре «Aldis» ул. Демократическая 65, Нижнем Новгороде «ТрансТехСервис» ул. Бринского 12, Краснодаре «Бакра» ул. Железнодорожная 23, в долях, кратных 100 млн.

Доходы компании зависят от того, как она распределит вложения различных количеств средств между пятью филиалами. Эффективность от капитальных вложений в каждый филиал приведена в таблице2. Требуется составить оптимальный план распределения вкладов компании в развитие филиалов.

Решение:

1. Задача о выборе оптимального маршрута

Рисунок 3.1 - Схема маршрутов и стоимости участков

Следуя алгоритму решения задачи ДП, основанном на принципе Беллмана, разобьем весь процесс на шаги (m+n = 5+5 = 10). Управлениями будем считать стоимость прокладки дороги по участкам, выходящим из узла (6;6) в направлении bji (горизонтально) и cji (вертикально).

Условная оптимизация:

Шаг 0: (6;6), i=10, x10

Шаг 1: (6;5) (5;6), i=9, x9

Шаг 2: (6;4) (5;5) (4;6), i=8, x8

Шаг 3: (6;3) (5;4) (4;5) (3;6), i=7, x7

Шаг 4: (6;2) (5;3) (4;4) (3;5) (2;6), i=6, x6

Шаг 5: (6;1) (5;2) (4;3) (3;4) (2;5) (1;6), i=5, x5

Шаг 6: (5;1) (4;2) (3;3) (2;4) (1;5), i=4, x4

Шаг 7: (4;1) (3;2) (2;3) (1;4), i=3, x3

Шаг 8: (3;1) (2;2) (1;3), i=2, x2

Шаг 9: (2;1) (1;2), i=1, x1

Шаг 10: (1;1), i=0, x0

Рассмотрим каждый шаг в отдельности. Воспользуемся основным функциональным уравнением Беллмана:

(3.1)

где - состояние системы на i-том шаге;

- состояние системы на (i+1) шаге;

- управление системой на (i+1) шаге;

- минимальное значение функции цели, полученное при переходе из некоторого i-ого состояния в конечное (k-тое состояние);

- приращение функции при переходе из некоторого i-ого состояния в (i+1);

- минимальное значение функции цели, полученное при переходе из некоторого (i+1) состояния в конечное (k-тое состояние).

Шаг 0

Точка В (г. Самара) соответствует состоянию системы x10 = (6;6), i=10

Fk-i-1=F10-9-1=F0=0

Шаг 1 В конечный пункт (г. Самара), определяемый узлом (6,6), ведут 2 узла: (5,6) и (6,5).

Узел (5,6) - г. Сызрань, (6,5) - г. Кузнецк

Координатами вектора состояния системы являются узловые точки. В сечение шага 1 попадают узлы (5,6) и (6,5):

Роль координат функции управления играют величины bji и сji:

Приращение функции: и

Перейти на страницу: 1 2 3 4 5 6 7