|
Задание:
. Задача о выборе оптимального маршрута
Компании ОАО «АвиаМоторс» поступил заказ от филиала «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 |
