Задача по "Логистике"

Задача

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

Решение:

На заданной схеме находим наименьшее звено. В данном случае это звено Б-3 = 3 км. Затем рассмотрим все звенья, связанные с одной из этих вершин и рассмотрим все звенья связанные с вершинами полученной ломаной Б-Ж-З : Б-А = 5 км, Б-Ж = 7 км, З-Ж = 4 км, З-И = 8 км, Ж-В = 4 км..

Рисунок 1 – Кратчайшая связывающая сеть

В каждый маршрут группируются пункты с учетом количества ввозимого и вывозимого грузов и вместимости единицы подвижного состава. Если все пункты данной ветви не могут быть включены в один маршрут, то ближайшие к другой ветви пункты группируются вместе с пунктами этой ветви.

Максимальная вместимость автомобиля, равная 2,5 т. Исходя из этого, пункты, указанные на рисунке 1, группируем следующим образом и представим в виде таблицы 1.

Таблица 1

При этом пункт  И не вошел в маршрут 1, так как автомобиль не смог бы принять его груз, и он расположен ближе остальных к другой ветви сети.

Для каждого маршрута строим таблицу. Для маршрута 1 она приведена  в  таблице 2. По главной диагонали в ней размещены пункты, включаемые в маршрут. Цифры  в клетках показывают кратчайшие  расстояния между ними. Начальный маршрут строим для трех пунктов матрицы А, В, Ж, имеющих наибольшие значения величины, показанной в  итоговой строке (36, 34, 27), т.е. маршрут АВЖА.

Таблица 2

Для включения последующих пунктов в маршрут выбираем из оставшихся пунктов в таблице пункт, имеющий наибольшую сумму - это Б (26). Затем необходимо определить между какими пунктами начального маршрута его следует вставить. Для этого  следует   поочередно вставлять пункт Б между каждой соседней парой пунктов АВ, ВЖ, ЖА.

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

∆kp = Cki + Cip –  Ckp ,

где С – расстояние, км;

i -  индекс включаемого пункта;

k – индекс первого пункта из пары;

p – индекс второго пункта из пары.

При включении пункта Б между первой парой пунктов АВ  определяем размер приращения ∆АВ при условии, что i =Б, k = A, p = В. Тогда

∆АВ = САБ + СБВ – САВ .

Соответствующие расстояния между пунктами  берем из таблицы 2  и получаем ∆АБ = 5 + 11 – 11 = 5.

Для пунктов ВЖ приращение маршрута при включении пункта Б равно:

∆ВЖ = СВБ + СБЖ – СВЖ ,

т.е. ∆ВЖ = 11 + 7 – 4 = 14.

Для пунктов ЖА соответственно:

∆ЖА = СЖБ + СБА – СЖА ,

т.е. ∆ЖА = 7 + 5 – 12= 0.

Из полученных значений выбираем минимальное значение, т.е. ∆ЖА = 0  и между соответствующими пунктами вставляем пункт Б. Получаем маршрут АВЖБА.

Вновь в таблице 2 выбираем один из еще не включенных в маршрут пунктов З.

∆АВ = САЗ + СЗВ–  САВ  =  8 +8 – 11 = 5

∆ВЖ = СВЗ  + СЗЖ – СВЖ    =  8 + 4 – 4 = 8

∆ЖБ = СЖЗ  + СЗБ – СЖБ   =  4 + 3 – 7 = 0

∆БА = СБЗ + СЗА – СБА =  3 + 8 – 5 = 6 .

Так как наименьшей величиной является ∆ЖБ, пункт З включаем между ЖБ и получаем  маршрут АВЖЗБА.

Получаем окончательный порядок объезда пунктов первого маршрута АВЖЗБА, длина которого составит 27 км. Можно утверждать, что полученная последовательность объезда дает наименьший или весьма близкий к наименьшему пути путь объезда пунктов маршрута 1.

По маршруту 2 проводятся аналогичные расчеты, исходные данные для которых представлены в таблице 3.

Начальный маршрут строим для трех пунктов матрицы А, Д, К, имеющих наибольшие значения величины, показанной в  итоговой строке (93, 90, 81), т.е. маршрут АДКА.

Для включения последующих пунктов в маршрут выбираем из оставшихся пунктов в таблице пункт, имеющий наибольшую сумму, например, Г (67). Затем  определяем между какими пунктами начального маршрута его следует вставить. Для этого  следует   поочередно вставлять пункт Г между каждой соседней парой пунктов АД, ДК, КА.

Таблица 3