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