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