Маршрутизация перевозок при помашинных отправках грузов

 

Повышение эффективности грузовых автомобильных перевозок связано с применением математических методов для решения прикладных задач. Одним из таких оптимизационных задач является составление рациональных маршрутов перевозок.

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

При составлении маршрутов возможны разные подходы к закреплению автомобилей на маршрутах:

- группы автомобилей закрепляются за поставщиками; в этом случае работа организуется по маятниковым маршрутам (l_г=l_х), значение коэффициента использования пробега, как правило, не может быть больше, чем 0,5.

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

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

Пусть заданы пункты отправления груза (ГОП) и пункты получения груза (ГПП), пункт размещения автомобилей (АТП), а также расстояния между этими пунктами. Известны груженые ездки, которые необходимо осуществить от конкретного ГОП к заданному ГПП. Рассмотрим пример решения такой задачи, исходные данные которого представлены в табл.9.

Таблица 9

Задание на перевозку

ГОП	ГПП	Количество груза, т	Вид груза
А1	В2	22,5	Песок
А2	В2	13,5	Уголь
А2	В3
А2	В4
А3	В1		Опилки
А3	В3
А4	В2	13,5	Щебень
А4	В4
А4	В5

 

Требуется так организовать процесс перевозок, чтобы был перевезен весь груз и при этом суммарный пробег автомобилей без груза был бы минимальным.

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

Для перевозки всех грузов выбирается одна модель подвижного состава. Например, при использовании для перевозок автомобиля-самосвала ЗиЛ-4503 грузоподъемностью 4,5 т и учитывая значение коэффициента использования грузоподъемности для разных грузов (для опилок , для остальных грузов ), задание на перевозки представим в виде табл. 10. Количество ездок по каждому маршруту определяется по формуле

,

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

 

Таблица 10

Задание на перевозку по количеству ездок

ГОП	ГПП	Вид груза	Количество ездок
А1	В2	Песок
А2	В2	Уголь
А2	В3
А2	В4
А3	В1	Опилки
А3	В3
А4	В2	Щебень
А4	В4
А4	В5

 

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

Представим исходные данные в виде таблицы (табл.11). Расстояния между пунктами записываем в правый верхний угол ячейки матрицы. Расстояние от АТП до грузоотправителя и грузополучателя запишем в скобках рядом с обозначением пункта. Занесем в таблицу суммарное количество ездок для каждого поставщика и потребителя.

Решим задачу составления оптимального плана подачи порожнего ПС под загрузку (см. табл.11). Для этого находим ячейки с наименьшим расстоянием между грузоотправителем и грузополучателем в каждом столбце и ставим туда максимальное возможное количество ездок, учитывая возможности грузоотправителя и спрос грузополучателя. Начинаем с первого столбца, здесь такая ячейка А₄В₁ (расстояние 6 км), ставим максимально возможное количество ездок (2), которое ограничено грузополучателем В₁. После исчерпания возможности грузополучателя переходим на следующий столбец. Таким образом, распределяем холостые ездки. Сумма холостых ездок по ячейкам строки должна быть равна общему числу ездок по вывозу соответствующего грузоотправителя.

Таблица 11

Оптимальный план холостых ездок

Грузо-отправи-тели	Грузополучатели	Итого по вывозу, ед
В1 (25)	В2 (10)	В3 (9)	В4 (5)	В5 (8)
А1(5)		(5)
А2(7)				(10)
А3 (7)		(6)
А4 (5)	(2)		(6)		(6)
Итого по ввозу, ед						-

 

Затем заносим в таблицу груженые ездки, которые необходимо выполнить согласно поставленной задаче (с табл.10). Груженые ездки занесены в таблицу курсивом. Таким образом, получается совмещенная матрица холостых и груженых ездок (табл. 12).

 

Таблица 12

Совмещенная матрица холостых и груженых ездок

Грузоотправители	Грузополучатели	Итого по вывозу, ед
В1 (25)	В2 (10)	В3 (9)	В4 (5)	В5 (8)
А1(5)		(5)
А2(7)				(10)
А3 (7)		(6)
А4 (5)	(2)		(6)		(6)
Итого по ввозу, ед						-

 

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

- маршрут №1: А₁ – В₂ - А₁ – 5 оборотов;

- маршрут №2: А₂ – В₄ – А₂ – 5 оборотов;

- маршрут №3: А₄ – В₅ – А₄ – 6 оборотов.

Количество перевозок по маятниковым маршрутам вычитают из загрузок соответствующих клеток и составляют новую матрицу для продолжения решения задачи (табл. 13).

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

 

Таблица 13

Матрица для составления кольцевых маршрутов

 

 

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

Построим контур А₃В₁ - А₃В₂ – А₂В₂ – А₂В₄ – А₄В₄ –А₄В₁ -А₃В₁. В матрице сплошные линии расположены горизонтально и соответствуют перевозке груза. Пунктирные линии, расположенные вертикально, соответствуют перевозке груза. Пунктирные линии, расположенные вертикально, соответствуют подаче порожнего подвижного состава. Минимальная загрузка по этому контуру составляет две ездки. Строим кольцевой маршрут№4: А₃ – В₁ – А₄ – В₄ – А₂ –В₂ -А₃ – 2 оборота.

Общий пробег ПС при перевозке грузов по рациональным маршрутам зависит от выбора начального пункта маршрута. На маятниковых маршрутах начальный пункт определен однозначно пунктом погрузки. На кольцевых маршрутах число возможных вариантов начального пункта соответствует числу пунктов погрузки на маршруте. Поэтому для определения начального пункта кольцевого маршрута необходимо рассмотреть все возможные сочетания пунктов первой погрузки и пунктов последней разгрузки. Для каждого варианта надо просчитать суммарный порожний пробег от АТП до пункта первой загрузки и от пункта последней разгрузки до АТП. За начальный пункт погрузки целесообразно принять тот пункт, при котором суммарный пробег минимален.

Для маршрута №4 возможно три варианта начального пункта:

- начало в пункте А₃, конец в пункте В₂, нулевой пробег 17 км;

- начало в пункте А₂, конец в пункте В₄, нулевой пробег 12 км;

- начало в пункте А₄, конец в пункте В₁, нулевой пробег 30 км.

В качестве начального пункта на кольцевом маршруте №4 принимаем пункт А₂, маршрут при этом будет заканчиваться в пункте В₄. Таким образом, маршрут №4: А₂ – В₂ – А₃ – В₁ – А₄ –В₄ –А₂ – 2 оборота.

Количество ездок, включенное в маршрут, вычитается из загрузки в вершинах контура. Затем переходят к построению следующего кольцевого маршрута. Построим следующий контур: А₄В₂ - А₃В₂ – А₃В₃ – А₄В₃ – А₄В₂ (табл. 14).

Для этого маршрута возможно два варианта выбора начального пункта:

- начало в пункте А₄, конец в пункте В₃, нулевой пробег 14 км;

- начало в пункте А₃, конец в пункте В₂, нулевой пробег 17 км.

За начальный пункт маршрута принимаем пункт А₄. По этому контуру организуем маршрут №5: А₄ – В₂ – А₃ – В₃ – А₄ – 3 оборота.

Вычитаем количество ездок, включенных в маршрут, из загрузки соответствующих клеток и выбираем следующий кольцевой маршрут по контуру: А₃В₃ - А₃В₂ – А₂В₂ – А₂В₄ – А₄В₄ – А₄В₃ – А₃В₃ (табл. 15).

 

Таблица 14

 

 

Таблица 15

 

Для этого маршрута возможно три варианта выбора начального пункта:

- начало в пункте А₂, конец в пункте В₄, нулевой пробег 12 км;

- начало в пункте А₄, конец в пункте В₃, нулевой пробег 14 км;

- начало в пункте А₃, конец в пункте В₂, нулевой пробег 17 км.

За начальный пункт данного маршрута принимаем А₂ и задаем маршрут №6: А₂ – В₂ – А₃ – В₃ – А₄ – В₄ – А₂ – 1 оборот.

Строим последний контур А₂В₃ – А₂В₄ – А₄В₄ – А₄В₃ – А₂В₃ (табл.16). Для этого маршрута возможно два варианта выбора начального пункта:

- начало в пункте А₂, конец в пункте В₄, нулевой пробег 12 км;

- начало в пункте А₄, конец в пункте В₃, нулевой пробег 14 км.

За начальный пункт принимаем А₂ и строим маршрут № 7: А₂ – В₃ – А₄ – В₄ – А₂ – 2 оборота.

Таким образом, план перевозок построен. Получены следующие маршруты:

- маятниковые

маршрут №1: А₁ – В₂ - А₁ – 5 оборотов;

маршрут №2: А₂ – В₄ – А₂ – 5 оборотов;

маршрут №3: А₄ – В₅ – А₄ – 6 оборотов;

- кольцевые

маршрут №4: А₂ – В₂ – А₃ – В₁ – А₄ –В₄ –А₂ – 2 оборота;

маршрут №5: А₄ – В₂ – А₃ – В₃ – А₄ – 3 оборота;

маршрут №6: А₂ – В₂ – А₃ – В₃ – А₄ – В₄ – А₂ – 1 оборот;

маршрут №7: А₂ – В₃ – А₄ – В₄ – А₂ – 2 оборота.

 

Таблица 16

 

Разработанные схемы маршрутов являются основанием для планирования перевозок, заполнения маршрутных листов и путевой документации водителей.

Для предупреждения ошибок при составлении маршрутного листа необходимо на основе транспортной сети составить схему каждого маршрута, как это показано для маршрута №7 на рис.6.

Рис. 6. Схема маршрута № 7

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

Время одного оборота

ч.

Время работы на маршруте

ч.

Возможное число оборотов, которое может выполнить один автомобиль:

оборота.

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

ч,

здесь - время движения от В₄ до А₂, которое не выполняется на последнем, втором обороте.

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

В данном случае после завершения работы на маршруте №7 наиболее целесообразно будет задействовать автомобиль для работы на маятниковом маршруте №2.

Количество оборотов данного автомобиля по маршруту №2

оборот,

здесь - время подъезда для переезда с точки завершения работы на маршруте №7.

Пример маршрутного листа для автомобиля, работающего на маршрутах №7 и №2, приведен в табл. 17.

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

 

Таблица 17

Маршрутный лист

Пункт отправ-ления	Время отправ-ления	Пункт назначе-ния	Время прибы-тия	Наимено-вание груза	, км	, км		, т
АТП	8:00	А2	8:10	-	-			-
А2	8:20, 13:30	В3	9:30, 14:30	Уголь		-		4,5
В3	9:40, 14:50	А4	10:10, 15:20	-	-			-
А4	10:20, 15:30	В4	11:20, 16:30	Щебень		-
В4	11:30, 16:40	А2	12:20, 17:30	-	-			-
Обед	12:20		13:20	-	-	-	-
А2	17:40	В4	18:30	Уголь				2,25
В4	18:40	АТП	18:50	-	-			-
Итого								15,75

Коэффициент использования пробега для этого автомобиля составит

.

Часовая производительность

т/ч.

Задание

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

Таблица 18

Пример варианта исходных данных

Грузо-отправители	Грузо- получатели	Расстояние между пунктами, км	Вид груза	Количество ездок
А1 (10)*	В1 (10)		Песок
А1	В3 (4)		Песок
А2 (3)	В2 (6)		Грунт
А2	В4 (2)		Грунт
А3 (8)	В3		Щебень
А3	В2		Щебень
А3	В4		Щебень
А4 (11)	В4		Опилки
А4	В1		Опилки
А4	В3		Опилки

 

^* около грузоотправителей и грузополучателей в скобках указаны расстояния от АТП до соответствующих пунктов

 

Таблица 19

Дополнительные данные

Расстояния, км
lА1-В2	lА1-В4	lА2-В1	lА3-В1	lА2-В3	lА4-В2

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

На планирование маятниковых маршрутов оказывают влияние следующие факторы:

▪ разная продолжительность рейсов на разных маршрутах;

▪ ограничение продолжительности работы подвижного состава рабочим временем водителя (временем наряда);

▪ ограничения по фронту и времени загрузки у грузовладельцев;

▪ требования грузовладельцев по регулярности, времени отправки и доставки грузов и др.

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

- достижение максимальной производительности за счет полного использования рабочего времени;

- сокращение холостых и нулевых пробегов при увязке маятниковых маршрутов.

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

Методику согласования маршрутов удобно пояснить непосредственно на примере. Исходные данные приведены в табл. 20.

 

Таблица 20

Задание на перевозку

 

Показатели	Заказчики перевозок (клинты)	Всего
Число ездок
Время одной ездки, мин

 

Исходя из лимита рабочего времени за смену в 480 мин (8 часов) на выполнение данных перевозок потребуется как минимум 4 автомобиля, причем запас времени

Т ₃ = 4 · 480 – 1884 = 36 мин.

Выбор лучшего варианта проводят последовательным подбором маршрутов. Первый, наиболее простой, вариант можно составить методом северо-западного угла (табл.21).

 

Таблица 21

Распределение заданий на перевозки

 

Автомобили (уровень расчета)	Число ездок получателям	Время, мин
					2·120+222=462
					222+240=462
					240+180=420
					2·180=360
					1·180=180
Всего

 

При таком сочетании маршрутов для выполнения заданного объема работы потребуется выделить 5 автомобилей с расходом рабочего времени

Т _р = 5 · 480 = 2400 мин,

при полезном использовании Т_п=1884 мин; из пяти выделяемых автомобилей один (№3) недогружен заданием на 60 мин, один (№ 4) – на 120 мин, последний же из выделяемых автомобилей загружен менее чем на 40% рабочего времени.

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

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

Остаются маршруты продолжительностью 120 мин – 2 ездки и 180 мин – 4 ездки. Их целесообразно совмещать с расчетом:

Т_н = 120 + 2 · 180 = 480,

т.е. одна ездка продолжительностью 120 мин и две ездки продолжительностью 180 мин.

При таком совмещении маршрутов план выполнения заказов клиентов будет выглядеть, как показано в табл. 22.

 

Таблица 22

Рациональный план распределения заданий

Автомобили	Число ездок получателям	Время, мин

 

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

min.

 

Задание

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

 

Таблица 23

Пример исходных данных

 

Показатели	Потребители
Число ездок
Время одной ездки, мин
Время в наряде, ч

5. Расчет рационального плана назначения груженых ездок при перевозках однородных грузов однотипным подвижным составом

Необходимость решения транспортных задач появляется, когда имеется несколько, иногда очень много, вариантов выполнения перевозок, а выбрать необходимо один, который при этом бы оптимальным.

Такими задачами могут быть:

▪ закрепление грузополучателей за грузоотправителями при условии минимума транспортной работы на перевозки;

▪ закрепление АТП за маршрутами перевозок из условия минимума нулевых пробегов;

▪ выбор варианта организации перевозок с минимальными затратами времени на их выполнение;

▪ выбор вариантов транспортного процесса при условии минимальной стоимости перевозок и др.

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

Рассмотрим формулировку транспортной задачи линейного программирования (рис.7).

Суть задачи такого вида состоит в следующем:

В пунктах отправления А₁, А₂, …, А_n имеется однородный груз в количестве а₁, а₂, …, а_n. Этот груз необходимо доставить в грузопоглощающие пункты В₁, В₂, …,В_m в количестве b₁, b₂, …,b_m.. Кратчайшие расстояния между грузоотправителями и грузополучателями C _ij.

Необходимо разработать такой план:

- чтобы удовлетворить потребности всех получателей;

 

- вывезти весь груз от грузоотправителей;

- при этом обеспечить минимум транспортной работы по грузообороту.

 

Рис.7. Схема перевозок (возможные варианты)

 

Экономико-математическая модель транспортной задачи с учетом перечисленных требований выглядит следующим образом:

- cистема ограничений по количеству груза, доставляемого получателям,

х₁₁ + х₂₁ + …+ х_n1 = b₁ ,

x₁₂ + x₂₂ + …+ x_n2 = b₂ ,

… … … … … … … …

x_1m + x_2m + …+ x_nm = b_m.

 

- система ограничений по количеству груза, вывозимого из пунктов отправки,

x₁₁ + x₁₂ + …+ x_1m = a₁ ,

x₂₁ + x₂₂ + …+ x_2m = a₂ ,

… … … … … … … …...

x_n1 + x_n2 + …+ x_nm = a_n .

 

Для совместимости систем уравнений предполагается, что возможности грузоотправителей по отправке и потребности грузополучателей совпадают:

.

План перевозок считается оптимальным, если будет получен минимум транспортной работы

при .

Рассмотрим пример решения задачи [1]. Известно количество однородного груза, которое имеется у грузоотправителей, условно обозначенных А₁, А₂, А₃ и А₄. Этот груз необходимо доставить потребителям, обозначенным В₁, В₂, В₃, В₄, В₅. Известны также расстояния между всеми грузоотправителями и грузополучателями. Исходные данные задачи записаны в таблицу, называемую матрицей (табл. 24). В матрице в верхнем правом углу соответствующих клеток записаны расстояния в километрах. Кроме того, в этой матрице имеются вспомогательные строка и столбец, клетки которых пока остаются незаполненными. Необходимо закрепить потребителей за поставщиками так, чтобы среднее расстояние перевозок груза было наименьшим, т.е. найти минимум объема транспортной работы в тонно-километрах.

Таблица 24

Исходные данные

 

Порядок решения задачи состоит из следующих этапов:

1) первоначальное закрепление (распределение);

2) анализ возможностей улучшения решения;

3) проверка оптимальности полученного решения;

4) оформление результата.

Первоначальное закрепление потребителей продукции за поставщиками можно выполнить разными методами:

Метод северо-западного угла наиболее прост: закрепление производится с левого верхнего угла таблицы (клетка В₁А₁), по мере удовлетворения потребности получателя или исчерпания ресурса поставщика заполняются последующие клетки, расположенные правее и ниже. Как правило, первый полученный результат далек от оптимального, и требуется многократно выполнять проверку на оптимальность и перерасчет.

Первоначальноераспределение методом двойного предпочтения и методом Фогеля достаточно полно описано в работах [1, 2, 4].

1. При решении представленной задачи рассмотрим применение метода северо-западного угла. Последовательно закрепляют грузополучателей за грузоотправителями, начиная с А₁. Для этого выбирают кратчайшее расстояние в столбце А₁ и в соответствующем клетке записывают потребность в грузе данного получателя, если она не превосходит наличия груза у отправителя А₁. Остаток груза у поставщика помещают в следующую по наименьшему расстоянию клетку этого столбца. После распределения всего груза грузоотправителя А₁ переходят к распределению груза следующего поставщика, что делается таким же путем. Если потребность в грузе у получателя больше, чем имеется груза у отправителя, в соответствующую клетку записывается количество груза, имеющегося у поставщика. Такое предварительное распределение сделано в табл.25.

Для отправителя А₁, имеющего 15 т груза, ближайшим получателем будет В₂, потребность в грузе которого составляет 40 т. Записываем наименьшее из этих чисел в клетку А₁В₂. Так как весь груз поставщика А₁ уже распределен, переходим к распределению 85 т груза отправителя А₂. Ближайшим к нему будет получатель В₂, у которого осталось неудовлетворенная потребность в грузе – 25 т. Записываем эту цифру в клетку А₂В₂. Так как у А₂ еще остается 60 т неиспользованного груза, отыскиваем следующего ближайшего к этому отправителю потребителя. Им будет В₃ с потребностью в грузе 80 т. Так как меньшей цифрой является 60, то ее и помещаем в клетку А₂В₃.

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

Клетки, где проставлены количества груза, называются загруженными.

Таким образом, в табл.25 получено предварительное распределение. Количество транспортной работы по этому распределению составляет 2815 т·км. Однако, является ли такое распределение оптимальным, пока остается неясным.

 

Таблица 25

 

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

В соответствии с этим все потенциалы определяются по следующему правилу.

Для одного из столбцов (отправителей) принимают потенциал , равный нулю. При этом целесообразно нулю приравнивать потенциал того столбца, в котором имеется загруженная клетка с наибольшим расстоянием. Остальные потенциалы определяют по загруженным клеткам исходя из следующих формул:

для столбцов ,

для строк .

Так, в табл. 25 загруженная клетка В₅А₄ с наибольшим расстоянием находится в столбце А₄. Поэтому принимаем потенциал для этого столбца . По загруженным клеткам этого столбца определяем потенциалы строк В₃, В₄, В₅:

; ; .

По загруженной клетке В₃А₂ определяем потенциал столбца А₂:

,

а по клеткам В₂А₂ и В₂А₁ соответственно потенциалы:

и .

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

,

где - число основных строк; - число основных столбцов.

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

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

В табл.25 нуль можно поставить в любую клетку в строке В₁ или в столбце А₃. Пусть такой клеткой будет клетка В₁А₁. Туда записываем и считаем эту клетку загруженной. Сделаем это в табл.26. Теперь можно определить потенциалы и

и .

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

 

Таблица 26

 

Сделаем такие подсчеты для всех незагруженных клеток табл.26. Например, для клетки В₁А₂ < , т.е. здесь разность потенциалов меньше расстояния. Просматривая, таким образом, все незагруженные клетки, обнаружим, что в табл. 26 числа можно определить для следующих клеток:

В₂А₄ >11; ;

В₄А₂ >14; ;

В₄А₃ >16; ;

В₅А₃ >19; .

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

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