Министерство образования Российской Федерации
Государственное образовательное учреждение высшего профессионального образования
Государственный Университет Управления
Институт Заочного Обучения
Контрольная работа
по дисциплине
«Логистика»
тема
«Составление рациональных развозочных маршрутов при расчетах вручную» Вариант №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 – М – Ц).