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

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

       Таблица 5

 

       Как видим, все c_ij неотрицательны, значит, план оптимален:  
 
 
 
 

       Таблица 6

6. Пример решения  типовой транспортной  задачи

 

       Задача  . На складах трех поставщиков A₁, A₂, A₃ хранится 300, 250 и

200 единиц  одного и того же груза. Этот  груз требуется доставить четырем потребителям B₁,B₂,B₃ и B₄, заказы которых составляют 220, 150, 250 и 180 единиц груза соответственно. Стоимости перевозок c_ij единицы груза с i-го склада j -му потребителю указаны в правых верхних углах соответствующих клеток Таблицы 7.

Таблица 7

       Составить такой план перевозок груза, при  котором общая стоимость всех перевозок была бы минимальной.

       Решение. Поскольку суммарный запас груза а = 300 + 250 + 200 = 750 меньше суммарной потребности b = 220 + 150 + 250 + 180 = 800, то рассматриваемая транспортная задача является открытой. Сведем ее к закрытой, добавив фиктивного поставщика  A'₄ с нулевыми тарифами перевозок и запасом груза a'₄ = b - a = 50.

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

       (4,2) → (3,2) → (2,3) → (3,4) → (1,1) →  (1,4).

       Получим Таблицу 8:

       Таблица 8

 

       Перейдем  к анализу полученного плана. Заметим, что в этой задаче m + n -1= 4 + 4 -1= 7 , а число занятых клеток в имеющемся плане равно 6.

       Значит, необходимо пополнить план еще 1 клеткой, записав в ней 0, так, чтобы пополненный план получился ациклическим. Выберем для этой цели, например, клетку (4,3).

       Вычислим  потенциалы по базисным клеткам плана:

        u₁ + v₁ = 4                                                      u₁ = 0

       u₁ + v₄ = 6                                                      u₂ = -4

       u₂ + v₃ = 1                                                      u₃ = -4

       u₃ + v₂ = 1                 =>                                 u₄ = -5

       u₃ + v₃ = 2                                                      v₁ = 4

       u₃ + v₄ = 0                                                      v₂ = 5

       u₄ + v₂ = 0                                                      v₃ = 5

       u₁ = 0                                                              v₄ = 6

       и вычислим для свободных клеток разности

       c_ij = c_ij – (u_i + v_j ).

       Получим Таблицу 9.

       Таблица 9

 

       Поскольку среди чисел c_ij есть отрицательные, то перераспределим груз на величину x = min(80,100,0) = 0 по циклу, обозначенному пунктиром. Клетка (1,3) станет базисной вместо клетки (4,3), и мы получим таблицу 10.

       План, указанный в таблице 10, не является оптимальным, поскольку c₂₂ = c₄₄ = - 1 < 0 .

       Улучшим этот план с помощью перераспределения  поставок по циклу, обозначенному в  таблице 10 пунктиром, на величину x = min(100,50) = 50 .

       Получим Таблицу 10:

       Таблица 10