Беклемишев - Дополнительные главы линейной алгебры (947281), страница 63
Текст из файла (страница 63)
гпах. — 2«д+ 2«2 ~ — 1, Легко видеть, что в каждой из задач ограничения несовместны. Получим одно важное следствие теоремы 3. Еслдд х, и иа— решения пары взаимно двойственных задач (3) н (5), то из теоремы 3 вытекает, что иаЬ иа,4ха (9) Действительно, имеют место соотношения иаЬ а иаАх, ( сх,, и и'Ь = сх,. Равенстпо (9) можно переписать в виде и'у= О, где у=Аха Элементы строки иа и столбца у неотрицательны. Это означает, что в выражении «у и)у +«2у +' +ипду $3. ОСНОВЫ ЛННЕЛНОГО ПРОГРАММ!НРОВАНИЯ все ненулевые слагаемые положительны. Поэтому из иву = О следует, что каждое слагаемое равно нулю. Пусть а'„— элементы матрицы А, а 6! и х', — элементы столбцов Ь и х,.
Тогда Л у'= ~ а'х,' — Ь', !'=1, ..., т, ч=! и мы приходим к следующему предложению. П р е д л о ж е н и е 3. Если х„и и" — региения пары взаимно дева<я!венных задач (3) и (5), и при некотором номере ! ~ 11, т1 выпо гнено ~ а,'х,'>Ь', А=! то !'-я координата и"; точки и' равна нулю. Наоборот, если иг > О, гпо и Х а!х" = Ь', е <а в=! Заметим, что одновременное обращение в нуль и! и уг возможно.
Аналогично может быть доказано П р е дл о ж е н и е 4. Для решений х, и ич пары взаимно двойственных задач из ияаг (с .<= ! <ледует х' = О, а из х< > О следует ива! = с, а г с г=! Представим себе, что элементы столбца Ь в (1) являются независимыми переменными, Рассмотрения такого рода существенны для исследования влияния изменений условий задачи на решение. Изменения могут быть связаны как с изменением самой задачи„ так и с ошибками в измерениях входных данных.
Столбец Ь не входит в систему ограничений двойственной задачи, и вершины и', ..., ия многогранного множества допустимых точек этой задачи не зависят от Ь. Если мы немного изменим Ь, то измененная целевая функция двойственной задачи будет достигать своего максимального значения в той же вершине и', что и старая функция. Покажем это, оценив возможное изменение Ь. Нам нужно, чтобы при всех ! = 1,, р выполнялось неравенство иаг(Ь+ <тЬ) .= иг (Ь+ са<Ь), 284 гл ч системы няпхввнств и линсяное пяогсхммиьовлниз или (ио иг)Ь~(и~ иа) ЛЬ Здесь левая часть неотрицательна, поскольку и' — решение исходной задачи. В силу неравенства Коши — Буняковского имеем (и' — и") ЛЬ ~ 11 и' — иь 11 1) ЛЬ )!.
Поэтому нужное нам неравенство будет выполнено при всех 1, если ) ЛЬ | ~ пп'и ( „, (10) Отсюда следует П р едл о же н не 5. При азменениях столбца Ь, не превосходна(их правую часть формулы (10), решение и" двойственной задачи (5) остается неизменным. В силу двойственности отсюда вытекает неизменность решения задачи (3) при малых изменениях коэффициентов с целевой функции ф. Воспользуемся предложением 5 для того, чтобы получить следующее свойство решения двойственной задачи. Минимальное значение сх, функции сх задачи (3), естественно, зависит от Ь, так как с изменением Ь меняется множество точек, на котором ищется минимум.
При этом мы знаем вид этой зависимости: сх, = и"Ь. Нельзя сказать, что эта зависимость линейна, так как при значительном изменении Ь строка и' изменяется. Но в некоторой окрестности столбца Ь (за исключением конечного числа таких столбцов) функция является линейной. Укажем, что одномерным аналогом такой функции является функция, график которой — ломаная линия. С учетом этого мы можем утверждать, что —,.— = и, д (ело) о (11) там, где эти частные производные существуют. Допустим, что некоторая компонента и) решения -иь двойственной задачи равна нулю.
Равенство и) — — 0 останется справедливым и после замены столбца Ь на близкий столбец Ь'. Следовательно, частная производная от сх„ по У равна нулю в некоторой окрестности исходного значения Ь'. Таким образом, равенство и," = 0 означает, что сх, не меняется при малых изменениях К С другой стороны, согласно предложению 3, и) обращается в нуль, если для решения хь исходной задачи (3) 1-е ограничение выполнено как строгое неравенство.
Мы получили П р едл о же н не 5. Минимальное значение функции ф не меняется при малых изменениях 1-го глемента столбца свободныл членов тогда и только тогда, когда равна нулю 1-я компонента $3. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ решения двойственной задачи. Для етого достаточно, чтобы 1-е ограничение вГчполнялось для хь как строгое неравенство. 5. Функция Лагранжа. Еще одна интерпретация решения двойственной задачи связана с функцией 7.
(х, и)=сх+и(Ь вЂ” Ах), (12) составляемой для задачи (3). Здесь и — строка длины т, и 1, (х, и), таким образом, есть функция от т + и переменных. Она называется функцией Лагранжа. Перегруппировав слагаемые, мы можем представить ее в виде Е(х, и)=иЬ-1-(с-иА)х. (13) Отсюда видно, что для пары взаимно двойственных задач функция Лагранжа одна и та же. П р едл о ж е н не 7. Пусть х, и и' — решения взаимно двойственных задач (3) и (5). Тогда точка (х„и') в в$' '"' является седловой точкой функиии Лагранжа, т. е.
для любых Х = О и и ~ О имеют место неравенства 1 (хы и) ~7 (ха, иь) ~1 (х, иь). Д о к а з а тел ь ство. При любом неотрицательном и из Ах, ) Ь следует и (Ь вЂ” Ах,) ~ О. Но в силу равенства (9) и'(Ь вЂ” Ах,) = О. Поэтому схо+и (Ь вЂ” Ахо) =-схь+ и'(Ь вЂ” Ахо), и левое из неравенств (14) доказано. Правое неравенство доказывается аналогично с использованием выражения (!3) и предложения 4. Из приведенного доказательства вытекает, что 7. (х„и') = сх, = иьЬ.
Функция Лагранжа известна из курса математического анализа (см. Кудрявцев 1161, т. П, стр. 96), где она строится для отыскания условного экстремума функции Г (х) при ограничениях вида Чч (х) = = О, 1 = 1, ..., т, и имеет вид 7. (х, )) =1(х)+ ~ Л,~,(х). с=и Переменные Л,,' ..., х называются множителями Лагранжа. В нашем случае ограничения являются неравенствами, и переменные подчинены условию неотрицательности. Теорема, которая распространяет метод Лагранжа на задачи с ограничениями более общего вида, называется теоремой Куна — Таккера. С ней можно познакомиться, например, по книге Карманова (14). Доказанное нами предложение 7 представляет собой теорему Куна — Таккера для случая линейной функции при ограничениях вида (!).
Мы видим, что переменные двойственной задачи играют роль множителей Лагранжа по отношению к исходной задаче. 286 ГЛ Ч СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕИНОЕ ПРОГРАММИРОВАНИЕ $4. Симплекс-метод 1. Введение. В этом параграфе мы познакомимся с симплекс- методом. Это основной из конечных методов решения задач линейного программирования, т. е. из таких методов, которые дзют в принципе точный результат за конечное число операций. Именно эффективность симплекс-метода обеспечила широкую популярность линейного программирования.
Слово «симплекс» на латыни означает <простойй». Это значение слова представляется наиболее подходящим для хаоактеристики метода, хотя и нет уверенности, что его авторы имели в виду именно это значение. Основная идея, лежащая в основе симплекс-метода, весьма прозрачна. По теореме 1 5 3 минимум целевой функции р достигается в одной из вершин многогранного множества, определяемого системой ограничений.
От одной вершины к другой мы можем переходить по ребру. При этом значение целевой функции ~р будет убывать, если проекция ее градиента на ребро (или, иначе, производная гр по направлению ребра) будет отрицательна. Пусть мы нашли некоторую вершину, из которой исходит такое ребро, что проекция градиента иа него отрицательна.
Имеются две возможности: а) Ребро является отрезком. В этом случае второй конец отрезка — вершина, в которой ~р принимает меньшее значение, чем в исходной вершине. б) Ребро является лучом. Тогда на ребре найдутся точки со сколь угодно малыми значениями ~р, и задача неразрешима ввиду неограниченности функции снизу. Допустим, что задача имеет решение, Так как после прохождения каждого ребра значение ч~ убывает, мы не можем вернутьсп в уже пройденную вершину, а всего вершин конечное число. Поэтому, через конечное число шагов мы придем в ту вершину, где достигается минимум.
Эта вершина характеризуется тем, что проекции градиента на все исходящие из нее ребра являются неотрицательными. Важное достоинство симплекс-метода состоит в том, что все вычисления, необходимые для реализации описанной схемы, легко осуществляются в процессе преобразования некоторой матрицы по алгоритму, близкому к методу Гаусса, Из других методов линейного программирования следует упомянуть итерационные методы, которые в последнее время шггенсивно совершенствуются и становятся все более употребптельньгли. Из-за недостатка места мы не сможем остановиться на этих методах. 2, Каноническая форма задачи. Симплекс-метод применяется к задачам так называемой канонической формы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
