6.2. Построение опорного плана транспортной задачи

Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:

	1	…	n
1		…
…	…	…	…	…
m		…
		…		=

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

1. сумма перевозок в каждой строке равна запасу в данной строке;

2. сумма перевозок в каждом столбце равна соответствующему спросу .

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

Опорный план называется вырожденным, если число ненулевых перевозок меньше , опорный план -невырожден, если число ненулевых перевозок равно

Рассмотрим способы построения опорного плана в невырожденном и вырожденном случаях [1,3].

6.3. Метод северо-западного угла

Рассмотрим «северо-западный угол» незаполненной таблицы, т.е. клетку, соответствующую первому поставщику и первому потребителю.

Возможны три случая:

1. Если , то . Это означает, что первый поставщик отгрузил весь продукт первому потребителю и его запас равен нулю, поэтому . При этом неудовлетворенный спрос в первом пункте потребления равен .

2. Если , то , т.е. спрос первого потребителя полностью удовлетворен и поэтому , а остаток продукта в первом пункте производства равен .

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

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

6.4. Пример

Найти опорный план транспортной задачи.

	1	2	3
1	15	20		35		20		0	0
2		0	30	30		30		30
	15	20	30	=
	0	20	30
	0	0	30
	0	0	0

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