Лекция 9

Решение транспортных задач с вырожденным опорным планом.

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

Пример. Табл. 9.1

Поставщики	Запас	В1	В2	В3
А1					=0
А2					=-3
Объём заявок				−
		=10	=4	=3	−

Этот план содержит 3 заполнения клетки, что меньше (m+n-1)=(3+2-1)=4, потому данный план является вырожденным. Запишем в клетку 1-2 значение объема груза равное «0». Тогда число заполненных клеток станет равно 4, и задачу можно решать как и для обычного опорного решения:

1-1 U₁+V₁=10

1-2 U₁+V₂=4 (9.1)

1-3 U₁+V₃=3

2-2 U₂+V₂=1

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

Табл.9.2

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

1-1 U₁+V₁=10

1-2 U₁+V₂=4 (9.2)

1-3 U₁+V₃=3

2-1 U₂+V₁=5,

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

Что план оптимален. Отметим, что минимальным числом в клетках помеченными знаком «-»является 0, и в этом случае к содержимому клеток цикла прибавляется или вычитается 0. При этом свободная клетка после прибавления 0 считается занятой, а клетка из которой вычитается 0, если она считалась занятой и содержала 0 считается свободной.