Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 7
Текст из файла (страница 7)
Доказательство. Допустим, что р содержит решение х с 1)т ненулевыми компонентами, и пусть х — решение из Р с наибольшим числом нулевых компонент. Не ограничивая общности, будем считать, что хь..., х~>0; хаен..., х„=О. Рассмотрим первые 1столбцов матрицы А. Они, очевидно, удовлетворяют равенству А,х,+...+А~х,=й. 12.4) Пусть г — ранг матрицы, составленной из этих 1 столбцов. Тогда г иО, поскольку если г=О, то бдр х=О лежит в Р. Кроме того, г~т(й Можно считать, что матрица с о„а„...
а,„ а„а„... а„ невырожденна. 1!оэтому можно, решив систему уравнений 2.4, вы- разить х„..., х, через х„+„..., хь Другими словами, хг — — 11, + Х а,;хо 1=1, .;,, г. ~=ге! Положим О=пни (х, о 8,), где и > о !аг+г е' г+И! Гл. 2. Симпл«кс-алгоритм х следующим образом; если 1=«+1, если 1>«+1, Зададим новое допустимое решение х,— О, х, хе= с ))«+ Х а;,хо ~=«+! если 1' < «+ 1. Теорема 2.2.
Пусть для задачи ЛП ш)п ох, Ах =Ь, х)0, слп) выполняются предположения 2.1 — 2.3. Тогда она эквивалентна (в том смысле, что обе задачи имеют одинакыое оптимальны значение функций стоимости) следующей задаче ЛП*: ппп с'х, Ах=Ь, х)0, ха-.я, (лп*) Тогда ху — — х — а, ~ уй пРи 1'(г. Если О=х„„, то х, г — 0; если 0=0, =хк1а,, „для некоторого й ( «, то х„=О. В любом случае х †допустим решение, в котором число нулевых компонент на единицу больше, чем в х, и приходим к противоречию. Это рассуждение показывает, что найдется решение х с 1~т ненулевыми компонентами и, более того, что соответствующие столбцы можно считать линейно независимыми.
Это множество столбцов можно затем расширить до базиса для х, поскольку ранг А равен т П Лля удобства примем еще одно заключительное предположение, которое, как мы покажем в дальнейшем, также не является необходимым. Именно, будем считать, что рассматриваемая задача ЛП имеет конечное минимальное значение целевой функции с'х. Предположение 2.3. Множество действительных чисел (с'х: х Е Р) ограничено снизу.
Но даже если стоимость с'х в задаче ЛП ограничена снизу, допустимое множество может простираться бесконечно в некоторых направлениях. В заключение этого параграфа покажем, что при предположении 2.3 можно тем не менее ограничиться задачами линейного программирования с ограниченными допустимыми множествами Р. Более точно можно считать, что р лежит внутри достаточно большого гиперкуба. 2.3.
Геометрия задач линейного программирования где М = (т + 1) ! а р, а=гпах(!а, ), (в,!), ~=гпахДЬг), /гЦ и г — наибольшая нижняя грань множества (с'х! Ах=Ь, х)0). Доказательство. Рассмотрим множество действительных чисел б=(с'х: Ах=Ь, х)0). Нетрудно показать, что 0 замкнуто (см. задачу 2.10). Поэтому существует точка х, допустимая для задачи ЛП, в которой достигается наибольшая нижняя грань г. Рассмотрим множество точек, удовлетворяющих ограничениям с'х=г, Ах=Ь, (2.5) х'-г О.
Это множество не пусто и состоит из всех оптимальных допустимых решений задачи ЛП. Допустим сначала, что система уравнений в (2.5) имеет ранг т+1. Тогда из теоремы 2.1 следует, что для ограничений (2.6) имеется бдр и по лемме 2.! его компоненты удовлетворяют требуемым ограничениям. Следовательно, ограничения х~М не изменяют оптимального решения задачи ЛП. Осталось рассмотреть случай, когда система уравнений в (2.б) имеет ранг нц В этом случае с' можно представить в виде линейной комбинации ~4а'; строк матрицы А, и стоимость с'х=~;йгЬ| постоянная для всех допустимых точек задачи ЛП. Следовательно, задача ЛП имеет оптимальное бдр, и его компоненты по лемме 2.1 ограничены числом, не превосходящим М. ! ) В соответствии с этим результатом будем далее считать, что Р всегда ограничено. 2.3 Геометрия задач линейного программирования Приведем теперь некоторые важные определения и результаты, относящиеся к геометрическому способу представления задачи ЛП.
2.3.!. Линейные н аффниные пространства. Рассмотрим векторное пространство 1гн. Производное подмножество 5 пространства Йа, замкнутое относительно операций сложения векторов н умножения вектора на скаляр, называется (линейным) подпространством. Подпространство 5 пространства 1тл можно также определить как 1аножество точек в йа, удовлетворяющих системе однородных ли- 38 Ги г. Свмплгкс-алгоритм нейных уравнений; 3 = (х Е !(": ау,х, +... + а „х„О, !' = 1, ..., т), (2.6) Хорошо известно, что каждое подпространство 5 имеет размерность д!п1(5), равную максимальному числу линейно независимых век- торов в нем, Эквивалентное определение дает формула г((ш (Я)=д— — ранг ((аы!), где !а;;! — матрица коэффициентов в (2.6).
Аффинног надпространство А пространства )г" — это линейное подпростраи- ство 5, сдвинутое на вектор и: А= (и+х: х ~ 5). Размерность А та же, что и размерность 5. Эквивалентным образом аффинное под- пространство А пространства Я" можно определить как множество всех точек, удовлетворяющих системе (неоднородных) уравнений А=(хб)с": амх, +... +а „х„=Ь; 1=1, ..., т). Размерность любого подмножества в Ял — это наименьшая размер- ность аффинного подпространства, содержащего это подмножество. Например, любой отрезок имеет размерность 1; любое множество, состоящее из й точек, где и Ы+1, имеет размерность самое большее й — 1.
Размерность множества Р, определенного следующей задачей ЛП (удовлетворяющей предположениям 2.1 и 2.2): ппп с'х, Ах=Ь, А — матрица размера тхд, х>О, не превосходит, таким образом, й — т. 2.3.2. Выпуклые многогранники. Афинное подпространство пространства Р" размерности д — ! называется гипгрплоскостью. Иначе гиперплоскость можно определить как множество точек х, удовлетворяющих равенству а,х,+а,х,+... +а„хл — — Ь, в котором не все а; равны О. Гиперплоскость определяет два (замкнутых) полупространства, а именно множества точек, удовлетворяющих соответственно неравенствам а,х,+ .+азха-эЬ, а,х,+...+авх„~Ь. Полупространство является выпуклым множеством. Следовательно, пересечение полупространства также выпукло.
Пересечение конечного числа полупространств в том случае, если оно ограничено и не пусто, называется вьтуклым многогранником, или просто многогран. ником. Мы будем далее интересоваться только выпуклыми многогран. никами, которые заключены в неотрицательном октанте; другимг словами, мы будем считать, что среди полупространств, опреде 2.8. Геометрия задач линейного программирования ляющих многогранник, всегда есть й полупространств вида хг~ ~О, )=), ..., 2.
Пример 2.3. Трехмерный многогранник Р на рис. 2.1 образован пересечением полупространств, задаваемых неравенствами (2.7). х,+ ха+хе <4, хг (2, хе<3, Зхе+хе ( б, х, . О, ха ~О, "а Рис. 2Д, 3-мерный многогранник из примера 3.3. Как и требовалось, Р ограничен, поскольку легко показать, что он полностью содержится в кубе О~хо х„хе~3. Д Пусть Р— выпуклый многогранник размерности ег и НЗ вЂ” полупростоаиство, определенное гиперплоскостью Н.
Если пересечение Г=РП НБ является подмножеством Н (другими словами, Р и Гл. 2. Симл»«к«.алгоршлм НБ только «касаются своими внешностями»), то ! называется гранью Р и Н называется опорной зиперплогкоогпьв, определяющей !'. Мы специально выделяем три типа граней. Гипергрань — грань размерности й †!. Вершина — грань размерности О (точка). Ребро — грань размерности ! (отрезок). Пример 2.3 (продолжение). На рис, 2,2 показаны многогранник Р и три гиперплоскости Н„Н, и Н„которые определяют соответственно три грани: гипергрань, ребро и вершину.
Г) кг Р«бр« Рас. 2.2. Следующее замечание интуитивно довольно очевидно и его легко строго доказать [Огц, Кос, ЮГ!. Гиперплоскость, определяющая гипергрань, соответствует определяющему полупространству многогранника. Обратное утверждение не всегда верно: если мы добавим к полупространствам, определяющим Р, полупространство х» (2, то Р останется тем же самым. Однако новое полупространство не будет определять гипергрань (оно будет, однако, определять ребро— 2,3. Геометр«я задо«ляяеаноч лрогроямлрооолля 4! отрезок [(О, 2, 0), (2, 2, О)!).
Интуитивно ясно, что причина состоит в том, что условие х«ч:2 излишне в определении Р. Вершина — это «угол» многогранника, что мы уже использовали ранее с меньшей строгостью. Ребро — это всегда отрезок, соединяющий две вершины. Не каждая пара вершин определяет ребро. Например, отрезки [(О, О, 3), (2, 2, 0)[ и [(1, О, 3), (2, 2, О)! не являются ребрами.
Другой ггигуггтивно довольно очевидный факт, который, правда, труднее доказать, состоит в том, что каждая точка многогранника Р является выпуклой комбинациеи его вершин; можно на самом деле показать, что всегда достаточно четырех вершин (г[+! вершин для размерности д). Например, точку (1, 1, 1), которая лежит внутри Р, можно представить в виде (1, 1, 1)=(1!2)(2, 2, 0)+(!г3)(0, О, 3)+ +(!гб) (О, О, 0). Сформулируем теперь общую теорему Теорема 2.3 Игц, г«ос, Юп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
