Логистика

 d  - количество транспортных средств;

 C  -стоимость перевозки(расстояние);

 j – поставщики (j-1, 2…  M).

Имеются пункты потребления  X i ( I =.1,2…n). Груз необходимо развести из начального пункта Х ( склад во все остальные (потребители).Потребность пунктов потребления в единицах объёма груза составляет: q1,q2,q3…qn.

В начальном пункте имеются транспортные средства грузоподъёмностью

Q1,Q2…Q d.

При этом d.> n в пункте X количество груза Х o≥ ∑ Xi 
,каждый пункт потребления снабжается одним типом подвижного состава.

Для каждой пары пунктов( Xi, Xj) определяют стоимость перевозки ( расстояние) Cij>0 ,причём матрица стоимостей в общем случае может быть асимметричная, т.е. Cij ≠ Cij.

Требуется найти  замкнутых путей  L1. L2…Lm из единственной общей точки, так чтобы выполнялось условие:

∑ Lk → min

Методика составления  рациональных маршрутов при расчётах вручную. Схема размещения пунктов  и расстояния между ними: 
 

                     2,2                                                         7,0

  

                                                            5,0

                                3,6              4,2                     3,2                            5,6

2,4                                                        1,9         2,0              5,0

                          3,4                                                        2,8           5,8

2,0                                2,6                                                     
 

 
 

Груз находится  в пункте А – 400 кг. Используется автомобиль грузоподъёмность 2,5  т.; груз – 2 класса ( γ= 0,8) .Необходимо организовать перевозку между пунктами с минимальным пробегом подвижного состава.

Решение состоит  из несколько этапов: 

Этап1. Строим кратчайшую сеть, связывающую все пункты без замкнутых контуров. 
 

Кратчайшая связывающая  сеть ( минимальное дерево): 
 

                                                                                                               4000 кг

              375 кг

                                                                                                            3,2 км

2,2 км

                                                                                                                500кг

                                                                                                             

                                                                                                          2,0 км

3,6 км

                                                                                                              300 кг

                                                                                                   

                                                                                                   5,0

425кг                                                                                            525 кг

            2,4 км                                                                     2,8 км

                       2,0                               2,6                      675 кг

         575 кг             

Затем по каждой ветви сети, начиная с пункта, наиболее удалённого от начального А.( считается по кратчайшей связывающей сети),группируем пункты на маршрут с учётом количества ввозимого груза и грузоподъёмности единицы подвижного состава .Причём ближайшие с другой ветви пункты группируем вместе с пунктами данной ветви. 

Исходя из данной грузоподъёмности подвижного состава  Q=2,5, γ=0,8,все пункты можно сгруппировать так:  
 

 

Сгруппировав  пункты по маршрутам, переходим ко второму этапу расчётов.

Этап 2. Определяем рациональный порядок объезда пунктов каждого маршрута. Для этого строим таблицу- матрицу, в которой по диагонали размещаем пункты ,включаемые в маршрут, и начальный пункт А ,а в соответствующих клетках – кратчайшие расстояния между ними. Для примера матрица является симметричной Cij = Cij,хотя приведённый ниже способ применим для размещения несимметричных матриц.

 

Начальный маршрут  строим для трёх пунктов матрицы  АКБА, имеющих наибольшее значение величины, показанных в строке ( 43,3; 29,9 ; 27,6 ),т.е. А; К; Б. Для включения  последующих пунктов выбираем из оставшихся пункт, имеющий наибольшую сумму ,например В ( сумма 25,8) ,и решаем, между какими пунктами его следует включать ,т.е. между А и К,К и Б или Б и А.

Поэтому для  каждой пары пунктов необходимо найти  величину приращения маршрута по формуле:

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,5

                           3,4                                                 5,6

                                                                                            9,1