Поиск оптимального маршрута для городской мусороуборочной машины

Размещено на http://www.allbest.ru/

Минобрнауки России

Государственное образовательное учреждение высшего профессионального образования

Национальный исследовательский университет «МИЭТ»

Институт экономики и управления

Кафедра высшей математики №2

Курсовая работа

по дисциплине: «Методы моделирования экономики»

тема: «Поиск оптимального маршрута для городской мусороуборочной машины»

Выполнила студентка группы ЭУ-25:

Черемская В.А.

Научный руководитель:

Мустафин Н.Н.

Москва 2015

Постановка задачи

ОАО «УДХиБ» обслуживает район города, осуществляя сбор мусора из мусорных баков, расположенных вдоль дорог. Район представлен в виде неориентированного графа G (рис.1) . На нем парк мусороуборочных машин находится в вершине S, другие вершины - это пересечения дорог, ребра - дороги, цифры на ребрах - длина дорог (в километрах). Требуется найти замкнутый путь (цикл), проходящий по каждой дороге хотя бы один раз и имеющий наименьший километраж, с целью минимизировать расходы предприятия на бензин мусороуборочной машины.

Рис.1

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

В неориентированном графе цикл, который проходит по каждому ребру ровно один раз, называется эйлеровым циклом.

Решить данную задачу можно, найдя в графе G эйлеров цикл.

Если G содержит эйлеров цикл, то любой такой цикл будет решением поставленной задачи.

Общее количество ребер, инцидентных вершине x, называется степенью вершины x.

Основная теорема о существовании эйлеровых циклов в графе формулируется так:

Теорема (Эйлер). Связный неориентированный граф G содержит эйлеров цикл (эйлерову цепь) тогда и только тогда, когда число вершин нечетной степени равно 0( 0 или 2).

Если граф G - эйлеров, то с помощью следующего алгоритма, предложенного Флёри, можно найти эйлерову цепь: выйдя из произвольной вершины, идем по рёбрам графа произвольным образом, соблюдая лишь следующие правила:

а) стираем ребра по мере их прохождения, а также изолированные вершины (т.е. вершины, не инцидентные никакому ребру), которые при этом образуются;

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

В противном случае, если граф не содержит эйлерова цикла, то по крайней мере одно ребро, инцидентное некоторой нечетной вершине x, будет проезжаться дважды. Теперь нужно построить граф G^-(М*), содержащий такие искусственные ребра (вес искусственного ребра берется равным весу параллельного ему реального ребра) между парой вершин с нечетными степенями, что в сумме их вес будет минимален. То есть, необходимо найти множество цепей M* (цепного паросочетания для множества вершин нечетной степени), дающего наименьший дополнительный вес. Цикл наименьшего веса, проходящий по G, будет иметь вес, равный сумме весов всех ребер из G плюс сумма весов ребер в цепях из M*. Это то же самое, что и сумма всех ребер - реальных и искусственных - графа G^-(М*).

эйлеровый граф дейкстра прибыль

Алгоритм решения задачи

Шаг 1. Для начала следует проверить, является ли заданный граф эйлеровым.

Если да, то по алгоритму Флёри найдем эйлеров путь - это и будет решением задачи

Если нет - сначала сделаем граф эйлеровым, а затем найдем эйлеров цикл.

Шаг 2.Чтобы сделать граф эйлеровым необходимо:

а) Используя алгоритм решения задачи о кратчайшем пути ( в данном случае алгоритм Дейкстры) образуем (|V^-|x|V^-|) - матрицу D=(d_ij) между вершинными нечетной степени, где d_ij - длина кратчайшего пути, идущего из некоторой вершины v_i V^- в другую вершину v_j V^- .

Алгоритм Дейкстры применяется для решения задачи о кратчайшем пути при условии, что w(e) 0 для всех e E. Алгоритм основан на присвоении вершинам меток. Первая часть метки l(u) вершины u указывает текущее кратчайшее расстояние от вершины s до вершины u, вторая - предшествующую вершину в текущем пути от вершины s до вершины u. Метки могут быть временными или постоянными. Постоянная метка не может изменяться в процессе выполнения алгоритма.

б) В полном графе на множестве вершин V^- найдем наибольшее паросочетание М* с минимальным весом (в соответствии с матрицей весов D). Это можно сделать эффективно с помощью венгерского алгоритма решения задачи о назначениях.

в. Если вершина v_a сочетается с вершиной v_b, то определим цепь _ab наименьшего веса (из v_a в v_b), соответствующую весу d_ab, Добавим искусственные ребра в G, соответствующие рёбрам из _ab, и проделаем это для всех других цепей из множества M*, в результате чего получится граф G^-(M*).

Шаг 3. Сумма весов всех ребер графа G^-(M*) (вес искусственного ребра берётся равным весу параллельного ему реального ребра), равна минимальному весу цикла, проходящего по G. При этом число прохождений цикла по ребра (v_i, v_j) равно общему числу параллельных рёбер между v_i V и v_j V^- в G^-(M*).

Решение задачи

Данный граф имеет 11 вершин и 21 реберо. Множество вершин нечётной степени этого графа есть {s;v2;v5; v9;v10;v11}. Данный граф не является эйлеровым.

Используя алгоритм нахождения кратчайшего пути Дейкстры, найдем матрицу D кратчайших расстояний между каждой парой вершин с нечётными степенями. D=

Далее с помощью венгерского алгоритма решения задачи о назначениях в соответствие с матрицей весов D в полном графе на шести вершинах находим наибольшее паросочетание M* с минимальным весом. Таковым является паросочетание (v2; s), (v9;v5), (v10, v11) веса 4, 23. Соединяем вершины v2 и s искусственным ребром длиной 0, 95, вершины v9 и v5 искусственным ребром длиной 1 и вершины v10 и v11 искусственным ребром длиной 2, 28.

Получился граф G^-(М*), изображенный на рис.2; пунктиром показаны искусственные ребра.

Рис.2

Из рис.2 видно, что оптимальный цикл в графе G проходит через рёбра (v2; s), (v9;v5), (v10, v11) дважды, а через все остальные рёбра - один раз.

Как только построен граф G^-(М*), то могут быть сразу же найдены по алгоритму Флёри эйлеров цикл этого графа и соответствующий оптимальный маршрут, проходящий по первоначальному графу G. Один из таких эйлеровых циклов задается последовательностью вершин (начиная с вершины s):s, v1, v7, v8, v11, v10, v9, v4, v5, v9, v5, v10, v11, v6, v7, v3, v6, v5, v3, v2, v1, v8, s, v2, s. Вес этого цикла равен 29. Этот цикл является также соответствующим оптимальным циклом, проходящим по первоначальному графу.

Найденный путь является одним из оптимальных для решения данной задачи, то есть он позволяет найти кратчайший путь, при котором будет собран мусор на всех улицах района.

Вывод

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

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

Список литературы

1. А.М. Ревякин, И.В. Бардушкина. Математические методы моделирования в экономике : учеб. пособие. - М.:МИЭТ, 2013.

2. Н. Кристофидес. Теория графов - М.: Мир, 1978

3. Э. Майника. Алгоритмы оптимизации на сетях и графах - М.:Мир, 1981

Размещено на Allbest.ru