Логистика 15 (стр. 3 из 5)
Поэтому для каждой пары пунктов необходимо найти величину приращения маршрута по формуле:
kp= Cki+Cip- Ckp
где С-расстояние ,км; i- индекс включаемого пункта; k- индекс первого пункта из пары; p- индекс второго пункта из пары.
При включении пункта В между первой парой пунктов А и К ,определяем размер приращения ΔАК при условии ,что i=B , k =A, p=K.
Тогда
ΔAK=Cаб + Cвк -Cак
Подставляя значения из таблицы – матрицы, получаем ,что
ΔAK=9,2+6,4-10,5=5,1.
Таким же образом определяем размер приращения ΔКБ, если В включим между пунктами К и Б: ΔКБ=С + С =6,4+2,2 – 7,6=1,0 км. ΔБА ,если В включить между пунктами Б и А:
ΔБА=Сбв+Сва-Саб=2,2+9,2-7,0=4,4 км.
Из полученных значений выбираем минимальные, т.е .ΔКБ=!.). Тогда из А-К-Б-А →А-К-В-Б-А. Используя этот метод и формулу приращения ,определяем, между какими пунктами расположить пункты З и Е. Начнём с З ,т.к. размер суммы этого пункта больше (24,9>»0,7) :
ΔБА=Саз+Сзк-Сак=9,5+2,0-10,5=1,0,
ΔАБ=Саз+Сзб-Саб=9,5+6,6-7,0=9,1,
ΔБВ=Сбз+Свз-Сбв=6,6+4,4-2,2=8,8,
ΔВК=Сзв+Сзк-Свк=4,4+2,0-6,4=0.
В случае ,когда Δсимметричной матрицы расчёты можно не продолжать, т.к. меньше значение,чем0 получено быть не может. Поэтому пункт З должен быть между пунктами В и К.Тогда маршрут получит вид: А-К-З-В-Б-А.
В результате проведённого расчёта включаем пункт Е между пунктами А и К, т.к. для этих пунктов мы получим минимальное приращение :
ΔАК=Сае+Сек-Сак=7,1+3,4-10,5=0;
ΔКЗ=Ске+Сез-Скз=3,4+2,4-2,0=3,8;
ΔЗВ=Сзе+Сев-Сзв=2,4+3,6-4,4=1,6;
ΔВБ=Све+Себ-Свб=3,6+4,2-2,2=5,6;
ΔБА=Сбе+Сеа-Сба=4,2+7,1-7,0=4,3.
Таким образом, окончательный порядок движение по маршруту 1 будет А-Б-В-З-К-Е-А.
Таким же методом определим кратчайший путь объезда пунктов по маршруту 2. В результате расчётов получим маршрут А-Г-Д-И-Ж-А длиной 19,4 км. Порядок движения по маршрутам 1 и 2 приведён ниже:
 |
7,0  |
 |
3,2 
2,2 
5,6 
1 7,1 
4,4 2,0 2  |
 |
 |
5,8 
2,8 
3,4Исходные данные для решения задачи № 1
1. m=69 т. q=23 т.
7,9 8,1 
 |
 |
 |
88888 
3,7 6,2  |
9,2 7,3
 |  |
10,8 3,3 3,53,4 5,6
9,1 | А | Б | Г | Д | Е | Ж |
| 4010 | 4800 | 6880 | 2500 | 3140 | 2700 |
| З | И | К | Л | М |
| 4680 | 8150 | 9140 | 2550 | 3570 |
| Н | О | П | С |
| 6460 | 3020 | 4290 | 3010 |
Задача 1
. Груз находится на базе А. Общая масса м=69 т., используется автомобиль q=23 т.
| Б | В | Г | Д | Е | Ж | З | И | К | Л | М | Н | О | П | С |
| 4010 | 4800 | 6880 | 2500 | 3140 | 2700 | 4680 | 8150 | 9140 | 2650 | 3570 | 6460 | 3020 | 4290 | 3010 |
Построим «минимальное дерево» Рис. 1. Минимальное дерево расстояний
Рис. 1. Минимальное дерево расстояний
На следующем этапе группируем пункты по маршрутам, исходя из потребности в материалах.
Учитывая общую массу груза в 69 т. и грузоподъемность автомобиля в 23 т., потребуется три маршрута.
Маршрут 1
| Пункт | Объем завоза, кг. |
| Б | 4010 |
| Г | 6880 |
| В | 4800 |
| П | 4290 |
| О | 3020 |
| Итого | 23 т. |
Маршрут 2
| Пункт | Объем завоза, кг. |
| Ж | 2700 |
| И | 8150 |
| С | 3010 |
| К | 9140 |
| Итого | 23 т. |
| Пункт | Объем завоза, кг. |
| Л | 2650 |
| З | 4680 |
| Е | 3140 |
| Д | 2500 |
| М | 3570 |
| Н | 6460 |
| Итого | 23 т. |
Маршрут 3