Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 198
Текст из файла (страница 198)
Заметим, что индект т сы у А, Ь и с необязательно являются множествами последовательных целых чисел; они зависят от того, какие индексы входят в множества В и Х. В качестве примера противоположности элементов матрицы А коэффициентам канонической формы заметим, что в уравнение для х1 входит слагаемое хз/6, так что коэффициент а2з равен — 1/6, а не +1/6. Упражнения 29.1.1 Если записать задачу линейного программирования (29.24) — (29.28) в компактном виде (29.19)-(29.21), то чему будут равны и, т, А, Ь и с? 22 222 3722 хз 28— 6 хз 8+ 6 8хз 4 —— 3 хз 18— 2 2хб 3 хб 3 хб + 3 898 Часть ГИ. Избранные тены 29.1.2 Укажите три допустимых решения задачи линейного программирования (29.24К29.28). Чему равно целевое значение для каждого решения? 29.1.3 Каковы зн', В, А, Ь, с и с для канонической формы (29.38)-(29.41)? 29.1.4 Приведите следующую задачу линейного программирования к стандартной форме: минимизировать 2х! + 7хг + хз при условиях х! — хз Зх! + хг 29.1.5 Приведите следующую задачу линейного программирования к канонической форме: хз <7 >8 2хз >О > О.
Зхз — хг -х! + 2хг + Х1~ хгз Хз Какие переменные являются базисными, а какие небазисными? 29.1.6 Покажите, что следующая задача линейного программирования является нераз- решимой: максимизировать Зх! — 2хг при условиях х! + хг < 2 -2х! — 2хг < -10 Х1 Х2 > О. максимизировать 2Х! при условиях Х! + Х2 > 24 > 0 < О.
899 Глава 29. Линейное нрограммирование Покажите, что следующая задача линейного программирования является неогра- ниченной: максимизировать х1 — хз при условиях -2х1 + хз < — 1 < — 2 — Х1 — 2хз х1 хз > О. 29.1.8 Пусть имеется задача линейного программирования общего вида с и переменными и тп ограничениями. Предположим, что мы преобразовали ее в стандартную форму. Укажите верхнюю границу числа переменных и ограничений в полученной задаче.
Приведите пример задачи линейного программирования, для которой допустимая область является неограниченной, но оптимальное целевое значение юнечно. 29.2. Формулировка задач в виде задач линейного программирования Хотя основное внимание в данной главе уделяется симплекс-алгоритму, важно также понимать, в каких случаях задачу можно сформулировать в виде задачи линейного программирования. После того как задача сформулирована в этом виде, ее можно решить за полиномиальное время с помощью эллипсоидного алгоритма, или алгоритма внутренней точки. Существует несюлько пакетов прикладных программ, эффективно решающих задачи линейного программирования, а значит, если проблему удастся сформулировать в виде задачи линейного программирования, то ее можно решить на практике с помощью такого пакета. Рассмотрим несколько конкретных примеров задач линейного программирования.
Начнем с двух уже рассмотренных ранее задач: задачи поиска кратчайших путей из одной вершины (см. главу 24) и задачи поиска максимального потока (см. главу 26). После этого мы опишем задачу поиска потока с минимальной стоимостью. Для данной задачи существует алгоритм с полиномиальными затратами времени, не основанный на линейном программировании, однако мы не будем его рассматривать.
И наконец мы опишем задачу многопродуктного потока (шп!Псошойеу-Лози ргоЫеш), единственный известный полиномиальный по времени алгоритм решения которой базируется на линейном программировании. При решении задач с графами в части Ч( мы использовали запись атрибутов в виде с. д и (и, с).1. Однако линейное программирование обычно использует не присоединенные атрибуты, а переменные с нижними индексами. Таким образом, выражая переменные в задачах линейного программирования, необходимо указы- часеь гтп избранные вема вать вершины и ребра с помощью индексов. Например, вес кратчайшего пути для вершины е обозначается не как о.
д, а как д„. Аналогично поток из вершины и в вершину о обозначается ие как (и,и).1, а как ~„,. Для величин, являющихся входными данными для задач, таких как веса или пропускные способности ребер, мы будем продолжать использовать записи ю(и, и) и с(и, и). Кратчайшие пути Задачу поиска кратчайших путей из одной вершины-источника можно сформулировать в виде задачи линейного программирования. В данном разделе мы остановимся на формулировке задачи кратчайшего пути для одной пары, а более общий случай задачи поиска кратчайших путей из одного источника предлагается рассмотреть в качестве упр.
29.2.3. В задаче поиска кратчайшего пути для одной пары у нас имеются взвешенный ориентированный граф С = (К, Е), весовая функция щ: Š— > )й, ставящая в соответствие ребрам ~рафа действительные веса, исходная вершина а и вершина назначения 1. Мы хотим вычислить значение И~, которое является весом кратчайшего пути из а в г. Чтобы записать эту задачу в виде задачи линейного программирования, необходимо определить множество переменных и ограничения, которые позволят определить, какой путь из а в 8 является кратчайшим. К счастью, алгоритм Беллмана-Форда именно зто и делает. Когда алгоритм Беллмана-Форда завершает свою работу, для каждой вершины о оказывается вычисленным значение г(„(мы используем запись с индексом, а не атрибут), такое, что для каждого ребра (и, о) е Е выполняется условие Н„< Н + ш(и, с).
Исходная вершина изначально получает значение Н, = О, которое никогда не изменяется. Таким образом, мы получаем следующую задачу линейного программирования для вычисления веса кратчайшего пути из а в 1: максимизировать 4 (29.44) при условиях Н„< о' + ш(и, о) для каждого ребра (и, о) Е Е, (29.45) о, =О. (29.46) Вас может удивить то, что данная задача линейного программирования максимизирует целевую функцию, в то время как предполагается, что задача вычисляет кратчайшие пути. Мы не хотим минимизировать целевую функцию, поскольку тогда присваивание Й„= О для всех о е Ъ' даст оптимальное решение задачи линейного программирования без решения задачи поиска кратчайшего пути.
Мы выполняем максимизацию, поскольку оптимальное решение задачи поиска кратчайших путей присваивает каждому о, значение ппп 4„,)ал (Ы„+ щ(и, с)), так что д„является наибольшим значением, которое не превышает все значения множества (д„+ ю(и, о)). Мы хотим максимизировать Н, для всех вершин с на кратчайшем пугн из а в 1 при условии выполнения указанных ограничений для всех вершин с, и максимизация 4 достигает этой цели. Эта задача линейного программирования имеет Щ переменных 4„по одной для каждой вершины с Е Ъ'.
В ней также имеется )Е~+ 1 ограничений: по одному гневи г9. Линейное врогриммировоние 901 для каждого ребра плюс дополнительное ограничение, что вес исходной вершины кратчайшего пути всегда имеет значение О. Максимальный поток Е~-- ЕьиЕУ оСУ 7 и < с(и,о) (29.47) максимизировать при условиях для всех и,о е И, (29.48) для каждой вершины и е И вЂ” (а,г), для всех и, о Е )г . (29.49) (29.50) ой У У„„> О Эта задача линейного программирования имеет ~Ц переменных, соответствующих потоку между каждой парой вершин, и 2 ~)г( + )Ц вЂ” 2 ограничений. Обычно более эффективно решаются задачи линейного программирования меньшей размерности. В задаче (29.47) — (29.50) для простоты записи считается, что поток и пропускная способность каждой пары вершин и,о, таких, что (и, о) ф Е, равны О.
Но было бы эффективнее переписать задачу так, чтобы в ней содержалось 0(И + Е) ограничений, что и предлагается сделать в упр. 29.2.5. Поиск потока минимальной стоимости До сих пор в данном разделе использовалось линейное программирование для решения задач, для которых уже известны эффективные алгоритмы. Фактически хороший алгоритм, разработанный специально для конкретной задачи, например алгоритм Дейкстры для задачи поиска кратчайшего пути из одной вершины или метод проталкивания для задачи максимального потока, обычно более эффективен, чем линейное программирование, — как в теории, так и на практике.
Истинная ценность линейного программирования состоит в возможности решения новых задач. Вспомним задачу подготовки к предвыборной кампании, описанную в начале данной главы. Задача получения необходимого количества Задачу поиска максимального потока также можно сформулировать в виде задачи линейного программирования. Напомним, что в ней задаются ориентированный граф С = (К Е), в котором каждое ребро (и,о) Е Е имеет неотрицательную пропускную способность с(и, о) > О, и две различные вершины, источник в и сток 1. Согласно определению из раздела 26.1 поток является действительной функцией 7: Ъ' х И вЂ” ~ И, удовлетворяющей ограничениям пропускной способности и сохранения потока.
Максимальный поток представляет собой поток, который удовлетворяет данным ограничениям и максимизирует величину потока, представляющую собой суммарный поток, выходящий из источника, минус суммарный поток, входящий в источник. Таким образом, поток удовлетворяет линейным ограничениям, а величина потока является линейной функцией. Напомним также, что мы предполагаем, что с(и, с) = О, если (и, о) ф Е. Теперь можно записать задачу максимизации потока в виде задачи линейного программирования: Часвль РД Избранные темы ф. с с~ ч,чв. Я'~ (в) Рнс. ЗРЗ. (в) Пример заавчи поиска потока минимальной стоимости.
Пропускные способностк обозначены как с„а стоимости — как о. Вершина в лвллетсл источником, а вершина З вЂ” стоком, и необходимо переслать четыре единицы потока нз е в С (б) Решение задачи поиска потока минимальной стоимости, в шторой из истока в в сток З пересылшотсл четыре единицы потока. длл камдото ребра поток и пропускнаа способность указаны в виде "поток/пропускала способносп".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
