Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 194
Текст из файла (страница 194)
В особенности порекомендуем следующие книги: Джордж (беог8е) и Лью (Ьш) [! 31], Голуб (Оо(пЪ) и ван Лоан (цап Ьоап) [! 43], Пресс (Ргеьа), Тукольски (Тепко!з(су), Ве|терлинг (Чепег(!п8) и Фланнери (Р!аппегу) [281,282], Стренг (8|гап8) [321,322]. В книге Голуба и ван Лоана [143] рассматриваются вопросы численной устойчивости. Авторы показали, почему с)ег(А) не может служить хорошим показателем устойчивости матрицы А, предложив вместо него использовать величину ))А!) !)А |)), где ()А)! = шах|5|<„~" | !а| ).
Кроме того, рассмотрен вопрос вычисления указанного значения без реального вычисления обратной матрицы А '. Метод исключения неизвестных Гаусса, на котором основаны алгоритмы Ш- и 1,()Р-разложения, был первым систематическим методом решения систем линейных уравнений и одним из первых численных алгоритмов. Хотя он был известен и ранее, его открытие обычно приписывают К. Ф. Гауссу (С.
Е бапзз) (1777-1855). В своей знаменитой работе [323] Штрассен показал, что матрица размером п х п может быть обращена за время О(п'к г). Виноград (%1по8гас!) [356] для | = 0,1,..., и — 2. Мы полагаем, что в первом и последнем узлах !со(хо) = ~~~'(О) = О И Ги(Х„) = Д,(1) = О. ЭтО ПрЕдПОЛОжЕНИЕ дЕЛаЕт 1с(Х) ЕСтЕСтВЕН- нмм кубическим сплайном (папка! спЪ|с зр1|пе). 882 Часть ел. Изяааииые темы доказал, что умножение матриц не сложнее обращения, а обратная оценка была получена Ахо (АЬо), Хопкрофтом (Норсгой) и Ульманом (1Л!щап) [5).
Еще одним важным разложением матриц является сингулярное разлаженве (з!пйн!аг ча!ие десощроябоп — ЯЧР). ЗЧР-разложение матрицы А размером т х и представляет собой разложение А = ЯгЕ(Д, где Х вЂ” матрица размером т х п, в которой ненулевые элементы находятся только на диагонали, !~1— матрица размером гп х т со взаимно ортонормапьными столбцами, а матрица Яз имеет размер и х п и также обладает свойством взаимной ортонормальности столбцов.
Два вектора называются ортонормальнымв (ог1лопоппа1), если их скалярное произведение равно О, а норма каждого вектора равна 1. Сингулярное разложение хорошо изложено в книгах Стренга [321, 3221, а также Голуба и ван Лоана [143). Прекрасное изложение теории симметричных положительно определенных матриц (и линейной алгебры вообще) содержится в книге Стренга [3221.
Глава 29. Линейное программирование Многие задачи можно сформулировать как задачи максимизации или минимизации некой цели в условиях ограниченности ресурсов и наличия конкурирующих ограничений. Если удастся задать цель в виде линейной функции нескольких переменных и сформулировать ограничения в виде равенств или неравенств, связывающих эти переменные, можно получить задачу линейного программирования (11пеаг-ргойгшпшшшй ргоЫеш). Задачи линейного программирования часто встречаются в разнообразных практических приложениях. Начнем их изучение на примере подготовки предвыборной кампании.
Политическая задача Представьте себя на месте политика, стремящегося выиграть выборы. В вашем избирательном округе есть районы трех типов — городские, пригородные и сельские. В этих районах зарегистрировано соответственно 100, 200 и 50 тысяч избирателей. Чтобы добиться успеха, желательно получить большинство голосов в каждом из трех регионов. Вы честный человек и никогда не будете давать обещания, в которые сами не верите.
Однако вам известно, что определенные пункты программы могут помочь завоевать голоса тех или иных групп избирателей. Основными пунктами программы являются строительство дорог, контроль над использованием огнестрельного оружия, сельскохозяйственные субсидии и налог на бензин, направляемый на улучшение работы общественного транспорта. Согласно исследованиям вашего предвыборного штаба можно оценить, сколько голосов будет приобретено или потеряно в каждой группе избирателей, если потратить тысячу долларов на пропаганду по каждому пункту программы.
Эта информация представлена в таблице на рис. 29.1. Каждый элемент данной таблицы показывает, сколько тысяч избирателей из городских, пригородных и сельских районов удастся привлечь, потратив тысячу долларов на агитацию в поддержку определенного пункта предвыборной программы. Отрицательные элементы отражают потерю голосов. Задача состоит в минимизации суммы, которая позволит завоевать 50 тысяч голосов горожан, 100 тысяч голосов избирателей из пригородных зон и 25 тысяч голосов сельских жителей.
Методом проб и ошибок можно выработать стратегию, которая позволит получить необходимое количество голосов, но затраты на такую стратегию могут оказаться не самыми низкими. Например, можно выделить 20 тысяч долларов на пропаганду строительства дорог, 0 долларов на агитацию в пользу контроля над Часть Ггй Избранные теми ВВ4 Рис. 29Л. Влияние предвыборной политики на настроения избирателей.
Каждая запись представляет собой величество тысяч голосов горожан, жителей пригорода и сельских жителей, получаемых при затрате тысячи долларов на рекламу определенных пунктов предвыборной программы. Отрицательные элементы отражают потерю пюосов. использованием оружия, 4 тысячи долларов на пропаганду сельскохозяйственных субсидий и 9 тысяч долларов на агитацию за введение налога на бензин. При этом удастся привлечь 20( — 2) + 0(8) + 4(0) + 9(10) = 50 тысяч голосов горожан, 20(5) + 0(2) + 4(0) + 9(0) = 100 тысяч голосов жителей пригородов и 20(3) + 0( — 5) + 4(10) + 9( — 2) = 82 тысячи голосов сельских жителей.
Таким образом, будет получено ровно необходимое количество голосов в городских и пригородных районах и большее количество голосов в сельской местности. (Получается, что в сельской местности привлечено голосов больше, чем имеется избирателей!) Чтобы получить эти голоса, придется потратить на пропаганду 20 + 0 + 4 + 9 = 33 тысячи долларов. Возникает естественный вопрос является ли данная стратегия наилучшей из возможных, т.е. можно ли достичь поставленных целей, потратив на пропаганду меньше денег? Ответ на этот вопрос можно получить, продолжая действовать методом проб и ошибок, однако вместо этого хотелось бы иметь некий систематический метод для ответа на подобные вопросы.
Сформулируем данный вопрос математически. Введем четыре переменные: хг — сумма (в тысячах долларов), потраченная на пропаганду программы стро- ительства дорог; хз — сумма (в тысячах долларов), потраченная на агитацию в пользу контроля над использованием оружия; хз — сумма (в тысячах долларов), потраченная на пропаганду программы сельскохозяйственных субсидий; х4 — сумма (в тысячах долларов), потраченная на агитацию за введение налога на бензин. Требование получить не менее 50 тысяч голосов избирателей-горожан можно записать в виде неравенства (29.1) — 2хг + 8хз + Охз + 10х4 > 50 .
Аналогично требования получить не менее 100 тысяч голосов избирателей, живущих в пригороде, и 25 тысяч голосов избирателей в сельской местности можно Глава гя Линейное нралеамаиравание зз5 записать как неравенства (29.2) 5х1 + 2хг + Охз + Ох4 > 100 н Зх1 — 5хг + 10хз — 2х4 > 25 .
(29.3) Любые значеииЯ пеРеменных хм хг, хз, хл, УдовлетвоРЯюЩие неРавенствам (29.1) — (29.3), позволят получить достаточное количество голосов избирателей в камском регионе. Чтобы сделать затраты минимально возможными, необходимо минимизировать сумму, затраченную на пропаганду, т.е. минимизировать выражение (29.4) Х1 + Х2 + ХЗ + Х4 Хотя отрицательная агитация часто встречается в политической борьбе, отрица- тельных затрат на пропаганду не бывает. Поэтому следует записать условия х1>0 хг>0, хз>0 и х4>0. (29.5) Объединив неравенства (29.1)-(29.3) и (29.5) для минимизации (29.4), мы по- лучаем то, что известно как задача линейного программирования. Запишем ее следующим образом: (29.6) минимизировать х1 + хг + хз при условиях Х1, Х2, ХЗ, Х4 Решение этой задачи линейного программирования позволит политику получить оптимальную стратегию предвыборной агитации.
Общия вид задач линейного программирования В общем случае в задаче линейного программирования требуется оптимизировать некую линейную функцию при условии выполнения множества линейных НЕРаВЕНСтВ. ДЛЯ ДаННЫХ ДЕйСтВИтЕЛЬНЫХ ЧИСЕЛ а1, аг,..., Он И МНОжЕСтВа ПЕРЕ- менных х1, хг,..., Х„линейная функция этих переменных 5 определяется как 5(х„хг,...,х„) =а1Х1+агхг+ +о„х„= ~~~ а х 1=1 Если 6 представляет собой действительное число, а 5' является линейной функцией, то уравнение 7'(Х1 Х2, ,Х„) = 5 называется линейным равенствам, а неравенства Г(хг,х„...,хн) < Ь -2х1+ 8хг + Охз 5х1 + 2хг + Охз Зх1 — 5хг + 10хз + 10х4 + Ох4 — 2х4 > 50 > 100 > 25 > О.
(29.7) (29.8) (29.9) (29.10) авб Часть У!!. Избранные темы г(х1,хз,...,хп) ~ 11 называются линейными неравенствами. Термин линейные ограничения применяется как к линейным равенствам, так и к линейным неравенствам. В линейном программировании не допускается использование строгих неравенств. Формально задача линейного программирования является задачей минимизации или максимизации линейной функции при соблюдении конечного множества линейных ограничений.
Если выполняется минимизация, то такая задача называется задачей минимизации, а если выполняется максимизация, то такая задача называется задачей максимизации. Вся оставшаяся часть данной главы будет посвящена формулированию и решению задач линейного программирования. Для решения задач линейного программирования существует несколько алгоритмов с полиномиальным временем выполнения, однако изучать их в данной главе мы не будем. Вместо этого мы рассмотрим самый старый алгоритм линейного программирования — симплекс- алгоритм. В наихудшем случае симплекс-алгоритм не выполняется за полиномиальное время, однако обычно он достаточно эффективен и широко используется на практике.
(29.11) максимизировать при условиях 4Х1 — ХЗ 2х1 + хз < 8 < 10 > — 2 (29.12) (29.13) (29.14) (29.15) 5х1 — 2хз х1 хз > О. Любой набор значений переменных х1 и хз, удовлетворяющий всем ограничениям (29.12) — (29.15), называется допустимым решением (теаз(Ые зо!пбоп) дан- Обзор задач линейного программирования Чтобы описывать свойства задач линейного программирования и алгоритмы их решения, удобно договориться, в каких формах нх записывать. В данной главе мы будем использовать две формы: стандартную и каноническую (з1аск).
Их строгое определение будет дано в разделе 29.1. Неформально стандартная форма задачи линейного программирования представляет собой задачу максимизации линейной функции при соблюдении линейных неравенств, в то время как каноническая форма является задачей максимизации линейной функции при соблюдении линейных равенств. Обычно мы будем использовать стандартную форму задач линейного программирования, однако при описании принципа работы симплекс-алгоритма удобнее использовать каноническую форму.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
