Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 199

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 199)

голосов при минимальных затратах не решается ни одним из алгоритмов, уже изученных нами в данной книге, однако ее можно решить с помощью линейного программирования. О реальных задачах, юторые можно решить с помощью линейного программирования, написано множеспю книг.

Линейное программирование также чрезвычайно полезно при решении разновидностей задач, для которых еще не известны эффективные алгоритмы. Рассмотрим, например, следующее обобщение задачи поиска максимального потока. Предположим, что каждому ребру (и, и), помимо пропускной способности с(и, и), соответствует некая стоимость а(и, и), принимающая действительные значения.

Как и в задаче поиска максимального потока, мы считаем, что с(и,п) = О, если (и,п) ф Е, и что антипараллельных ребер в графе нет. Если по ребру (и, и) послано у„„единиц потока, зто приводит к стоимости пересылки а(и, п)у„„. Также задано целевое значение потока и'. Необходимо переправить с( единиц потока из а в ( таким образом, чтобы общая стоимость, связанная с пеРедачей попжа, 2 („„) л а(и, и)У"„„, была минимальной. Эта задача называется задачей поиска потока минимальной снзонмоснчн.

На рис. 29.3, (а) представлен пример задачи поиска потока минимальной стоимости. Нужно переслать четыре единицы потока из в в г, минимизирован суммарную стоимость (пропускная способность каждого ребра обозначена как с, а стоимость — как а). С любым допустимым потоком, т.е. с функцией у, удовлетворяющей ограничениям (29.48)-(29.50), связана стоимость ~ („„) е а(и, п)~„„. Необходимо найти такой попж, который минимизирует эту стоимость. Оптимальное решение показано на рис. 29.3,(б); ему соответствует суммарная стоимость 2,(„„) .Иа(и,п)У„„= (2 2)+ (б 2)+ (3 1)+(7 1)+(1 3) = 27.

Существуют алгоритмы с полиномиальными затратами времени, специально разработанные для задачи поиска потока минимальной стоимости, но они выходят за рамки данной книги. Запишем рассматриваемую задачу в виде задачи линейного программирования. Эта задача линейного программирования напоминает задачу, записанную для максимизации потока, однако содержит дополнительное ограничение, состоящее в том, что величина патока составляет ровно и' единиц„ Глааа 29. Ли«едко««рограмчщювааае 903 и новую целевую функцию минимизации стоимости: минимизировать ~~ а(и, и)1„« при условиях («,«)ее А- ~ Л~«г~~ у«« «и' «еи ~ л.-~ь.

«ЕЪ' «ЕК ««« (29.51) < с(и, и) для всех и, и Е Ъ', для каждой вершины и Е К вЂ” (а,1), для всех и, и Е Ъ' . (29.52) Многопродуктный поток В качестве последнего примера рассмотрим еще одну задачу поиска потоков. Предположим, что компания 1нску Риск из раздела 26.1 приняла решение о расширении ассортимента продукции и отгружает не только хоккейные шайбы, но также клюшки и шлемы. Каждый элемент снаряжения выпускается на отдельной фабрике, хранится на отдельном складе и должен ежедневно доставляться с фабрики на склад. Клюшки производятся в Ванкувере и доставляются в Саскатун, а шлемы производятся в Эдмонтоне и доставляются в Реджину. Однако пропускная способность сети доставки не изменилась, и различные элементы, или лродуквзы, должны совместно использовать одну и ту же сеть. Данный пример представляет собой экземпляр задачи мкоголродуазвного потока (пш!бсопппобйу бои).

В этой задаче снова задан ориентированный граф С = (г', Е), в котором каждое ребро (и, и) Е Е имеет неотрицательную пропускную способность с(и,и) > О. Как и в задаче поиска максимального потока, неявно подразумевается, что с(и, и) = 0 для (и, и) ф Е и что в графе нет анти- параллельных ребер. Кроме того, даны к различных продуктов Кы Кз,..., Кы причем каждый 1-й продукт характеризуется тройкой К, = (вп 1„4), где о; — источник продукта з, 1, — место назначения продукта 1, а 4 — спрос, т.е. желаемая величина потока продукта1 из э, в Ц. По определению поток продукта 1, обозначаемый Г', (так что Д„„представляет собой поток продукта 1 из вершины и в вершину и), — это действительная функция, удовлетворяющая ограничениям сохранения потока и пропускной способности.

Определим совокупный ловюк (аййгейа1е бом) г" „как сумму потоков различных продуктов; 1'„„= 2 ~ гз„„. Совокупный поток по ребру (и, и) не должен превышать пропускную способность ребра (и, и). При таком способе описания задачи не нужно ничего минимизировать; необходимо только определить, можно ли найти такой поток.

Поэтому мы записываем Часть егь Избрааныетеаы задачу линейного программирования с "пустой'* целевой функцией; минимизировать прн условиях .г гас г=1 Лаь ~~~ Леи ее и ьс'г' ече„а ~~' ее,е,ь, ( с(и, с) для всех и, гг Е Г, для всех г = 1,2,...,/с и для всех и Е Ъ' — (а;, 1Д, =О для всех г = 1, 2,..., /с, ьсЪ' Д„„> О для всех и, гг б $~ и для всех г = 1,2,...,/с.

Единственный известный алгоритм решения зтой задачи с полиномиальным вре- менем выполнения состоит в том, чтобы записать ее в виде задачи линейного программирования, а затем решить с помощью полиномиального по времени ал- горитма линейного программирования. Упражнения 29.2.2 Запишите в явном виде задачу линейного программирования„соответствующую задаче поиска кратчайшего пути из узла а в узел у на рис.

24.2,(а). 29.2.3 В задаче поиска кратчайшего пути из одной вершины необходимо найти ве- са кратчайших путей из вершины а во все вершины с е 1е. Запишите задачу линейного программирования для данного графа С, решение мзторой обладает тем свойством, что И„является весом кратчайшего пути из а в с для всех вер- шин с Е Ъ'. 29.2.4 Запишите задачу линейного программирования, соответствующую поиску макси- мального потока на рис. 26.1,(а).

29.2.5 Перепишите задачу линейного программирования для поиска максимального по- тока (29.47) — (29.50) так, чтобы в ней было толью О(У + Е) ограничений. 29.2.1 Приведите задачу линейного программирования поиска кратчайшего пути для одной пары вершин, заданную формулами (29.44)-(29.4б), к стандартной форме. Глава 29. Пинейиое лрограммироаание 905 29.2.6 Сформулируйте задачу линейного программирования„которая для заданного двудольного графа С = ($', Е) решает задачу о взвешенных паросочетаниях с максимальным весом (шах(шшп-Ь(рап!!е-ша!с)з)п8).

29.2. 7 В задаче поиска многопрооуктного потока с минимальной стоимостью (ппшпппп-соз! пшй!сопппойзу-Оо59 ргоо!еш) задан ориентированный граф С = ()г, Е), в котором каждому ребру (и,и) б Е соответствуют неотрицательная пропускная способность с(и,и) > О и стоимость а(и,и). Как и в задаче многопродуктного потока, имеется к различных товаров Кы Кз,..., Кы при этом каждый продукт ! характеризуется тройкой К; = (в„г„п',).

Поток !, для з-го продукта и совокупный поток )'„„вдоль ребра (и, и) определяются так же, как и в задаче многопродуктного потока. Допустимым является таюй поток, для которого совокупный поток вдоль каждого ребра (и, и) не превышает его пропускной способности. Стоимость потока определяется как !" „к а(и, и)!'„„, и цель состоит в том, чтобы найти допустимый поток с минимальной стоимостью. Запишите данную задачу в виде задачи линейного программирования. 29.3. Симплекс-алгоритм Симплекс-алгоритм является классическим методом решения задач линейного программирования.

В отличие от многих других приведенных в данной книге алгоритмов, время выполнения этого алгоритма в худшем случае не является полиномиальным. Однако он действительно выражает суть линейного программирования и на практике зачастую бывает замечательно быстрым. В дополнение к описанной ранее геометрической интерпретации можно провести определенные аналогии между ним и методом исключения Гаусса, рассмотренным в разделе 28.!.

Метод исключения Гаусса применяется при поиске решения системы линейных уравнений. На каждой итерации система переписывается в эквивалентной форме, имеющей определенную структуру. После ряда итераций получается система, записанная в таком виде, что можно легю найти ее решение. Симплекс-алгоритм работает аналогичным образом, и его можно рассматривать как метод исключения Гаусса для неравенств. Опишем основную идею, лежащую в основе итераций симплекс-алгоритма. С каждой итерацией связывается неюе "базисное решение", которое легко получить из канонической формы задачи линейного программирования: каждой небазисной переменной присваивается значение О, и из ограничений-равенств вычисляются значения базисных переменных. Базисное решение всегда соответствует некой вершине симплекса.

С алгебраичесюй точки зрения каждая итерация преобразует одну каноническую форму в эквивалентную. Целевое значение, соответствующее новому базисному допустимому решению, должно быть не меньше (как правило, больше) целевого значения предыдущей итерации. Чтобы добиться 90б Часть УП. Избраиныетеаы этого увеличения, выбирается некоторая небазисная переменная, причем такая, что при увеличении ее значения от нуля целевое значение также увеличится. То, насколько можно увеличить данную переменную, определяется другими ограничениями, а именно — ее значение увеличивается до тех пор, пока какая-либо базисная переменная не станет равной нулю. После этого каноническая форма переписывается так, что эта базисная переменная и выбранная небазисная переменная меняются ролями.

Хотя мы использовали определенные начальные значения переменных для описания алгоритма и будем использовать их в наших доказательствах, в алгоритме данное решение в явном виде не поддерживается. Он просто переписывает задачу линейного программирования до тех пор, пока оптимальное решение не станет "очевидным". Пример симплекс-алгоритма Начнем с конкретного примера.

Характеристики

Список файлов книги