Постановка классической транспортной задачи

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

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

Потребителям В₁, В₂,..., В_j,..., В_n требуется однородный продукт (груз) в количествах соответственно b₁, b₂,..., b_j ,…, b_n тонн, который производится (или хранится) у поставщиков А₁, А₂,..., А_i,....А_m в количествах а₁, а₂,...,а_i,..., а_m тонн. Так как все поставщики производят одну и ту же продукцию, каждый из них может удовлетворять запросы любого потребителя. Расстояния между отправителями и получателями груза известны и составляют 1ц километров. Требуется составить такой план перевозок грузов, который обеспечит удовлетворение запросов всех потребителей при минимальной транспортной работе (минимальной сумме тонно-километров). Очевидно, что для решения рассматриваемой задачи необходимо равенство общей потребности получателей наличию груза у отправителей.

Условия задачи удобно записывать в виде табл. 1, называемой матрицей условий.

Таблица 1

Пункт отправления	Пункт назначения						Наличие груза, т
	В1	В2	…	Вj	…	Вn
А1	111	112	…	11j	…	11n	а1
А2	111	122	…	12j	…	12n	а2
…	….	…	…	…	…	…	…
Аi	1j1	1i2	…	1ij	…	1in	аi
…	…	…	…	…	…	…	…
Аm	1m	1m2	…	1mj	…	1mn	аm
Потребность в грузе, т	b1	b2	…	bj	…	bn	bj==аi

Обозначим через х_ij количество тонн груза, предназначенного к отправке из пункта А_i в пункт В_j. Тогда количество груза, планируемое к доставке в пункт В_jиз всех пунктов отправления, составит

х_1j + х_2j +…+ x_mj = Х_ij . (1)

Так как потребность пункта назначения В_j составляет b_j, то при планировании перевозок должно соблюдаться равенство

X_ij = b_j .

Сказанное справедливо для любого пункта В_j. Поэтому получаем n уравнений

х ₁₁ + х ₂₁ +…+ х _m1 = b ₁

х ₁₂+ х ₂₂ +…+ х_m2 = b ₂

….……………………… (2)

х _1n + х _2n+…+ х _mn = b _n

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

х_i1+х_i2+...+x_in= Х _ij. (3)

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

Х _ij=a_i .

Так как приведённое рассуждение относится к любому пункту отправления, имеем m уравнений

х ₁₁ + х ₂₁ +…+ х _1n = a ₁

х ₂₁+ х ₂₂ +…+ х_2n = a ₂

……………………. (4)

х _m1 + х _m2+…+ х _mn = a _m

Более компактно уравнения (1.1) - (1.4) можно записать следующим образом:

Х _ij= b_j, j = 1, 2, …, n; (5)

Х _ij= a_i, i = 1, 2, …, m; (6)

P = 1₁₁x₁₁ +1₁₂ x₁₂+…+1_ij x_ij +…+1_mn x_mn = l _ij X _ij. (7)

Очевидно, что объем каждой поставки не может быть отрицательным числом, т.е.

x_ij >0, i=1,2,..., m; j=1,2,..., n. (8)

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

l _ij X _ij, j = 1, 2, …, n, i = 1, 2, …, m (9)

при условиях

X _ij= b_j, j = 1, 2, …, n; (10)

X_ij= a_i, i = 1, 2, …, m; (11)

x_ij>0, i =1, 2,..., m; j=1, 2,..., n. (12)

Соблюдение равенства (1.10) обеспечивает полное удовлетворение запросов всех потребителей. Уравнения (1.11) гарантируют полный вывоз из пунктов отправления, а уравнения (1.9) - неотрицательность переменных. Для совместности системы уравнений (1.9 - 1.12) необходимо, чтобы

a_i = b_j. (13)

Равенство (1.13) является не только необходимым, но и достаточным условием для совместности системы уравнений (1.9 -1.12).

Поскольку уравнения (1.10 - 1.12) содержат неизвестные только в первой степени, а показатель L_ij в формуле (1.9) не зависит от x_ij, сформулированная задача является задачей линейного программирования. Формулировка задачи, в которой спрос и предложение равны, получила название закрытой модели.

Модель транспортной задачи имеет следующие особенности:

1. Модель выражается неопределённой системой линейных уравнений и, следовательно, имеет бесчисленное множество возможных решений.

2. Модель совместна, т.е. имеет решение.

3. Элементами матрицы системы являются единицы и нули.

4. Система является линейно-зависимой, так как любое её уравнение можно представить в виде линейной комбинации остальных уравнений.

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

6. Целевая функция выражается линейной формой. Матрица целевой функции -это матрица-строка, элементами которой могут быть расстояния, время или стоимость перевозки.

Для решения транспортной задачи разработаны специальные методы, позволяющие из бесчисленного множества решений найти оптимальное. Одним из таких методов является распределительный, имеющий несколько разновидностей, которые отличаются в основном способом выявления оптимального решения. Общая схема метода следующая. Вначале составляют допустимый исходный план задачи, который затем исследуется на оптимальность. Если при проверке окажется, что составленный план оптимален, то решение закончено. В противном случае при помощи специального приёма осуществляется переход к новому, лучшему плану. Этот план снова исследуется на оптимальность и в случае неоптимальности опять улучшается. Указанный процесс вычислений повторяется до получения оптимального решения.

Разновидности распределительного метода отличаются в основном способом выявления оптимального решения.

2. Первый способ (метод Хичкока)

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

Распределение груза по потребителям производится начиная с грузоотправителя А₁ и грузополучателя В₁ т.е. с клетки А₁В₁. Потребность в грузе потребителя В₁ удовлетворяется полностью грузоотправителем А₁. В клетку А₁В₁ записывается объем потребления грузополучателя В₁ - 200 т. Оставшийся в точке А₁, груз в количестве 200 т будет вывозиться потребителю В₂. Но потребителю В₂ нужно завезти не 200, а 400 т груза. Недостающие 200 т груза можно ввозить от грузоотправителя А₂. Оставшиеся у грузоотправителя А₂ 400 т груза можно вывезти в точку В₃ и т.д. Рассуждая таким образом, распределим весь груз по потребителям.

Таблица 2

Грузообразующие точки	Грузопоглощающие точки				Итого по вывозу, т	Потенциалы
	B1	В2	B3	В4
А1	16 200	6 200	10	4	400	-16
А2	8	2 200	12 400	14	600	-12
А3	2	18	8 400	6600	1000	- 8
Итого по ввозу, т	200	400	800	600	2000	Vj
Потенциалы	0	10	0	2	Ui	--

В табл. 2 распределение груза по потребителям (закрепление потребителей за грузоотправителями) выразится в заполнении клеток А₁В₁, A₁B₂,А₂В₃, А₂В₂, А₃В₃, А₃В₄.

Условимся в дальнейшем называть клетки таблицы, в которых отмечено количество груза, перевозимого от грузоотправителя к данному грузополучателю, загруженными. Количество загруженных клеток всегда должно равняться величине базиса, который будет равен n + m - 1 (n- число строк таблицы; m - число столбцов). В данном примере это условие соблюдено: 3 + 4-1=6.

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

200-16 + 200-6 + 200-2 + 400-12 + 400-8 + 600-6 = 16 400 т*км.

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

1. Во всех загруженных клетках получить нулевой потенциал. Для этого по строчкам и столбцам табл. 1.2 к расстояниям, проставленным в верхних правых углах клеток, прибавляют такие числа (потенциалы), которые в сумме с расстояниями загруженных клеток дают нуль (нулевой потенциал). Например, чтобы получить в загруженной клетке А₁В₁, нулевой потенциал, нужно ко всем расстояниям строки А₁ прибавить потенциал - 16(16-16 - 0). В загруженной клетке А₁В₂ нулевой потенциал получится в том случае, если к ее расстоянию 6 и ранее прибавленному по строке А₁ потенциалу - 16 прибавить по столбцу В₂потенциал + 10 (6 -16+ 10= 0) и т.д.

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

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

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

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

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

1. Проверяют, чтобы количество загруженных клеток в предыдущем шаге равнялось n + m - 1. Если количество загруженных клеток меньше, чем n + m - 1 (случай вырождения), то недостающее число клеток достигается путем загрузки соответствующего количества свободных клеток нулями. Клетка, в которой будет проставлена загрузка, равная нулю, считается загруженной.

2. Для наиболее потенциальной клетки А₁В₄ строится контур. Контуром называется замкнутая ломаная линия, образованная прямыми отрезками, углы соединений между которыми равны 90°. Строится контур так, чтобы все углы, кроме одного, располагались в загруженных клетках, а один угол находился в свободной, наиболее потенциальной клетке. При соблюдении этих двух правил для каждой свободной клетки можно построить только один контур.

3. Определяют положительные (+) и отрицательные (-) углы контура, считая, что первый положительный угол лежит в свободной клетке, для которой строится контур, рядом с ним находятся отрицательные углы, рядом с отрицательными - положительные и т.д. Количество положительных углов всегда равно количеству отрицательных углов контура.

Таблица 3

Грузообразующие точки	Грузопоглощающие точки						Итого по вывозу, т
	B1		B2		B3	B4
A1	16 200		-6 200		10	+4	400
A2	8		+2 200		-12400	14	600
A3	2		18		+8400	-6600	1000
Итого по ввозу, т	200		400		800	600	2000

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

В результате такого действия одна или несколько из ранее загруженных клеток становятся свободными, а наиболее потенциальная клетка становится загруженной. Ранее загруженные клетки, которые не оказались расположенными в углах контура, переносят в таблицу (табл. 4) нового варианта закрепления потребителей груза за грузоотправителями без изменений.

В табл. 3 из всех клеток, занятых отрицательными углами контура, наименьшую загрузку имеет клетка А₁В₂ - 200 т. Эти 200 т вычитаются из клеток, занятых отрицательными углами контура, и прибавляются в клетки, занятые положительными углами. В результате клетка А₁В₂ становится свободной, а наиболее потенциальная клетка А₁B₄ получает загрузку в 200 т. Загрузка клетки А₁В₁, в которой нет угла контура, в новом варианте решения остаётся без изменения (см. табл. 4).

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

200 * 16 + 200 * 2 + 200 * 12 + 600 * 8 + 400 * 6 = 14400 т*км.

Это на 2000 т*км меньше, чем получено в первом варианте решения. Величину сокращения грузооборота можно определить и как произведение количества груза, которое получила наиболее потенциальная клетка, на её потенциал.

Таблица 4

Грузообразующие точки	Грузопоглощающие точки							Итого по вывозу, т				Потенциалы
	B1		B2	B3		B4
A1	16 200		6	10		4 200		400				-16
A2	8		2 400	12 200		14		600				-22
A3	2		18	8 600		6 400		1000				-18
Итого по ввозу, т	200		400	800		600		2000
Потенциалы	0		+20	+10		+12

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

Задача решается до тех пор, пока не будет найден оптимальный вариант. Количество промежуточных решений зависит от сложности задачи. В нашем примере второй вариант, как и первый, является неоптимальным (табл. 5), оптимальный же вариант получен в результате третьего шага решения (табл. 6).

 

Таблица 5

Грузообразующие точки	Грузопоглощающие точки						Итого по вывозу, т
	B1		B2		B3	B4
A1	- 16 200		6		10	+ 4200	400
A2	8		2 400		12200	14	600
A3	2 +		18		8600	6 -400	1000
Итого по ввозу, т	200		400		800	600	2000

Таблица 6

Грузообразующие точки	Грузопоглощающие точки								Итого по вывозу, т		Потенциалы
	B1		B2		B3	B4
A1	16		6		10	4 400			400		-4
A2	8		2 400		12 200	14			600		-10
A3	2 200		18		8 600	6 200			1000		-6
Итого по ввозу, т	200		400		800	600			2000
Потенциалы	+4		+8		-2	0

Объем грузовой работы при оптимальном решении

400*4 +400*2+ 200*12 + 200*2 + 600*8 + 200*6 =11200 т*км.