Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 27
Текст из файла (страница 27)
Вели теперь нужно перевезти заданное количество товара нз источйика в сток с минимальными затратами, то, возможно„ не удастся весь поток пропустить по единственной цепи. Но число ненулевых базисных переменных всегда 'будет меньше чем и— — 1 + т. Это значит, что задача останется вырожденной.
8.5. Свойство абсолютной унимодулярностя (Гофман, Краскал [103[, Вейнотт, Данциг,[199)) Выше было показано, что всякая задача о потоке в сети может быть сформулирована как задача линейного программирования максимизировать г= сх при условиях Ах=Ь, х)0. Задача о максимальном потоке, изучаемая в этой главе, и задача о потоке минимальной стоимости (гл. 10) могут быть представлены в виде (1). В з 8.2 было показано, что всегда существует целочисленное оптимальное решение задачи о максимальном потоке, если пропускные способности дуг целочисленпы. Мы не можем утверя5дать, что и для общей задачи линейного программирования оптимальное решение всегда целочисленно. Будем исследовать подкласс тех задач линейного программирования, которые обладают целочисленным оптимальным решением. Гофман и Краскал [103) показали, что задача линейного программирования с ограничениями Ах ( Ь, х ) О, всегда имеет целочисленное оптимальное решение при любом целочисленном векторе ограничений Ь, если матрица А является абсолютно унимодулярной.
Напомним, что матрица А называется абсолютно упимодулярной, если все ее миноры равны либо О, либо ~1. Результат, полученный Гофманом и Краскалом, означает, что выпуклый многогранник, определяемый ограничениями Ах - Ь, х ) О, имеет целочисленные крайние точки при любом целочисленном векторе Ь, если матрица А абсолютно упимодулярна.
Ясно, что условие абсолютной унимодулярпости матрицы А достаточно для существования целочисленного оптимального решения. Труднее показать, что это условие является и необходимым. Доказательство Гофма- тба гл. г. млксимлльнын поток па и Краскала ПОЗ[ довольно громоздко, позтому рассмотрим более простое доказательство Вейнотта и Данцига И99[. Если А есть (т х и)-матрица ранга т, то любую ее квадратную подматрицу ранга т назовем базисом матрицы А.
Твогвмь 8.8. Пусть задача линейного программирования имеет ограничения вида Ах = Ь, х ) О. Если при этом матрица А целочисленна, ее вектор-строки линейно независимы, а вектор Ь целочислен, то следующие три условия являются эквивалентными. 1. Определитель любого базиса В матрицы А равен 1 или — 1 2. Все крайние точки вьтуклого многогранника С, определяемого ограничениями Ах = Ь, х ь О, целочисленны при любом целочисленном векторе Ь. 3. Обращение В " любого базиса В является целочисленной зсатрицей.
Докьзктвльство. Из условия 1 следует условие 2. Действительно, пусть к — произвольная крайняя точка выпуклого многогранника С, а  — соответствующий ей базис. Тогда х = = [хв, хн[, где Вхв - — — Ь, и х„= О. По предположеяию Ь— целочисленный вектор, а по условию 1, йе$ В = ~1.
Тогда по правилу Крамера следует, что х„— целочисленный вектор. Значит, крайняя точка х = [хг, хн[ целочислепна. Из условия 2 следует условие 3. Действительно, пусть В— базис, а у — произвольный целочисленный вектор, такой, что у + В 'е; с О, где е; есть Ьи единичный вектор-столбец. Пусть х =- у + В 'е; ) О. Тогда Вз:= Ву + е; — целочисленный вектор, так как В, у, е~ целочнслеппы. Поскольку в качестве Ь можно взять любой целочисленный вектор, то положим Вх =-. Ь. Имеем Вх .— — Ь, з ' . О, а зто значит, что х является крайнейточкой выпуклого многогранника С, определяемого ограничениями Ах — - Ь, х ) О. По условию 2 з является целочисленным вектором. Но з — у = В 'е;, значит, В 'с; — целочисленный вектор (как разность двух целочисленных векторов з и у). Вектор В 'е;.
является 1-и вектор-столбцом в В-', значит, 1-й столбец матрицы В ~ целочислен. Эти рассуждения справедливы для любого еь 1 .=- 1, 2, ..., т. Следовательно, матрица В ~ целочпслепна. Из условия 3 следует условие 1. Пусть  — некоторый базис. По предполоясекню матрица В целочисленпа и, следовательно, <)еФ В вЂ” целое число, пе равное О. По условию 3, В ' — целочисленная матрица, де$ В ' — также целое число, пе равное О. Но (де1 В) (бес В ") =1, откуда следует, что бес  — - ось В ' = -Е1. ° Аналогичные результаты могут быть получены для выпуклого многогранника С, определяемого ограничениями Ах ( Ь, х ) О, 8.8. СВОЙСТВО АГСОЛЮТНОЙ УНИМОДУЛЯРНОСТИ Слвдствис. Рассмотрим выпуклый многогранник С, определяемый условиями Ах ( Ь, х ) О, где матрица А целочислепна.
Тогда следующие три условия являются гквивалентными. 1'. Матрица А абсолюсппо унимодулярна, 2'. Все крайние точки многогранниьа С целочисленны при любом целочисленном векторе Ь. 3'. Каждая певырождениая подматрица масприцы Аобладает иелочисленной обратной матриией. Положим А = (А, 1). Можно легко доказать эквивалентность условий 1 и Г, 2 и 2', 3 и 3'. Покажем, например, что из условия 1' следует условие 1. Пусть М вЂ” произвольная певырожденная подматрица матрицы А, имеющая ранг т — й. Тогда некоторый базис В матрицы А можно представить (после перестановки столбцов) в следующем виде: где 18 — единичная матрица размера й Х й. Очевидно, с[е1 В = .= с)е1М, и, следовательно,' в силу 1' с)е1 В =- ~1. Аналогичными преобразованиями можно получить все остальные результаты, впервые приведенные в работе [103[.
Заметим, что осли хотя бы одна из матриц А, Ат, — А, (А, А) или (А, 1) абсо:потно уписсодулярна, то этим свойством обладают и все остальные выписавлсые матрицы. Более подробный материал, касающийся рассмотреипых преобразований, можно найти в работах [103), [199[. Чтобы проверить, обладает ли ьсатрица А свойством абсолютной унимодулярности, надо провести большук! работу, ее!и!перебиратьь все мипорь! матрицы А. Существу!от, однако, достаточные (ко пе пеобходимыо) условия абсо.потной угиысодулярности матриц, которые проверяются гораздо легче. Ткорвмл 3.9.
1с1атрица А абсолютно уиимодулярна, если выполняются следующие условия. 1. Каждый ее злемент равен О, --1 или — 1. 2. Каждый ее столбец содержит не более двух ненулевых элементов ). 3. Строки лсатрицы А можно разбить на два непересекающихся множества К! и Лг таким образом, что !) в!овско показать, что осли матрица А обладает свойством 2, то условия 1, За, Зб необходимы дзя абсоспотной ушгмодузяркостк матрацы А.— Прил. ред.
11 т. ху Гл. 8. максимальный поток 462 а) если столбец из А содержит два ненулевых элемента одного знака, то один из них входит в й» а другой — е Лв', б) если столбец из А содержит два ненулевых элемента с противоположными знаками, то оба они входят либо в В» либо в Л,. Доклзатвльство. (Предложено Гофманом в добавлении к работе (99).) Легко видеть, что л>обая подматрица матрицы А в свою очередь удовлетворяот условиям теоремы. Поэтому достаточно доказать, что определитель любой квадратной матрицы, удовлетворяющей условиям теоремы, равен О, +1 или — 1. Доказательство проводем ипдукцней по размеру матрицы. Для матрицы размера 1 Х 1 теорома выполняется согласно условя>о (1). 11родположим теперь, что теорема верна для матрицы размера (и — 1) Х Х (и — 1), и пусть А — матрица размера и Х и. Если в некотором столбце все элементы равны О, то с(ес А = О. Если в каком- нибудь столбце матрицы А только один ненулевой элемент, то разло>ким определитель матрицы А по элементам этого столбца.
Тогда е)е$ А = ~А', где А' — алгебраическое дополнение ненулевого элемента, равное О илн ~1 по индуктивному предположению. Остается рассмотреть случай, когда каждый столбец матрицы А имеет ровно два ненулевых элемента. Тогда нз условий (1)— (3) следует, что У а» =- ~~' а», у —.- 1, 2,..., п. Отсюда сле>ев! севе дует, что деФ А = О ').
Заметим, что все рассу;кдення справедливы и в случао, когда одно из множеств Л> пусто. ° Упражнения 1. Используя метод расстановки пометок, найти максимальный поток из Л>а в Л>> в сети, изображенной на рнс. 8.13. В качестве исходного потока взять х„= х>в —— хвг .— — хм — — 2, остальные х» = О, (Число, написанное около дуги, обозначает ое пропускную способность.) 2. Пайти минимальное связывающее дерево длн сети, изображенной на рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
