Построение  плана начнем с клетки с наименьшим тарифом перевозок. При наличии нескольких клеток с одинаковыми тарифами выберем любую из них. Пусть это будет клетка (i, j). Запишем в эту клетку элемент x_ij = min(a_i, b_j). Если a_i < b_j, то запасы поставщика A_i исчерпаны, а потребителю B_j требуется еще b'_j = b_j - a_i единиц груза. Поэтому, не принимая более во внимание i-ю строку, снова ищем клетку с наименьшей стоимостью перевозок и заполняем ее с учетом изменившихся потребностей. В случае a_i > b_j из рассмотрения исключается j-й столбец, а запасы A_i полагаются равными a'_i = a_i - b_j. Продолжаем этот процесс до тех пор, пока все запасы не будут исчерпаны, а все потребности удовлетворены.

       Необходимо  отметить, что при наличии в  таблице клеток с одинаковыми  тарифами, планы, полученные с помощью  этого метода, могут быть разными, однако они, несомненно, ближе к оптимальному плану, чем план, составленный по методу северо-западного угла.

       Сформируем  теперь первоначальный план по методу наименьшей стоимости для рассмотренного в параграфе 3.1 примера и сравним результаты (Таблица 3). Поскольку наименьший тариф (число 2) стоит в клетке (2,3), то запишем в эту клетку элемент x₂₃ = 30. Тогда b'₃ = 50, а 2-ю строку таблицы можно больше не учитывать. Среди оставшихся клеток имеются три клетки с наименьшим тарифом перевозок, равным 4: (1,1); (3,1) и (3,2). Выберем, например, клетку (1,1) и запишем в нее число x₁₁ = 100. Получаем, что a'₁= 60, а 1-й столбец таблицы больше не рассматриваем. Теперь наименьший тариф, равный 4, проставлен в клетке (3,2), поэтому x₃₂ = 40, b'₃ = 50 и 2-й столбец больше не нужен. Далее выбираем клетку (1,4) с тарифом 5 и пишем в нее 60 14 x = . Исключив из рассмотрения сразу 1-ю строку и 4-ый столбец (поскольку     a'₁ = b₄ = 60), переходим к последней клетке (3,3), в которую записываем перевозку x₃₃ = 50.

       Таблица 3

 

       Найдем  суммарную стоимость перевозок  по этому плану:

z = 4 ×100 + 5 × 60 + 2 × 30 + 4 × 40 + 6 × 50 = 1220

       Сравнивая это значение со стоимостью плана, полученного  по методу северо-западного угла, видим, что 1220 < 1460, то есть мы получили более выгодный план перевозок.

4. Вырожденные планы.  Циклы и пополнение  плана

 

       Прежде, чем перейти к анализу оптимальности  планов и способам их улучшения, выясним, каким требованиям должны удовлетворять составляемые планы. Для этого вернемся к системе ограничений (1). В соответствии с определением плана перевозок у матрицы X = {xij } сумма элементов i-й строки равняется a_i, i = 1,2,..., m, а сумма элементов j-о столбца равняется b_j, j = 1,2,..., n. Условие закрытости транспортной задачи a = b означает, что среди m + n уравнений системы (1) независимыми являются только m + n -1 уравнений, поэтому в любом базисном решении этой системы должно быть m + n -1 базисных переменных. Поскольку свободные переменные в таком решении равны нулю, то в транспортной таблице им будут соответствовать пустые клетки.

       Клетки  таблицы, в которые записаны отличные от нуля перевозки, называются базисными, а остальные (пустые) - свободными.

       План  называется вырожденным, если количество базисных клеток в нем меньше, чем m + n -1.

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

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

       План  называется ациклическим, если его базисные клетки не содержат циклов.

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

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

план, полученный по методу наименьшей стоимости, имеет 5 базисных клеток, однако m + n -1 = 3 + 4 -1 = 6. Значит, план нужно пополнить еще одной базисной клеткой. Попробуем выбрать для этого клетку (2,2). Соединив базисные клетки горизонтальными и вертикальными отрезками (рис. 1), получаем:

(1,1) –––––––––––––  (1,4)                       (1,1) –––––––––––––– (1,4)

            (2,2) –– (2,3)                                                          (2,3) –– (2,4)

               │           │                                                              │

            (3,2) –– (3,3)                                             (3,2) –– (3,3)

                 рис.1                                                             рис.2

       Видим, что пополненный таким образом  план содержит цикл из клеток (2,2); (2,3); (3,3) и (3,2), следовательно, клетка (2,2) была выбрана  неудачно. Взяв вместо нее клетку (2,4), получим ациклический план (рис. 2). Поэтому  можно заполнить эту клетку, положив x₂₄ = 0.

 

5. Проверка оптимальности  плана и перераспределение поставок c помощью метода потенциалов

 

       Для анализа полученных планов и их последующего улучшения удобно ввести дополнительные характеристики пунктов отправления  и назначения, называемые потенциалами.

5.1. Вычисление потенциалов

 

       Сопоставим  каждому поставщику A_i и каждому потребителю B_j величины u_i и v_j соответственно так, чтобы для всех базисных клеток плана были выполнены соотношения

       u_i + v_j = c_ij, i =1,2,...,m, j =1,2,..., n. (2)

       Поскольку число базисных клеток в плане  равно m + n -1 (вырожденные планы должны быть предварительно пополнены), то для определения потенциалов получается система из m + n -1 уравнений с m + n неизвестными. Такая система имеет бесконечное множество решений. Нам требуется любое ее решение. Обычно для простоты полагают один из потенциалов равным нулю и затем вычисляют остальные. В транспортной таблице для потенциалов v₁, v₂,… v_n заводится дополнительные строка, а для потенциалов u₁, u₂,… u_m – дополнительный столбец, куда проставляются найденные значения.

5.2. Проверка оптимальности  плана

 

       Для каждой свободной клетки плана вычислим разности c_ij = c_ij – (u_i + v_j) и запишем полученные значения в левых нижних углах соответствующих клеток. Заметим, что для базисных клеток выполнено соотношение c_ij = 0, и этим фактом можно пользоваться для контроля правильности нахождения потенциалов.

       План  является оптимальным, если все разности c_ij ≥ 0. В противном случае план можно улучшить следующим способом.

5.3. Перераспределение  поставок

 

       Найдем  клетку с наибольшей по абсолютной величине отрицательной разностью  c_ij и построим цикл, в котором кроме этой клетки все остальные являются базисными. Такой цикл всегда существует и единственен.

        Заметим, что в новом плане  суммы элементов по строкам и  столбцам должны остаться прежними, поэтому изменение значения в одной клетке цикла повлечет за собой соответствующие изменения значений во всех остальных клетках этого цикла. Так как в свободной клетке значение будет увеличено, то проставим в ее правом нижнем углу знак    . Теперь пройдем по всей ломаной цикла, проставляя в правых нижних углах клеток поочередно знаки «плюс в кружке» и «минус в кружке».

       Груз  будет перераспределен по клеткам цикла на величину Δx = min x_ij следующим образом. В клетках со знаком «плюс» значение перевозки нужно увеличить на величину Δx, а в клетках со знаком «минус» – уменьшить на величину Δx. Так как после пересчета у нас добавилась лишняя базисная клетка, то их количество необходимо сократить, убрав нуль в одной из клеток цикла. Если таких клеток получилось несколько, то свободной делаем ту из них, в которой тариф перевозок максимален.

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

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

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

        u₁ + v₁ = 4                                                      u₁ = 0

       u₁ + v₂ = 8                                                      u₂ = -8

       u₁ + v₃ = 10                                                    u₃ = -4

       u₂ + v₃ = 2                 =>                                 v₁ = 4

       u₃ + v₃ = 6                                                      v₂ = 8

       u₃ + v₄ = 5                                                      v₃ = 10

       u₁ = 0                                                              v₄ = 9 

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

       Таблица 4