Оптимизация затрат отдела доставки интернет-магазина «Лабиринт»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Московский институт электронной техники»

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

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

Тема: «Оптимизация затрат отдела доставки интернет-магазина «Лабиринт»»

Выполнила студентка группы М-24

Арсентьева Ю. А.

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

канд. физ.-мат. наук, доцент Ревякин А. М.

Москва 2019

Содержание

1. Постановка задачи………………………………………………….. 3
2. Основная расчетная часть.………………………………………… 4
3. Выводы ………………………………………………………………  9
4. Список литературы ………………………………………………… 11

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

Интернет-магазин «Лабиринт» занимается продажей книг. Компания существует на рынке с 2015 года и в целях повышения объема выручки стала расширяться географически и заниматься услугой «Доставка».

Для увеличения выручки был организован новый отдел доставки в городе Зеленоград, в который входят: оператор, курьер и менеджер отдела доставки. Отдел каждый день с 10 часов в течение 3 часов сначала принимает заказы, а потом развозит их заказчикам. Заказы принимаются до 22:00. В течение дня курьер развозит заказы и возвращается назад в отдел каждые три часа.

В целях экономии затрат перед отделом доставки стояла основная логистическая задача: доставить все заказы, поступившие в магазин, затратив минимальное расстояние и время на доставку.

Основная расчетная часть

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

Обозначим улицы города, где есть заказчики, как рёбра aⱼ графа G, а пересечения дорог (перекрестки) – как вершины. Длине дороги будет соответствовать величина w(aⱼ) – вес ребра aⱼ. Тогда проблема оптимальной для компании доставки книг в данном районе сводится к нахождению пути (цикла) с наименьшим расстоянием в графе G, проходящего хотя бы один раз по каждому ребру с возвратом в исходную току отправления курьера.

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

Рассмотрим один из примеров заказа, который поступил в магазин. На рисунке 1.1 звездой обозначен отдел доставки интернет-магазина «Лабиринт», а галочками – адреса заказчиков в г. Зеленоград.

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

[pic 1]

Рис. 1.1  Заказ, который поступил в магазин Лабиринт

[pic 2]

Рис. 1.2  Граф G. Заказ в магазине Лабиринт

Множество вершин нечетной степени этого графа - {Л, 4, 5, 8} равно 4. Следовательно, связный граф G не содержит эйлеров цикл, так как число вершин нечётной степени не равно 0 или 2. Для того чтобы получить эйлеров граф G (М*), выполним следующие преобразования.

...