§5. Алгоритм решения транспортной задачи

1. Определение опорного транспортного плана

Как и в общем случае, решение транспортной задачи начинается с нахождения первого опорного плана. Существует несколько ме­тодов построения опорного плана перевозок. Рассмотрим один из них – метод наименьшей стоимости.

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

 1 Построение опорного плана перевозок

Условия транспортной задачи заданы транспортной таблицей 1:

Таблица 1

Базы	Магазины									Запас
	B1		B2		B3			A4
A1		7		3			4		2	15
A2		6		1			4		6	31
A3		6		9			5		3	25
A4		10		4		7			9	22
Спрос	28		17		28			20

Составим опорный план перево­зок методом наименьшей стоимости.

Заполним таблицу 1, начиная с клетки (A₂, B₂), в которой мы имеем минимальную стоимость перевозки (c₂₂ = 1). За счет запаса базы A₂ можно удовлетворить всю заявку магазина B₂, поэтому записы­ваем 17 в клетку (A₂, B₂).

Следующую по величине стоимость, равную 2, имеем в клетке (A₁, B₄). Поскольку запас базы A₁ меньше заявки магазина B₄, в эту клетку записываем перевозку, равную запасу базы A₁ (15 еди­ниц). Следующую по величине стоимость равную 3, имеем в клетках (A₁, B₂) и (A₃, B₄). Клетку (A₁, B₂) нельзя заполнять, поскольку запас ба­зы A₁ уже исчерпан. Заполняем клетку (A₃, B₄), удовлетворяя оставшуюся часть заявки магазина B₄ (5 единиц) за счет базы A₃.

Рассуждая аналогично, заполняем остальные клетки в такой последовательности: (A₂, B₃), (A₃, B₃), (A₃, B₁), (A₄, B₁). Будем иметь:

Таблица 2

Базы	Магазины									Запас
	B1		B2		B3			A4
A1		7		3			4		2	15
								15
A2		6		1			4		6	31
			17		14
A3		6		9			5		3	25
	6				14			5
A4		10		4		7			9	22
	22
Спрос	28		17		28			20

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

x=(0, 0, 0, 15, 0, 17, 14, 0, 6, 0, 14, 5, 22, 0, 0, 0),

или, в матричной форме,

Вычислим стоимость плана x:

E(x)=215+117+414+66+514+35+1022=444.

Отметим, что число заполненных (базисных) клеток равно т + п – 1= 7, то есть, действительно построен опорный план перевозок.

 При построении опорного плана перевозок в рассмот­ренной задаче на каждом шаге, кроме последнего, либо исчерпы­вался запас базы (но оставалась невыполненной заявка), либо выполнялась заявка магазина (но оставалась неиспользованной часть запаса базы). Может оказаться, что на некотором (не послед­нем!) шаге будет одновременно выполнена заявка магазина и исчерпан запас базы, тогда число заполненных клеток окажет­ся меньше, чем т + п – 1. В этом случае следует записать нуле­вую перевозку в ту клетку, которая заполнялась бы, если бы оста­ток запаса данной базы не был бы равен нулю. Эта клетка в даль­нейшем считается базисной.