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

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

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

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

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

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

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

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

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

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

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

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