Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 182
Текст из файла (страница 182)
Избранные темы Рис 29.2. Пример задачи поиска потока с минимальными затратами и ее решение также клюшки и шлемы. Каждый элемент снаряжения выпускается на отдельной фабрике, хранится на отдельном складе и должен ежедневно доставляться с фабрики на склад. Клюшки производятся в Ванкувере и доставляются в Саскатун, а шлемы производятся в Эдмонтоне и доставляются в Реджину. Пропускная способность сети доставки не изменилась, и различные элементы, или нродукты, должны совместно использовать одну и ту же сеть.
Данный пример — образец задачи многонрооуктового потока (пш!1!сопппод!гу йод). В этой задаче снова задан ориентированный граф С = (У Е), в котором каждая дуга (и, и) Е Е имеет неотрицательную пропускную способность с(и, и) > О. Как и в задаче максимального потока, неявно подразумевается, что с (и, и) = О для (и, и) ф Е, а кроме того, требуется, чтобы из с (и, и) ) О вытекало с(и,и) = О. Кроме того, даны к различных продуктов Кы Кз,..., Кы причем каждый 2-й продукт характеризуется тройкой К; = (з;, Ц, 4), где з; — источник продукта г, г; — место назначения продукта г, а 4 — спрос, т.е. желаемая величина потока продукта ! из в; в Ц.
По определению, поток продукта з, обозначаемый ,!з (так что (! (и, и) — поток продукта з из вершины и в вершину и), — это действительная функция, удовлетворяюшая ограничениям сохранения потока, смены знака при изменении направления и пропускной способности. Определим совокупный ноток (аййгейаге йод) Г (и, и) как сумму потоков различных продуктов: ,((и,и) = 2,', 1 !; (и,и).
Совокупный поток по дуге (и,и) не должен превышать пропускную способность дуги (и,и). При таком способе описания задачи нам не нужно ничего минимизировать; необходимо только определить, возможно ли найти такой поток. Поэтому мы записываем задачу линейного программирования с "пустой" целевой функцией: Глава 29. Линейное программирование 891 Минимизировать при условиях 0 Л(и,с)( с(и,с) 1=1 Л (и, с) = -Л (с, и) Л(и,с) < с(и,с) Л(и,с) = 0 пе1г ~~> Л (з, с) = А для всех и,с Е ь', для всех 1= 1,2,...,/с и и,се 1г, для всех 1 = 1, 2,..., /с и и, с е 1г, для всех 1 = 1, 2,..., й и и е Ъ' — (з;,тг), для всех 1 = 1, 2,..., и иль' Упражнения 29.2-1.
Приведите задачу линейного программирования поиска кратчайшего пути для одной пары вершин, заданную формулами (29.44Н29.46), к стандартной форме. 29.2-2. Запишите в явном виде задачу линейного программирования, соответствующую задаче поиска кратчайшего пути из узла а в узел у на рис. 24.2а. В задаче поиска кратчайшего пути из одной вершины мы хотим найти веса кратчайших путей из вершины з ко всем вершинам с е 'г'. Запишите задачу линейного программирования для данного графа С, решение которой обладает тем свойством, что И [с] является весом кратчайшего пути из з в с для всех вершин с Е 1г. 29.2-3. 29.2-4. Запишите задачу линейного программирования, соответствующую поиску максимального потока на рис.
26.1а. 29.2-5. Перепишите задачу линейного программирования для поиска максимального потока (29.47)-(29.50) так, чтобы в ней было только 0(Ъ" + Е) ограничений. Сформулируйте задачу линейного программирования, которая для заданного двудольного графа С = (У, Е) решает задачу о взвешенных паросочетаниях с максимальным весом (шахпппш-Ь1рап1ге-ша1сЫпй). В задаче поиска многолродуктового потока с минимальными затратами (пип1шшп-соз1 пш1псопппо61гу-Лоач ргоЫеш) задан ориентированный граф С = (К Е), в котором каждой дуге (и, с) е Е соответствуют неотрицательная пропускная способность с(и, с) > 0 и затраты а (и, с).
29.2-6. 29.2-7. Единственный известный алгоритм решения этой задачи с полиномиальным вре- менем выполнения состоит в том, чтобы записать ее в виде задачи линейного программирования и затем решить с помощью полиномиального по времени ал- горитма линейного программирования. Часть ЧП. Избранные темы 892 Как и в задаче многопродуктового потока, имеется й различных товаров Кы Кз,...,Кы при этом каждый продукт з характеризуется тройкой К; = (в;,Ц,4). Поток й для г-го продукта и совокупный поток Г (и, о) вдоль дуги (и, о) определяются так же, как и в задаче много- продуктового потока. Допустимым является такой поток, для которого совокупный поток вдоль каждой дуги ~и, и) не превышает ее пропускной способности.
Затраты для определенного потока определяются как ~;„„ег, а (и, о) ~ (и, ю), и цель состоит в том, чтобы найти допустимый поток с минимальными затратами. Запишите данную задачу в виде задачи линейного программирования. 29.3 Симплекс-алгоритм Симплекс-алгоритм является классическим методом решения задач линейного программирования.
В отличие от многих других приведенных в данной книге алгоритмов, время выполнения этого алгоритма в худшем случае не является полиномиальным. Однако он действительно выражает суть линейного программирования и на практике обычно бывает замечательно быстрым.
Симплекс-алгоритм имеет геометрическую интерпретацию, описанную ранее в данной главе, кроме того, можно провести определенные аналогии между ним и методом исключения Гаусса, рассмотренным в разделе 28.3. Метод исключения Гаусса применяется при поиске решения системы линейных уравнений. На каждой итерации система переписывается в эквивалентной форме, имеющей определенную структуру. После ряда итераций получается система, записанная в таком виде, что можно легко найти ее решение. Симплекс-алгоритм работает аналогичным образом, и его можно рассматривать как метод исключения Гаусса для неравенств. Опишем основную идею, лежащую в основе итераций симплекс-алгоритма. С каждой итерацией связывается некое "базисное решение", которое легко получить из канонической формы задачи линейного программирования: каждой небазисной переменной присваивается значение О, и из ограничений-равенств вычисляются значения базисных переменных.
Базисное решение всегда соответствует некой вершине симплекса. С алгебраической точки зрения каждая итерация преобразует одну каноническую форму в эквивалентную. Целевое значение, соответствующее новому базисному допустимому решению, должно быть не меньше (как правило, больше) целевого значения предыдущей итерации. Чтобы добиться этого увеличения, выбирается некоторая небазисная переменная, причем такая, что при увеличении ее значения целевое значение также увеличится.
То, насколько можно увеличить данную переменную, определяется другими ограничениями; а именно: ее значение увеличивается до тех пор, пока какая-либо базисная переменная не станет равной О. После этого каноническая форма переписывается так, Глава 29. Линейное программирование 893 по эта базисная переменная и выбранная небазисная переменная меняются ролями. Хотя мы использовали определенные начальные значения переменных для описания алгоритма и будем использовать их в наших доказательствах, в алгоритме данное решение в явном виде не поддерживается.
Он просто переписывает задачу линейного программирования до тех пор, пока оптимальное решение не станет "очевидным". Пример симплекс-алгоритма Рассмотрим следующую задачу линейного программирования в стандартной форме: Максимизировать Зх1+ хз+ 2хз при условиях (29.56) х1+ ха+ Зхз ( 30 2х1+ 2хз + 5хз < 24 4х1+ ха+ 2хз (36 хы хз) хз ~ ~0 .
(29.57) (29.58) (29.59) (29.60) Зхг + хз + 2хз х4 = 30 х1 — хз — Зхз хь = 24 — 2х1 — 2хз — 5хз ха = Зб — 4х1 — хз — 2хз (29.61) (29.62) (29.63) (29.64) Чтобы можно было применить симплекс-алгоритм, необходимо преобразовать данную задачу в каноническую форму, как описано в разделе 29.1.
Вспомогательные переменные — не просто элементы алгебраического преобразования, они являются содержательным алгоритмическим понятием. Напомним (см. раздел 29.1), что каждой переменной соответствует ограничение неотрицательности. Будем говорить, что ограничение-равенство является строгим (й8)п) при определенном наборе значений его небазисных переменных, если при этих значениях базисная переменная данного ограничения становится равной О.
Аналогично, набор значений небазисных переменных, который делает базисную переменную отрицательной, нарушает данное ограничение. Таким образом, вспомогательные переменные наглядно показывают, насколько каждое ограничение отличается от строгого, и тем самым помогают определить, насколько можно увеличить значения небазисных переменных, не нарушив ни одного ограничения. Свяжем с ограничениями (29.57)-(29.59) вспомогательные переменные х4, хь и ха соответственно, и приведем задачу линейного программирования к канонической форме. В результате получится следующая задача: 894 Часть ЧП.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
