![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Модели задач транспортной логистики
Метод присвоения меток Необходимо найти кратчайший путь на графе от какой-то выделенной вершины до любой другой вершины. Данная задача, часто применяется для построения оптимальных путей доставки товаров.
Пример. Узел 7 – склад, остальные узлы – строительные площадки компании. Показатели на ребрах – расстояния в километрах.
Необходимо найти кратчайшее расстояние от склада до каждой строительной площадки Каждому узлу присваиваем метку из двух чисел. Первое число – это минимальное расстояние от узла 7 до данного узла, второе – номер предыдущего узла на пути от узла 7 к данному узлу. Узел для которого был определен путь от узла 7 называется помеченным. Узел для которого такой путь еще не определен, соответственно, непомеченный. Если определено кратчайшее расстояние от узла 7 до данного узла, то соответствующую метку назовем постоянной и будем обозначать в круглых скобках. Все остальные метки назовем временными и будем обозначать в квадратных скобках. Узлы с постоянными метками будем закрашивать. Итак, узлу 7 присваиваем метку (0, S), где 0 – это расстояние от узла 7, S – обозначение стартового узла.
Узел 7 связан с узлами 2, 4, 6. Длины соответствующих ребер равны 17, 5, 6. Поэтому узлам 2, 4, 6 присваиваем временные метки – [17, 7], [5, 7] и [6, 7] соответственно (первое число – длина пути от узла 7 до данного узла, а второе – номер предшествующего узла).
После выполнения данной операции можно сделать два следующих шага: найти участок минимальной длины и соответствующую временную метку (метки) сделать постоянной, пометить ее сплошной штриховкой; узел (узлы), которому соответствует появившаяся постоянная метка, становится новой точкой отсчета. Анализируем полученную ситуацию. Минимальное расстояние от склада у пункта 4, поэтому превращаем его метку в постоянную и помечаем его.
Рассматриваем узел 4 как новую точку отсчета, он непосредственно связан с узлом 2 и 5. Найдем и проставим соответствующие временные метки: для узла 2 – [5+6, 4]=[11, 4]; для узла 5 – [5+4, 4]=[9, 4]. Метка на втором узле уже есть, сопоставим ее с новой. Так как расстояние на новой метке меньше, т.е. 11< 17, то старую метку заменяем новой. Затем снова анализируем все оставшиеся временные метки. Выполняем аналогичные действия, пока не превратим все узлы в помеченные.
|