Markets-Web.ru

Кратчайшее расстояние между А и Б — 7,0 км. Пишем 7,0 на пересечении строк А и Б, под А. Кратчайшее расстояние между А и В: А-Б + Б-В = 7,0 км + 2,5 км = 9,5 км. Пишем 9,5 на пересечении строк А и В, под А. Для маршрута А-Е может быть три варианта движения: 1) А-Б + Б-В + В-Е, 2) А-Б + Б-Е и 3) А-Г + Г-Д + Д-Е. Считаем: 1) 7,0 + 2,5 + + 4,1 = 13,6; 2) 7,0 + 5,0 = 13,0; 3) 3,5 + 2,5 + 2,4 = 8,4. 8,4 км — наименьшее расстояние между А и Е, его и пишем на пересечении строк А и Е, под А. Таким образом заполняется вся матрица.

Начальный маршрут строим для трех пунктов матрицы, из которых один является пунктом отправления, а два других имеют наибольшие значения величины в строке суммы. Таким образом, в нашем примере начальный маршрут строим для трех пунктов матрицы А-Б-К-А. Пункт А входит, потому что является пунктом отправления грузов, а пункты Б и К имеют наибольшие значения величины, показанные в строке суммы (28,4; 30,1).

Для включения последующих пунктов выбираем из оставшихся пункт, имеющий наибольшую сумму, и решаем, между какими пунктами его следует включить. В нашем примере пункт В из оставшихся имеет наибольшую сумму, и его надо вставить между А и Б, Б и К или К и А.

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

Akp = Ckj + Cjp - Ckp,

где С — расстояние, км; j — индекс включаемого пункта; к — индекс первого пункта из нары; p — индекс второго пункта из нары.

Из полученных значений выбирается минимальное, и пункт включения вставляется между теми пунктами, приращение которого окажется минимальным.

Таблица 26

Матрица кратчайших расстояний между пунктами первого маршрута

При включении пункта В между первой парой пунктов А и Б определяем размер приращения ААБ, при условии, что j - В, к — А, p — Б. Тогда

ААБ = СЛВ + СВБ — САБ.

Подставляя значения из таблицы, получаем ААБ = 9,5 + 2,5 — 7 = 5.

Таким же образом определяем размер приращения АБК и АКА:

АБК = Сбв + СВК — СБК = 2,5 + 5,2 — 7,7 = 0

Поскольку значение приращения АБК получилось равным нулю, дальнейшие расчеты уже необязательных, потому что меньше нуля значения уже не будет. Тогда из начального маршрута А-Б-К-А мы получаем А-Б-В-К-А.

Используя этот метод и формулу приращения, определяем, между какими пунктами расположить пункты Е и З. Начнем с пункта З, т.к. сумма этого пункта больше.

ААБ = 10,5 + 6,2 — 7 = 9,7 АБВ = 6,2 + 3,7 — 2,5 = 7,4 АВК = 3,7 + 1,5 — 5,2 = 0

Таким образом, пункт З включается между пунктами В и К, и из маршрута А-Б-В-К-А получаем маршрут А-Б-В-З-К-А.

И оставшийся пункт Е:

ААБ = 8,4 + 5 — 7 = 6,4 АБВ = 5 + 4,1 — 2,5 = 6,6 АВЗ = 4,1 + 2,1 — 3,7 = 2,5

Рис. 36. Схема полученных оптимальных маршрутов.

АЗК = 2,1 + 3,7 — 1,5 = 4,3 АКА = 3,6 + 8,4 — 12 = 0

Минимальным значением является АКА = 0, значит, пункт Е включается между пунктами К и А. В результате мы имеем оптимальный маршрут развоза продукции А-Б-В-З-К-Е-А.

Таким же методом определим кратчайший путь объезда пунктов по маршруту 2. В результате расчетов получим маршрут А-Ж-И-Д-Г-А. Порядок движения по полученным оптимальным маршрутам показан на рис. 36.