Матрица условий

Пункт отправления	Вспом.	Пункт
	Строка Столб.	А1	А2	А3	А4	А5	А6	А7	А8
		V1=0	V2=12 11	V 17 3=18	V4=4	V5=11	V6=8	V7=16	V8=15
A1	U1=0		12		4		8
A2	U2=12 11	12		6	7	8
A3	U 17 3=18		6			6		9
A4	U4=4	4	7			7	6
A5	U5=11		8	6	7		8	5	7
A6	U6=8	8			6	8			7
A7	U7=16			9		5			6
A8	U8=15					7	7	6

(исходный вариант), заполняя расстояния между соседними пунктами. При дальнейших расчётах пользуемся следующим правилом. Каждому пункту А_j соответствует некоторое число V_j, характеризующее расстояние от пункта А₁ до пункта А_j.

Приступаем к нахождению индексов, используя правила

V_j = U_i; V_j= U_i+l_ij.

1. Принимаем индекс U₁=V₁=0.

2. По правилу находим через А₁А₂, А₁А₄ и А₁А₆ V₂=0+12=12, V₄=0+4=4, V₆=0+8=8 и V_j= U_i, U₂=V₂=12, U₄=V₄=4, U₆=V₆=8 и заносим в табл.26.

3. Находим V₃ через А₂А₃ с известным U₂:

V₃=U₂+l₂₃=12+6=18 и V₃=U₃=18.

4. V₅ =min (по столбцу) =11, V₅ =U₅ =11.

5. V₇=min (по столбцу) =16, V₇=U₇ =16.

6. V₈=min (по столбцу) =A₆A₈ =15, V₈=U₈=15.

Проверяем заполненные клетки таблицы на оптимальность по критерию l_ij ≥V_j- U_i.

В табл.15 l₄₂ <V₂ – U₄ 7<12-4=8, критерий не соблюдается, поэтому решение не оптимально.

Рассчитываем новый индекс V₂ по вышеуказанному критерию V_j = U_i+l_ij=4+7=11.

Получаем U₂=V₂=11.

Получаем новую таблицу (со значениями V₂ U₂ в кружках) и проверяем её на оптимальность. Она не оптимальна, так как l₅₃<V₃-U₅ 6<18-11.

Определяем новый индекс V₃=U₅+l₅₃=11+6=17, U₃=V₃=17.

Проверка табл.15 (с индексом кружочек и квадратик) показывает, что решение оптимально.

Следовательно, кратчайшее расстояние от точки А₁ задано числами V₂…V₈, т. е. А₁ – А₂=11 км, А₁ – А₃=17 км……..А₁- А₈=15 км.

Таблица (оптимальная) даёт также последовательность прохождения промежуточных пунктов, например из А₁ в А₇, и определяется следующим образом:

1. В столбце, соответствующему конечному пункту А₇ отыскиваем заполненную клетку, у которой расстояние равно разности индексов столбца и строки l_ij=V_j-U_i (у нас А₅А₇). Она означает последнее звено маршрута А₅-А₇.

2. Для определения предпоследнего операция повторяется для столбца А₅. Это будет звено А₄-А₅.

3. Затем перед ним по столбцу А₄ звено А₁-А₄.

Итак, ААААкратчайший путь найден.

Затем повторяем все решения с самого начала (всю матрицу), принимая:

а) исходный пункт А₂ (т.е. V₂=U₂=0);

б) исходный пункт А₃ (V₃=U₃=0) и т. д. определяем все кратчайшие расстояния.

.

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

В общем виде она формулируется так: при постоянных множествах пунктов производства, потребления, размещения подвижного состава, объёма поставок и потребления грузов и ограничениях на ресурсы подвижного состава необходимо найти допустимые, т. е. удовлетворяющие налагаемым практикой планирования ограничениям и упорядоченные подмножества связанных пунктов, при реализации которых достигается экстремальное значение целевой функции, отражающей эффективность процесса поставок грузов.

В настоящее время ярко выраженная разница в технологии перевозок разделяет методы маршрутизации на два класса: маршрутизация помашинных отправок грузов и маршрутизация мелких партий грузов.

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

Решение состоит из двух этапов: оптимального решения транспортной задачи и формирования набора маршрутов.

Технология конструирования маршрутов может быть выполнена методом совмещённых планов, разработанным на базе линейного программирования. Идея метода совмещённых планов (матриц) состоит в следующем. На первом этапе ищем оптимальный план холостых пробегов автомобилей (как это делалось при решении задачи по закреплению потребителей за поставщиками). На втором этапе в одну матрицу записываем два плана: заданный и полученный, после чего путём специальной процедуры выбираем маршруты движения автотранспорта.

В простейшей постановке задача маршрутизации грузовых перевозок состоит в следующем.

Разнородный груз сосредоточен в пунктах отправления А₁, А₂…А_i…А_m в количествах соответственно а₁, a₂…a_i…a_m единиц. Его необходимо доставить в пункты назначения В₁, В₂…В_j…В_n в количествах в₁, в₂…в_j…в_n соответственно.

Объём перевозок из i-го пункта отправления в j-й пункт назначения составляет q_ij единиц и известен для всех пунктов.

Расстояние от i-го пункта отправления до j-го пункта назначения равно l_ij и известно для всех комбинаций ij.

В процессе выполнения перевозок в пунктах назначения В₁, В₂…В_j…В_n после разгрузки автомобилей будет образовываться порожняк в количествах в₁¹, в₂¹…в_j¹…в_n¹ единиц.

Этот порожняк необходимо подать под очередную загрузку в пункты отправления А₁, А₂…А_i…А_m в количестве а₁¹, а₂¹…а_i¹…а_m¹.

Величины а_i, в_j, q_ij, a_i¹, в_j¹ могут выражаться либо в тоннах, либо в ездках автомобиля. Для существа задачи это безразлично, тем более что тонны всегда можно перевести в ездки. Однако с методической точки зрения удобнее пользоваться ездкой автомобиля с грузом и без груза.

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

По смыслу рассматриваемой задачи всегда имеет место условие

в_j¹ = в_j= , гдеj=1, 2…n

a_i¹ = a_i = , где i=1,2…m.

Расстояние от В_j до А_i , равное l_ji=l_ji , известно для всех сочетаний i, j.

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

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

Таким образом, требуется составить такой план перевозок (маршруты движения автомобилей и сменные задания водителям), который обеспечит выполнение заданных объёмов перевозок с наименьшим холостым пробегом автомобилей.

Обозначим количество порожняка в автомобилеездках, подаваемого из пункта В_j в пункт А_i, через х_ji. Суммарный холостой пробег автомобилей из всех пунктов наличия порожняка во все пункты его подачи при этом составит

.

Условие полного удовлетворения спроса на порожняк каждого пункта отправления за счёт подачи из разных пунктов наличия порожняка записывается следующим образом:

i=1, 2…m.

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

j=1, 2…n.

Количество автомобилей не может быть отрицательным, т. е.

Х_ji≥0 j = 1,2…n; I = 1,2….m. (11)

Таким образом, требуется определить совокупность величин х_ji (план возврата порожняка), удовлетворяющих условиям

, j = 1, 2…n. (12)

, I =1, 2…m. (13)

и минимизирующих суммарный холостой пробег автомобилей

. (14)

По смыслу задачи имеет место равенство

.

Сформулированная задача (11 – 14) называется задачей минимизации холостых пробегов автомобилей. Это транспортная задача линейного программирования, имеющая n·m число переменных, связанных посредством n+m линейных уравнений.

Далее рассмотрим постановку указанной задачи на конкретном примере – задания на перевозку грузов на известные расстояния. Исходные данные приведены в табл.16.

Таблица 16