Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (Методы анализа сетей. Филлипс. Гарсиа-Диас (1981).djvu), страница 10

Случай 2. Задача о назначениях. В случае когда поток по каждой дуге не ограничен сверху (т. е. У~»=со для й »енй) и, кроме того, а;= 1 для (е=й( и Ьс 1 для (~й(з, то возникает задача о назначениях: Глава л обходи~мое условие существования допустимого решения заключается в том, что число источников должно быть не меньше числа стоков. Случай 3. Задача о максимальном потоке.

Рассмотрим случай, когда имеется только один источник (1= 1) и один сток (1'=и), предложение не ограничено (а1 =со), а спрос нулевой (Ь =0). Если пропускная способность каждой дуги ограничена, а стоимость единицы потока по дуге равна с; — 1 для /Фп и нулю в противном случае, то задача, рассмотренная в случае 1, переходит в задачу максимизации суммарной величины потока, втекающего в сток п/ максимизировать ~ /,.„ (2.34) 1~и минимизировать ~~) ~ с1//1/ с / при условии, что Х/11< 1 /вн ~~~~ ~;„~» 1, /вн '«~~/1/ '~~ //1=0, 1Ф1, /Мп, / / /1/ > О, (/,!) чА. (2.38) (2.39) (2.40) (2.41) при условии, что ~~~ ~1/ — и~~~/1= 0, /-ь 1, ! ~ и, (2.35) в 0< /1/< Уп. (1',/) сА.

(2.36) Случай 4. Задача о кратчайшей цепи. Предположим, что параметр дуги сп соответствует стоимости единицы потока по дуге (ь /) или времени, необходимому для передачи единицы потока от узла / к узлу /. Как отмечалось в равд. 2.!.1, в данном случае возникает задача определения минимальной стоимости (времени) передачи единицы потока от источника к заданному стоку. Пусть а 1, р=!, Ь(„=(1) и Мз=(п). Предположим далее, что а1=1 и Ь„=1. Поскольку предложение составляет одну единицу, а ограничения на поток по дуге записываются в виде 0<)и<1, то оии никогда не нарушаются и поэтому могут вообще не рассматриваться. Наконец, предположим, что сеть не содержит контуров отрицательного веса. Если все дуги сети ориентированные, то задача состоит в нахождении кратчайшей цепи из узла 1 (источника) в узел п (стока). Математически это может быть записано следующим образом: (2.37) Детерминированиие потеки е сетях Следует отметить, что неравенства (2.38), (2.39) при подстановке в них значений 1и, образующих оптимальное решение, переходят в равенства.

Как было показано выше, постановка широкого круга важных потоковых задач может быть записана в виде (2.21)— (2.25). Алгоритмы, решения этих н некоторых других задач будут описаны. ниже в данной главе. Сейчас наша цель заключается в том, чтобы показать, что если величины аь Ь; и Уи— целые, то любое базисное допустимое решение общей задачи (2.21) — (2.25) является целочисленным. Для доказательства этого факта введем два важных определения. Определение 1. Квадратная целочисленная матрица, определитель которого равен О, +1 нли — 1, называется унимодулярнои Определение 2. Целочисленная матрица называется абсолютно унимодулярной, если все ее квадратные подматрицы унимодулярные.

Следующая система линейных неравенств (2.42) и (2.43) определяет область допустимых значений элементов неотрицательного вектора Г (будем предполагать, что матрица Р и вектор В являются целочисленными): РГ< В, Г>0. (2.42), (2.43) Данные определения используются в следующих двух теоремах. Теорема 1. Если матрица Р абсолютно унимодулярная, то любое базисное решение системы РГ= В, Г)0 является целочисленным.

Теорема 2. Рассмотрим произвольную целочисленную матрицу Р. Следующие два условия являются эквивалентными: А. Матрица Р является абсолютно унимодулярной. Б. Все базисные решения задачи линейного программирования сограничениями РГ(В, Г)0 являются целочисленными. Эти теоремы занимают центральное место в наших исследованиях, поскольку из них следует что если в задаче ЛП ограничения записываются в форме РГ(В, Г)0, где Р— абсолютно унимодулярная матрица, а  — целочисленный вектор, то любое базисное решение (угловая точка) этой задачи является целочисленным.

Особый интерес представляет оптимальное решение, которое также должно быть целочисленным. Мы покажем, что если величины аь Ь| и Уи — целые, то оптимальное решение потоковой задачи (2.21) — (2.25) является целочисленным. Для простоты изложения рассмотрим сеть с одним источником (а=1, в(и=(1)), одним стоком (р=1, о(=(6))' и шестью промежуточными узлами (~р=б, Ь(т=(2, 3, 4, 5, 7, 8)). 4' 52 Глаза 2 Графическое изображение данной сети дается на рис. 2.!О. Задача (2.21) — (2.25) в рассматриваемом случае может быть сформулирована следующим образом: минимизировать~ ~ см1м ь / прн условии, что 1ы+1ы+1ье ео иь 1вз+1гь+1г.— 1вз = О 1вз+ 1вь+1м 1ьв = Оэ 183+ 1вь+1вт 11в 1зе 1гз 1вз 1вз = О 1ье — 1ъ — 1вь — 1вь = (' 1гв 1гз 1м 1вз — О1 1вв+1ье+1зе ~ ~('е О < 1» < Ум, (ь', 1) еА. Для того чтобы доказать, что любое допустимое базисное .решение данной задачи является целочисленным, достаточно по- Рис.

2ЛО. Поток в сети. казать, что матрица коэффициентов в общей задаче является абсолютно унимодулярной. Матрица ограничений может быть представлена в виде 0 = [Е/Цв (2.44) где матрица Х состоит из коэффициентов при 1п в равенствах, выражающих сохранение потока, и в неравенствах, соответствующих ограничениям на предложение и спрос, а в— единичная матрица, образованная из коэффициентов прн 1п в неравенствах, соответствующих ограничениям на потоки в дугах. Наша цель состоит в том, чтобы доказать, что матрица Р является абсолютно унимодулярной. Детерминированные яотохи в сетях Подматрицы Х и 1 матрицы Р, определенной равенством (2.44), имеют следующий вид: Лб Лт Лее о о о о о о о о о — о о о Уве Лет о о о о о о 1 1 о о о о о о Ле Ле о о о о о о о о о о о о — ! — 1 Ле Ля Ле 1 1 1 о о о-! о о о — ! о о о о о о о о о о о о ЛЗ Л5 Лт о о о 1 1 1 о о о о о о — о о о — ! о о о о о о Ле Ле о о о о 1 1 о о — о о -! о о о о о о о о о о ! -1 о о о о о о о о о о о о о о о ! о о о о о о о о о о о о о о о ! о о о о о о о о о о о о о о о ! о о о о о о о о о о о о о о о ! о о о о о о о о о о о о о о о ! о о о о о о о о о о о о о о о ! о о о о о о о о — о о о о о о о ! о о о о о о о ° о о о о о о о о ! о о о о о о о о о о о о о о о ! о о о о о о о о о о о о о о о ! о о о о о о о о о о о о о о о ! о о о О О О О О О О О О О О О 1 О О о о о о о о о о о о о о о ! о о о о о о о о о о о о о о о Отметим, что матрица Е совпадает с матрицей инциденций узлы-дуги (см.

гл. 1). Для того чтобы показать, что матрица Р является абсолютно унимодулярной, воспользуемся следующими теоремами. Теорема 3 [281. Целочисленная матрица М является абсолютно унимодулярной, если выполнены следующие условия: а) каждый элемент матрицы равен О, +1 или — 1; б) каждый столбец матрицы содержит не более двух ненулевых элементов; в) строки матрицы М можно разбить на два непересекающихся множества Е! н Ет таким образом, что 1. Если некоторый столбец содержит два ненулевых элемента одного знака, то один нз них входит в Еь а другой— в Ег 2.

Если некоторый столбец содержит два ненулевых элемента с противоположными знаками, то оба онн входят либо в Е1, либо в Еь Теорема 4 [191. Если М вЂ” абсолютно унимодулярная матрица, а 1 — единичная матрица, то матрица Р= [М ~ Ц, составленная из М и 1, также является абсолютно унимодулярной. 54 Глава 2 Утверждение. Матрица, транспонированная по отношению к абсолютно унимодулярной матрице, также является абсолютно унимодулярной. Из соотношений (2.21) — (2.25) или соответствующих соотношеняй рассматриваемого примера видно, что каждый столбец матрицы Х содержит только два ненулевых элемента: +! и — 1. Таким образом, условия (а) и (б) теоремы 3 выполнены.

Условие (в) выполняется, когда Е1 содержит все строки матрицы Е, а Ет — пустое множество. Следовательно, матрица Х является абсолютно унимодулярной. Согласно теореме 4'>, матрица 1Х/11 также является абсолютно унимодулярной. Тогда из теорем 1 и 2 следует существование целочисленного оптимального решения. Сформулированные выше математические утверждения несколько заслонили собой основной результат, полученный нами в данном разделе.

Он заключается в том, что если задача ЛП может быть сформулирована в виде (2.21) — (2,25), а элементы матрицы ограничений удовлетворяют условиям абсолЮтной унимодулярности, то оптимальное решение исходной задачи является целочисленным. На практике задачи ЛП редко решаются обычным симплексным методом. Значительно чаще используются модифицированный симплексный метод илн эффективные специальные потоковые алгоритмы решения сетевой задачи, эквивалентной исходной задаче ЛП. Это говорит о том, что большое число задач ЛП может решаться как потоковые задачи. В тех случаях, когда это удается сделать, как правило, становятся очевидными простота сетевых методов и эффективность соответствующих алгоритмов.