Исследование операций на примере ОАО "АвиаМоторс" - Экономико-математическое моделирование курсовая работа
Главная
Экономико-математическое моделирование
Исследование операций на примере ОАО "АвиаМоторс"
Решение задачи линейного программирования графическим и симплекс-методом. Способы решения транспортных задач: методы северо-западного угла, наименьшей стоимости и потенциалов. Динамическое программирование. Анализ структуры графа, матрицы смежности.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
Самарский государственный аэрокосмический университет имени академика С. П. Королёва
на тему: Исследование операций на примере: ОАО «АвиаМоторс»
Математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов функций на множествах векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами), называется математическим программированием.
Разделами математического программирования являются параметрическое программирование, динамическое программирование и стохастическое программирование. Математическое программирование используется при решении оптимизационных задач исследования операций.
В данной работе будет исследован экономический процесс работы предприятия. Будут проанализированы максимальный доход предприятия, минимальные затраты времени и ресурсов для производства, перевозки и реализации продукции. Исследуемая компания ОАО «АвиаМоторс» занимается продажей и транспортировкой автомобилей марки BMW , а так же производством различных запчастей. Производство и центральный офис компании находиться в г. Санкт- Петербурге ул. Старшовая 10. Данная компания имеет разветвленную сеть филиалов в городах России и ближнего зарубежья, что облегчает транспортировку и дает возможность выбора маршрута.
Проанализируем транспортную деятельность компании, производственную и инвестиционную и т.д.
Линейное программирование -- математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем дробно-линейного программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно -- основа нескольких методов решения задач целочисленного и нелинейного программирования.
Дана математическая модель задачи ЛП:
Графический метод, несмотря на свою очевидность и применимость лишь в случае малой размерности задачи, позволяет понять качественные особенности задачи линейного программирования, характерные для любой размерности пространства переменных и лежащие в основе численных методов ее решения.
Очевидно, что при данной постановке задачи допустимое множество X в плоскости (x1, x2) представляет собой многоугольник (не обязательно замкнутый), образованный пересечением полуплоскостей, соответствующих ограничениям вида ai1x1 + ai2x2 ? bi в исходной задаче. Линии уровня функции f(x) = (c, x) образуют семейство параллельных прямых.
При этом grad f(x) = c, т.е. градиент целевой функции всюду одинаков и является нормалью каждой из данных полуплоскостей.
Поиск решения задачи сводится к нахождению максимального числа б* среди всех таких б, что полуплоскость Hcб имеет непустое пересечение с X.
Мы получаем 4 точки A , B , C, D принадлежащие области.
Найдем точные координаты точек. A (4,06;0)
FD = 1,63 • 2,86 + 1,23 • 1,5 = 6,55
Вывод: минимум функции существует в точке D (2,86;1,5) и FD равен 6,55.
F = 1,63x1 + 1,23 x2 > min и система ограничений
Введем искусственный базис x3, x4, x5, x6
Добавим балансные переменные z1, z2
Задача приведена к каноническому виду, составим симплекс-таблицу.
Все значения в строке z должны быть положительными. Для этого произведем следующие действия. В строке z выберем наименьшее значение. Это столбец x1. Именно он войдет в базис. В нем есть положительные коэффициенты. Для них составим отношения столбца bi к x1. Выберем наименьшее. Это 1, соответствует строке x4. Значит x4 выйдет из базиса.
Разделим строку x4 на значение, находящееся на пересечении x1 и x4, чтобы получить на месте пересечения единицу. В данном случае значение уже равно единице. Теперь из каждой строки вычтем строку x4, умноженную на значение, стоящее на пересечении строки и столбца x1 (т.е. так, чтобы все элементы в столбце x1 обнулились, кроме строки x4)
В строке z все еще имеются отрицательные значения, поэтому переходим к следующему приближению.
Считаем отношения. Наименьшее в столбце x5 (1.52). Следовательно, x5 выходит из базиса. Делим строку x5 на 2,5. Затем из каждой строки вычитаем x5, умноженную на пересечение строки и столбца x2.
Все элементы в строке z положительны. Следовательно, достигнут оптимум и задача решена.
Вывод: результаты, полученные при решении задачи ЛП графическим методом и симплекс методом, совпадают. Это означает, что при затратах равных 6,55 компания ОАО «АвиаМоторс» будет вести успешную деятельность.
Транспортная задача - задача о наиболее рациональном плане перевозок однородного продукта из пунктов производства в пункты потребления.
Цель транспортной задачи - разработка наиболее рациональных путей и способов транспортировки товаров, устранение чрезмерно дальних и невыгодных перевозок.
Пусть в пунктах производства имеется однородный груз в количествах . Этот груз необходимо доставить в пунктов его потребления в количествах . Стоимость перевозки одной единицы груза (тариф) из пункта в пункт равна . Требуется составить план перевозок, позволяющий вывезти все грузы, удовлетворив поставщиков и потребителей, и минимизировать стоимость расходов. Суть транспортной задачи состоит в составлении оптимального плана перевозок, минимизирующего суммарные транспортные издержки, при реализации которого запросы всех пунктов потребления были бы удовлетворены за счёт производства продукта в пунктах . Пусть - количество продукта, перевозимого из пункта в пункт . Тогда транспортная задача формулируется так: определить значения переменных , , , минимизирующих суммарные транспортные издержки. Заявки потребителя будут удовлетворены, если сумма всех товаров поставщиков на складах больше либо равна объему заказа потребителя:
Если суммарный объем производства равен суммарному объему потребления (т.е. неравенство (2.2) превращается в строгое равенство), то выполняется уравнение баланса:
и система называется сбалансированной.
Общая стоимость перевозок составляет сумму:
где - количество единиц продукции, получаемой от .
При этом от поставщика будет вывезено количество товара - , а потребитель получит единиц продукции.
В зависимости от соотношения между суммарными запасами груза и суммарными запросами, можно выделить ТЗ открытого и закрытого типа.
Если сумма запасов груза равна суммарной потребности (выполняется уравнение баланса (2.3) ):
Математическая модель закрытой ТЗ имеет вид:
Если сумма запасов не совпадает с суммой потребностей: (2.10) то задача называется открытой.
Существует два варианта открытых задач:
а) если объем поставок больше объема потребления:
Т.е. все потребители будут удовлетворены полностью, а часть запасов останется невывезенной.
б) если сумма поставок меньше суммы потребления:
В этом случае поставщики не могут в полной мере удовлетворить запросы потребителей и теряют свою значимость на рынке.
Каждый из описанных вариантов имеет свою математическую модель
1). Задача ЛП (2.4) - (2.7) имеет оптимальное решение только в случае соблюдении условия баланса (2.3):
2). Если и - целые числа, и выполняется уравнение баланса (2.3), то ТЗ имеет оптимальное решение с целочисленными координатами;
3). Ранг системы векторов условий ТЗ равен (m+n-1) (ранг на единицу меньше, чем количество переменных).
На трех складах компании ОАО «АвиаМоторс» располагаются автомобили марки BMW. Необходимо осуществить доставку машин для четырех филиалов, находящихся в Екатеринбурге «Bayerhof» ул. Блохера 45, Перми «Верра- Моторс» ул. Героев Хасана 81, Самаре «Aldis» ул. Демократическая 65 и Нижнем Новгороде «ТрансТехСервис» ул. Бринского 12. План перевозок, полностью удовлетворяющий партнеров и обеспечивающий минимум затрат зависит от стоимости доставки автомобилей от поставщика к потребителю.
1. Составить исходные планы перевозок:
2. Методом потенциалов найти план перевозок, полностью удовлетворяющий партнеров и обеспечивающий минимум затрат на перевозку продукции.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. Осуществляется это таким образом:
1. если <, то и исключается поставщик с номером i, ,; 2. если> , то и исключается потребитель с номером j, ,;
если =, то и исключается либо i-й поставщик, , , либо j-й потребитель, , .
Таблица 2.2: Нахождение решения методом северо-западного угла
Определим затраты на перевозки по формуле
Вывод: стоимость перевозок для компании ОАО «АвиаМоторс», найденная по методу северо-западного угла составляет F1=9460.
Метод минимальной стоимости позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи , ,. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости , и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель).
Очередную клетку, соответствующую, заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично с потребителем.
В зависимости от состояния между суммарными запасами груза и суммарными в нем запросами, транспортные задачи могут быть открытыми и закрытыми.
Если сумма запасов груза равна суммарной потребности, то есть то транспортная задача называется закрытой.
Клетки, в которые поместим грузы называются закрытыми, им соответствуют базисные переменные опорного решения. Остальные клетки пустые, им соответствуют переменные. При распределении грузов может оказаться, что количество занятых клеток меньше чем m+n-1. В этом случае недостающее их число заполняется клетками с нулевыми поставками. Такие клетки называются условно занятыми. Такая транспортная задача называется выраженной. В нашей задаче число заполненных клеток равно 5, m + п - 1 = 6, следовательно, задача является вырожденной.
Таблица 2.4 Нахождение решения методом потенциалов
Строим систему потенциалов, соответствующих опорному решению. Для этого решим системы уравнений:
Для того чтобы найти частное решение системы, одному из потенциалов задаем произвольно некоторое значение, равное нулю.
Так как матрица положительная, то мы получили план перевозок, полностью удовлетворяющий партнеров и обеспечивающий минимум затрат на перевозку продукции.
Вывод: стоимость перевозок для компании ОАО «АвиаМоторс», найденная по методу потенциалов составляет F3=9460, и F1= F2= F3.
Минимальные затраты на перевозки машин марки BMW от компании ОАО «АвиаМоторс» в филиалы, находящиеся в Екатеринбурге «Bayerhof» ул. Блохера 45, Перми «Верра- Моторс» ул. Героев Хасана 81, Самаре «Aldis» ул. Демократическая 65 и Нижнем Новгороде «ТрансТехСервис» ул. Бринского 12, равны 9460, что подтверждается тремя методами.
3. Задача динамического программирования
Динамическое программирование (ДП) -- это вычислительный метод для эффективного решения задач с пересекающимися подзадачами. Возникло и сформировалось в 1950 -- 1953 гг. благодаря работам Р. Беллмана.
Динамическим программированием (в наиболее общей форме) называют процесс пошагового решения задач, когда на каждом шаге выбирается одно решение из множества допустимых (на этом шаге) решений, причем такое, которое оптимизирует заданную целевую функцию или функцию критерия. В основе теории динамического программирования лежит принцип оптимальности Беллмана: «каково бы ни было начальное состояние на любом шаге и решение, выбранное на этом шаге, последующие решения должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага». Использование этого принципа гарантирует, что решение, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения задачи в целом.
Динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения. Рекурсивные алгоритмы также делят задачу на независимые подзадачи, эти подзадачи - на более мелкие подзадачи и так далее, а затеи собирают решение основной задачи «снизу вверх». Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи». В этом случае при использовании рекурсии будут решаться одни и те же подзадачи несколько раз. Формы алгоритма динамического программирования могут быть разными - общим для них является заполняемая таблица и порядок формирования ее элементов.
Алгоритм, основанный на динамическом программировании, решает каждую из подзадач только один раз и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче. Типичными для динамического программирования являются задачи оптимизации. У подобных задач может быть много возможных решений а, их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи). В общем случае, оптимум может достигаться для нескольких разных решений.
В задачах динамического программирования (ДП):
(; ) - функция прибыли (или затрат перехода системы из начального состояния в конечное) (некая количественная характеристика).
Таблица 3.1 - Таблица стоимостей прокладки участков пути
1. Задача о выборе оптимального маршрута
Компании ОАО «АвиаМоторс» поступил заказ от филиала «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 (вертикально).
Шаг 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
Рассмотрим каждый шаг в отдельности. Воспользуемся основным функциональным уравнением Беллмана:
где - состояние системы на i-том шаге;
- управление системой на (i+1) шаге;
- минимальное значение функции цели, полученное при переходе из некоторого i-ого состояния в конечное (k-тое состояние);
- приращение функции при переходе из некоторого i-ого состояния в (i+1);
- минимальное значение функции цели, полученное при переходе из некоторого (i+1) состояния в конечное (k-тое состояние).
Точка В (г. Самара) соответствует состоянию системы x10 = (6;6), i=10
Шаг 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
Узел (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,6) - г. Уфа, (4,5) - г. Пенза, (5,4) - г. Тамбов, (6,3) - Воронеж
Из узлов (3,6) и (6,3) путь в смежные с ними узлы однозначен. Обходной путь существует, но он не оптимален.
Стоимость прокладки дороги из г. Уфы и г. Воронежа в конечный пункт г. Самару равна:
А для г. Пензы и г. Тамбова следует рассмотреть по 2 варианта маршрута.
Из узла (4,5) г. Пензы можно продолжить дорогу к пункту В либо через (4,6)
г. Ульяновск, либо через (5,5) г. Саранск.
Путь из г. Пензы в г. Самару через г. Ульяновск складывается из суммы работ:
Путь из г. Пензы в г. Самару через г. Саранск складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Ульяновск
Из узла (5,4) г. Тамбова можно продолжить дорогу к пункту В либо через (6,4)
Путь из г. Тамбова в г. Самару через г. Саранск складывается из суммы работ:
Путь из г. Тамбова в г. Самару через г. Ниж. Ломов складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Ниж. Ломов
При выборе оптимального маршрута достаточно знаний прокладывания маршрута в пункт В из (3,6), (4,5), (5,4), (6,3).
Найдем минимальное значение функции цели (оптимальный маршрут) при i=7, используя основное функциональное уравнение Беллмана (3.1):
Рисунок 3.4 - Сетевая модель шага 3
Узел (2,6) - г. Казань, (3,5) - г. Саранск, (4,4) - г. Липецк, (5,3) - г. Курск, (6,2) - г. Белгород
Из узлов (2,6) и (6,2) путь в смежные с ними узлы однозначен. Обходной путь существует, но он не оптимален.
Стоимость прокладки дороги из г. Казани и г. Белгорода в конечный пункт г. Самару равна:
А для г. Саранска, г. Липецка и г. Курска следует рассмотреть по 2 варианта маршрута.
Из узла (3,5) г. Саранска можно продолжить дорогу к пункту В либо через (3,6) г. Уфу, либо через (4,5) г. Пензу.
Путь из г. Саранска в г. Самару через г. Уфу складывается из суммы работ:
Путь из г. Саранска в г. Самару через г. Пензу складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Пензу
Из узла (4,4) г. Липецка можно продолжить дорогу к пункту В либо через (4,5) г. Пензу, либо через (5,4) г. Тамбов.
Путь из г. Липецка в г. Самару через г. Пензу складывается из суммы работ:
Путь из г. Липецка в г. Самару через г. Тамбов складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Пензу
Из узла (5,3) г. Курска можно продолжить дорогу к пункту В либо через (5,4) г. Тамбов, либо через (6,3) г. Воронеж.
Путь из г. Курска в г. Самару через г. Тамбов складывается из суммы работ:
Путь из г. Курска в г. Самару через г. Воронеж складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Тамбов
При выборе оптимального маршрута достаточно знаний прокладывания маршрута в пункт В из (2,6), (3,5), (4,4), (5,3) и (6,2).
Найдем минимальное значение функции цели (оптимальный маршрут) при i=6, используя основное функциональное уравнение Беллмана (3.1):
Рисунок 3.5 - Сетевая модель шага 4
Узел (1,6) - г. Киров, (2,5) - г. Владимир, (3,4) - г. Калуга, (4,3) - г. Тула, (5,2) - г. Брянск, (6,1) - г. Гомель.
Из узлов (1,6) и (6,1) путь в смежные с ними узлы однозначен. Обходной путь существует, но он не оптимален.
А для г. Владимира, г. Калуги, г. Тулы, г. Брянска следует рассмотреть по 2 варианта маршрута.
Из узла (2,5) г. Владимира можно продолжить дорогу к пункту В либо через (2,6) г. Казань, либо через (3,5) г. Саранск.
Путь из г. Владимира в г. Самару через г. Казань складывается из суммы работ:
Путь из г. Владимира в г. Самару через г. Саранск складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Саранск
Из узла (3,4) г. Калуги можно продолжить дорогу к пункту В либо через (3,5) г. Саранск, либо через (4,4) г. Липецк.
Путь из г. Калуги в г. Самару через г. Саранск складывается из суммы работ:
Путь из г. Калуги в г. Самару через г. Липецк складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Саранск
Из узла (4,3) г. Тулы можно продолжить дорогу к пункту В либо через (4,4) г. Липецк, либо через (5,3) г. Курск.
Путь из г. Тулы в г. Самару через г. Липецк складывается из суммы работ:
Путь из г. Тулы в г. Самару через г. Курск складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Курск
Из узла (5,2) г. Брянска можно продолжить дорогу к пункту В либо через (5,3) г. Курск, либо через (6,2) г. Белгород.
Путь из г. Брянска в г. Самару через г. Курск складывается из суммы работ:
Путь из г. Тулы в г. Самару через г. Белгород складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Курск
При выборе оптимального маршрута достаточно знаний прокладывания маршрута в пункт В из (1,6), (2,5), (3,4), (4,3), (5,2) и (6,1)
Найдем минимальное значение функции цели (оптимальный маршрут) при i=5, используя основное функциональное уравнение Беллмана (3.1):
Рисунок 3.6 - Сетевая модель шага 5
Узел (1,5) - г. Иваново, (2,4) - г. Москва, (3,3) - г. Глазово, (4,2) - г. Рославль, (5,1) - г. Могилев
Для г. Иваново, г. Москвы, г. Глазово, г. Рославля, г. Могилев следует рассмотреть по 2 варианта маршрута.
Из узла (1,5) г. Иваново можно продолжить дорогу к пункту В либо через (1,6) г. Киров, либо через (2,5) г. Владимир.
Путь из г. Иваново в г. Самару через г. Киров складывается из суммы работ:
Путь из г. Иваново в г. Самару через г. Владимир складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Владимир
Из узла (2,4) г. Москвы можно продолжить дорогу к пункту В либо через (2,5) г. Владимир, либо через (3,4) г. Калугу.
Путь из г. Москвы в г. Самару через г. Владимир складывается из суммы работ:
Путь из г. Москвы в г. Самару через г. Калугу складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Калугу
Из узла (3,3) г. Глазово можно продолжить дорогу к пункту В либо через (3,4) г. Калугу, либо через (4,3) г. Тулу.
Путь из г. Глазово в г. Самару через г. Калугу складывается из суммы работ:
Путь из г. Глазово в г. Самару через г. Тулу складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Тулу
Из узла (4,2) г. Рославля можно продолжить дорогу к пункту В либо через (4,3) г. Тулу, либо через (5,2) г. Брянск.
Путь из г. Рославля в г. Самару через г. Тулу складывается из суммы работ:
Путь из г. Рославля в г. Самару через г. Брянск складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Брянск
Из узла (5,1) г. Могилева можно продолжить дорогу к пункту В либо через (5,2) г. Брянск, либо через (6,1) г. Гомель.
Путь из г. Могилева в г. Самару через г. Брянск складывается из суммы работ:
Путь из г. Могилева в г. Самару через г. Гомель складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Брянск
При выборе оптимального маршрута достаточно знаний прокладывания маршрута в пункт В из (1,5), (2,4), (3,3), (4,2) и (5,1).
Найдем минимальное значение функции цели (оптимальный маршрут) при i=4, используя основное функциональное уравнение Беллмана (3.1):
Рисунок 3.7 - Сетевая модель шага 6
Узел (1,4) - г. Кострома, (2,3) - г. Вязьма, (3,2) - г. Ярцево, (4,1) - г. Орша Для г. Костромы, г. Вязьмы, г. Ярцево, г. Орша следует рассмотреть по 2 варианта маршрута.
Из узла (1,4) г. Костромы можно проложить дорогу к пункту В либо через (1,5) г. Иваново, либо через (2,4) г. Москву.
Путь из г. Костромы в г. Самару через г. Иваново складывается из суммы работ:
Путь из г. Костромы в г. Самару через г. Москву складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Иваново
Из узла (2,3) г. Вязьмы можно продолжить дорогу к пункту В либо через (2,4) г. Москву, либо через (3,3) г. Глазово.
Путь из г. Вязьмы в г. Самару через г. Москву складывается из суммы работ:
Путь из г. Вязьмы в г. Самару через г. Глазово складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Глазово
Из узла (3,2) г. Ярцево можно продолжить дорогу к пункту В либо через (3,3) г. Глазово, либо через (4,2) г. Рославль.
Путь из г. Ярцево в г. Самару через г. Глазово складывается из суммы работ:
Путь из г. Ярцево в г. Самару через г. Рославль складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Глазово
Из узла (4,1) г. Орши можно продолжить дорогу к пункту В либо через (4,2) г. Рославль, либо через (5,1) г. Могилев.
Путь из г. Орши в г. Самару через г. Рославль складывается из суммы работ:
Путь из г. Орши в г. Самару через г. Могилев складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Могилев
При выборе оптимального маршрута достаточно знаний прокладывания маршрута в пункт В из (1,4), (2,3), (3,2), (4,1).
Найдем минимальное значение функции цели (оптимальный маршрут) при i=3, используя основное функциональное уравнение Беллмана (3.1):
Рисунок 3.8 - Сетевая модель шага 7
Узел (1,3) - г. Ярославль, (2,2) - г. Тверь, (3,1) - г. Смоленск
Для г. Ярославля, г. Твери, г. Смоленска следует рассмотреть по 2 варианта маршрута.
Из узла (1,3) г. Ярославля можно продолжить дорогу к пункту В либо через (1,4) г. Кострому, либо через (2,3) г. Вязьмы.
Путь из г. Ярославля в г. Самару через г. Кострому складывается из суммы работ:
Путь из г. Ярославля в г. Самару через г. Вязьму складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Кострому
Из узла (2,2) г. Твери можно продолжить дорогу к пункту В либо через (2,3) г. Вязьму, либо через (3,2) г. Ярцев.
Путь из г. Твери в г. Самару через г. Вязьму складывается из суммы работ:
Путь из г. Твери в г. Самару через г. Ярцев складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Вязьму
Из узла (3,1) г. Смоленска можно продолжить дорогу к пункту В либо через (3,2) г. Ярцев, либо через (4,1) г. Орши.
Путь из г. Смоленска в г. Самару через г. Ярцев складывается из суммы работ:
Путь из г. Смоленска в г. Самару через г. Орши складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Орши
При выборе оптимального маршрута достаточно знаний прокладывания маршрута в пункт В из (1,3), (2,2), (3,1).
Найдем минимальное значение функции цели (оптимальный маршрут) при i=2, используя основное функциональное уравнение Беллмана (3.1):
Рисунок 3.9 - Сетевая модель шага 8
Узел (1,2) - г. Вологда, (2,1) - г. Великий Новгород
Для г. Вологды, г. Вел. Новгорода следует рассмотреть по 2 варианта маршрута.
Из узла г. Вологды можно продолжить дорогу к пункту В либо через (1,3) г. Ярославль, либо через (2,2) г. Тверь.
Путь из г. Вологды в г. Самару через г. Ярославль складывается из суммы работ:
Путь
Исследование операций на примере ОАО "АвиаМоторс" курсовая работа. Экономико-математическое моделирование.
Требования К Оформлению Решений Реферат
Реферат: Теплопроводность через сферическую оболочку
План Урока Сочинение
Курсовая Работа На Тему Предмет, Задачи, Сущность И Основные Понятия Управленческой Психологии
Реферат: Федор Степун: русский философ против большевизма и нацизма
Курсовая Работа На Тему Економічне Виховання Молодших Школярів
Реферат: Денежная реформа Алексея Михайловича 1649-1663
Пример Декабрьского Сочинения 2022
Лабораторная работа: Исследование системы автоматического регулирования угловой скорости двигателя внутреннего сгорания
Сочинение Вечная Проблема
Сочинение Егэ 2022 Видеоурок
Реферат: Сравнение деловых культур России и США
Реферат по теме Ислам: история появления, распространение его на территории России
Реферат: Анализ основных техникоэкономических показателей работы предприятия РУП Завод Электроника
Мое Хобби На Английском Танцы Эссе
Реферат: Оценка бизнеса 6
Отчет По Практике Газета
Реферат: Фредерик IV король Дании
Курсовая Работа На Тему Турфирма
Практические Работы Текстовый Редактор Word
Технологические процессы в животноводстве по откорму КРС в условиях Обь-Иртышской поймы - Сельское, лесное хозяйство и землепользование курсовая работа
Привлечение в качестве обвиняемого - Государство и право курсовая работа
Машинный агрегат - Производство и технологии курсовая работа