Распределительный метод решения транспортной задачи

Пример. Найти оптимальное распределение поставок задачи таблица 1.

Решение. Начнем с базисного распределения поставок полученного в задаче (таблица5). Как было установлено (см. задачу таблицу 10 и 15) данное распределение не оптимально. Учитывая результаты последней задачи (16) имеем

Значение найдено в задаче таблица 5. Далее поступаем так, как поступили бы, решая задачу симплексным методом: переменную , коэффициент при котором отрицателе, будем переводить в основные (базисные) переменные. Переменная начинает возрастать от нуля. Как было показано ранее, перевод поставки в свободную клетку вызывает перераспределение поставок (передвижение поставок по циклу). Означенный цикл пересчета для клетки(1,3) показан на рисунке 2.

Рис.2

Увеличиваем поставку в клетке(1,3), до тех пор пока поставка в одной из заполнены клеток не станет равной нулю. Эта клетка принадлежит циклу (рис2) для клетки (1,3). Если в клетку(1,3) передать поставку, равно Z, то по поставка в клетках цикла со знаком «+» увеличится на Z, а в клетках со знаком «-» уменьшится на Z. Поэтому искомая клетка находится среди клеток цикла имеющих знак «-». Более того, она имеет минимальную поставку среди таких клеток. Т.к. (рис2) то в нашем случае- это клетка(3,3), и для обнуления поставки в этой клетке по циклу следует передать 40 единиц, т.е поставка передаваемая по циклу, определяется как минимум среди поставок со знаком «-». После этого клетка(1,3) считается заполненной, а клетка(3,3) свободной,

Клетки со знаком «+» увеличивают на передаваемую поставку: клетка(3,2) равна 90 единиц, клетка(1,3) равна 40 единиц. Аналогично в клетках со знаком «-» поставка уменьшится на передаваемую поставку, например(1,2) станет равной 20 единиц. Вновь полученное распределение базисное (таблица 11).

Табл.11

(3)-1

(17)

! Возникает вопрос об оптимальности. Найдем оценки свободных клеток (матрицу оценок) распределение поставок. Для этого подберем потенциалы, так чтобы коэффициенты затрат заполненных клеток стали = 0. Тогда матрица оценок будет (17).

Т.к.(1,1) имеет отрицательную оценку, то найденное решение не оптимально и передача поставки в(1,1) ведет к уменьшению суммарных затрат на перевозку. Означенный цикл пересчета для(1,1) приведен на рисунке 3.

Рис.3

По правилу сформулированному выше, поставка, передаваемая по циклу . Передвигая эту поставку по циклу (рисунок 3), приходим к новому распределению поставок (таблица12).