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

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

Метод северо-западного угла. На примере конкретной задачи продемонстрируем этот метод нахождения опорного плана.

З а д а ч а 12. На три базы А₁, А_2, А₃ поступил однородный груз в количествах, соответственно равных 140, 180, 160 ед. Этот груз требуется перевезти в пять пунктов назначения В₁, В₂, В₃, В₄, В₅ соответственно в количествах 60, 70, 120, 130, 100 ед. Тарифы перевозок единичного количества груза с каждого из складов в соответствующие пункты назначения указаны в табл.16. Найти план перевозок данной транспортной задачи методом северо-западного угла.

Таблица 16

Структурная запись задачи

Поставщик	Пункт назначения					Запасы
	В1	В2	В3	В4	В5
А1	2	3	4	2	4	140
А2	8	4	1	4	1	180
А3	9	7	3	7	2	160
Потребность	60	70	120	130	100	480

Р е ш е н и е. Введем понятие маршрута – наименование клетки А_iB_j, где i – порядковый номер поставщика, j – порядковый номер потребителя.

Задача является закрытой, так как количество имеющегося у поставщиков грузов равно объему грузов, запрашиваемых потребителями. Здесь число пунктов отправления m=3, а число пунктов назначения n=5. Следовательно, невырожденный опорный план задачи будет определяться числом заполненных маршрутов (ненулевых переменных) в количестве 5+3-1=7.

По рассматриваемому методу заполнение маршрутов начнем с клетки, стоящей в левом верхнем углу. Потребность в грузе пункта В₁ составляет 60 ед и от поставщика А₁ можно эту потребность полностью удовлетворить. Иначе, по маршруту А₁В₁ будет запланирована поставка в размере 60 ед. Следующий потребитель В₂ нуждается в поставке 70 ед груза, что также можно выполнить, доставив требуемый объем груза от поставщика А₁ , у которого после первой поставки осталось 140-60=80 ед. Таким образом, по маршруту А₁В₂ можно запланировать доставку груза в полном объеме. Оставшийся у поставщика А₁ объем груза в 10 ед запланируем доставить потребителю В₃,

т.е. по маршруту А₁В₃. Так как ресурсы поставщика А₁ полностью израсходованы, потребителю В₂ оставшиеся 110 ед груза запланируем доставить по маршруту А₂В₃ , т.е. от поставщика А₂. Пользуясь подобным алгоритмом, по маршруту А₂В₄ запланируем доставку 70 ед, по маршруту А₃В₄ доставку 60 ед и по маршруту А₃В₅ оставшиеся 100 ед груза (табл.17).

Таблица 17

Результирующая таблица опорного плана задачи 12

Поставщик	Пункт назначения					Запасы
	В1	В2	В3	В4	В5
А1	2 60	3 70	4 10	2	4	140
А2	8	4	1 110	4 70	1	180
А3	9	7	3	7 60	2 100	160
Потребность	60	70	120	130	100	480

Теперь рассчитаем суммарные затраты на доставку всего объема грузов:

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

.

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

Метод минимального элемента. В методе северо-западного угла алгоритм заполнения маршрутов был построчный с учетом остатков груза у очередного поставщика, при этом полностью игнорировались размеры тарифных ставок на перевозки. Очевидно, что минимальная стоимость перевозок будет обеспечена в большей мере, если при заполнении соответствующих маршрутов (клеток) отдавать предпочтение маршрутам с минимальной тарифной ставкой на перевозку. В этом и заключается идея метода минимального элемента.

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

В общем наборе тарифов есть два маршрута со ставкой «1» и три маршрута со ставкой «2», два маршрута со ставкой «3», четыре маршрута со ставкой «4», два маршрута со ставкой «7», по одному маршруту со ставками «8» и «9». В такой же последовательности будем перераспределять груз. При равенстве тарифов маршрут выбирают произвольно.

Начнем с маршрута А₂В₅. Назначим объем перевозок по нему 100 ед, а по маршруту А₂В₃ оставшиеся у поставщика А₂ 80 ед груза. Естественно, маршруты А₁В₅ и А₃В₅ , а также А₂В₁, А₂В₂, А₂В₄ должны быть выключены из списка свободных (знак Х). Теперь заполним маршрут А₁В₁ , назначив по нему перевозку груза в объеме 60 ед (таков запрос потребителя В₁) и выведем из состава свободных маршрут А₃В₁. Следующим заполняем маршрут А₁В₄ количеством груза в объеме 80 ед (оставшиеся у поставщика А₁ после заполнения маршрута А₁В₁). Соответственно исключаем маршруты А₁В₂, А₁В₃. Оставшиеся маршруты закрываем безвариантно (табл.18).

Таблица 18

Заполнение таблицы при методе минимального элемента

Поставщик	Пункт назначения					Запасы
	В1	В2	В3	В4	В5
А1	2 60	3 Х	4 Х	2 80	4 Х	140
А2	8 Х	4 Х	1 80	4 Х	1 100	180
А3	9 Х	7 70	3 40	7 50	2 Х	160
Потребность	60	70	120	130	100	480

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

,

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

.

Полученный план имеет 7 заполненных маршрутов, поэтому план невырожденный и может быть в дальнейшем улучшен (если при первом шаге начать составление плана с маршрута А₂В₃, то получим план со значением функции цели F=1480).

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

Метод аппроксимации по Фогелю. В принципе этот метод является развитием идеи метода минимального элемента, т.е. заполнение маршрутов с учетом тарифных ставок.

З а д а ч а 14. Рассмотрим его на примере той же задачи. Правее столбцов и ниже строк записывают текущую разность между тарифными ставками незакрытых маршрутов как по строкам (справа), так и по столбцам (внизу). Разность определяется между двумя минимальными ставками. Из полученных разностей выбирается наибольшая по абсолютному значению и далее первым заполняется тот маршрут в данном столбце или строке, который имеет минимальную тарифную ставку. Если по какому-либо потребителю или поставщику полностью используются запасы или закрываются поставки, все остальные маршруты по данному направлению закрываются и прекращаются процедуры нахождения разностей по тарифам. В табл.19 представлены результаты поиска опорного плана по вышеописанной схеме.

Таблица 19

Нахождение опорного плана по Фогелю

Склад	Потребитель					Запас		Разность по строкам
	В1	В2	В3	В4	В5
А1	2 60	3 Х	4 Х	2 80	4 Х	140		1		1	1	1	-
А2	8 Х	4 60	1 120	4 Х	1 Х	180		3		3	3	0	0
А3	9 Х	7 10	3 Х	7 50	2 100	160		1		1	5	0	0
Потреб- ность	60	70	120	130	100	480
Разность по столбцам	6	1	2	2	1
	-	1	2	2	1
	-	1	-	2	1
	-	1	-	2	-
	-	3	-	3	-

В таблице соблюдался следующий порядок заполнения маршрутов: А₁В₁, А₂В₃, А₃В₅, А₁В₄, А₂В₂, А₃В₂, А₃В₄. Максимальные разности по столбцам и строкам выделены жирным шрифтом.

В результате получен следующий опорный план:

,

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

.

Очевидно, наилучший опорный план получен по методу Фогеля, но и он может быть в дальнейшем улучшен (см. ниже).