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