Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 18
Текст из файла (страница 18)
Пусть, например, иам дана задача ЛП, в которой матрица ограничений является матрицей иицидеиций вершин и дуг очень большого графа, ио граф имеет вид, показанный иа рис. 4.6. Ребра в этом графе имеются только между вершинами одного и того же множества и между множеством дгр и остальными множествами. Матрицу иицидеиций вершин и дуг такого графа можно представить следующим образом: Метод декомпозиции направлен иа использоваиие преимуществ этой специальной структуры путем сведения решения всей задачи к итеративному решению задач, размеры которых совпадают с размерами А, В и С.
У пас уже имеется материал для построения метода декомпозиции. Во-первых, модифицированный симплекс-алгоритм позво- 4.4. 44етад декомиаэиции леаицига — Вулфа ляет неограниченно увеличивать ч~исло столбцов без увеличения размера рабочей матрицы (которую мы назвали СА)сгс)л), Вторая идея исходит из данной нами формулировки ЗМП в форме дуг и цепей. Мы переформулировали эту задачу, введя гро- мадное число столбцов, однако мы учитывали тот факт, что в модифицированном методе никогда не нужно выписывать все столбцы явно. В этой формулировке с помощью дуг и цепей «и операция оценивания столбца оказалась операцией вычисления цены цепи для стоимости, ' Вр определяемой двойственной переменной и (иногда называемой вектором цен). При этом мы избежал и оцен иванна всех столбцов подряд путем нахождения только кратчайшей цепи, бс В методе декомпозиции эти приемы доводятся до крайности.
Мы введем по столбцУ длЯ р 4 в г Рис. 4.6. Граф с легко декомиоеируе. каждой вершины некоторой под- мой митриией иицидеиций верший и задачи. Это уменьшит число дуг. строк, но резко увеличит число столбцов Однако операция оценивания сведется к решению задачи ЛП размера той подзадачи, которую мы разрушили. Рассмотрим более детально как пример с двумя подзадачами задачу ЛП со следующей матрицей ограничений; и, столбцов л, столбцов ) т, строк ) т, строк ) т, строк (4.8) А н пусть переменная »Е)си соответствует первым и, столбцам, а переменная уЕ )си* — последующим и, столбцам.
Полностью эта :,. задача ЛП (в стандартной форме) имеет вид пцп г = с'х+ й'у, Ох+ и у =- Ь„ А» =бе, Ву= ба х, у>0. (4. 9) !ов г"л. 4. Вычислительиые аспекты симплекс. алгоритма Назовем первые те уравнений сцепляющими уравнениями; задачи, соответствующие последующим множествам строк, назовем соот- ветственно подзадачами А и В. Рассмотрим, в частности, ограниче- ния в подзадаче А: Лх=й, х) О. (4. РО) По теореме 2.3 любая допустимая точка в этой подзадаче может быть записана как выпуклая комбинация вершин допустимого множества. Назовем эти вершины х„..., хр', тогда х = х,г )игхг, (4. 11) ~ ы! где )7) О и Щ, ) =1.
Аналогично, представим У в виде У= 1!АУ! (4. 12) ~=1 где р,)~ О, ~,', р7 — — 1, и у,— вершины подзадачи В. Заменяя х и У в (4.9) их йредставлениями (4.1!) и (4.12), получаем задачу ЛП относительно переменных Ц и ро представленную ниже: переменные: ), Х ~ )с, р, (А,...А, Ф,...Фе О ...
О (О ... О ие (4, И) ! 1 те строк ! строка 1 строка где А,=-0х, (=1, ..., р, с)з,=-ру,, (=1, ..., д, и стоимость имеет вид пн'п г=$Ъ+6')л, где $е=-с'хп 1=1,..., р, б,=й'Угз 1=1,..., д, ), п)О, (4,14) (4.!5) (4.!6) (4.17) — новые переменные соответственно в гсе и гс". Задача, представленная в таком виде, называется обычно главной задачей, ,1(ля любого разумного примера получается, таким образом, астрономическое число столбцов, по одному на каждую вершину каждой из двух подзадач.
Однако число строк понизилось с еле+ +гп,+гп, до те+2, и можно применить модифицированный метод с матриней СА7сйг' размера (гпе ь3)х(иге+3). Если не касаться других вопросов, то это означает, что можно разместить намного 4.4. Метод деиомиооицио ааонцого — Вулфа !03 Ь с;=$т — (л, а, р)' 1 0 = $ — л'аа,.— а, (4.18) и, следовательно, критерий выгодного введения столбца в текущий базис имеет вид $ — л'Ат(а, ! 1, ..., р. (4.19) Если это условие выполняется для некоторой вершины подзадачи А, то мы находим выгодный столбец среди первых р столбцов. Теперь мы подходим к главному моменту. Как было обещано, мы не должны вычислять левую часть в (4.19) для каждой вершины подзадачи А; зто, очевидно, было бы практически неосуществимо для задачи среднего размера.
Вместо этого мы ищем наименьшее значение левой части в (4.19) по всем вершинам этой подзадачи. То есть ищется ппп Дг л Ат). 1 ° !<о (4.20) Это эквивалентно вычислению ппп (с' — л'0) х . по асам ааршииам «у ппдаадаии д (4.21) Но поиск минимального значения линейной функции по всем вершинам допустимого множества некоторой задачи ЛП есть просто задача ЛП! Таким образом, операцию оценивания для первых р столбцов можно выполнять, решая следующую задачу ЛП: ш!п (с' — л'О) и, Ах=ба, (4. 22) х «О.
Рассуждения, аналогичные тем, которые были применены к (4,18), большие задачи в памяти с быстрой выборкой. Сейчас требуется только (т,+3)' ячеек памяти для САИИ)г в отличие от (та+т + +т,+1)' в исходной формулировке. При т,=-т,=т„например, необходимый объем основной памяти сократится почти в 9 раз. Предположим теперь, что используется модифицированный симплекс-метод.
Тогда необходимо понять, как производить операцию оценивания. На каждом шаге в строке 0 матрицы САИН' будет стоять множество цен, которое мы запишем в виде вектора с разделенными компонентами со! (л, а, р), где л Е И ° соответствует первым т, строкам и а, () Е И' — следующим двум строкам главной задачи (4.13). Таким образом, относительная стоимость столбца Ха(1 =1,..., р) будет равна 104 Гх.
4. Вычислите«аныг аспекты симплекс-ихгоритмо показывают, что, решая задачу пнп (д' — и'Е) у, Ву=Ь„ у>(), (4.23) и сравнивая минимальную стоимость с р, можно определить, име. ется ли подходящий столбец среди последних д столбцов. Полностью описанный алгоритм приведен на рис. 4.7. Можно следующим образом описать работу метода декомпозиции. Главная задача на основании информации о ситуации в целом ргосейпге ЛЕКОМПОЗИПИЯ Ьей!п олт: = «нет»; построить матрицу САККУ с нулевой строкой (л, а, й); пщ1е опт=«нет» бо Ьей!п решить задачу ЛП ш!и (с' — и'О) х =- х», Ах =Ь», х сев; И х» < а !Ьеп вычислить столбец, соответствующий решению данной стоимости, и произвести замещение в матрице САККУ е!зе Ьей!п реши~ь задачу ПП пнп (б' — л'Р) у =ха, Ву=ь,, угвв; И х, < б гиен вычислить столбец, соответствующий решению данной стоимости, и произвести замещение в мзтрице САККУ е!зе олт:= «да» епб епе епб Рис.
4.7. Алгоритм декомпозиции. посылает цену подзадаче А, Эта подзадача на основании ее локальной информации и цены выдает в ответ решение (называемое предложением) для возможного улучшения всей задачи. Главная задача сравнивает стоимость г, этого предложения с ее критерием а для подзадачи А. Если предложение дешевле, чем и, оно вводится в базис. Если нет, то цена посылается в подзадачу В, и от нее запрашивается предложение. До тех пор пока подзадачи могут давать подходящие предложения, главная задача может находить подходящее замещение.
Если ни одна из подзадач не может внести подходящего предложения, то это означает, что мы достигли оптимального решения всей задачи. (Забавную драматизацию одного примера читатель может найти в (ь)а 1) ) То, что мы сделали для двух подзадач, можно, очевидно, сделать для любого числа подзадач. В этом случае матрица ограничений будет иметь следующий вид: иэб Задачи л" о строк ~ т~ строк (4.
24) хя строк ~ Эта задача содержит ~! „гп, строк в отличие от гпз+г строк в главной задаче алгоритма декомпозиции Пример 4.2. Г1родемонстрируем при помощи несложных вычислений эффективность описанного подхода для размещения бапьших задач в вычислительной машине. Пусть нам даны 100 подзадач, каждая со 100 строками, и 100 сцепляющих уравнений. Тогда в исходной задаче !О!00 строк и в матрице САцл)тг' 10101 х 1010!ж -10' элементов, которые, насколько нам известно, невозможно поместить в быстродействующую память ни одной вычислительной машины.
С другой стороны, матрица СА)с)с)х в главной задаче будет содержать 201 х 201=4х 10' элементов, которые можно хранить в быстродействующей памяти любой достаточно большой вычислительной машины. ! 1 Очевидным преимуществом алгоритма декомпозиции является уменьшение требуемой для него памятш при этом невозможно сказать что-либо определенное о времени, которое при этом за тратится, поскольку мы не знаем, сколько раз придется решать подзадачи, прежде чем будет достигнута оптимальность. Задачм !. Покажите, что число цепей из з в ( в потоковой сети может расти как экспо. иеициальиая функция от числа вершин 2.
Иа решения задачи о максимальиом потоке с помощью симплекс-алгоритма выведите следующее утверждение: в любой задаче о максимальном потоке для сети с гл дугами имеется оптимальный поток, который молкио разбить в сумму потоков по ие более чем т цепям. 3. Проверьте, что в модифицированном симплекс-методе можно легко следовать правилу Баэида, устраняющему зацикливаиис 4л. Исследуйте детали реализации двухэгапиого аариапта метода декомпозиции с использоваиием модифицированного загори~на. В часгиости, по будет, если некоторая подзадача: а) недопустима; б) псреоцредслеиа; в) неограниченна? Г Легко ли следовать правилу Блэида и получить тем самым коиечиость алгоритма? б. (Задапие по программироваиию.) Повторите э~дачу )5 из гл.
2 для модифицироваииого симплекс-алгоритма. Сравните обычный и ллодифицироваииый методы иа различных задачах, собирая статистику ~псла замсщеиий и числа умиожеиий. вл. докажите или приведи ге коитрпримср: а) во время решения задачи о максимальиом потоке лшдифицироз;шиым сичплскс-алгоритмом абра гиая базисная матрица никогда ие содержит эллчектов, отличных от О илп ~ ); б) и; всегда рав- ио 0 или 106 Гл.
4. Вычислительные аспекты симплекс-плгаритнн 7. Рассмотрите решение задачи о крзтчзйшем пути в форме вершин и дуг с использованием модифицированного симплекс-алгоритма. Опишите шаг выбора столбца. 8. Пусть р1=х„— это «.й ведущий элемент в модифицировзнном симплекс. алгоритме. Покажите, что после й замещений определитель базисной матрицы В равен Па,р;. 9.
При решении сильно вырожденной задачи линейного программкрования у нас может быть много неопределенностей при выборе строк для операции замещения в начале применения симплекс-алгоритма. Объясните, почему мы можем встретиться с серьезными численными проблемами, если будем разрешать эти неопределенности, не обращая внимания на размер потенциальных ведущих элементов. (Указание: см. задачу 8.) Предложите, как избежать этого (Укизиние: не обращайте внимания на зацикливание и посмотрите, как реализуется обычно метод Гаусса.) 10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
