Исходные данные
Груз находится в пункте А – 4000 кг. Используется автомобиль грузоподъемностью 2,5 т; груз – П класса (γ = 0,8). Необходимо организовать перевозку между пунктами с минимальным пробегом подвижного состава.
Таблица 1
| Пункты
|
Б
|
В
|
Г
|
Д
|
Е
|
Ж
|
З
|
И
|
К
|
Л
|
| Выгрузка
|
700 | 300 | 500 | 300 | 600 | 400 | 200 | 200 | 400 | 400 |
| Погрузка
|
600 | 800 | 600 | 200 | 200 | 500 | 100 | 400 | 300 | 300 |
Рисунок 1 Схема размещения пунктов
Решение
Этап 1 Нахождение кратчайшей сети, связывающей все пункты
Рисунок 2 Кратчайшая связывающая сеть
Назовем все пункты, указанные на рис.1, вершинами сети, а линию, соединяющую две соседние вершины, - звеном.
Кратчайшей связывающей сетью называется незамкнутая сеть, связывающая две и более вершины с минимальной суммарной длиной всех соединяющих их звеньев.
На схеме (рис.1)находится наименьшее звено. В данном случае это звено А-Б = 4 км
. Затем рассматриваются все звенья, связанные одной из своих вершин с выбранным звеном, т.е. звенья: А-В = 5км
, Б-З = 7 км
. Из них выбирается звено с наименьшим расстоянием (А - В = 5 км
). Далее рассматриваются все звенья, связанные с вершинами полученной ломаной линии Б-А-В, из них выбирается наименьшее, и так до тех пор, пока не будут выбраны все вершины сети. При этом нельзя выбирать звено, соединяющее две ранее включенные в сеть вершины. На рис. 2 представлена кратчайшая связывающая сеть.
Этап 2 Набор пунктов в маршруты
По каждой ветви сети (рис.2), начиная с той, которая имеет наибольшее количество звеньев, производится группировка пунктов для включения в маршрут. В каждый маршрут группируются пункты с учетом количества ввозимого и вывозимого грузов (табл. 1) и вместимости единицы подвижного состава . Если все пункты данной ветви не могут быть включены в один маршрут, то ближайшие к другой ветви пункты группируются вместе с пунктами этой ветви.
Необходимо учитывать, что максимальная вместимость автомобиля равна 2т. (2,5*0,8) Исходя из этого, пункты, указанные на рис. 2, группируются следующим образом. (табл. 2)
Таблица 2
| Маршрут 1 | Маршрут 2 | ||||
| Пункт | Количество груза, кг | Пункт | Количество груза, кг | ||
| Б | 600 | 700 | В | 800 | 300 |
| З | 100 | 200 | Е | 200 | 600 |
| К | 300 | 400 | Д | 200 | 300 |
| И | 400 | 200 | Ж | 500 | 400 |
| Г | 600 | 500 | Л | 300 | 400 |
| Итого | 2000 | 2000 | Итого | 2000 | 2000 |
Этап 3. Определение очередности объезда пунктов маршрута
Этот этап расчетов имеет целью связать все пункты каждого маршрута, начиная с пункта А, замкнутой линией, которой соответствует кратчайший путь объезда этих пунктов. С этой целью проводятся специальные расчеты, один из методов которых, называемый «методом треугольников», приводится ниже.
Для каждого маршрута строят таблицу, называемую симметричной матрицей. Для маршрута 1 она приведена в табл. 3. По главной диагонали в ней размещены пункты, включаемые в маршрут. Цифры в клетках показывают кратчайшие расстояния между ними. Для примера матрица является симметричной Cij
= Cji , хотя приведенный ниже способ применим для размещения несимметричных матриц.
Начальный маршрут строим для трех пунктов матрицы А,Г,И, имеющих наибольшие значения величины, показанной в итоговой строке (77, 73, 70 ), т.е. маршрутГАИГ.
Таблица 3
| А
|
4 | 12 | 17 | 23 | 17 |
| 4 | Б
|
7 | 13 | 20 | 21 |
| 12 | 7 | З
|
5 | 13 | 19 |
| 17 | 13 | 5 | К
|
8 | 14 |
| 23 | 20 | 13 | 8 | И
|
6 |
| 17 | 21 | 19 | 14 | 6 | Г
|
| 73 | 65 | 56 | 57 | 70 | 77 |
Для включения последующих пунктов в маршрут выбираем из оставшихся пунктов в таблице пункт, имеющий наибольшую сумму, например, Б (65). Затем необходимо определить между какими пунктами начального маршрута его следует вставить. Для этого следует поочередно вставлять пункт Б между каждой соседней парой пунктов ГА, АИ, ИГ.
При этом для каждой пары пунктов необходимо найти величину приращения маршрута (∆) по формуле:
∆kp
= Cki
+ Cip
– Ckp
,
где С – расстояние, км
;
i - индекс включаемого пункта;
k – индекс первого пункта из пары;
p – индекс второго пункта из пары.
При включении пункта Б между первой парой пунктов ГА определяем размер приращения ∆АГ при условии, что i =Б, k = A, p = Г. Тогда
∆ГА
= САБ
+ СГБ
– СГА
.
Соответствующие расстояния между пунктами берутся в табл. 3 и получаем ∆ГА
= 21 + 4 – 17 = 8.
Для пунктов БВ приращение маршрута при включении пункта Е равно:
∆ИГ
= СГБ
+ СИБ
– СИГ
, т.е. ∆ИГ
= 20 + 21 – 6 = 35.
Для пунктов АИ соответственно:
∆АИ
= СИБ
+ САБ
– САИ
, т.е. ∆АИ
= 4+ 20 – 23 = 1.
Из полученных значений выбираем минимальное значение, т.е. ∆АИ
= 1 и между соответствующими пунктами вставляем пункт Б. Получаем маршрут ГАБИГ.
Вновь в табл.3 выбираем один из еще не включенных в маршрут пунктов К. Все дальнейшие расчеты проводятся, как это было показано выше:
∆ГА
= СГК
+ САК
– СГА
= 14+17 – 17 = 14
∆АБ
= САК
+ СБК
– САБ
= 17 + 13 – 4 = 26
∆БИ
= СБК
+ СИК
– СБИ
= 13 + 8 – 20 = 1
&#
= СИК
+ СГК
– СИГ
= 6 + 14 – 6 = 14 .
Так как наименьшей величиной является ∆БИ
, пункт К включаем между БИ и получаем маршрут ГАБКИГ.
Остается определить, куда следует вставить пункт З. Производим соответствующие расчеты :
∆ГА
= СГЗ
+ САЗ
– СГА
= 19 + 12 – 17 = 14
∆АБ
= САЗ
+ СБЗ
– САБ
= 12 + 7 – 4 = 15
∆БК
= СБЗ
+ СКЗ
– СБК
= 7 + 5 – 13 = -1
∆КИ
= СКЗ
+ СИЗ
– СКИ
= 5 + 13 – 8 = 10
∆ИГ
= СИЗ
+ СГЗ
– СИГ
= 13 + 19 – 6 = 26.
Здесь наименьшее приращение ∆БК
, поэтому получаем окончательный порядок объезда пунктов первого маршрута ГАБЗКИГ. Можно утверждать, что полученная последовательность объезда дает наименьший или весьма близкий к наименьшему пути путь объезда пунктов маршрута 1.
По маршруту 2 проводятся аналогичные расчеты, исходные данные для которых представлены в табл. 4. В результате указанных расчетов порядок объезда пунктов в этом маршруте будет ЛЖДАВЕДЛ.
Если указанные маршруты являются только развозочными или только сборными, то на этом все расчеты заканчиваются. Если же по маршруту одновременно производится развоз и сбор груза, необходимо провести дополнительный, четвертый этап расчетов.
Таблица 4
| А
|
5 | 10 | 10 | 20 | 27 |
| 5 | В
|
5 | 14 | 25 | 31 |
| 10 | 5 | Е
|
9 | 20 | 26 |
| 10 | 14 | 9 | Д
|
10 | 17 |
| 20 | 25 | 20 | 10 | Ж
|
14 |
| 27 | 31 | 26 | 17 | 14 | Л
|
| 72 | 80 | 70 | 60 | 89 | 115 |
ЛЖВЛ, чтобы вставить А рассчитываем:
∆ЛЖ
= СЛА
+ СЖА
– СЛЖ
= 27+20 – 14 = 33
∆ЖВ
= СЖА
+ СВА
– СЖВ
= 20 + 5 – 25 = 0
∆ВЛ
= СВА
+ СЛА
– СВЛ
= 5 + 27 – 31 = 1
Отсюда получаем наименьше значение и ставим А между ЖВ и маршрут становится ЛЖАВЛ. Далее вставляем Е:
∆ЛЖ
= СЛЕ
+ СЖЕ
– СЛЖ
= 26+20 – 14= 32
∆ЖА
= СЖЕ
+ САЕ
– СЖА
= 20 + 10 – 20 = 10
∆АВ
= САЕ
+ СВЕ
– САВ
= 10 + 5 –5= 10
∆ВЛ
= СВЕ
+ СЛЕ
– СВЛ
= 5 + 26 – 31 = 0 .
Отсюда маршрут становится ЛЖАВЕЛ, ставим пункт Д.
∆ЛЖ
= СЛД
+ СЖД
– СЛЖ
= 17 + 10 – 14 = 13
∆ЖА
= СЖД
+ САД
– СЖА
= 10 + 10 –20= 0
∆АВ
= САД
+ СВД
– САВ
= 10 + 14 –5= 19
∆ВЕ
= СВД
+ СЕД
– СВЕ
= 14 + 9 – 5 = 18
∆ЕЛ
= СЕД
+ СЛД
– СЕЛ
= 9 + 17 – 26 = 0.
И так получаем окончательный порядок объезда пунктов второго маршрута ЛЖДАВЕДЛ.
Рисунок 3 Схема движения по маршрутам № 1 и 2
Этап 4. Определение возможности одновременного развоза и сбора груза на маршруте
Так как вместимость подвижного состава ограничена, необходимо определить возможность его использования для одновременного развоза и сбора груза на маршруте в той последовательности объезда пунктов, которая получена на предыдущем этапе расчетов.
В табл. 5 пункты маршрута 1 приведены в полученной последовательности и дан расчет наличия груза после погрузки и выгрузки на каждом пункте. Из таблицы видно, что на протяжении всего маршрута автомобиль не будет перегружен, так как в условии задано, что максимальная загрузка автомобиля составляет 2т (2,5*0,8).
Таблица 5
| Пункт | Количество груза, кг
|
||
| Погрузка | Выгрузка | Всего в автомобиле | |
| А | - | 2000 | 2000 |
| Б | 600 | 700 | 1900 |
| З | 100 | 200 | 1800 |
| К | 300 | 400 | 1700 |
| И | 400 | 200 | 1900 |
| Г | 600 | 500 | 2000 |
В таблице . 6 сделаем то же самое для маршрута 2 (но 2 проезд через пункт дД не будем учитывать, так как там уже ничего не загружается и не выгружается)
Таблица 6
| Пункт | Количество груза, кг
|
||
| Погрузка | Выгрузка | Всего в автомобиле | |
| А | - | 2000 | 2000 |
| В | 800 | 300 | 2500 |
Уже на втором пункте В автомобиль не вместит количество груза, которое необходимо иметь в автомобиле при такой последовательности движения по маршруту.
Одним из способов избежать это является изменение направления движения на маршруте, что не повлечет за собой увеличения расстояния объезда. Если так поступить на маршруте 2, то последовательность объезда будет АДЖЛЕВ, т.е. противоположная маршруту, представленному на рис. 3. Из табл. 7 видно, что это изменение позволит выполнить перевозки по данному маршруту.
Таблица 7
| Пункт | Количество груза, кг
|
||
| Погрузка | Выгрузка | Всего в автомобиле | |
| А | - | 2000 | 2000 |
| Д | 200 | 300 | 1900 |
| Ж | 500 | 400 | 2000 |
| Л | 300 | 400 | 1900 |
| Е | 200 | 600 | 1500 |
| В | 800 | 300 | 2000 |
Министерство образования и науки Российской Федерации
Алтайский Государственный Технический Университет
им. И.И. Ползунова
Кафедра «Экономика и производственный менеджмент»
Расчетное задание
по дисциплине: «Логистика»
Расчетное задание выполнил
студент гр. Ма-71 Попова Е. В.
Преподаватель: Родина Г.Е.
Барнаул – 2010