3.1.1. Транспортная задача в матричной постановке и ее свойства. Вернемся к транспортной задаче в матричной, постановке, о которой мы уже упоминали при рассмотрении вопросов построения математических моделей. Напомним, что данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (║ xi,j ║ m x n ), который минимизирует целевую функцию
на множестве допустимых планов
при соблюдении условия баланса
Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения.
Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (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), i ∊1: m, а второй — через vj, j ∊1: n (рис. 3.2). Тогда двойственная задача будет иметь вид:
Переменные ui называют потенциалами пунктов производства, а vj — потенциалами пунктов потребления. Применяя доказанные в главе 1 теоремы двойственности (см. теорему 1.7), можно получить критерий оптимальности для плана транспортной задачи:
F F Для того, чтобы допустимый план транспортной задачи х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).
Потенциал первого пункта потребления принимаем равным нулю (v 1=0). Теперь, зная его, мы можем определить потенциалы для всех пунктов производства, связанных с первым пунктом ненулевыми перевозками. В данном случае их два (это первый и второй пункты), получаем:
Имея u 2 и учитывая, что во второй строке таблицы существуют еще ненулевые компоненты х 2,2 и х 2,3, можно определить v 2 = u 2 + c 2,2 = -10+17=7 и v 3 = u 2 + c 2,3 = -10+15=5, после чего появляется возможность рассчитать u 3 = v 3 – c 3,3 =5 - 25 = - 20 и, наконец, v 4 = u 3+ c 3,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), причем x 2,1 = 6, x 3,3 = 26. Вычислив значение θ = min{ x 2,1, x 3,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. Основные понятия и определения. Многие экономические задачи, такие как перевозка грузов, перекачка нефти и газа по трубопроводам, управление запасами и т. п., удобно моделировать и решать в терминах сетей и потоков. Основой подобного рода моделей служат ориентированные или неориентированные графы. Приведем некоторые определения.
F F Ориентированным графом называется тройка (I, D, G), в которой I — непустое множество вершин, D — множество дуг и G — отображение, которое каждой дуге d∊D ставит в соответствие упорядоченную пару вершин (i, j), где i, j ∊ I.
F F Неориентированным графом называется тройка (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) называется упорядоченная последовательность различных дуг (d 1, d 2,..., 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 -, I 0.
Для определенной выше сети потоком называется такая совокупность величин, заданных на множестве дуг, Х ={ хd } d∊D, что
где Di + — множество дуг, исходящих из вершины i, a Di - — множество дуг, входящих в нее. Величина хd называется значением потока по дуге d и содержательно интерпретируется как количество продукта, пропускаемого по данной дуге.
Соотношение (3.11) означает, что для любой вершины сети разность выходящего и входящего потоков равна ее интенсивности.
На базе введенной терминологии может быть сформулировано много различных задач. Рассмотрим наиболее известные из них. Для каждой дуги d ∊ D определим значения cd ≥ 0, называемые стоимостью перемещения единицы продукта по дуге, тогда суммарная стоимость потока Х примет вид
Задачу минимизации функции (3.13) при ограничениях (3.11)-(3.12) обычно называют линейной сетевой задачей. Очевидно, что она является задачей линейного программирования. Если дополнительно для каждой дуги сети d ∊ D определить величины 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) справедлив критерий оптимальности:
F F Для того, чтобы допустимый поток Х={хd}d∊D (т. е. удовлетворяющий условиям (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}d∊D. Рассмотрим множество дуг D(X) = { d ∊ D | 0 < xd < rd }. Опорой потока Х называется частичный граф (I, D(X), G). Говорят, что поток Х невырожден, если его опора (7, D(X), G) является остовом сети (I, D, G). Иными словами, используя терминологию транспортной задачи, в невырожденном потоке, которому отвечает допустимый базисный план задачи, дороги, по которым осуществляются перевозки груза, не достигающие по объему ограничения на пропускную способность, образуют остов (связанную подсеть без циклов) рассматриваемой транспортной сети.
Теперь дадим краткое описание схемы метода потенциалов для транспортной задачи в сетевой постановке.
1°. Предполагается, что в начале очередной итерации q имеется некоторый допустимый невырожденный поток Х={хd (q) }d∊D (о методах его генерации на начальном этапе будет сказано в дальнейшем).
По имеющемуся потоку Х ( q ) строится система потенциалов пунктов сети. Для этого выбирается произвольный пункт i 0, потенциал которого полагается vi 0 =0. Множество вершин, смежных с i 0, обозначим через I (i 0). Тогда для любой вершины j ∊ I (i 0) потенциалы рассчитываются по правилу
если (i 0, j) ∊ D (X ( q )) (дуга направлена от i 0),и
если (j,i 0) ∊ G (D (X ( q ))) (j,i 0) ∊ D (X ( q )) (дуга направлена к i 0).
Получив очередную группу вершин с известными потенциалами, мы имеем возможность на основе (3.22)-(3.23) вычислить потенциалы для следующей группы смежных вершин и т. д., пока не будут определены все потенциалы. Возможность сделать это единственным образом вытекает из свойства отсутствия циклов у остова сети.
Имея полную систему потенциалов, для всех дуг следует проверить условия критерия оптимальности (3.19)-(3.21). Если они выполняются, то текущий поток Х ( q ) — оптимальный и, следовательно, алгоритм завершен; в противном случае — переходим к построению следующего «улучшенного» потока.
2°. По аналогии с другими методами последовательного улучшения плана очередной поток получается за счет «ввода» в него одной дуги и «вывода» другой. Если условия критерия оптимальности нарушаются сразу для нескольких дуг, то для ввода имеет смысл выбрать ту, на которой достигается максимальное отклонение цены от разности потенциалов соединяемых вершин. Пусть для ввода выбрана некоторая дуга dl = (s, t), направленная из вершины s в вершину t. Из правил построения потенциалов следует, что в остове существуют две цепи, одна из которых соединяет базовую вершину i 0, потенциал которой был принят равным нулю, с s, а другая — i 0 с 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. К множеству вершин сети добавляется фиктивная нулевая вершина с нулевой интенсивностью (b 0= 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=i 0, i 1 ,..., ip- 1, ip=t).
На предварительном (нулевом) этапе алгоритма:
Ø Ø формируется массив значений так называемых модифицированных длин i,j, которые перед началом первой итерации полагаются равными сi,j ≥0;
Ø Ø осуществляется отметка вершины i 0 = s числом mi 0 = 0.
Стандартная итерация включает этапы:
1°. Отметка вершин сети. Обозначим множество вершин cети, отмеченных на предыдущих итерациях, как (на первой итерации ={ i 0}). Для каждой вершины i ∊ ищутся дуги, соединяющие ее с еще не помеченными вершинами-потомками j, модифицированная длина которых i,j = 0. Найденные таким способом вершины j помечаются числом mj = i, указывающим на «родителя». В том случае, когда сразу несколько дуг, имеющих i,j = 0, заканчиваются в одной и той же вершине j, значение для ее пометки выбирается произвольно.
Если среди вновь помеченных вершин окажется вершина t, то, значит, найден искомый путь (i 0, i 1,..., i ( p- 1), ip), где
на чем алгоритм завершается.
В случае, если вершины t нет среди отмеченных, и одновременно нельзя отметить ни одной новой вершины, то переходим к этапу 2.
2°. Преобразование значений модифицированных длин дуг. Для каждой вершины i ∊ ищутся дуги, соединяющие ее с еще не помеченными вершинами j, и находятся
Далее модифицированные длины всех дуг, которые соединяют отмеченные вершины с неотмеченными (i ∊ , j ∉ ), уменьшаются на величину
в результате чего кратчайшие неиспользованные дуги получают нулевую модифицированную длину.
Затем происходит переход к следующей итерации.
Путь, построенный по методу Минти, будет кратчайшим. Это можно доказать с помощью индукции по номеру итерации, на которой была помечена вершина t, или, что то же самое, по количеству дуг, составляющих кратчайший путь. Если это произошло на первом шаге (что возможно только в случае, если начальная и конечная вершины соединены дугой нулевой длины), то доказываемое утверждение очевидно. Предположим,
что оно верно для всех пунктов, помеченных за первые r итераций, т. е. тех, которые достигаются переходом по r дугам. Тогда, если конечная вершина t помечена на (r + 1)-ой итерации, то полученный путь также будет кратчайшим, так как данная вершина помечается в результате минимально возможного продолжения одного из путей, полученного за предыдущие r итераций и являющегося по предположению кратчайшим.
Отметим, что описанный алгоритм пригоден для построения кратчайших путей на неориентированных графах.
Рассмотрим изложенный метод на конкретном примере, а именно: определим кратчайший путь из вершины 1 в вершину 6 для неориентированной сети, показанной на рис. 3.5.
На предварительном этапе вершина 1 отмечается числом m 1 = 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 m 2 = 1 (см. рис. 3.6). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с помеченными вершинами 1 и 2 являются вершины 3,4,5. Из чего определяем ∆ = min{ 1,3, 2,3, 2,4, 2,5}=1 и после соответствующего преобразования имеем
Итерация 3. В вершину 3 ведут дуги нулевой длины как из вершины 1, так и из вершины 2. Поскольку выбор здесь может быть произвольным, пометим вершину 3 числом m 3 = 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 m 4 =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 числом m 5 =3 (рис. 3.9). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежной с ранее отмеченными вершинами является вершина 6. Из чего определяем ∆ = min{ 4,6, 5,6}=2 и после преобразования имеем 4,6 = 3, 5,6 = 0.
Итерация 6. В вершину 6 ведет дуга нулевой длины из вершины 5, поэтому помечаем ее числом m 6=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. Перечислите основные этапы метода Минти.