Министерство образования Российской Федерации
Государственное образовательное учреждение высшего профессионального образования
Государственный Университет Управления
Институт Заочного Обучения
Контрольная работа
по дисциплине
«Логистика»
тема
-
«Составление рациональных развозочных маршрутов при расчетах вручную» Вариант №11
Выполнил студент
группы
Студенческий билет №
Москва
ОГЛАВЛЕНИЕ
Основные обозначения……………………………………………………..……..3
Формулировка задачи………………………………………………………..……3
Исходные данные……………………………………………………….….…..….4
Решение.
Составление рациональных развозочных маршрутов при расчетах
вручную (2 этапа)……………………………………………..…….......................5
Результаты расчетов………………………………………………………………9
Основные обозначения.
Гi – населенный пункт (пункт потребления); i = A – Z, 0 – 9;
Ц – распределительный центр (или склад, начальный пункт);
q – потребность заказчиков в единицах объема груза (стандартная коробка);
грузоподъемность транспортного средства;
Cij – стоимость перевозки (расстояние).
Формулировка задачи.
Имеются пункты потребления Гi (i = A – Z, 0 – 9). Груз необходимо развести из начального пункта (распределительного центра – Ц) во все остальные пункты, т. е. к потребителям. Потребность пунктов потребления в единицах объема груза составляет: qA, qB…qZ; q0…q9.
В начальном пункте (распределительном центре – Ц) имеются транспортные средства грузоподъемностью: Q1, Q2…Qd. Для каждой пары пунктов (Гi , Гj ) определяют стоимость перевозки Cij ? 0.
Требуется найти m-количество замкнутых путей 11, 12…1m из единственной общей точки (распределительного центра – Ц) так, чтобы выполнялось условие:
Lk ® min
k = 1
Исходные данные.
Таблица 1. Заявки потребителей продукции на один день.
Показатели | Потребители продукции |
Количество коробок | G | K | M | N | U | W | Z | 1 | 2 |
Объем продукции | 28 | 46 | 11 | 65 | 39 | 15 | 27 | 12 | 57 |
Груз находится в пункте Ц – 300 коробок. Используется автомобиль грузоподъемностью 150 коробок. Необходимо организовать перевозку между пунктами потребления с минимальным пробегом подвижного состава.
Таблица 2. Исходные данные о расстояниях между пунктами потребления сети развоза мелких партий груза.
Расстояния между пунктами сети развоза продукции |
Ц–G | G–K | K– W | W-Z | Z– 1 | 1– 2 | 2–Ц | Ц– M | G– N | K– N | W- U | Z– U | 1– U | 2– U | 2– M | M– N | N– U |
4,2 | 2,5 | 9,3 | 2,7 | 1,8 | 5,1 | 3,7 | 2,8 | 1,8 | 2,1 | 2,8 | 5,2 | 4,3 | 3,3 | 6,1 | 2,2 | 3,9 |
Схема 1. Размещение пунктов потребления и транспортные связи между ними.
3,7
5,1
2,8
3,3 6,1 4,2
1,8 4,3
2,2
1,8
5,2
3,9
2,8 2,1 2,5
2,7
9,3
Ц
Решение.
Составление рациональных развозочных маршрутов при расчетах вручную.
I этап.
Строим кратчайшую сеть, связывающую все пункты без замкнутых контуров (рис. 1).
Рис. 1 Кратчайшая связывающая потребителей сеть («минимальное дерево»).
57 кор.
Ц
5,1
2,8
12 кор.
11 кор.
4,3
39 кор. 2,2
65 кор.
5,2 1,8
2,7 9,3 2,5
27 кор.
15 кор. 46 кор. 28 кор.
Далее, по каждой ветви сети, начиная с пункта наиболее удаленного от распределительного центра, группируем пункты по маршрутам с учетом:
Исходя из заданной грузоподъемности собственного транспортного средства – 150 коробок и количества развозимого груза, все пункты потребления можно сгруппировать в 2 группы (табл. 3).
Таблица 3. Распределение пунктов потребления по группам (маршрутам).
Группа I | Группа II |
пункт | объем заказа, коробок | пункт | объем заказа, коробок |
2 | 57 | K | 46 |
1 | 12 | G | 28 |
U | 39 | N | 65 |
Z | 27 | M | 11 |
W | 15 | | |
Итого: | 150 коробок | Итого: | 150 коробок |
Сгруппировав пункты по группам, переходим ко второму этапу расчетов.
II этап.
Определяем рациональный порядок (маршрут) объезда пунктов каждой группы пунктов. Для этого строим таблицу-матрицу, в которой по диагонали размещаем пункты, включаемые в маршрут, и начальный пункт Ц, а в соответствующих клетках – кратчайшие расстояния между ними (табл. 4).
Таблица 4. Таблица-матрица для маршрута 1.
Ц | 3,7 | 8,8 | 7,0 | 10,6 | 9,8 |
3,7 | 2 | 5,1 | 3,3 | 6,9 | 6,1 |
8,8 | 5,1 | 1 | 4,3 | 1,8 | 4,5 |
7,0 | 3,3 | 4,3 | U | 5,2 | 2,8 |
10,6 | 6,9 | 1,8 | 5,2 | Z | 2,7 |
9,8 | 6,1 | 4,5 | 2,8 | 2,7 | W |
39,9 | 25,1 | 24,5 | 22,6 | 27,2 | 25,9 |
Начальный маршрут строим для трех пунктов матрицы Ц – Z – W – Ц, имеющих наибольшее значение суммы расстояний в итоговой строке, соответственно, 39,9; 27,2; 25,9.
Для включения последующих пунктов выбираем из оставшихся пункт, имеющий наибольшую сумму, т. е. пункт 2 (сумма 25,1) и решаем между какими пунктами его следует включать, между (Ц – Z) – 1 пара, (Z – W) – 2 пара или между (W – Ц) – 3 пара.
Для каждой пары пунктов необходимо найти величину приращения маршрута Dkp по формуле:
Dkp = Cki + Cip – Ckp; где С – расстояние, км; k – индекс первого пункта из пары; i – индекс включаемого пункта; p – индекс второго пункта из пары.
а) При включении пункта 2 между первой парой пунктов Ц и Z определяем размер приращения, исходя из условия: i = 2; k = Ц; р = Z.
Dцz = Сц2 + С2z – Сцz, подставляя значения из таблицы 2 находим:
Dцz = 3,7 + 6,9 – 10,6 = 0,0
б) Таким же образом определим приращение Dzw, если пункт 2 включить между пунктами Z и W:
Dzw = Cz2 + C2w – Czw = 6,9 + 6,1 – 2,7 = 10,3
в) Приращение Dwц, если пункт 2 включить между пунктами W и Ц:
Dwц = Сw2 + С2ц – Сwц = 6,1 + 3,7 – 9,8 = 0,0
Из полученных значений выбираем минимальное приращение Dцz = 0, тогда маршрут Ц – Z – W – Ц преобразуется в маршрут Ц – 2 – Z – W – Ц.
Используя этот метод и формулу приращения, определяем между какими пунктами надо расположить пункты 1 и U.
Начнем с пункта 1, т.к. размер суммы в итоговой таблице 24,5 > 22,6.
Dц2 = Сц1 + С12 – Cц2 = 8,8 + 5,1 – 3,7 = 10,2;
D2z = С21 + С1z – C2z = 5,1 + 1,8 – 6,9 = 0,0 ® min;
Dzw = Cz1 + C1w – Czw = 1,8 + 4,5 – 2,7 = 3,6;
Dwц = Сw1 + С1ц – Сwц = 4,5 + 8,8 – 9,8 = 3,5.
Пункт 1 должен быть между пунктами 2 и Z. Тогда маршрут получит вид: Ц – 2 – 1 – Z – W – Ц.
Определим между какими пунктами надо расположить пункт U.
Dц2 = Сцu + Сu2 – Cц2 = 7,0 + 3,3 – 3,7 = 6,6;
D21 = С2u + Сu1 – C21 = 3,3 + 4,3 – 5,1 = 2,5;
D1z = C1u + Cuz – C1z = 4,3 + 5,2 – 1,8 = 7,7;
Dzw = Czu + Cuw – Czw = 5,2 + 2,8 – 2,7 = 5,3;
Dwц = Сwu + Сuц – Сwц = 2,8 + 7,0 – 9,8 = 0,0 ® min.
Пункт должен находиться между пунктами W и Ц, таким образам, окончательный порядок движения по маршруту: Ц – 2 – 1 – Z – W – U – Ц.
Рис. 2. Порядок движения по маршруту 1.
Ц
3,7
5,1 7,0
1,8 2,7 2,8
L = 23,1 км
Далее определяем кратчайший путь объезда пунктов по маршруту 2. Определяем рациональный порядок объезда пунктов маршрута 2. Для этого формируется таблица-матрица маршрута 2, в которой по диагонали размещаются пункты, включаемые в маршрут 2, и начальный пункт Ц, а в соответствующих клетках кратчайшие расстояния между ними.
Таблица 5. Таблица-матрица для маршрута 2.
Ц | 6,7 | 4,2 | 5,0 | 2,8 |
6,7 | K | 2,5 | 2,1 | 4,3 |
4,2 | 2,5 | G | 1,8 | 4,0 |
5,0 | 2,1 | 1,8 | N | 2,2 |
2,8 | 4,3 | 4,0 | 2,2 | M |
18,7 | 15,6 | 12,5 | 11,1 | 13,3 |
Начальный маршрут строим для трех пунктов матрицы: Ц – К – М – Ц, имеющих наибольшие значения в итоговой строке: 18,7; 15,6; 13,3.
Для включения последующих пунктов выбираем из оставшихся пункт, имеющий наибольшую сумму – 12,5 (пункт G) и решаем между какими пунктами его следует включать: Ц – К, К – М или М – Ц. Поэтому для каждой пары надо найти величину приращения маршрута. В новый маршрут включаем пункт N.
а) Включение пункта G между парами пунктов Ц – К, К – М и М – Ц:
Dцk = Cцg + Cgk – Cцk = 4,2 + 2,5 – 6,7 = 0,0 ® min;
Dkm = Ckg + Cgm – Ckm = 2,5 + 4,0 – 4,3 = 2,2;
Dmц = Cmg + Cgц – Cmц = 4,0 + 4,2 – 2,8 = 5,4.
Пункт G следует включить между парой пунктов Ц – К, т. е. маршрут Ц – К – М – Ц превращается в маршрут Ц – G – К – М – Ц.
б) Пункт N включаем в маршрут Ц – G – К – М – Ц:
Dцg = Cцn + Cng – Cцg = 5,0 + 1,8 – 4,2 = 2,6;
Dgk = Cgn + Cnk – Cgk = 1,8 + 2,1 – 2,5 = 1,4;
Dkm = Ckn + Cnm – Ckm = 2,1 + 2,2 – 4,3 = 0,0 ® min;
Dmц = Cmn + Cnц – Cmц = 2,2 + 5,0 – 2,8 = 4,4.
Пункт N включаем между К и М: Ц – G – К – N – М – Ц.
Рис. 3. Порядок движения по маршруту 2.
Ц
2,2 2,8
2,1 4,2
2,5
L = 13,8 км
Результаты расчетов.
Получено 2 маршрута, порядок движения по которым представлен на рисунке 2 (1 маршрут: Ц – 2 – 1 – Z – W – U – Ц) и рисунке 3 (2 маршрут: Ц – G – К – N – М – Ц).
12