ГЛАВА 3. ТРАНСПОРТНЫЕ И СЕТЕВЫЕ ЗАДАЧИ : Математические методы исследования операций в экономике - П. Конюховский : Книги по праву, правоведение

ГЛАВА 3. ТРАНСПОРТНЫЕ И СЕТЕВЫЕ ЗАДАЧИ

1 2 3 4 5 6 7 8 9 10 11 12 
РЕКЛАМА
<

 

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

 

3.1. ТРАНСПОРТНАЯ ЗАДАЧА И МЕТОДЫ ЕЕ РЕШЕНИЯ

 

3.1.1. Транспортная задача в матричной постановке и ее свойства. Вернемся к транспортной задаче в матричной, постановке, о которой мы уже упоминали при рассмотрении вопросов построения математических моделей. Напомним, что данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты по­требления (║xi,j║mxn), который минимизирует целевую функцию

 

 

на множестве допустимых планов

 

 

 

при соблюдении условия баланса

 

 

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

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n) х mn. Матрицы систем уравне­ний в ограничениях (3.2) и (3.3) имеют ранги, равные соответ­ственно m и n. Однако, если, с одной стороны, просуммировать уравнения (3.2) по m, а с другой — уравнения (3.3) по n, то в силу (3.5) получим одно и то же значение. Из этого следует, что одно из уравнений в системе (3.2)-(3.3) является линейной комбинацией других. Таким образом, ранг матрицы транспорт­ной задачи равен m+n-1, и ее невырожденный базисный план должен содержать m+n-1 ненулевых компонент.

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

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта аi), а столбцы — пунктам потребления (послед­няя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о пе­ревозке из i-го пункта в j-й: в левом верхнем углу находится

 

 

цена перевозки единицы продукта, а в правом нижнем — значе­ние объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (хi,j = 0), называют сво­бодными, а ненулевые — занятыми (xi,j >0).

3.1.2. Построение исходного допустимого плана в транс­портной задаче. По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом мето­де северо-западного угла. Суть метода состоит в последова­тельном распределении всех запасов, имеющихся в первом, вто­ром и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте про­изводства или к попытке полного, удовлетворения потребно­стей в очередном пункте потребления. На каждом шаге q вели­чины текущих нераспределенных запасов обозначаются аi(q), а текущих неудовлетворенных потребностей — bj(q). Построение допустимого начального плана, согласно методу северо-запад­ного угла, начинается с левого верхнего угла транспортной таб­лицы, при этом полагаем аi(0) = аi, bj(0) = bj. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются зна­чения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: xi,j = min{аi(q), bj(q)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на дан­ную величину:

 

 

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: аi(q+1) = 0 или bj(q+1) = 0 . Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте произ­водства i +1, т. е. переместиться к следующей клетке вниз по столбцу. Если же bj(q+1) = 0, то значит, полностью удовлетворе­на потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все пере­численные операции.

Основываясь на условии баланса запасов и потребностей (3.5), нетрудно доказать, что за конечное число шагов мы полу­чим допустимый план. В силу того же условия число шагов ал­горитма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не ис­ключено, что на некотором промежуточном шаге текущий не­распределенный запас оказывается равным текущей неудовлет­воренной потребности (аi(q) = bj(q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и по­требления), а это означает «потерю» одной ненулевой компо­ненты в плане или, другими словами, вырожденность построен­ного плана.

 

 

Рассмотрим применение метода северо-западного угла на конкретном примере. Транспортная таблица 3.1 содержит ус­ловия некоторой задачи, а в табл. 3.2 показан процесс поиска допустимого плана, включая последовательное изменение объема нераспределенных запасов и неудовлетворенных по­требностей. Стрелки отражают траекторию перехода по клет­кам транспортной таблицы, а цифры, находящиеся за ее преде­лами, — текущие нераспределенные остатки после назначения объема для очередной клетки.

Особенностью допустимого плана,, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимально­го. Это происходит потому, что при его построении никак не учитываются значения сi,j. В связи с этим на практике для по­лучения исходного плана используется другой способ — ме­тод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наи­меньшими ценами.

3.1.3. Критерий оптимальности. Рассмотрим более по­дробно структуру матрицы транспортной задачи. Схематично она показана на рис. 3.2.

Из него видно, что матрица имеет размерность (m+n) х mn, состоит из нулей и единиц и распадается на две группы однотип­ных блоков. Первая (верхняя) соответствует ограничениям на

 

 

объемы вывоза из пунктов производства, а вторая — ограниче­ниям на удовлетворение потребностей в пунктах производства.

Построим двойственную задачу. С учетом специфической структуры матрицы транспортной задачи вектор двойственных переменных будет иметь размерность m+n, причем его компо­ненты, соответствующие первой группе ограничений, обозна­чим через (-ui), i1: m, а второй — через vj , j1:n (рис. 3.2). Тогда двойственная задача будет иметь вид:

 

 

Переменные ui называют потенциалами пунктов производства, а vj — потенциалами пунктов потребления. Применяя доказанные в главе 1 теоремы двойственности (см. теорему 1.7), можно получить критерий оптимальности для плана транспортной задачи:

 

Для того, чтобы допустимый план транспортной зада­чи хi,j был оптимальным, необходимо и достаточно, чтобы нашлись такие потенциалы иi, vj, для которых

 

 

Данные условия имеют содержательную экономическую интерпретацию. Потенциалы ui, и vj можно рассматривать как цены на перевозимый груз в пунктах производства и потребле­ния (это, кстати, объясняет то, зачем понадобилось обозначать соответствующую двойственную переменную через (-ui)). Тогда, согласно условию (3.8), для оптимальности плана пере­возок требуется, чтобы на тех маршрутах, по которым действи­тельно перевозится груз, его цена в пункте потребления воз­растала ровно на цену его перевозки, а в соответствии с условием (3.9) в оптимальном плане цена груза в пункте потреб­ления не может быть меньше его цены в пункте производства с учетом затрат на транспортировку.

3.1.4. Алгоритм метода потенциалов для транспорт­ной задачи. Критерий (3.8)-(3.9) положен в основу одного из методов решений транспортной задачи, получившего название метода потенциалов. Впервые он был предложен в 1949г. Л. В. Канторовичем и М. К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом.

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

Алгоритм начинается с выбора некоторого допустимого ба­зисного плана (методы его построения были рассмотрены в п. 3.1.2). Если данный план не вырожденный, то он содержит m + n -1 ненулевых базисных клеток, и по нему можно так оп­ределить потенциалы ui и vj, чтобы для каждой базисной клет­ки (т. е. для той, в которой хi,j > 0) выполнялось условие

 

 

Поскольку система (3.10) содержит m+n-1 уравнение и m+n неизвестных, то один из потенциалов можно задать произволь­но (например, приравнять vj или ui к нулю). После этого ос­тальные неизвестные ui и vj определяются однозначно.

Рассмотрим процесс определения потенциалов текущего плана транспортной задачи на примере. В табл. 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 = v3 – c3,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 ненулевых компонент. Способ преодоления вы­рожденности в транспортной задаче весьма прост, а именно: предлагается дополнить текущий план необходимым коли­чеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они позволяли рассчитать полную систему по­тенциалов, и далее действовать в соответствии с правилами опи­санного выше алгоритма. Фактически здесь мы имеем дело не с чем иным, как с аналогом метода возмущений для транспортной задачи как частного случая ЗЛП. К такому выводу легко прий­ти, если положить, что добавляемые фиктивные клетки содер­жат некоторый малый объем ε.

 

3.2. СЕТЕВЫЕ ЗАДАЧИ

 

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

 

Ориентированным графом  называется тройка (I, D, G), в которой I — непустое множество вершин, D — множество дуг и G — отображение, которое каж­дой дуге dD ставит в соответствие упорядоченную пару вершин (i, j), где i, j  I.

 

Неориентированным графом называется тройка (I, D, G), в которой I — непустое множество вершин, D — множество ребер и G — отображение, которое каж­дому ребру dD ставит в соответствие неупорядочен­ную пару вершин [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}dD, что

 

 

где Di+ — множество дуг, исходящих из вершины i, a Di- — мно­жество дуг, входящих в нее. Величина хd называется значени­ем потока по дуге d и содержательно интерпретируется как количество продукта, пропускаемого по данной дуге.

Соотношение (3.11) означает, что для любой вершины сети разность выходящего и входящего потоков равна ее интенсив­ности.

На базе введенной терминологии может быть сформулирова­но много различных задач. Рассмотрим наиболее известные из них. Для каждой дуги dD определим значения cd ≥ 0, называ­емые стоимостью перемещения единицы продукта по дуге, тогда суммарная стоимость потока Х примет вид

 

 

Задачу минимизации функции (3.13) при ограничениях (3.11)-(3.12) обычно называют линейной сетевой задачей. Очевидно, что она является задачей линейного программирова­ния. Если дополнительно для каждой дуги сети dD опреде­лить величины rd ≥ 0, называемые пропускными способно­стями, то, добавив ограничения

 

 

мы получаем задачу о потоке в сети с ограниченными пропуск­ными способностями.

Приведенные формулировки задач специально даны в столь абстрактном виде, что позволяет подчеркнуть их универсаль­ность. К очевидной сфере их приложения относится организа­ция грузоперевозок в транспортной сети. В таких моделях вершины i трактуются как пункты, соединенные сетью дорог, и характеризуются потребностями в некотором продукте (bi<0) или его запасами (bi>0). Задачи определения плана, минимизирующего затраты на перевозки, которые с матема­тической точки зрения полностью идентичны (3.11)-(3.13), (3.14), также называют транспортными задачами в сете­вой постановке.

3.2.2. Метод потенциалов для транспортной задачи в сетевой постановке. Рассмотрим задачу определения опти­мального потока Х в некоторой сети (I, D, G), для которого

 

 

при ограничениях

 

 

где rd ≥ 0. Предполагается также, что сеть является сбаланси­рованной, т. е.

 

 

Для задачи (3.15)-(3.17) справедлив критерий оптималь­ности:

 

Для того, чтобы допустимый поток Х={хd}dD (т. е. удовлетворяющий условиям (3.16)-(3.17)) был опти­мальным, необходимо и достаточно существование для каждой вершины i I такого числа vi, называемого по­тенциалом, что для всех дуг d = (i, j)

 

 

Заметим, что логика обоснования данного критерия абсо­лютно идентична той, которая использовалась для обоснова­ния критерия оптимальности плана транспортной задачи в мат­ричной постановке: построение двойственной задачи и приме­нение соответствующей теоремы двойственности.

Для решения транспортной задачи в сетевой постановке (3.15)-(3.17) также может быть применен метод потенциа­лов, который является обобщением описанного выше мето­да потенциалов для транспортной задачи в матричной поста­новке.

Поскольку задача (3.15)-(3.17) является частным случаем задачи линейного программирования, ее можно привести к ка­нонической форме. При этом достаточно просто устанавлива­ется, что ранг матрицы задачи равен m-1, где m — количество вершин в сети. Введем дополнительно еще некоторые понятия, используемые при описании свойств сетевых задач.

Остовом сети (I, D, G) называется любое ее частичное дере­во (частичный граф, являющийся деревом). Справедливо утвер­ждение:

 

F Произвольному остову сети (I, D, G) соответствует ба­зис задачи (3.15)-(3.17) и наоборот.

 

Пусть имеется некоторый поток Х={хd}dD. Рассмотрим множество дуг D(X) = {d D | 0 < xd < rd}. Опорой потока Х назы­вается частичный граф (I, D(X), G). Говорят, что поток Х не­вырожден, если его опора (7, D(X), G) является остовом сети (I, D, G). Иными словами, используя терминологию транспорт­ной задачи, в невырожденном потоке, которому отвечает допу­стимый базисный план задачи, дороги, по которым осуществля­ются перевозки груза, не достигающие по объему ограничения на пропускную способность, образуют остов (связанную под­сеть без циклов) рассматриваемой транспортной сети.

Теперь дадим краткое описание схемы метода потенциалов для транспортной задачи в сетевой постановке.

1°. Предполагается, что в начале очередной итерации q имеется некоторый допустимый невырожденный поток Х={хd(q)}dD (о методах его генерации на начальном этапе бу­дет сказано в дальнейшем).

По имеющемуся потоку Х(q) строится система потенциалов пунктов сети. Для этого выбирается произвольный пункт i0, потенциал которого полагается vi0 =0. Множество вершин, смежных с i0, обозначим через I(i0). Тогда для любой вершины j I(i0) потенциалы рассчитываются по правилу

 

 

если (i0,j) D(X(q)) (дуга направлена от i0),и

 

 

если (j,i0) G(D(X(q))) (j,i0) D(X(q)) (дуга направлена к i0).

Получив очередную группу вершин с известными потенциа­лами, мы имеем возможность на основе (3.22)-(3.23) вычис­лить потенциалы для следующей группы смежных вершин и т. д., пока не будут определены все потенциалы. Возможность сде­лать это единственным образом вытекает из свойства отсут­ствия циклов у остова сети.

Имея полную систему потенциалов, для всех дуг следует про­верить условия критерия оптимальности (3.19)-(3.21). Если они выполняются, то текущий поток Х(q) — оптимальный и, следовательно, алгоритм завершен; в противном случае — пе­реходим к построению следующего «улучшенного» потока.

2°. По аналогии с другими методами последовательного улуч­шения плана очередной поток получается за счет «ввода» в него одной дуги и «вывода» другой. Если условия критерия опти­мальности нарушаются сразу для нескольких дуг, то для ввода имеет смысл выбрать ту, на которой достигается максимальное отклонение цены от разности потенциалов соединяемых вер­шин. Пусть для ввода выбрана некоторая дуга dl = (s, t), направ­ленная из вершины s в вершину t. Из правил построения по­тенциалов следует, что в остове существуют две цепи, одна из которых соединяет базовую вершину i0, потенциал которой был принят равным нулю, с s, а другая — i0 с t. Если дополнить остов дугой dl, образуется единственный цикл. Построенный цикл является аналогом цепочки преобразования плана в мето­де потенциалов для транспортной задачи в матричной постанов­ке. Обозначим через D+(s,t) множество дуг данного цикла, ориен­тация которых совпадает с ориентацией дуги dl = (s, t), а через D-(s,t) — множество дуг, имеющих противоположную ориента­цию. Определим величину возможной корректировки объемов грузоперевозок, «перемещаемых» по циклу

 

 

Идея формулы (3.24) достаточно прозрачна: при циклическом преобразовании текущего потока увеличиваются объемы гру­зоперевозок на тех дугах, которые сонаправлены вводимой дуге, и уменьшаются на дугах, имеющих обратную ориентацию. Соответственно, при добавлении мы должны следить за тем, чтобы не превысить ограничения на пропускные способности (θ ≤ rd – хd(q)), а при вычитании — за неотрицательностью хd(q). После определения θ происходит пересчет компонент текуще­го потока по формуле

 

 

В результате мы получаем новый допустимый поток хd(q+1)), полагаем номер текущей итерации q+1 и переходим к п. 1°.

В описанном алгоритме, как и в случае с матричной транс­портной задачей, мы не гарантированы от возникновения вы­рожденного потока. Как уже упоминалось выше, такому пото­ку будет соответствовать несвязная опора. Для преодоления вырожденности рекомендуется включить в текущий план фик­тивные компоненты с нулевыми объемами так, чтобы соответ­ствующие им дуги дополняли опору до остова сети. Построен­ный таким способом план позволяет выполнить все действия, входящие в стандартную итерацию метода потенциалов.

Отдельно следует остановиться на методах генерации исход­ного допустимого потока. Наиболее простой из них (хотя, воз­можно, и наименее рациональный) основан на идеях, сходных с идеями метода минимизации невязок, используемого для по­строения допустимого базисного плана ЗЛП. Данный метод предполагает решение соответствующей вспомогательной за­дачи, которая получается из основной в результате следующих преобразований:

1. К множеству вершин сети добавляется фиктивная нулевая  вершина с нулевой интенсивностью (b0= 0).

2. Все вершины, имеющие отрицательную интенсивность (спрос) bi < 0, соединяются с добавленной вершиной 0 входя­щими дугами (0, i), а вершины, обладающие положительной интенсивностью (запасом) bi > 0, — исходящими дугами (i, 0). Ограничения на пропускные способности для добавляемых дуг отсутствуют.

3. Стоимости перемещения единицы продукта для вновь до­бавленных дуг полагаются равными 1, а для дуг, соответствую­щих транспортной сети основной задачи, — 0.

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

3.2.3. Задача о кратчайшем пути. Классическим приме­ром сетевых задач является определение кратчайшего пути между вершинами сети. Пусть задан граф (I, D, G), каждой дуге которого поставлено в соответствие число cd, называемое дли­ной. Также пусть выделены две вершины графа s и t, и требует­ся найти путь наименьшей длины, ведущий из вершины s в вер­шину t.

Если в графе имеются «кратные» дуги, соединяющие одина­ковые начало и конец, то достаточно оставить одну — с наи­меньшей длиной, а остальные отбросить. Таким образом, доста­точно рассматривать задачу о кратчайшем пути для простого графа (I, D), в котором дуги определяются упорядоченными па­рами вершин d = (i, j). Тогда естественно путь L, идущий из вер­шины s в вершину t, задавать в виде упорядоченного набора вер­шин, через которые проходит данный путь:

 

 

а длины дуг обозначать как cd  = ci,j.

Длина описанного выше произвольного пути L определяет­ся по формуле

 

 

Легко заметить, что задача о кратчайшем пути является част­ным случаем транспортной задачи в сетевой постановке (или, что то же самое, задачи об оптимальном потоке). Для этого до­статочно присвоить вершине s единичный запас, вершине t еди­ничную потребность, все остальные вершины положить нейт­ральными, а дугам присвоить неограниченные пропускные способности. Однако, как правило, более рациональным оказывается использование конкретных свойств данной задачи и ре­шение ее специальными (частными) методами. К их числу отно­сится, например, метод Минти, основные идеи которого мы изложим ниже.

Метод Минти решения задачи о кратчайшем пути в сети представляет собой итеративный процесс, в ходе которого строится путь L=(s=i0, i1, ..., ip-1, ip=t).

На предварительном (нулевом) этапе алгоритма:

 

формируется массив значений так называемых модифициро­ванных длин i,j, которые перед началом первой итерации полагаются равными сi,j ≥0;

 

осуществляется отметка вершины i0 = s числом mi0 = 0.

 

Стандартная итерация включает этапы:

1°. Отметка вершин сети. Обозначим множество вершин cети, отмеченных на предыдущих итерациях, как  (на первой итерации  ={i0}). Для каждой вершины i ищутся дуги, со­единяющие ее с еще не помеченными вершинами-потомками j, модифицированная длина которых i,j = 0. Найденные таким способом вершины j помечаются числом mj = i, указывающим на «родителя». В том случае, когда сразу несколько дуг, имею­щих i,j  = 0, заканчиваются в одной и той же вершине j, значе­ние для ее пометки выбирается произвольно.

Если среди вновь помеченных вершин окажется вершина t, то, значит, найден искомый путь (i0, i1,..., i(p-1), ip), где

 

 

на чем алгоритм завершается.

В случае, если вершины t нет среди отмеченных, и одновре­менно нельзя отметить ни одной новой вершины, то переходим к этапу 2.

2°. Преобразование значений модифицированных длин дуг. Для каждой вершины i ищутся дуги, соединяющие ее с еще не помеченными вершинами j, и находятся

 

 

Далее модифицированные длины всех дуг, которые соединя­ют отмеченные вершины с неотмеченными (i, j), умень­шаются на величину

 

 

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

Затем происходит переход к следующей итерации.

Путь, построенный по методу Минти, будет кратчайшим. Это можно доказать с помощью индукции по номеру итерации, на которой была помечена вершина t, или, что то же самое, по ко­личеству дуг, составляющих кратчайший путь. Если это про­изошло на первом шаге (что возможно только в случае, если начальная и конечная вершины соединены дугой нулевой дли­ны), то доказываемое утверждение очевидно. Предположим,

 

что оно верно для всех пунктов, помеченных за первые r итера­ций, т. е. тех, которые достигаются переходом по r дугам. Тогда, если конечная вершина t помечена на (r + 1)-ой итерации, то полученный путь также будет кратчайшим, так как данная вер­шина помечается в результате минимально возможного продол­жения одного из путей, полученного за предыдущие r итераций и являющегося по предположению кратчайшим.

Отметим, что описанный алгоритм пригоден для построе­ния кратчайших путей на неориентированных графах.

Рассмотрим изложенный метод на конкретном примере, а именно: определим кратчайший путь из вершины 1 в вершину 6 для неориентированной сети, показанной на рис. 3.5.

На предварительном этапе вершина 1 отмечается числом m1 = 0, а модифицированные длины совпадают с заданными дли­нами дуг.

Итерация 1. Так как из вершины 1 не выходят дуги нулевой длины, дальнейшая отметка вершин невозможна. Переходим к этапу 2. Смежными с вершиной 1 являются вершины 2 и 3. Для них определяем ∆ = min{1,2, 1,3}=2 и вычитаем ее из 1,2, 1,3. После преобразования имеем 1,2 = 0, 1,3 = 1.

Итерация 2. Помечаем вершину 2 m2 = 1 (см. рис. 3.6). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с помеченными вершинами 1 и 2 являются верши­ны 3,4,5. Из чего определяем ∆ = min{1,3, 2,3, 2,4, 2,5}=1 и после соответствующего преобразования имеем

 

 

 

Итерация 3. В вершину 3 ведут дуги нулевой длины как из вершины 1, так и из вершины 2. Поскольку выбор здесь может быть произвольным, пометим вершину 3 числом m3 = 1 (рис. 3.7). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее отмеченными вершинами являются вершины 4,5. Из чего определяем ∆ = min{2,4, 2,5, 3,4, 3,5}=1 и после пре­образования имеем 2,4 = 8, 2,5 = 0, 3,4 = 3, 3,5 = 5.

Итерация 4. Помечаем вершину 4 m4 =2 (см. рис. 3.8). Даль­нейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее помеченными вершинами являются верши­ны 5,6. Из чего определяем ∆ = min{2,5, 3,5, 4,5, 4,6}=3 и после преобразования имеем 2,5 = 5, 3,5 = 0, 4,5 = 0, 4,6 = 5.

 

 

Итерация 5. В вершину 5 ведут дуги нулевой длины как из вершины 3, так и из вершины 4. Руководствуясь теми же сообра­жениями, что и на итерации 3, пометим вершину 5 числом m5 =3 (рис. 3.9). Дальнейшая пометка невозможна, поэтому перехо­дим к этапу 2. Смежной с ранее отмеченными вершинами являет­ся вершина 6. Из чего определяем ∆ = min{4,6, 5,6}=2 и после преобразования имеем 4,6 = 3, 5,6 = 0.

Итерация 6. В вершину 6 ведет дуга нулевой длины из вер­шины 5, поэтому помечаем ее числом m6=5 (см. рис. 3.10). По­скольку мы отметили конечную вершину маршрута, то алго­ритм завершен и мы можем, используя значения отметок для родителей, выписать искомый кратчайший путь (1, 3, 5, 6).

 

 

Следует также добавить, что если бы наш выбор на итераци­ях 3 и 5 был иным, то мы получили бы альтернативный путь той же длины (1, 2, 4, 5, 6), т. е. рассмотренная задача имеет не­сколько решений.

 

КЛЮЧЕВЫЕ ПОНЯТИЯ

 

Транспортная таблица

Метод северо-западного угла.

Потенциал.

Цепочка преобразования плана.

Граф (ориентированный и неориентированный).

Ребра и вершины.

Путь и контур.

Цепь и цикл.

Связность.

Дерево.

Частичный граф.

Транспортная сеть.

Поток.

Линейная сетевая задача.

Остов сети.

Опора потока.

Невырожденный поток.

Задача о кратчайшем пути.

Алгоритм Минти.

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

 

3.1. Какие специфические свойства позволяют выделить транспортные задачи в отдельный класс из

       множества за­дач линейного программирования?

3.2. Опишите метод построения допустимого плана транспор­тной задачи.

3.3. Сколько ненулевых элементов должен содержать невы­рожденный базисный план транспортной

       задачи?

3.4. Сформулируйте критерий оптимальности для допустимо­го плана транспортной задачи.

3.5. Что положено в основу метода потенциалов?

3.6. Из чего вытекает критерий оптимальности допустимого плана транспортной задачи?

3.7. Перечислите основные этапы метода потенциалов.

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

       потенциалов?

3.9. Что следует делать при возникновении ситуации вырож­денности текущего плана в транспортной

        задаче?

3.10. Приведите формулировку линейной сетевой задачи.

3.11. Покажите, что транспортная задача в матричной поста­новке является частным случаем

         транспортной задачи в сетевой постановке.

3.12. Дайте определение понятия «остов сети». Какая связь су­ществует между остовом сети и

         базисом транспортной за­дачи в сетевой постановке?

3.13. Какой поток называют невырожденным?

3.14. Перечислите основные этапы метода потенциалов для транспортной задачи в сетевой

         постановке.

3.15. Каким способом можно получить допустимый поток в транспортной сети?

3.16. В чем состоит задача о кратчайшем пути?

3.17. Перечислите основные этапы метода Минти.