Транспортная задача пример

Покажем, как нужно пользоваться методом потенциалов, на примере первоначального плана, полученного ранее по методу северо-западного угла.

Вначале проверим, не является ли этот план вырожденным. Так как m + n - 1 = 3 + 4 - 1 = 6 , и число базисных клеток в плане также равно 6, то план в пополнении не нуждается. Найдем потенциалы по базисным клеткам таблицы, положив u₁ = 0,

и занесем полученные значения в таблицу. Вычислим теперь разности Δc_ij для свободных клеток и также проставим эти данные в левых нижних углах соответствующих клеток. В итоге получим следующую таблицу

Таблица 1

Поскольку Δc₁₄ = -4 < 0, то этот план не является оптимальным. Перераспределим груз по циклу, обозначенному в таблице 1 пунктиром, на величину Δx = min(20,60) = 20. Для этого в клетках со знаком «плюс» увеличим поставки на 20 единиц, а клетках со знаком «минус» – поставки на столько же уменьшим. Для сохранения количества базисных клеток число 0 в клетке (1,3) не записываем, и она становится свободной.

Вычислив потенциалы и разности Δc_ij для нового плана, видим, что снова есть отрицательная разность Δc₃₂ = -4. Поэтому придется еще раз улучшать план. С этой целью перераспределим груз по циклу, отмеченному в таблице 2 пунктиром, на величину Δx = min(40,40) = 40. Так как в результате в цикле получаются две клетки с нулевыми перевозками: (1,3) и (3,4), то сделаем свободной клетку (1,3), поскольку ее тариф перевозок больше. После перераспределения груза по циклу вычислим все необходимые разности Δc_ij.

Таблица 2

Как видим, все Δc_ij неотрицательны, значит, план оптимален (таблица 3).

Таблица 3