Беклемишев - Дополнительные главы линейной алгебры (947281), страница 64

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 64)

Именно, система ограничений должна иметь вид амх'+... + а,„х" = о1, х')О, ..., х" ~О. (1) а„,х'+...+а,х" = 6'", з м симплнкс матов 2ат При этом предполагается, что свободные члены неотрицательны, Ь'.~ О...,, Ь'" ~ О, а строки коэффициентов линейно независимы. Из последнего предположения,.в частности, следует, что т ~ п, В системе (1) имеется т независимых жестких неравенств и а (также независимых) неравенств вида хт — О. Таким образом, если система совместна, она определяет выпуклое многогранное множество размерности - п — т, имеющее вершины. В общей постановке задача может и не иметь канонической формы, и тогда симплекс-метод непосредственно неприменим.

Однако за счет увеличения числа переменных каждая задача может быть сведена к эквивалентной ей задаче канонического вида. Эквивалентность здесь понимается в том смысле, что по решению канонической задачи легко может быть указано решение исходной задачи. П р е д л о ж е н и е 1. Любая задача линейного программирования мозсет быть сведена к задаче канонического види Д о к а з а т е л ь с т в о. Пусть система ограничений исходной задачи имеет вид а„х'+...+а,„х"- Ь', (2) п,х'+...-~-а вхя~Ь . Сначала преобразуем неравенства в равенства, аах'+...+амх" — у'=Ь', 1=1, ..., т, где у' — неотрицательные переменные. (Конечно, если в систему (2) входит неравенство вида хт ~ О, то нет нужды преобразовывать его в хт — уг = О, у1 ) О.) После этого умножим на — 1 каждое из равенств, имеющее отрицательную правую часть. В полученной системе вместо каждой из переменных, не под- чиненных условию неотрицательности, введем две новые неотрица- тельные переменные, связанные с ней равенством хГ гу гвм Теперь, если отбросить линейно зависимые уравнения, система отличается от системы (!) толью обозначениями коэффициентов и переменных.

Для простоты записи предположим, что в исходной системе не содержалось неравенств вида х1 ) О и было добавлено т дополнительных переменных у'. Пусть ~! х', ..., х" à — допустимая точка исходной задачи. Положим гг = х1, г"'/ = О, если Ф~ О, и гу = О, г"ы = — х1, если хг ( О. Обозначим разности (аах'+... + аых") — Ь' через у'. Тогда )( гв, ..., гэ', уг, ..., у"' à — допустиман точка квмв нической задачи. Наоборот, по допустимой точке канонической зав гл, н, систгмы нвядванств и лингяноя пеогглммияовхниь задачи легко построить допустимую точку исходной задачи.

Поэтому системы ограничений той и другой задачи совместны или несовместны одновременно. Для целевой функции <р(х) = с,х'+ ... + с„х" исходной задачи определим соответствующую функцию для канонической задачи: ф (г) =с1г1+... +спг" — с~г"м —,, — сыгг" + ОУ1+... + ОУ"'. Если точке г=)г', ..., г'", у', ..., у'"(г сопоставлена точка х= Р(г)=)г' — г"+', ..., г" — г'"(г, то очевидно, что ф (г) = ~р (х). Множества значений обеих функций совпадают, и р(х) ограничена снизу тогда и только тогда, когда ограничена снизу ф(г). Если минимальное значение ч(г) достигается в точке г„то то же значение гр(х) принимает в точке х, = Р (г,), и оно также минимальное. Предложение доказано. Следует сказать, что в погоне за простотой и общностью при доказательстве мы не скупились на дополнительные переменные.

Возможны другие способы сведения задачи к канонической, при которых число переменных возрастает не так сильно или даже убывает, Вот один из них. Пусть система (2) имеет матрицу коэффициентов ранга и и первые и неравенств имеют линейно независимые правые части. Введем новые переменные уг=аих'+...+ат„х" — 6г, 1=1, ..., и, Тогда первые и неравенств примут вид у' ~ О, ..., у" ) О. В оставшиеся неравенства подставим вместо х', ..., х" их выражения через новые переменные и затем преобразуем их в линейно независимые равенства с неотрицательными свободными членами так же, как это было сделано при доказательстве предложения 1.

Имеются и другие приемы преобразования ограничений, но метод, примененный при доказательстве, очень широко применяется благодаря его простоте. Далее в этом параграфе будет предполагаться, что решается каноническая задача линейного программирования Ах=О, х=-О, (3) сх — гшп при условии ййА=ги, Ь:~О.

3. Задача, двойственная канонической. Чтобы построить за.дачу, двойственную задаче (3), мы перепишем (3) в виде х= О, Рх)д, сх-~ш(п, 4 4 симплекс-лгетоп где матрица Р и столбец д имеют следующее клеточное строение: Тогда двойственная задача запишется, согласно (5) э 2, в виде уР (с, у)0, уЬ-~шах. Здесь у — строка длины 2п, которую мы запишем как соединение двух строк у' и у' длины п каждая: у = !!у', уз !!. Это позволит записать двойственную задачу подробнее: (у' — у') А = с, у = О, (у' — у') Ь 4- гпах. Помимо условия неотрнцательности, строки у' и у' входят сюда только в виде разности у' — у', которую мы обозначим через и.

Строка и не обязана быть неотрицательной. Если !!у', у' !! удовлетворяет системе ограничений, то и удовлетворяет системе иА =-с. Обратно, если для некоторой строки и выполнено иА --". с, то нетрудно построить такую строку у длины 2п', что уР == с и у ~ О. Поэтому задача, двойственная канонической задаче (3), сводится к задаче иА -= с, иЬ -4- тпах, (4) которую мы и будем называть двойственной задаче (3). Задача (4) не является канонической. Мы придадим ей вид, более близкий к каноническому, если введем л неотрицательных переменных г', ..., г", записываемых в столбец х, и превратим ограничения этой задачи в равенства Атит+я Ст Ьтит ~П4аХ (5) Так как переменные и не подчинены условию неотрицательности, не имеет смысла добиваться неотрицательности свободных членов.

4. Вершины и ребра многогранника канонической зцхачи. Вершины многогранного множества, задаваемого системой линейных неравенств, определяются обращением в точные равенства каких- либо и независимых неравенств системы. Система (!) содержит а4 равенств а)хт ! ...

+ а„'х" = Ьт, а~хт+... + а'"х~ = Ь' . ! Поэтому в каждой вершине должны обращаться в равенства по меньшей мере и — лг из неравенств х' ~ О, ..., х" ~ О. Это означает, что каждая вершина имеет по меньшей мере п — и нулевых координат. Вершины, имеющие больше чем л — т нулевых координат, называются выролгденными. Если такая вершина существует, то 2ЗО Гл. ч.

Оистел9ы неРАВенстВ и, ланеаное ОРОГРАммиРОРлРНР и многогрзнное множество и вся задача, также называются вырожденныл9и. Примером вырожденного многогранного множества может служить отрезок, задаваемый системой неравенств х'+х'+х'=1, х1+ — хи+ 2хи = 1, 1 2 х~О. Конец Л' 11, О, 0) этого отрезка — вырожденная вершина (рис. 5). Пример незырожденного многогранного множества дает система неравенств х1+ 99+хи 1 2 — х" + 2хи+ 2хи = 1, которая задает отрезок МУ на рис. 6.

Сравнение этих примеров показывает, что вырожденность — свойство не многогранного мно. жества, а его расположения по отношению к системе координат. Рис. 6. Риы 5. П р е дл о же н и е 2. Для каждой вершины выпунмзва многогранного множества, определяемого системой 11), найдутся т линейно независимых столбцов матрицы А, в число которых входят все столбцы, соответствующие положительным координатам данной вершины.

Д о к а з а т е л ь с т в о. Для простоты записи. Ерацнвлоиапц, что рассматриваемая вершина определена Обраццвм9цаг и 9еаагв последних ц — т координат и рассмотрим квадратную матрицу порядка и: симплекс, метод где А — матрица системы (!), а Š— единичная матрица порядка п — т. Матрица (! состоит из строк, соответствующих неравенствам, обращающимся в равенства для данной вершины. По предположению эти неравенства линейно независимы, и следовательно, детерминант матрицы не равен нулю. Отсюда вытекает, что отличен от нуля минор порядка т матрицы А, который расположен в первых т столбцах. Это и заканчивает доказательство. Столбцы, о которых идет речь в предложении 2, являются столбцами базисного минора матрицы А.

В линейном программировании ги линейно независимых столбцов матрицы А называются просто базисом. Координаты вершины, соответствующие базисным столбцам, называются баэисньыли. Соответствие между базисами и вершинами можно описать следующими утверждениями: а) Каждой вершине соответствует хоть один базис. Если вершина вырождена (и только в этом случае) ей может соответствовать больше одного базиса. б) Базису не обязательно соответствует вершина.

Если мы положим небазнсные переменные равными нулю и найдем базисные из системы, то столбец х' высоты т, составленный из значений этих переменных, окажется равным А,'Ь, где Ал — подматрица матрицы А, состоящая из базисных столбцов. Итак, базису будет соответствовать вершина, если хл=А~'Ь= О, и только в этом случае.

Базис, которому соответствует вершина, называется допистимь:м. Существование вырожденных задач вызывает существенные трудности в теории симплекс-метода. При вычислениях по симплекс- методу должны приниматься специальные меры, без которых алгоритм может оказаться неэффективным для вырожденной задачи. Ниже мы будем предполагать задачу невырожденной, отложив обсуждение вырожденных задач до и. 9. Ребро многогранника, исходящее из вершины х„может быть определено параметрическим уравнением х = хэ+!!, (7) где ! — направляющий вектор, а ! — неотрицательный параметр. Для ребра-отрезка ! е= [О, Т1), для ребра-луча ! е= [О, + со).

Так как для всех точек многогранника выполнены равенства Ах = Ь, направляющий вектор ребра удовлетворяет условию А!=0. (8) Как одномерная грань многогранника ребро определяется обращением в точные равенства и — 1 неравенств системы (!), а значит, у всех точек ребра должны равняться нулю одни и те же и — т— — ! координат. Пусть ! = [(„..., ! ) — набор номеров столбцов базиса, соответствующего вершине х,. Так как задача предполагается 292 ГЛ, Ч СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕЙНОЕ ПРОГРАМЛ1ИРОВАНИЕ Р = — !ААу'а,. (10) Подстановка значений (9) в параметрическое уравнение (7) дает Х'= ХАО+й, ха=!А(, хх=О, 1~1, !Фй. (1! ) Теперь мы можем определить, является ребро лучом или отрезком и чему равно в последнем случае значение Т, соответствующее второму концу отрезка.

Характеристики

Список файлов книги