Нахождение кратчайшего пути в транспортной сети - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")
В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих случаев разработаны две разновидности алгоритма решения задачи. Рассмотрим первый из случаев. Транспортная сеть представлена графом G1, в котором длины ребер одинаковы и равны некоторой постоянной величине (l1=const). Для простоты изложения будем считать, что l1=1. Каждому узлу xI графа G1 приписываем индекс I, равный длине кратчайшего пути из xI в конечный узел xN.
Алгоритм основан на последовательном приписывании индексов, последовательно проходя в обратном направлении (от xN до x0) следующим образом.
- - Узлу xN приписывается индекс N=0. - Всем узлам (еще не имеющим индексов), от которых идет ребро в конечный узел, приписываем индекс I=1. - Всем следующим узлам, от которых идут ребра в только что помеченные узлы приписываем индекс (I+1).
Этот процесс продолжается, концентрическими кругами расширяясь от xN, до тех пор, пока не будет помечен начальный узел x0 графа G1. Значение индекса 0 у начального узла x0 и будет равно длине кратчайшего пути.
Пример. Относительно КУП "СПЕЦКОММУНТРАНС" задача формулируется, как нахождение кратчайшего пути следования автомобиля, производящего работу по вывозу мусора на свалку. В общем виде задача звучит так. Пусть дан граф G1, представленный на рисунке 5. Сеть состоит из десяти узлов. Необходимо найти кратчайший путь от x0 до xN. На рисунке 5 показаны значения индексов I для каждого i-го узла. Начинается расчет узла xN (для которого N=0) и завершается установкой индексов у всех остальных узлов. Индекс при x0 равен 0=3. Поэтому длина кратчайшего пути равна LКр=3. Само направление кратчайшего пути находим путем составления последовательности узлов по направлению убывания у них индексов от 0=3 до N=0. Для графа G1 кратчайший путь составляют узлы: x0, x1, x7, xN. На рисунке 5 кратчайший путь выделен жирными стрелками.
Рисунок 4. Транспортная сеть равных расстояний
Рассмотрим случай 2, когда длины lIj ребер (xI, xJ) транспортной сети различны. Задача усложняется, поскольку часто путь, проходящий через минимальное число вершин, может иметь бльшую длину (стоимость или время продвижения), чем обходные пути. Алгоритм расчета индексов похож на предыдущий. Однако, есть различия.
- - Первоначально конечному узлу приписываем индекс N=0, а для остальных узлов устанавливаем индекс, равный бесконечно большому числу (I=). - Ищем такую дугу (xI, xJ), для которой справедливо неравенство:
(30)
И заменяем индекс у xJ узла:
(31)
- Продолжаем этот процесс замены индексов аналогично предыдущему случаю до тех пор, пока остается хотя бы одна дуга, позволяющая уменьшить индекс J.
Правило нахождения кратчайшего пути при вычисленных индексах I формулируется следующим образом: при обратном проходе по графу G от x0 к xN выбираем тот из узлов, для которого I минимально.
Пример. По аналогии с предыдущим примером относительно КУП "СПЕЦКОММУНТРАНС" задача формулируется, как нахождение кратчайшего пути следования автомобиля, производящего работу по вывозу мусора на свалку. В общем виде задача звучит так. Пусть дан граф G2, представленный на рисунке 6 Сеть состоит из шестнадцати узлов. Расстояния между узлами различны и каждое из ребер графа G2 помечено величиной расстояния между узлами, соединенными данным ребром. На рисунке 6 также указаны значения индексов I для каждого i-го узла. Расчет начинаем с узла xN, имеющего индекс N=0, и завершаем установкой индексов у всех остальных узлов. Индекс при x0 равен 0=26, что означает LКр=26. Само направление кратчайшего пути находим аналогично первому случаю путем составления последовательности узлов по направлению убывания у них индексов от 0=26 до N=0. Для графа G2 кратчайший путь составляют узлы: x0, x5, x8, x11, x13, xN. На рисунке 6 кратчайший путь также выделен жирными стрелками. Обратим внимание на формирование индексов у x12: 12=11 как результат сложения индекса 13=6 с длиной l(x13, x12)=5. Как видим, работает правило минимизации длины возможных путей от x12 до xN.
Рисунок 5. Транспортная сеть с разными расстояниями между узлами
Похожие статьи
-
Основные понятия сетевых и графовых моделей Объектом исследования является сеть, состоящая из узлов и линий связи. Предполагается, что в сети имеется два...
-
Модели теории игр. Основные определения и термины В разных областях целенаправленной деятельности, например при разработке и эксплуатации АСУ, часто...
-
Применительно к предприятию КУП "СПЕЦКОММУНТРАНС" данная задача представляет собой задачу нахождения наилучшего маршрута движения автомобиля,...
-
Из перечисленного обзора типов ММ, составляющих предмет ИСО, можно выделить следующие особенности ММ ИСО [3]. - Системный подход, заставляющий...
-
Для достижения поставленной цели предприятию требуются материалы, оборудование, энергия, рабочая сила и другие ресурсы. Каждое предприятие такими...
-
Наиболее ранним способом формализации экономико-математических и ТС является представление физических явлений с помощью систем дифференциальных...
-
Постановка задачи применительно для КУП "СПЕЦКОММУНТРАНС": двум погрузчикам разной мощности, это автомобили ТО 28 и ТО 49, за 23 часа нужно погрузить на...
-
Теория игр исследует оптимальные стратегии в ситуациях игрового характера. К ним относятся ситуации, связанные с выбором наивыгоднейших производственных...
-
Модели линейного программирования. Основные определения Еще одним классом задач экономико-математического моделирования являются задачи линейного...
-
Основные понятия и обозначения Динамическое программирование как самостоятельная дисциплина сформировалась в пятидесятых годах двадцатого века. Большой...
-
Важным этапом изучения явлений предметов процессов является их классификация, выступающая как система соподчиненных классов объектов, используемая как...
-
Анализ комплексных расходов позволяет выявить дополнительные резервы снижения затрат на производство продукции [16], повышения эффективности...
-
Основные понятия теории экономико-математического моделирования Кибернетический подход к исследованию экономико-математических систем Обычно...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
-
Структура производства и управления КУП "СПЕЦКОММУНТРАНС" Краткая технико-экономическая характеристика В январе 1949г. по решению Гомельского...
-
Введение - Моделирование крупномасштабной транспортной сети предфрактальными графами
Транспорт - важный стратегический комплекс, в значительной степени определяющий мощь экономики страны и обеспечивающий нужды общества в перемещении людей...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
В основе модели крупномасштабной транспортной сети лежит принцип иерархической организации территорий (в нисходящем направлении). Рассмотрим карту сети...
-
Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...
-
Для заданного региона обслуживания с помощью технологии ГИС предоставляется карта автомобильных дорог, на которой указаны пункты, соответствующие...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Экономические задачи, сводящиеся к транспортным моделям - Экономико-математические методы
Алгоритмы и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с...
-
В результате проведенного финансового анализа предприятия можно сделать вывод, что состояние его удовлетворительное, но имеется ряд недостатков: В...
-
Введение - Оптимизация управлением производства на примере ОАО "Днепропетровский стрелочный завод"
Современный этап развития экономики характеризуется переходом предприятий на новые условия хозяйствования, необходимостью развития перспективных...
-
Определим понятие предфрактального графа индуктивно. Обозначим через - конечный связный n-вершинный граф с множеством вершин и множеством ребер, который...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Оптимальный план - Модели оптимального плана управления запасами
Найдем наилучший план поставок. План, для которого в моменты доставок очередных партий запас равен 0 (т. е. y(t) = 0), назовем напряженным. Утверждение...
-
Модель с определением точки заказа - Экономико-математические модели управления запасами
В реальных ситуациях следует учитывать время выполнения заказа Q. Для обеспечения бесперебойного снабжения заказ должен подаваться в момент, когда...
-
В предыдущем разделе мы определили, что существуют различные виды управления: производственное, техническое, государственное, идеологическое,...
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
Эффективность работы предприятия существенно зависит от организационной формы, выбранной для управления им. Поэтому организационная структура должна...
-
В начале пятилетнего периода работы предприятию выделена сумма в C руб. для приобретения нового оборудования. Стоимость одного комплекта оборудования...
-
На сегодняшний день основным видом деятельности ОАО "Огонек" является розничная торговля. В процессе труда человек вступает во взаимодействие с...
-
Основные направления совершенствования организационной структуры предприятия ОАО "Огонек". Любую перестройку структуры управления необходимо оценивать, в...
-
В современных условиях эффективность деятельности предприятия, прежде всего, определяется эффективностью использования главного ресурса - людей....
-
Нахождение функций роста экономики региона Применив математическую модель на практике, можно узнать на сколько увеличится валовый региональный продукт,...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
Нахождение кратчайшего пути в транспортной сети - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")