Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 181
Текст из файла (страница 181)
Пусть имеется задача линейного программирования общего вида с и переменными и т ограничениями. Предположим, что мы преобразовали ее в стандартную форму. Укажите верхнюю границу числа переменных и ограничений в полученной задаче. 29.1-9. Приведите пример задачи линейного программирования, для которой допустимая область является неограниченной, но оптимальное целевое значение конечно.
29.2 Формулирование задач в виде задач линейного программирования Хотя основное внимание в данной главе уделяется симплекс-алгоритму, важно также понимать, в каких случаях задачу можно сформулировать в виде задачи линейного программирования. После того как задача сформулирована в таком виде, ее можно решить за полиномиальное время с помощью эллипсоидиого алгоритма, или алгоритма внутренней точки. Существует несколько пакетов прикладных программ, эффективно решающих задачи линейного программирования, а значит, если проблему удастся сформулировать в виде задачи линейного программирования, то ее можно решить на практике с помощью такого пакета. Рассмотрим несколько конкретных примеров задач линейного программирования.
Начнем с двух уже рассмотренных ранее задач: задачи поиска кратчайших путей из одной вершины (з1п8!е зоигсе зЬоПез1 раПз ргоЫеш) (см. главу 24) и задачи максимального потока (шах1шпш-1(ои ргоЫеш) (см. главу 26). После этого мы опишем задачу поиска потока с минимальными затратами (ш(п(ппип-соз1-йо~ч). Для данной задачи существует алгоритм с полиномиальными затратами времени, не основанный на линейном программировании, однако мы не будем его рассматривать. И наконец, мы опишем задачу многопродуктового потока (шп111сошой1упоч ргоЫеш), единственный известный полиномиальный по времени алгоритм решения которой базируется на линейном программировании. Глава 29. Линейное программирование 887 Кратчайшие пути Максимизировать Н [г] при условиях И [с] < и'[и] + и (и, е) для всех (и, о) е Е, И[а] = О. (29.44) (29.45) (29.46) В этой задаче [У[ переменных Н [с], по одной для каждой вершины и е Е, и [Е[+ + 1 ограничение, по одному для каждой дуги плюс дополнительное ограничение, состоящее в том, что исходной вершине всегда соответствует значение О.
Максимальный поток Задачу максимального потока также можно сформулировать в виде задачи линейного программирования. Напомним, что нам задан ориентированный граф С = ()г, Е) в котором каждая дуга (и, с) Е Е имеет неотрицательную пропускную способность с(и,и) > О, и две различные вершины, источник а и сток 1. Согласно определению из раздела 26.1, поток — это действительная функция г': Ъ" х У вЂ” В., обладающая тремя свойствами: она удовлетворяет ограничениям пропускной способности; меняет знак при изменении направления; обеспечивает сохранение потока. Максимальный поток — это поток, который удовлетворяет Задачу поиска кратчайших путей из одной вершины-источника, описанную в главе 24, можно сформулировать в виде задачи линейного программирования. В данном разделе мы остановимся на формулировании задачи кратчайшего пути для одной пары источник-адресат, а более общий случай задачи поиска кратчайших путей из одного источника предлагается рассмотреть в качестве упражнения 29.2-3.
В задаче поиска кратчайшего пути для одной пары источник-адресат нам дан взвешенный ориентированный граф С = (г',Е), весовая функция ю: Е - хь, ставящая в соответствие дугам графа действительные веса, исходная вершина а и конечная вершина ~. Мы хотим вычислить значение д[г], которое является весом кратчайшего пути из з в г.
Чтобы записать эту задачу в виде задачи линейного программирования, необходимо определить множество переменных и ограничения, которые позволят определить, какой путь из з в 1 является кратчайшим. К счастью, алгоритм Беллмана-Форда именно для этого и предназначен. Когда алгоритм Беллмана-Форда завершает свою работу, для каждой вершины е оказывается вычисленным значение 0 [и], такое что для каждой дуги (и, е) Е Е выполняется условие Н [е] < Н [и] + и (и, с). Исходная вершина первоначально получает значение И [а] = О, которое никогда не изменяется. Таким образом, мы получаем следующую задачу линейного программирования для вычисления веса кратчайшего пути из з в г: Часть ЧП.
Избранные темы 888 данным ограничениям и максимизирует величину потока, представляющую собой суммарный поток, выходящий из источника. Таким образом, поток удовлетворяет линейным ограничениям, а величина потока является линейной функцией. Напомним также, что мы предполагаем, что с(и,и) = О, если (и,с) ф Е. Теперь можно записать задачу максимизации потока в виде задачи линейного программирования: г (з,с) ьеи ,г (и,с) < с(и,п) У (и, с) = -г" (и, и) ,) (и, о) = 0 (29.47) Максимизировать при условиях для всех и, о Е У, (29.48) для всех и, с Е У, (29.49) для всех и е У вЂ” (з, г) . (29.50) ьеи Эта задача линейного программирования содержит ~Ц переменных, соответствующих потоку между каждой парой вершин, и 2 Щ~ + ٠— 2 ограничений.
Обычно более удобно решать задачу линейного программирования меньшей размерности. Запись задачи (29.47)-(29.50), например, можно упростить, если учесть, что поток и пропускная способность каждой пары вершин и, о, таких что (и, и) ф Е, равны О.
Но более эффективно было бы переписать задачу так, чтобы в ней содержалось 0(У+ Е) ограничений, что и предлагается сделать в упражнении 29.2-5. Поиск потока с минимальными затратами До сих пор в данном разделе мы использовали линейное программирование для решения задач, для которых нам уже известны эффективные алгоритмы. Фактически, хороший алгоритм, разработанный специально для некой задачи, как, например, алгоритм Дейкстры (РОкз1га) для задачи поиска кратчайшего пути из одной вершины или метод проталкивания для задачи максимального потока, обычно более эффективен, чем линейное программирование, — как в теории, так и на практике. Истинная ценность линейного программирования состоит в возможности решения новых задач. Вспомним задачу выработки предвыборной политики, описанную в начале данной главы.
Задача получения необходимого количества голосов при минимальных затратах не решается ни одним из алгоритмов, уже изученных нами в данной книге, однако ее можно решить с помощью линейного программирования. О реальных задачах, которые можно решить с помощью линейного программирования, написано множество книг. Линейное программирование также чрезвычайно полезно при решении разновидностей задач, для которых еще не известны эффективные алгоритмы.
Глава 29. Линейное программирование 889 а (и, с) .г (и, о) = (2 . 2) + (5 2) + (3 . 1) + (7 . 1) + (1 . 3) = 27. Существуют алгоритмы с полиномиальными затратами времени, специально разработанные для задачи поиска потока с минимальными затратами, но в книге мы не будем их рассматривать. Запишем данную задачу в виде задачи линейного программирования. Эта задача линейного программирования напоминает задачу, записанную для максимизации потока, однако она содержит дополнительное ограничение, состоящее в том, что величина потока составляет ровно д единиц, и новую целевую функцию минимизации затрат: а (и, о) г" (и, и) (ь,и)ед г (и,с) < с(и, и) г" (и,о) = — г" (с,и) У(и,о) = О иеи ,'~ У(а,о)= с1. (29.5!) Минимизировать при условиях для всех и, с Е У, (29.52) для всех и,о Е 1г, (29.53) для всех и Е У вЂ” (з, й), (29.54) (29.55) иЕЕ Мпогопродуктовый поток В качестве последнего примера рассмотрим еще одну задачу поиска потоков.
Предположим, что компания 1лс1су Риск из раздела 26.1 приняла решение о расширении ассортимента продукции и отгружает не только хоккейные шайбы, по Рассмотрим, например, следующее обобщение задачи максимального потока. Предположим, что каждой дуге (и, с), помимо пропускной способности с(и, о), соответствует некая стоимость а (и, с), принимающая действительные значения. По техническим причинам мы требуем, чтобы в случае а (и, о) ) О выполнялось соотношение а(с,и) = О. Если по дуге (и,с) послано г'(и,с) единиц потока, это приводит к затратам а(и,п) . Г" (и, с).
Нам также задано целевое значение потока Н. Мы хотим переправить Н единиц потока из а в 1 таким образом, чтобы общая стоимость, связанная с передачей потока, ~ („„~ на(и,и) У(и,о), была минимальной. Эта задача называется задачей поиска потока с минимальными затратами (пшшпшп-созыйои). На рис. 29.2а представлен пример задачи поиска потока с минимальными затратами.
Нам нужно переслать 4 единицы потока из в в 1, минимизировав суммарные затраты (пропускная способность каждого ребра обозначена как с, а затраты передачи — как а). С любым допустимым потоком, т.е. функцией 7', удовлетворяющей ограничениям (29.48К29.50), связаны затраты 2;(„„1 и а (и, о) з (и, о). Мы хотим найти такой поток, который минимизирует эти затраты. Оптимальное решение показано на рис. 29.2б; ему соответствуют суммарные затраты 890 Часть Ч!!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
