Алгоритм решения закрытой транспортной задачи

1. Для данного базисного распределения поставок подберем потенциалы строк и столбцов таблицы поставок, так чтобы коэффициент затрат заполненных клеток стали равны нулю. Составляем матрицу оценок.

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

3. Для избранной свободной клетки строится означенный цикл пересчета. Поставка Z, передаваемая по циклу, определяется как минимум среди поставок в клетках со знаком -. Найденная поставка передвигается по циклу. При этом поставка в клетках цикла со знаком + увеличивается на z, а в клетках с – уменьшается на z. Клетка, поставка в которой при этом станет = 0 будет считаться свободной (далее рассмотрим случай, когда таких клеток несколько), остальные клетки цикла – заполненными. Т. о. получено новое базисное распределение поставок.

4 Переходим к п. 1 алгоритма.

Рассмотрим особые случаи, которые могут возникнуть при решении транспортной задачи.

1. В некоторых случаях поставка, переводимая по циклу, может оказаться = 0. Это возможно тогда, когда клетка цикла со знаком – содержала нулевую поставку. В этом случае по циклу передается нулевая поставка. В результате та свободная клетка, для которой был построен цикл, становится заполненной (нулевой поставкой), а клетка с нулевой поставкой – свободной.

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

Разберем эти случаи на примере.

Задача. Завершить решение транспортной задачи таб. 6.

Табл.13

 

 

Решение. Сначала установим оптимально ли распределение полученное методом «северо-западного» угла. Подберем потенциалы строк и столбцов, так чтобы коэффициент затрат заполненных клеток стали равны 0, матрица (19). Так как клетка (3,2) отрицательна, распределение не оптимально.

 

матр.19

Переведем поставку в клетку (3,2) с отрицательной оценкой. Построим для (3,2) цикл пересчета, находим, что объем передаваемой поставки равен x_3.2=min(0.10)=0. Передавая по построенному циклу нулевую поставку, приходим к новому базисному распределению (табл.14). Подбирая потенциалы к строкам и столбцам табл. 14 находим матрицу оценок распределения (20).

Т. к. (1,3) отрицательна то данное базисное распределение не оптимально. Найдем новое базисное распределение передавая постановку в (1,3) с отрицательной оценкой. Построим цикл для (1,3).

 

 

Табл. 14

			-		+
			+		-

-2

 

 

(20)

 

Поставка, передаваемая в клетку(1,3): . При передачи по циклу 10 единиц груза станут равными нулю поставки в клетках (1,2) и (3,3). Только одна из них стала свободной напр.(3,3), а (1,2) заполнена нулевой поставкой т.о. получим базисное распред. поставок таблица 15.

 

					-1

 

(21)

 

			-2

 

 

Определим матрицу поставок. Среди оценок свободных клеток найденного распределения нет отрицательных т.с. найденное распред.(таблица 15) оптимально.