Математические методы исследования операций в экономике (стр. 22 из 37)
Кандидатом на ввод, очевидно, может быть любая клетка, в которой α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 ненулевых компонент. Способ преодоления вырожденности в транспортной задаче весьма прост, а именно:предлагается дополнить текущий план необходимым количеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они позволяли рассчитать полную систему потенциалов, и далее действовать в соответствии с правилами описанного выше алгоритма. Фактически здесь мы имеем дело не с чем иным, как с аналогом метода возмущений для транспортной задачи как частного случая ЗЛП. К такому выводу легко прийти, если положить, что добавляемые фиктивные клетки содержат некоторый малый объем ε.
3.2.1. Основные понятия и определения. Многие экономические задачи, такие как перевозка грузов, перекачка нефти и газа по трубопроводам, управление запасами и т. п., удобно моделировать и решать в терминах сетей и потоков. Основой подобного рода моделей служат ориентированные или неориентированные графы. Приведем некоторые определения.
-Ориентированным графомназывается тройка (I, D, G), в которой I — непустое множество вершин,D — множестводуги G — отображение, которое каждой дуге d∊D ставит в соответствие упорядоченную пару вершин (i, j), где i, j ∊ I.
-Неориентированным графомназывается тройка (I, D, G), в которой I — непустое множествовершин, D — множестворебери G — отображение, которое каждому ребру d∊D ставит в соответствие неупорядоченную пару вершин [i, j], где i, j∊ I.
Граф (I, D, G) называется конечным, если множестваI и D конечны.
Геометрически граф может быть представлен в виде множества точек (изображающих вершины) и соединяющих их линий (со стрелками), соответствующих ребрам (дугам) (рис. 3.3, 3.4). Очевидно, что с каждым ориентированным графом можно однозначно связать неориентированный, заменив дуги на ребра. Если любые две вершины графа соединяются не более чем одной дугой (ребром), то граф называется простым и может быть задан с помощью пары (I, D). В этом случае каждая дуга (ребро)d полностью определяется парой соединяемых вершин (i, j), что условно записывается в виде:d=(i,j). Упорядоченная пара вершин (i, j), которая ставится в соответствие некоторой дуге d, задает ее ориентацию: i называется началом дуги, аj — ее концом, а сама дуга считается инцидентной данным вершинам.
Путем длины п в ориентированном графе (I,D) называется упорядоченная последовательность различных дуг (d1, d2,..., dn), для которых начало каждой последующей совпадает с концом предыдущей. Конечный путь, у которого начальная вершина совпадает с конечной, называется контуром.
Для неориентированного графа аналогом понятия путь является цепь, а контура — цикл.
Если две любые вершины неориентированного графа могут быть соединены цепью, то он называется связным. Ориентированный граф называется связным, если ему отвечает связный неориентированный граф.
Связный неориентированный граф, не содержащий циклов,называется деревом.
Если Y⊂D, а отображениеGY является сужением отображенияG на множество Y, то граф (I, Y, GY) называют частичным графом (реберным подграфом) графа (I, D, G).
Рассмотрим задачу: имеется конечный граф (I, D, G), каждой вершине i которого сопоставлено некоторое число bi, называемое интенсивностью вершины. Граф (I, D, G), вершинам которого сопоставлены значения интенсивностей bi, будем называть сетью. Если bi > 0, то вершина i называется источником, если bi < 0, то — стоком, а если bi = 0, то — нейтральной вершиной. Множество источников, стоков и нейтральных вершин обозначим соответственноI+, I-,I0.
Для определенной выше сети потоком называется такая совокупность величин, заданных на множестве дуг, Х={хd}d∊D,что
где Di+ — множество дуг, исходящих из вершины i, a Di- — множество дуг, входящих в нее. Величина хd называется значением потока по дуге d и содержательно интерпретируется как количество продукта, пропускаемого по данной дуге.
Соотношение (3.11) означает, что для любой вершины сети разность выходящего и входящего потоков равна ее интенсивности.
На базе введенной терминологии может быть сформулировано много различных задач. Рассмотрим наиболее известные из них. Для каждой дуги d∊D определим значения cd ≥ 0, называемые стоимостью перемещения единицы продукта по дуге, тогда суммарная стоимость потока Х примет вид