Дан ориентированный граф с множеством вершин V=s,1,2,3,4,5,6,7,8,t и множеством ребер – ориентированных дуг
R=s,1,s,2,s,3,1,4,1,2,1,5,2,3,3,4,3,6,4,5,4,t,5,t),6,5,(6,t.
Орграф задает транспортную сеть автомобильных дорог. Затраты по доставке крупного груза вдоль каждого участка сети определяются с помощью весовых коэффициентов ребер: cs1=32, cs2=37, cs3=72, c14=10, c12=11, c15=21, c23=18, c34=20, c36=27, c45=21, c4t=29, c5t=64, c65=14, c6t=26.
Необходимо выбрать оптимальный маршрут доставки груза и определить его длину.
Указать вид задачи оптимизации и математическую модель задачи.
Нужно полное решение этой работы?
Решение
Вид задачи: выбор оптимального маршрута перевозки грузов.
Пусть дан пример нахождение кратчайшего пути. Итак, дана сеть автомобильных дорог, соединяющих области города. Некоторые дороги односторонние. Найти кратчайшие пути от центра города до каждого города области.
Для решения указанной задачи можно использовать алгоритм Дейкстры – алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Работает только для графов без рёбер отрицательного веса.
Сначала построим сетевой график, который задает сеть автомобильных дорог.
Далее выполним вычисления непосредственно на сетевом графике, определим наиболее оптимальный маршрут доставки груза, а также его длину.
С помощью алгоритма Дейкстры найдем кратчайший маршрут из вершины s до вершины t.
Метка самой вершины s полагается равной 0, метки остальных вершин – недостижимо большое число. Это отражает то, что расстояния от вершины s до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Первый шаг
Минимальную метку имеет вершина s
. Её соседями являются вершины 1, 2 и 3. Обходим соседей вершины по очереди.
Первый сосед вершины s – вершина 1, потому что длина пути до неё минимальна. Длина пути в неё через вершину s равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из s в 1-ю, то есть 0+32=32. Это меньше текущей метки вершины 1, поэтому новая метка 1-ой вершины равна 32.
Аналогично находим длины пути для всех других соседей (вершины 2 и 3).
Все соседи вершины s проверены. Текущее минимальное расстояние до вершины s считается окончательным и пересмотру не подлежит. Вершина s отмечается как посещенная.
Второй шаг
Шаг_1 алгоритма повторяется. Находим «ближайшую» из непосещенных вершин. Это вершина 1 с меткой 32.
Пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 1-ю вершину. Соседями вершины 1 являются вершины 2, 4 и 5.
Проверим первого соседа вершины 1 – вершину 4, так как имеет минимальную метку из вершин, отмеченных как не посещённые
Задать вопрос
на новый заказ в Автор24.
