Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Процесс определения потенциалов текущего плана транспортной задачи

Рассмотрим процесс определения потенциалов текущего плана транспортной задачи на примере. В табл. 3.3 переписаны условия задачи из табл. 3.1 и ее допустимый базисный план, построенный методом северо-западного угла (см. табл. 3.2).

Потенциал первого пункта потребления принимаем равным нулю (v1=0). Теперь, зная его, мы можем определить потенциалы для всех пунктов производства, связанных с первым пунктом ненулевыми перевозками. В данном случае их два (это первый и второй пункты), получаем:

Имея u2 и учитывая, что во второй строке таблицы существуют еще ненулевые компоненты х2,2 и х2,3, можно определить v2 = u2 + c2,2 = -10+17=7 и v3 = u2 +c2,3 = -10+15=5, после чего появляется возможность рассчитать u3 = v3c3,3 =5 - 25 = - 20 и, наконец, v4 = u3+ c3,4 = -20 +21=1. В результате получаем полную систему потенциалов, показанную в табл. 3.3.

Для свободных клеток транспортной таблицы вычисляются величины αi,j = vj - ui, называемые разностями потенциалов. В табл. 3.4 они выписаны для всех небазисных клеток под ценами.

Разность потенциалов αi,j можно трактовать как увеличение цены продукта при его перевозке из пункта i в пункт j. Согласно критерию оптимальности (3.8)-(3.9), если все αi,jсi,j, то план оптимален, в противном случае, если существует хотя бы одна разность потенциалов αi,j > сi,j, то он может быть улучшен. Процесс «улучшения» плана состоит в определении вводимой и выводимой клеток, в чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.

Кандидатом на ввод, очевидно, может быть любая клетка, в которой αi,j > сi,j, поскольку после ввода в базис будет обеспечено равенство αi,j = сi,j. Для определенности обычно рекомендуется брать ту клетку, в которой оценка αi,j - сi,j максимальна. В рассматриваемом нами примере это будет клетка (3, 1).

Выводимая клетка определяется с помощью так называемой цепочки преобразования плана, описывающей характер перераспределения грузовых потоков. В соответствии со свойствами транспортной задачи для невырожденного базисного плана в текущей таблице можно образовать замкнутую цепочку, состоящую только их вертикальных и горизонтальных звеньев, одной из вершин которой является выбранная свободная клетка, а остальные — занятые клетки. В табл. 3.5 показана цепочка преобразования текущего плана относительно вводимой в него клетки (3, 1).

Логика алгоритма построения цепочки достаточно проста: «выйдя» из клетки (3,1) в горизонтальном направлении, мы должны «остановиться» в той занятой клетке плана, из которой сможем двигаться дальше по вертикали. В данном примере этому требованию удовлетворяют как клетка (3,3), так и клетка (3,4). Однако цепочка от (3,4) не может быть продолжена дальше, в то время как двигаясь от (3,3) по вертикали к (2,3) и далее к (2,1), мы возвращаемся к исходной клетке (3,1) и образуем замкнутый цикл.

В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются вершины: нечетные — знаком «+», а четные знаком «—». Знаком «+» отмечаются те клетки, в которых объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план, поскольку она должна стать базисной). Знаком «—» — те клетки, в которых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком «—», выбирается клетка с наименьшим значением хi,j (обозначим его θ). Она и становится кандидатом на вывод, т. к. уменьшение объема перевозок на большую величину может привести к отрицательным значениям хi,j в других «минусовых» клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком «+», добавляется объем θ, а из объемов клеток, помеченных знаком «—», он вычитается. В результате ввода одной клетки и вывода другой получается новый базисный план, для которого на следующей итерации описанные выше действия повторяются.

В нашем примере знаком «—» отмечены клетки (2,1) и (3,3), причем x2,1 = 6, x3,3 = 26. Вычислив значение θ = min{x2,1, x3,3} = 6, осуществляем преобразование и переходим к следующему базисному плану, показанному в табл. 3.6.

Для вновь полученного плана повторяются действия стандартной итерации: рассчитываются потенциалы и оценки для небазисных клеток транспортной таблицы. Как можно видеть, план в табл. 3.6 также не является оптимальным (в клетке (1,3) αi,j = 25 > сi,j = 21), поэтому вновь строим цепочку преобразования плана и переходим к следующему базисному плану (табл. 3.7).

Из транспортной таблицы 3.7 видно, что полученный план оптимален, так как все разности потенциалов для небазисных клеток αi,j = vj – ui не превышают соответствующих цен сi,j. По данному плану вычисляется оптимальное (наименьшее) значение суммарных издержек на перевозку

Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке: если одинаковое минимальное значение будет достигнуто сразу на нескольких клетках, помеченных знаком «—», то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем m+n-1 ненулевых компонент. Способ преодоления вырожденности в транспортной задаче весьма прост, а именно: предлагается дополнить текущий план необходимым количеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они позволяли рассчитать полную систему потенциалов, и далее действовать в соответствии с правилами описанного выше алгоритма. Фактически здесь мы имеем дело не с чем иным, как с аналогом метода возмущений для транспортной задачи как частного случая ЗЛП. К такому выводу легко прийти, если положить, что добавляемые фиктивные клетки содержат некоторый малый объем ε.