Решение задачи о кратчайшем маршруте при организации оптимального плана перевозок

Краткое описание

СОДЕРЖАНИЕ

ВВЕДЕНИЕ…3

1.ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЗАДАЧ О КРАТЧАЙШЕМ РАССТОЯНИИ

1.1.Определение..4

1.2.Задача о кратчайшем пути с учетом дополнительных ограничений...5

1.3.Алгоритмы…6

1.4 Задача поиска кратчайшего пути из одной вершины во все остальные…10

-Взвешенный ориентированный граф…10

-Ориентированный граф с неотрицательными весами…10

-Ориентированный граф с произвольными весами…11

1.5. Задача о кратчайшем пути между всеми парами вершин…11

2.ПРИМЕР РЕШЕНИЯ ЗАДАЧ О КРАТЧАЙШЕМ РАССТОЯНИИ ПРИ ОРГАНИЗАЦИИ ОПТИМАЛЬНОГО ПЛАНА ПЕРЕВОЗОК.

ЗАКЛЮЧЕНИЕ…26

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ..27

ВВЕДЕНИЕ

На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа, дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения.

Задача о кратчайшем пути — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь.

Кратчайшая (простая) цепь часто называется геодезической .

Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для ее решения.

У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе.

Значимость данной задачи определяется ее различными практическими применениями. Например в GPS-навигаторах, где осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Сумма расстояний всех дорог между перекрестками должна быть минимальной, тогда найден самый короткий путь.

Цель курсовой работы  - рассмотреть решение задачи о кратчайшем маршруте при организации оптимального плана перевозок.