Оптимизация затрат отдела доставки интернет-магазина «Лабиринт»
Автор: Юлия Арсентьева • Сентябрь 26, 2019 • Курсовая работа • 1,702 Слов (7 Страниц) • 367 Просмотры
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Московский институт электронной техники»
Курсовая работа
по дисциплине «Методы моделирования экономики»
Тема: «Оптимизация затрат отдела доставки интернет-магазина «Лабиринт»»
Выполнила студентка группы М-24
Арсентьева Ю. А.
Научный руководитель
канд. физ.-мат. наук, доцент Ревякин А. М.
Москва 2019
Содержание
- Постановка задачи………………………………………………….. 3
- Основная расчетная часть.………………………………………… 4
- Выводы ……………………………………………………………… 9
- Список литературы ………………………………………………… 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 (М*), выполним следующие преобразования.
...