Математические методы в экономике
Главная | Вырожденные планы. Циклы и пополнение плана | Регистрация | Вход
 
Пятница, 24.11.2017, 23:08
Приветствую Вас Гость
Главное меню
Статистика
Форма входа

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

Прежде, чем перейти к анализу оптимальности планов и способам их улучшения, выясним, каким требованиям должны удовлетворять составляемые планы. В соответствии с определением плана перевозок у матрицы X = {xij} сумма элементов i-й строки равняется ai, i = 1,2,...,m, а сумма элементов j-о столбца равняется bj, 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). Поэтому можно заполнить эту клетку, положив x24 = 0.


Copyright MyCorp © 2017Бесплатный конструктор сайтов - uCoz