Исследование операций на примере ОАО "АвиаМоторс"
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
°ммирования являются задачи оптимизации. У подобных задач может быть много возможных решений а, их качество определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи). В общем случае, оптимум может достигаться для нескольких разных решений.
В задачах динамического программирования (ДП):
- состояние системы на -ом шаге;
- управление системой на -ом шаге;
(; ) - функция прибыли (или затрат перехода системы из начального состояния в конечное) (некая количественная характеристика).
Исходные данные:
Таблица 3.1 - Таблица стоимостей прокладки участков пути
28 35 15 32 39 282431362330 2526363921 383029352735 4632 421930 143818402337 3840374124 332127272632 1525282940 322835343430 33 34 37 23 38 Задание:
. Задача о выборе оптимального маршрута
Компании ОАО АвиаМоторс поступил заказ от филиала 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:
Приращение функции: и
Итак, найдем минимальное значение функции цели при i=9, используя основное функциональное уравнение Беллмана (3.1):
Рисунок 3.2 - Сетевая модель шага 1
Шаг 2
В вектор состояния входят 3 узла:
Узел (4,6) соответствует г. Ульяновску, (5,5) - г. Саранск, (6,4) - г. Нижний Ломов.
Из узлов (4,6) и (6,4) путь в смежные с ними узлы однозначен. Обходной путь существует, но он не оптимален.
Стоимость прокладки дороги из г. Ульяновска и г. Ниж. Ломов в конечный пункт
г. Самару равна:
Из узла (5,5) г. Саранска можно продолжить дорогу к пункту В либо через (5,6)
г. Сызрань, либо через (6,5) г. Кузнецк.
Путь из г. Саранска в г. Самару через г. Сызрань складывается из суммы работ:
Путь из г. Саранска в г. Самару через г. Кузнецк складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Сызрань
При выборе оптимального маршрута достаточно знаний прокладывания маршрута в пункт В из (4,6), (5,5), (6,4).
Найдем минимальное значение функции цели (оптимальный маршрут) при i=8, используя основное функциональное уравнение Беллмана (3.1):
Рисунок 3.3 - Сетевая модель шага 2
Шаг 3
В вектор состояния входят 4 узла:
Узел (3,6) - г. Уфа, (4,5) - г. Пенза, (5,4) - г. Тамбов, (6,3) - Воронеж
Из узлов (3,6) и (6,3) путь в смежные с ними узлы однозначен. Обходной путь существует, но он не оптимален.
Стоимость прокладки дороги из г. Уфы и г. Воронежа в конечный ?/p>