Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 17
Текст из файла (страница 17)
4.2 Вычислительные эффекты модифицированного симплекс-алгоритма (Ве, ОН, (.аэ) На первый взгляд кажется, что преобразование матрицы размера (еп+!) х (пе+ !) вместо таблицы размера (не+1) х (в+1) уже должно прив.сти к сокращению вычислений. Рассмотрим, однако, операцию оценивания в модифицированном симплекс методе, Она требует вычисления скалярных произведений и'А, двойственной переменной ц на столбец А, из таблицы исходной задачи. Если это вычисление производится для каждого внебазисного столбца, то оно требует тх(н — пе) умножений.
Но это не намного меньше, чем число умножений, необходимых для преобразования таблицы в обычном симплекс-методе! Реальные преимущества модифицированного метода менее заметны, однако очень важны, Во-первых, нам ве обязательно вычислять относительные стоимости всех внебазиспых столбцов; мы можем взять первый столбец с отрицательной стоимостью, как в правиле Блэнда (см. 5 2.7). При этом объем вычислений составит лишь некоторую долю от вычислений, необходимых для оценивания всех столбцов, долю, определяемую средним числом столбцов, ко.
торые нужно просмотреть прежде, чем будет найден столбец с отрицательной относительной стоимостью. Второе реальное преимущество модифицированного метода вытекает из того факта, что операция оценивания использует столбцы Ае исходной таблицы. Как мы видели в задаче о кратчайшем пути и увидим во многих аналогичных задачах комбпиаторного характера, исходная таблица очень часто оказывается разреженной. Например, если оиа является матрицей инциденций вершин и дуг графа, то она содержит всего 2п ненулевых элементов. Отсюда вытекает не только то, что операцию оценивания можно производить быстро, но также и то, что исходную таблппу можно хранить в очень компактном виде и, быть может, вообще не вычислять явно.
Мы проиллюстрируем эти преимущества в следующем параграфе. кв. Задаиа о максимальном потоке Необходимо упомянуть одно усовершенствование модифицированного симплекс-метода, в котором обратная базисная матрица хранится в виде произведения, а не в виде явной матрицы размера (и+1)х(лз+!). Каждую операцию замещения можно рассматривать как умножение слева на матрицу Р, совпадающую с единичной матрицей размера (т+1) х (т+!) везде, кроме столбца г, содержащего вектор где элемент !~х„, стоит на г-м месте.
Тогда на каждом шаге ! текущая матрица СА!с!сУзо может быть записана в виде САРРУ"'=Р, ... Р,-САКИНА'", и каждую матрицу Р можно хранить очень компактно, поскольку она определяется только индексом г и вектором з). Когда последовательность векторов з) становится слишком длинной, ее можно заменить более короткой последовательностью, используя процесс, называемый переобршь(ениеж, в результате которого находится эквивалентная, по более короткая последовательность замещений, приводящая к текущему базису. Этот метод может существенно уменьшить память и время, необходимые для выполнения симплекс- алгоритма, особенно если обратить специальное внимание на уменьшение числа ненулевых элементов в последовазельности векторов з!.
Более детальное рассмотрение этих методов читатель может найти в (ОН, 1.аз). 4.3 Задача о максимальном потоке и ае решение модифицированным методом В некоторых задачах о сетях, которые можно сформулировать как задачи линейного программирования, матрицу ограничений можно извлечь непосредственно из графа, рассматриваемого в задаче, и, как мы отметили в предыдущем параграфе, эту матрицу вовсе не обязательно вычислять явно. Мы проиллюстрируем это на задаче о максимальном потоке, фундаментальной задаче, которая неоднократно будет появляться далее в этой книге.
Определение 4.1. !!усть дана потоковая сеть й1=(з, й )г, Е, Ь) с и= !'г"! вершинами и лз= !Е! дугами. Индивидуальная задача о максимальном потоке (ЗМП) определяется как задача нахождения потока ~ Е И из з в ! максимальной величины о. () Пример 4,1. На рис. 4.! показана потоковая сеть с в=4 вершинами и гп=-5 дугами. Легко проверить, что величина максимального потока из з в ! равна 2. 06 Гл, 4. Вычаглагпельныг аспгкгпы симплекс-алгоритма Сформулируем теперь задачу о максимальном потоке как задачу ЛП несколько необычным способом.
Пусть дуги занумерованы, как обычно, е„..., е„, и О О пусть С„..., С,, — занумерованный список всех цепей из з в б В нашей задаче ЛП будет х о! пт строк, по одной для каждой дуги, и р столбцов, по одному О для каждой цепи С, из з в !. Конечно, в любой достаточно большой задаче будет огромное чисрис. 4.!.
!тотоковая сеть, илпюст- ло цепей из з в ! ~то как отме пропускные способности. рирующая ЗМ!!. Числа в кружках— чено выше, мы пе намерены выписывать явно матрицу ограничений. Определим матрицу инциденций дуг и цепей О=Им) следующим образом: 1, если е, входит в С, й! ( О в противном случае, !'= 1, ..., пц ! = 1, ..., р, Тогда ограничения пропускных способностей принимают вид 0~(Ь, Задача состоит в максимизации суммы всех потоков повсем цепям, т.
е. ищется пппб 1 где с=( — !...„— 1)~рп, Таким образом, полная формулировка задачи имеет вид ппп е'Г, О) <Ь, у гО. Чтобы преобразовать эту задачу ЛП к стандартной форме, введем переменные недостатка з Е Й" и определим расширенный вектор потока 1=(Дз), соответствую!ций вектор стоимости с=-(с~О), и новую матрицу ограничений 0=(0 ~ !). Тогда наша задача в стандартной форме будет иметь вид ппп г = е'у, Оу= Ь, ~~О. Каждая переменная недостатка з; представляет собой разность между потоком подуге ! и пропускной способностью Ь;,1=1,..., пп Предположим теперь, что для решения этой задачи используется модифицированный симплекс-алгоритм, н на некотором шаге мы имеем бдр и соответствующую двойственную переменную и Е Й". (Заметим, что нет необходимости проводить этап 1, поскольку на- 4.8.
Задача о максимальном коогоке чальное допустимое решение задачи (4.7) можно получить, положив 7=0 и з=о, что соответствует нулевому потоку.) Тогда, согласно (4.3), критерием выгодного введения столбца (цепи Су) в базис будет условие с =с — и'0 (О, где О, есть )хй столбец матрицы инциденций дуг и цепей О.
3тот критерий можно записать в виде ( — и')О, -+1, поскольку су —— = — 1 для всех 1=-1,, р. Последнее неравенство имеет следующую интерпретацию. Вектор — и — это некоторый вектор весов на дугах, и — и'0; — стоимость цепи С; при этих весах. Тогда введение некоторой цепи в буазис выгодно, если ее стоимость меньше чем 1. Итак, мы пришли к основному выводу: для нахождения выгодного столбца достаточно найти крат шйпгую цепь из ь в ! для весов Рие. 4.2. Нумеровав дуг в примере.
— и. Если стоимость этой кратчайшей цепи, скажем Сп не меньше чем 1, то выполняется критерий оптимальности, в противном случае Су вводится в базис. Таким образом, в процессе вычислений требуется только хранить матрицу САИгГ размера (от+1) х (гп+!) и многократно решать задачу о кратчайшем пути. Задача о кратчайшем пути становится (как мы увидим позднее) намного проще, если стоимости ребер неотрицательны. Это можно 'обеспечить следующим образом если некоторое — и, отрицательно, то мы просто вставляем соответствующую переменную недостатка аг в базис. Пример 4.1 (продолжение). Вернемся к простой задаче о максимальном потоке, показанной на рис 4.1.
Занумеруем дуги так, как показано на рис. 4.2, и запишем первую матрицу СА)г74)' в виде л! м . дддлгип .- м м 4 ъ воза вв Гл. 4. Вычислительные аснекты симклекс-алгоритма Исходные веса всех дуг равны нулю, поэтому мы можем начать алгоритм с введения в базис любой кратчайшей цепи (длины О). Давайте поступим неправильно и начнем с цепи, которая не входит в оптимальное решение, например С,=(е„е„е,). В таблице ей соответствует столбец и после выполнения указанной операции замещения мы получим следующую матрицу САРИ'.
-Г1- 1 1 слллт ! ! Взвешенная сеть, соответствующая этому решению, показана на рис. 4.3, Кратчайшим путем в этой сети является цепь С,=(е„е,) длины О(), поэтому мы введем С, в базис. Перед этим мы должны вычислить текущий столбец по формуле ;> = -1-ар, и- С, = После указанной операции замещения получим С! = ег = САДА 1'!г! ы е! == Сь = ге 4.8. Задача о максимальном во!лаке Новая извещенная сеть показана на рис. 4.4. Кратчайшим путем в этой сети является Са=(е„е,) стоимости 0«1; поэтому мы вычис- Рвс.
4мь Задача о кратчайшем пути, соответствуюшая второму замещению, ляем текущий столбец е 1 — 1,~ — - г, .=. -! — л'!У! В Гт=- ! 1 — ! и производим указанное замещение, что приводит к матрице 1 ст- 1 ! САЛА !ни — ~з " 1 -1 1 а5 ' 1 в которой г= — 2 (что соответствует потоку величины 2).
Новая задача о кратчайшем пути показана на рис. 4.5. Теперь кратчайший Рвс. 4.4. Задача о кратчайшем пути для третье. го замешенвя. путь имеет длину 141, следовательно, мы пришли к оптимальному решению. |оо Гл. 4, Вычислительные аспекты симплекс-алгоритма Прежде чем продолжить изложение, заметим, что мы начали с одиой задачи — задачи о максимальном потоке и свели ее к после- Рис. 4.о. Задача о иратчайюем пути при достижении оптимальности. довательиости близких и более простых задач, а именно задач о кратчайшем пути. Эта ситуация часто встречается в теории оптимизации, и оиа еще много раз появится в данной книге. 4.4 Метод декомпозиции Данциге — Вулфа [0ти] Часто оказывается, что большая задача линейного программироваиия является иа самом деле набором меньших задач линейного программирования, в большой степени независимых друг от друга.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
