Беклемишев - Дополнительные главы линейной алгебры (947281), страница 69
Текст из файла (страница 69)
Для приведения задачи к канонической форме введем дополнительные переменные уц, ! = О, ..., и; / = 1, ..., и + 1, такие, что ограничение на пропускные способности запишется в виде равенств хц+у!т=Ат (4) Дополнительные переменные уу неотрицательны. Матрица Я системы ограничений (2), (4) имеет две группы строк: строки первой группы состоят из коэффициентов уравнений (2), а строки второй — из коэффициентов (4). Каждая переменная ху входит с ненулевым коэффициентом в два уравнения первой группы: в одном — в первую сумму, в другом — во вторую. Каждой переменной х!! соответствует уравнение второй группы, куда, кроме нее, входит только переменная уу с теми же значениями индексов.
Таким образом, столбец матрицы Я, который соответствует переменной ху, содержит три ненулевых элемента, именно +1 и — 1 в строках первой группы и +1 в строках второй группы. Столбцы, которые соответствуют переменным уу, содержат одну единицу. По аналогии с предложением 1 мы можем доказать П р е д л о ж е н н е 3. Каждая невырожденная квадратная подматрица матрицы 8 системы ограничений (2), (4) при пол!ои)и перестановки строк и столбцов может быть приведена к треугольному виду.
Как мы видели, достаточно доказать, что каждая невырожденная подматрица имеет столбец с одним ненулевым элементом. Докажем это. Во-первых, если подматрица содержит столбец, соответствующий у!р то доказывать нечего: единственная единица этого. столб!!а 312 гл, Р системы ИВРАВенстВ и линеиное пРОГРАммиРОВАние должна входить в подматрицу. Поэтому мы будем считать, что таких столбцов иет, Если подматрица содержит строки только из второй группы, то в каждом столбце только одна единица. Если же присутствуют строки из обеих групп, то детерминант подматрицы распадается в произведение минора, содержащего все единицы из строк второй группы, и его дополнительного минора, расположенного целиком в первой группе строк.
Так вопрос сводится к исследованию подматриц, целиком лежащих в первой группе строк. К таким подматрицам применяется доказательство от противного, вполне аналогичные проведенному для предложения 1. Конечно, нет смысла вводить в матрицу 8 столбцы, соответствующие заведомо равным нулю переменным. Представление матрицы зависит от выбранного способа задания сети. Нам только нужно отметить, что удаление из матрицы 5 каких бы то ни было столбцов не меняет предложения 3. !1усть матрица 3 содержит столбцы, соответствующие Ф различным парам значений индексов 1, 1.
В число базисных переменных какого бы то ни было базиса для каждой пары 1, 1' обязательно входит или хьч или у», или обе эти переменные, поскольку уравнение хп + уе = 4~, как и всякое уравнение, должно содержать хоть одну базисную переменную. В соответствии с этим пары 1, 1 разделяются на три класса: 6,: обе переменные хц и уп базисные; 6,: переменная хп базисная, уп — нет; 6,: переменная уп базисная. хц — нет. Число пар первого класса легко может быть сосчитано. Если таких пар й, то остальных 1Р' — й, и общее число базисных переменных равно 2Ф+ У вЂ” й. Но число базисных переменных равно числу независимых уравнений, т. е. и + У.
Отсюда следует, что й = п. Рассмотрим подматрнцу, составленную из базисных столбцов, и переставим строки и столбцы так, чтобы столбцы, соответствующие базисным дц, были последними„и строки, содержащие единицы в этих столбцах, также были последними. Это приведет подматрицу к клеточному Виду й:.3 Очевидно, что бе1 Я, чь О и Я, должна содержать столбец, в который входит один ненулевой элемент. Но в иее входят все строки первой группы, и следовательно, этим столбцом может быть только столбец, соответствующий переменной хм или х, „„. Более того, вторая единица из этого столбца в ЯА не вошла, значит, пара О, 1 (или 1, и + 1) относится к парам первого класса 6,.
Сформулируем задачу, двойственную задаче о максимальном потоке. Для задачи максимизации функции при канонической форме ограничений двойственная задача может быть сформулирована % 5. ПРИЛОЖЕНИЯ ЛИНЕИНОГО ПРОГРАММИРОВАНИЯ З1З аналогично задаче (4) 3 4 так: уА.= с, уЬ-~.пп'и. В рассматриваемом случае двойственная задача будет содержать и переменных и„соответствующих ограничениям (2), и У пере. менных пч, соответствующих ограничениям (4). Можно считать, что иА соответствуют узлам сети, а пп — ее дугам. Система ограниче- ний двойственной задачи кмеет вид иА+ поА ~ 1„ — и,+Ос„н)0, — их+ ис+ пы ) 0 си~0.
Здесь и далее индексы принимают следующие значения: 1 = О, ..., п; 1 = 1, ..., п + 1; й, 1 = 1, ..., и, но не в произвольных сочетаниях, так как в систему входят ограничения только для тех пар индек- сов, которые соответствуют входящим в основную задачу 1У пере- менным х;;. Пусть их, о1 — решение двойственной задачи, а ф, у~,— решение исходной. Предположим задачу невырожденной и рас- смотрим базис исходной задачи, соответствующий решению. Будем говорить, что дуга сети и переменная оы относятся к классу 6„ 6, или б„если соответствующая пара индексов 1, 1 относится к этому классу. Для пар индексов класса 6, имеем ху~ О, у)1) О.
Это зна- чит, что дуга занята некоторым потоком, но не загружена до пре- дела пропускной способности. Согласно предложению 3 3 3 и$ и пй удовлетворяют соотношениям: и1=1, если О, йенбн и1=0, если й, п+1 ен6„ их'=и~, если й, 1~6„ Р$=0, если 1, (евбм На и, здесь всего и независимых соотношений по числу пар в 6,. Сопоставим источнику из = 1, а стоку и„'+, — — О. Тогда можно вывести отсюда, что ир —— 1 для всех узлов сети, которые соединены с источником не загруженными до предела дугами, а ит = 0 для тех узлов, которые соединены незагруженными дугами со стоком. При этом каждая переменная и„имеет значение иы равное нулю или единице, Для пар индексов класса 6, имеем хп О, у,*~ — — О.
К этому классу относятся загруженные до предела дуги. Для них имеем Рй)0 Ф=ПА — п1 и$+о,'А=1, если О, йенб„ их — ОА,„1=0, если й, и+1енб„ 314 ГЛ, У. СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕПНОЕ ПРОГРАММИРОВАНИЕ Отсюда следует, что при 1, / еи 6«выполнено и," =! и и« = О. Это означает, что загруженные до предела дуги соединяют узлы, для которых и," = 1, с узлами, для которых и," = О. Для пар индексов класса 0«имеем х,"; = О, у,"~ ) О.
Это свободные от потока дуги, которые могли бы быть исключены из сети без изменения максимального потока. Имеем ф= О, если 1, (ее 6, и«*<и~, если й, 1ее0,. Последнее означает, что свободные дуги соединяют те вершины, для которых и1 — — О, с теми, для которых и« вЂ” — 1. Целевая функция двойственной задачи есть Х йооу. ь ~ Ее минимальное значение в силу сказанного выше равно йцоп А«' дц. (5) А у А нес, В последней сумме суммирование распространяется только на пары из класса б„так как только для них о5 отлично от нуля. Рассмотрим интерпретацию этого результата в терминах сети. Сумма (5) есть сумма пропускных способностей некоторого множе- ства дуг.
Введем следующее О п р е д е л е н и е. Пусть множество узлов сети разбито на два непересекающихся подмножества У, и У„причем источник входит в Фн а сток в У«. Л1ножество всех дуг, начало которых при- надлежит д'„а конец принадлежит д'„называется разрезом сети. Сумму пропускных способностей всех дуг разреза назовем пропуск- ной способностью этого разреза. Основанием для введения термина «разрезь служит следующее свойство. Рассмотрим ориентированный путь от источника к стоку. Это такая последовательность узлов и„и;, ..., и~, и„„, что каждый узел в ней связан дугой со следующим.
Последовательность начи- нается в источнике и„а кончается в стоке и«„н Каков бы ни был разрез сети, каждый путь от источника к стоку обязательно содер- жит одну йз дуг этого разреза. Действительно, будем двигаться вдоль пути, отмечая, к какому из подмножеств д', или У«относятся проходимые узлы. Мы начинаем с узла из б«м а кончить должны узлом из д'«. Поэтому где-то должны перейти из д', в д'«. Если мы отнесем к д', те узлы, для которых и';= 1, а к ӫ— Д''., , для которых и« вЂ” — О, то это разбиение определит разрез, состоя- .,~,ва дуг класса 6«, Сумма (5) есть пропускная способность этого разреза. Ф 5 ПРИЛОЖЕНИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ З1З Назовем разрез минимальным, если его пропускная способность не превосходит пропускную способность любого другого разреза.
Легко видеть, что величина максимального потока в сети не может превосходить пропускной способности минимального разреза. Действительно, прежде чем попасть в сток, максимальный поток должен попасть в множество есгм определяющее минимальный разрез. Теперь теорема двойственности в применении к задаче о максихиальном потоке может быть сформулирована следующим образом. Т е о р е м а 1. Величина максилсального гготока в некоторой сети равна пропускной способноспги минимального разреза этой сети. 3. Дискретное линейное програмкироеание. Ряд практически важных моделей приводит к задачам линейного программирования с тем дополнительным условием„что все (или некоторые) переменные должны принимать только целые значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
