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

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

Из трёх пунктов отправления нужно отправить груз в четыре пункта потребления.

В пункте A1 в наличии 40 единиц груза, в пункте A2 - 60 единиц, в пункте A3 - 100. Пункту потребления B1 требуются 35 единиц груза, пункту B2 - 35, пункту B3 - 80, пункту B4 - 50.

Решение. Строим таблицу, в которой в последний столбец записываем количества грузов в пунктах отправления, а в последнюю строку - количества грузов, которые требуются в пунктах потребления. В клетки пересечения пункта отправления Ai и пункта потребления Bj записываем затраты в условных единицах на перевозку груза из соответствующего пункта отправления в соответствующий пункт потребления. Получилась следующая таблица:

Таблица 1. Условие транспортной задачи в примере 1

Строим первоначальный план перевозок, применяя правило минимального элемента

Из всех клеток таблицы выбираем клетку с минимальной стоимостью перевозок. Это клетка A3B4. Ей соответствует стоимость c34 = 1. Это клетка, соответствующая пункту отправления A3 и пункту потребления B4. Запас груза в пункте A3 равен 100 единицам, а потребность в грузе в пункте B4 - 50 единицам.

Удовлетворим потребность пункта B4 за счёт пункта A3: впишем в правый нижний угол клетки A3B4 число 50, а стоимость, равную 1, возьмём в кружок.

Теперь по правилу минимального элемента следующую клетку с минимальным элементом следует искать или в столбце, или в строке, в которой находится пройденная клетка A3B4. В нашем случае в пункте отправления A3 осталилось неизрасходовано 50 единиц груза. Поэтому следующую клетку с минимальной стоимстью ищем в строке, соответствующей пункту отправления A3. Это клетка A3B1 с минимальной стоимостью c31 = 2. Пункту потребления B1 требуются 35 единиц груза. Удовлетворим потребность пункта B1 за счёт пункта A3: впишем в правый нижний угол клетки A3B1 число 35, а стоимость 2 возьмём в кружок.

Далее следует двигаться или по столбцу, или по строке, в которой находится кретка A3B1. В пункте отправления A3 осталось неизрасходовано 15 единиц груза. Поэтому вновь движемся по строке и находим клетку A3B2 с минимальной стоимостью c32 = 3. Оставшиеся в пункте A3 15 единиц груза отправляем в пункт потребления B2, в правый нижний угол клетки A3B2 впишем число 15, а стоимсть 3 возьмём в кружок.

Вновь нам предстоит двигаться или по столбцу, или по строке, в которой находится пройденная клетка. В пройденной клетке A3B2 запасы груза в пункте отправления A3 были израсходованы, поэтому дальше двигаемся уже по столбцу. Приходим на строку, соответствующую пункту отправления A2, в клетку A2B2, с минимальной в данном столбце стоимостью перевозок c22 = 4. У пункта потребления B2 остались неудовлетворённые потребности в 20 единицах груза. Удовлетворим эти потребности за счёт пункта отправления A2: в правый нижний угол клетки A2B2 вписываем число 20, а стоимость 4 возьмём в кружок.

Как двигаться дальше - по строке или по столбцу? Угадайте с одного раза! Правильно, по строке, потому что в пункте отправления A2 остались неизрасходованы 40 единиц груза. Попадаем в клетку A2B3. Куда направим оставшиеся 40 единиц груза? Потребности пунктов потребления B1, B2 и B4 уже удовлетворены, поэтому 40 единиц груза, требующиеся пункту потребления B3, направим в этот пункт, в правый нижний угол клетки A2B3 вписываем число 40, а стоимость 5 берём в кружок.

Таблица 2. Первоначальный план перевозок в примере 1

Все запасы груза, находившиеся в пункте отправления A2, израсходованы, поэтому дальше двигаемся по столбцу и попадаем в клетку A1B3, соответствующую пункту отправления A1. Запасы груза в этом пункте составляют 40 единиц, а неудовлетворённые потребности в грузе в пункте потребления B3 - также 40 единиц. Удовлетворим потребности пункта B3 за счёт пункта A1, впишем в правый нижний угол клетки A1B3 число 40, а стоимость перевозки 6 возьмём в кружок.

На этом потребности в грузе во всех пунктах потребления удовлетворены, а запасы груза во всех пунктах отправления израсходованы.

Найдём значение линейной формы, соответствующей первоначальному плану перевозок:

z(x1) = 6⋅40 + 4⋅20 + 5⋅40 + 2⋅35 + 3⋅15 + 1⋅50 = 685.

Клетки таблицы, содержащие кружочки, будем называть "занятыми местами", а клетки, не содержащие кружочков - "свободными местами". Первоначальный план перевозок составлен. Но мы ещё не решили всю транспортную задачу!

Оценка "свободных мест" и оптимальности плана перевозок

Следующий этап решения транспортной задачи после составления плана перевозок - исследование этого плана на минимум. Для этого исследуются знаки "свободных мест". Если во всех "свободных местах" имеются знаки "плюс", то транспортная задача решена, то есть план перевозок по стоимости является минимальным. Если же хотя бы одно из "свободных мест" имеет знак "минус", то план не даёт мимимума стоимости и его нужно улучшить.

Знаки "свободных мест" определяются следующим образом: начиная с любого "свободного места", двигаемся по ломаной линии, шагая только по "занятым местам". После каждого кружочка поворот делается только под прямым углом. Затем двигаемся до второго кружочка (не обязательно соседнего) и опять поворачиваем под прямым углом.

Таким образом, на пути по строке или столбцу в строке или столбце не могут встретиться больше двух кружков. Такое движение продолжается до тех пор, пока поворот от последнего кружочка не приведёт к исходному пункту, то есть исходному "свободному месту". Каждое движение должно быть или вертикальным, или горизонтальным, то есть перемещение по диагонали не допускается. Идя от исходной точки, то есть "свободного места", не обязательно брать первый встретившийся на пути кружок. Иногда можно пропустить один или несколько кружков, если через них невозможно кратчайшим путём вернуться к исходной точке. Путь, пройденный по вышеизложенным правилам, называется циклом.

Составим цикл для свободного места A1B1. В первой клетке, то есть A1B1, в правом верхнем углу ставим знак "плюс" (и так делаем всегда в начальной клетке цикла). Идём к "занятому месту" - к клетке A1B3, в правом верхнем углу которой ставим знак "минус". Далее знаки чередуются по правилу: у нечётных вершин цикла - знак "плюс", у чётных - "минус".

Получаем следующий цикл:

A1B1 → A1B3 → A2B3 → A2B2 → A3B2 → A3B1.

Значение "свободного места" получаем так: составляем ряд из стоимостей перевозки в каждой клетке цикла, взятых со знаком "плюс" или "минус", в зависимости от того, какой знак поставлен в правом верхнем углу соответствующей клетки. По этому правилу получаем оценку свободного места A1B1:

Δ11 = 2 − 6 + 5 − 4 + 3 − 2 = −2.

Точно так же составляем циклы для "свободных мест" A1B2, A1B4, A2B1, A2B4, A3B3 и вычисляем их оценки:

Δ12 = 5 − 6 + 5 − 4 = 0,

Δ14 = 4 − 1 + 3 − 4 + 5 − 6 = 1,

Δ21 = 2 − 4 + 3 − 2 = −1,

Δ24 = 2 − 1 + 3 − 4 = 0,

Δ33 = 4 − 3 + 4 − 5 = 0.

Так как оценки Δ11 и Δ21 отрицательны, первоначальный план перевозок - не оптимальный и его нужно улучшить. Таким образом, решение транспортной задачи ещё не получено.

Улучшение плана перевозок

Среди оценок "свободных мест" две отрицательные: Δ11 = −2 и Δ21 = −1. Выберем наименьшее из этих отрицательных значений: Δ11 = −2. Вдоль цикла для соответствующего ему "свободного места" A1B1 выбираем наименьшее из чисел в кружочке, отмеченных знаком "минус". Это число 20, обозначим его буквой θ ("тэта"):

θ = min{40, 20, 35} = 20.

Смотрим в первоначальный план перевозок. Найденное число "тэта" прибавляется ко всем "кружочкам" в клетках с положительными знаками и вычитается из всех "кружочков" в клетках с отрицательными знаками, включая само наименьшее число.

Таким образом, получаем перенаправление единиц груза для нового плана перевозок:

x'11 = x11 + θ = 0 + 20 = 20,

x'23 = x23 + θ = 40 + 20 = 60,

x'32 = x32 + θ = 15 + 20 = 35,

x'13 = x13 − θ = 40 − 20 = 20,

x'31 = x31 − θ = 35 − 20 = 15,

x'34 = x34 = 50.

Так как x'22 = x22 − θ = 20 − 20 = 0, то в новой таблице клетка A2B2 становится "свободным местом". Значение в клетке A3B4 остаётся прежним: x'34 = x34 = 50, так как эта клетка не входит в цикл.

Таблица 3. Второй план перевозок в примере 1

Значение линейной формы для нового плана перевозок вычисляется следующим образом. Вычисляется "экономия": наименьшее число "тэта" умножается на число, стоящее в кружочке в соответствующей клетке. Получается отрицательное число, так как "тэта" - отрицательное число. К значению линейной формы предыдущего плана прибавляется "экономия", то есть отрицательное число (фактически вычитается "экономия", если удобнее смотреть на неё "экономически", то есть считать положительным числом).

Вычислим значение линейной формы для плана перевозок x2:

z(x2) = z(x1) + θ⋅Δ21 = 685 + 20⋅(−2) = 645.

Для новой таблицы, как уже было показано, составляем циклы от "свободных мест" и вычисляем оценки "свободных мест":

Δ12 = 5 − 3 + 2 − 2 = 2,

Δ14 = 4 − 1 + 2 − 2 = 3,

Δ21 = 2 − 2 + 6 − 5 = 1,

Δ22 = 4 − 3 + 2 − 2 + 6 − 5 = 2,

Δ24 = 2 − 1 + 2 − 2 + 6 − 5 = 2,

Δ33 = 4 − 2 + 2 − 6 = −2.

Среди оценок свободных мест - одна отрицательная: Δ33 = −2, поэтому план x2 - не оптимальный.

Рассмотрим цикл, соответствующий "свободному месту" с отрицательной оценкой:

A3B3 → A3B1 → A1B1 → A1B3.

Точно так же, как было сделано в случае первоначального плана, вдоль этого цикла выбираем наименьшее из чисел в кружочке, отмеченных знаком "минус". Это число 15:

θ = min{15, 20} = 15.

Это число прибавляем ко всем "кружочкам" в клетках с положительными знаками и вычитаем из всех "кружочков" в клетках с отрицательными знаками и получаем перенаправление единиц груза для нового плана перевозок:

x'11 = x11 + θ = 20 + 15 = 35,

x'33 = x33 + θ = 0 + 15 = 15,

x'13 = x13 − θ = 20 − 15 = 5,

x'31 = x13 − θ = 15 − 15 = 0.

Таблица 4. Третий план перевозок в примере 1

Вычислим значение линейной формы для плана перевозок x3:

z(x3) = z(x2) + θ⋅Δ33 = 645 + 15⋅(−2) = 615.

Составим циклы для "свободных мест" плана x3 и вычислим оценки:

Δ12 = 5 − 6 + 4 − 3 = 0,

Δ14 = 4 − 1 + 4 − 6 = 1,

Δ21 = 2 − 2 + 6 − 5 = 1,

Δ22 = 4 − 5 + 4 − 3 = 0,

Δ24 = 2 − 1 + 4 − 5 = 0,

Δ31 = 2 − 2 + 6 − 4 = 2.

Так как оценки всех "свободных мест" неотрицательны, план x3 - оптимальный, он даёт минимум линейной формы z = 615.

Так как оценки Δ12, Δ22 и Δ24 равны нулю, то эта транспортная задача имеет бесконечное множество оптимальных планов (решений).

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

Из трёх пунктов отправления нужно отправить груз в три пункта потребления.

В пункте A1 в наличии 20 единиц груза, в пункте A2 - 40 единиц, в пункте A3 - 40. Пункту потребления B1 требуются 20 единиц груза, пункту B2 - 20, пункту B3 - 60.

Строим таблицу, руководствуясь теми же соображениями, что в примере 1.

Таблица 5. Условие транспортной задачи в примере 2

Применение правила северо-западного угла начинается с составления плана перевозок для первого пункта отправления (для A1), то есть с левого верхнего (северо-западного) угла таблицы. Далее, как и по правилу минимального элемента, нужно двигаться вперёд по строке или столбцу, в которых находится пройденная клетка, но, в отличие от правила минимального элемента, не требуется искать в этих строке или столбце минимальный элемент (клетку с минимальной стоимостью), а можно двигаться последовательно от соседнего элемента к соседнего до тех пор, пока все запасы груза в пунктах отправления не будут распределены по всем пунктам потребления.

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

Итак, начинаем движение с клетки A1B1. Запас груза в пункте отправления A1 равен 20. Потребность в грузе в пункте потребления B1 составляет также 20. Удовлетворяем потребность пункта потребления B1 за счёт пункта отправления A1 и в правый нижний угол клетки A1B1 вписываем 20. Видим, что мы получаем вырожденный (сингулярный) план перевозок. Поэтому в правый нижний угол соседней клетки с меньшими транспортными расходами (A2B1) вписываем нуль.

Далее, соответственно правилу северо-западного угла, движемся по клеткам A2B2, A2B3, A3B3 и получаем план перевозок x1.

Таблица 6. Первый план перевозок в примере 2

Значение линейной формы плана x1:

z(x1) = 3⋅20 + 1⋅20 + 2⋅40 + 4⋅40 = 280.

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

A1B2 → A2B2 → A2B1 → A1B1,

A1B3 → A2B3 → A2B1 → A1B1,

A3B1 → A2B1 → A2B3 → A3B3,

A3B2 → A2B2 → A2B3 → A3B3.

Вычисляем оценки "свободных мест":

Δ12 = 4 − 1 + 1 − 3 = 1,

Δ13 = 3 − 2 + 1 − 3 = −1,

Δ31 = 1 − 1 + 2 − 4 = −2,

Δ32 = 5 − 1 + 2 − 4 = 2.

Так как два свободных места имеют отрицательные оценки, план x1 - не оптимальный и его нужно улучшить. Решение транспортной задачи ещё не получено.

Выбираем "свободную" клетку A3B1, у которой минимальная отрицательная оценка: Δ31 = −2. Вдоль цикла, соответствующего этой клетке, выбираем наименьшее из чисел в кружочке, отмеченное знаком минус:

θ = min{0, 40} = 0.

В результате перенаправления грузов клетка A2B1 становится "свободным местом" в плане перевозок x2, а "свободное место" A3B1 становится "занятым местом", которому соответствует количество груза 0 единиц.

Таблица 7. Второй план перевозок в примере 2

Вычисляем значение линейной формы для плана x2:

z(x2) = z(x1) + θ⋅Δ31 = 280 + 0⋅(−2) = 280.

Для плана x2 вычисляем оценки "свободных мест":

Δ12 = 4 − 1 + 2 − 4 + 1 − 3 = −1,

Δ13 = 3 − 4 + 1 − 3 = −3,

Δ21 = 1 − 2 + 4 − 1 = 2,

Δ32 = 5 − 1 + 2 − 4 = 2.

Среди оценок свободных мест две - отрицательные, поэтому план перевозок необходимо улучшить. В следующем плане перевозок "свободное место" A1B3 становится "занятым местом", так как его оценка Δ13 = −3 - наибольшая по модулю отрицательная оценка.

Вдоль цикла, соответствующего этой клетке, выбираем наименьшее из чисел в кружочке, отмеченное знаком минус:

θ = min{40, 20} = 20.

Таблица, соответствующая плану перевозок x3, будет следующей:

Таблица 8. Третий план перевозок в примере 2

Находим значение линейной формы для плана x3:

z(x3) = z(x2) + θ⋅Δ13 = 280 + 20⋅(−3) = 220.

Вычисляем оценки "свободных мест":

Δ11 = 3 − 3 + 4 − 1 = 3,

Δ12 = 4 − 3 + 2 − 1 = 2,

Δ21 = 1 − 2 + 4 − 1 = 2,

Δ32 = 5 − 1 + 2 − 4 = 2.

Окончательное решение данной транспортной задачи получено. Поскольку все оценки "свободных мест" - неотрицательные, план x3 является оптимальным планом и ему соответствует минимум линейной формы z = 220.