[Список тем] [Вступление к этой теме] страницы темы: [1] [2]

Особые случаи решения транспортной задачи.

Рассмотрим особые случаи, которые могут возникнуть при решении транспортной задачи.
1. В некоторых случаях поставка, переводимая по циклу, может оказаться равной нулю. Это возможно тогда, когда клетка цикла со знаком "-" содержала нулевую поставку. В этом случае по циклу передается нулевая поставка. В результате та свободная клетка, для которой был построен цикл, становится заполненной (нулевой поставкой), а клетка с нулевой поставкой - свободной.
2. Если при переводе поставки по циклу поставка обращается в нуль сразу в нескольких заполненных клетках, то свободной из них следует считать только одну (любую), остальные клетки, поставка в которых стала равной нулю, следует считать заполненными нулевой поставкой. Разберем перечисленные особые случаи на примере.

Задача 7.8

Завершить решение транспортной задачи из задачи 7.4. Решение. Установим сначала, оптимально ли распределение, полученное в указанном примере методом "северо-западного" угла (см. табл. 7.8). Подберем потенциалы строк и столбцов этой таблицы поставок так, чтобы коэффициенты затрат заполненных клеток стали равны нулю (табл. 7.14). Таблица 7.14 Это приводит к матрице оценок (7.16). (7.16) Так как среди свободных клеток таблицы есть клетка (3,2) с отрицательной оценкой, то данное базисное распределение поставок не оптимально. Переведем поставку в клетку (3,2) с отрицательной оценкой. Строя для клетки (3,2) означенный цикл пересчета (рис. 7.5), находим, что объем передаваемой поставки в данном случае равен x32 = min{0,10} = 0. Передавая по построенному циклу нулевую поставку, Рис. 7.5 приходим к новому базисному распределению (табл. 7.15). Таблица 7.15 Подбирая потенциалы к строкам и столбцам табл. 7.15, находим матрицу (7.17) оценок данного распределения. Так как среди свободных клеток таблицы есть клетка (1,3) с отрицательной оценкой, то данное базисное распределение не оптимально. Найдем новое базисное распределение, передавая поставку в клетку (1,3) с отрицательной оценкой. Построим цикл для клетки (1,3), показанный на рис. 7.6. Поставка, передаваемая в клетку (1,3): -Со = mm{10,10} = 10. При передаче по циклу (см. рис. 7.6) 10 единиц фуза станут равными нулю поставки в клетках (1,2) и (3,3). Полагаем, что только одна из них стала свободной, например клетка (3,3), а клетка (1,2) заполнена нулевой поставкой. Таким образом, будет получено базисное распределение поставок, представленное в табл. 7.16. Рис. 7.6 Таблица 7.16 Определяя матрицу оценок (7.18), видим, что среди оценок свободных клеток найденного распределения нет отрицательных, т.е. найденное распределение (см. табл. 7.16) оптимально.

[Список тем] [Вступление к этой теме] страницы темы: [1] [2]

[В начало страницы]