Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 4
Текст из файла (страница 4)
— у~~ уж~ (11) Если бы система (10) имела неотрицательное решение х', ) О, 1 = 1,..., и — 1, то в силу (8) коэффициент при а, в (11) был бы положителен. Тогда, очевидно, система (3) имела бы неотрицательное решение нопрекн предположени1о. Итак, система (10) не имеет неотрицательных решений. Применяя индуктивное предположение к системе (10), получаем: существует такои у', что у'а,')О при 1=- 1, ..., п — 1 и у'Ь' (О. (12) Полагая теперь уап у =- у — = у уаи легко убеждаемся в топ, что уа,= (у' — =" у) аз= у'а,— ="уа;= / уап у а =у' ~а; — ='а„) =у' а~)0 (~=-1, ..., п — 1) уа„ (в силу (12)); уа„= (у' — =" у) а„—.
у'а„— — "уа„=О, уа„) уа„ так как в рассматриваемом случае уаа(0; УЪ= (ул — =" у) Ь=- у' (Ь вЂ” ="УЬ) =у'Ъ'(О уа„ уа„ (в силу (12)). Таким образом, вектор у является решением системы (4). 1!пдук- ция 'завершена и теорема доказана, ° Ах< Ь Ткогкма 1.3. ( Лемма Минковского — Фаркаша о неотрицательном решении системы линейных неравенств.) Выполняется только одпа ив следуютих альтернатив.' либо система неравенств гл, ь основные понятия имеемся неотрицательное решение, либо неотрицательное решение имеет система уА)0, уЬ(О.
Доклзхтзльство. Пусть А* — произвольная (т и н)-матрица. По теореме 1.2 либо А*х* — — Ь имеет неотрицательное решение, либо имеет решение система норавенств уАе ) О, уЬ ( О. Положим А* —.. [А, И, х" .—. [х, з[. Тогда теорему 1.2 можно сформулировать следующим образом( а) либо система уравнений Ах+ 1з=Ь имеет решение х ) О, з ) О, б) либо имеет решение система неравенств уА)0, у1)0, уЬ(0. Следствие 1.1. Из двух систем линейных неравенств Ах ) Ь, [уА<0, [уЬ) О (13) (14) одна и только одна имеет неотрицательное решение. Тковвмь 1.4.
Система неравенств (15) Кх)0, х)0, где Кт' = — К, имеет но крайней мере одно такое решение х, что Кх+ х)О. Доказьткльство. Через К; обозначим 1и1о строку пз К. Докажем, что существует такой воктор х~ = [хм, хоь ..., хн...., х~[, что Кх;+хн- О, Кх; ~ хм)0. (16) 11о утверждение (а) эквивалентно тому, что Ах ( Ь имеет неотрицательное решоние, а утверждение (б) эквивалентно тому, что уА 0 и уЬ ( О имоет неотрицательное решение.
Теорема доказана полностью. ° Поскольку теорема 1.3 верна для любых А и Ь, мы можем заменить А и Ь на — А* и — Ь". Затем умножим обе части неравенств на — 1, что изменит смысл неравенств на противоположный. Освободившись от (е), оформим полученный результат в виде следствия, 1 1 КОНУСЫ, ВЫПУКЛЫГ МНОЖЕСТВА Н ВЫНУКЛЫЕ ФУНКЦИН 23 Положим в следствии 1 1 Ь .= е; и А = К.
Если неотрицательным решением обладает система (13), то существует такой х1) О, что Кх1)еь К;х;)1, К1х1 ~0 (1 ~ 1). Следовательно, К;х;+хи-- О, К~х1+хм)0. Если пеотрицателыкю решение имоется у системы (14), то существует х; )О, такой, что т тке-О (зто равносильно любому из следующих неравенств: Ктх, О, — Кх1 » ~О, Кх1) 0), и соотвотственно — г х1е)0, т. е. хн)0 и х )О, откуда, как и выше, получаем соотношения (16). Итак, в обоих случаях К1х;+хи )О и К,х; ~-г11)0 (1чь)).
Пусть в следствии 1.1 Ь последовательно принимает значения е1, ем ..., еь ..., е„, а х1, ..., х„суть соответствующие им решения. Тогда х = = ~ х1 будет искомым решенном (17), для которого выполняется 1=1 Кх-1-х > О. 1.4. Конусы, выпуклые множества и выпуклые функции Каждый вектор с п компонентами соответствует точке и-мерного евклидова пространства. Компоненты вектора совпадают с координатами точкп. Пусть дан вектор а; множество точек прятюй, содержащей начало координат и данный вектор, может быть аналитически задано как (х ) х = Ла, Л ~ О). Будем называть лучом полупрямую с одним концом в начале координат, а другим — уходящим з бесконечность. Луч, выходящий из начала координат и содержащий вектор а, есть множество (х)х=Ла, Л г:0).
Часть прямой, заключенная между двумя точками, вместе с этими точками называется отрезком. Отрезок от точки а до точки Ь можно представить как множество в виде (х ! х = Ла + (1 — Л) Ь, 0 ~ Л ~ 1). гл. к основныв понятна По аналогии с плоскостью в трехмерном пространстве, гнперплоскость в Е" определяется как множество точек (х ~ ах = а). Замкнутое полупространство, состоящее нз гиперплоскостп и точек, расположенных по одну сторону от этой гиперплоскости, будем обозначать (х ) ах «а). Лонусом С называется множество точек, таких, что если хЕС, Х~«0, то ХхЕС. Пример 1. Лгобая прямая, проходящая через начало координат, является конусом; в качестве х можно выбрать:побой вектор, принадлежащий прямой.
Пример 2. Любая полупрямая, проходящая через начало координат, является конусом. (Останется ли полупрямая конусом, если исключить из нео точку, совпадающую с началом коордкиатП Пример 3. Любая гиперплоскость в Е", проходящая через начало координат, есть конус. Пример 4.
Замкнутое полупространство с граппчной гиперплоскостью, проходящей через начало координат, ость конус. Пример 5. Заштрихованная область на рис. 1.1 есть конус. Пример 6. Заштрихованная область на ркс. 1.2 есть конус. Р к с. 1.2. Р к с.1Л. Пример 7. Множество решений системы Ах «» 0 обрааует конус. ГЛ НОГ!УСЫ, ВЫПУКЛЫЕ МГГО>ГГКСТВА И ВЫПУК ГЫЕ ФУНКПИП 25 Пример 8.
Будут ли конусами отрезок и прямая, проходящая через две дакпыс точкиг (х ~ х = — Ла + (1 — Л) Ь, О = Л ( 1), (х ~х =Ла+(1 — Л) Ъ, — оо - Л со). Множество С точек из Е" называется выпуклым конусом, если выполняются следуя>щио условия: 1) если х, у и С, то х + у и С; 2) если х и С и Л ) О, то Лх и С. Конусы, приведенные в приыерах 1, 2„3, 4 и 6, являются выпуклыми, а конус в примере 5 — невыпуклый, псскольку можно указать два вектора, сумма которых не принадлежит С.
Определим операции пад выпуклыми конусами и установим некоторые их свойства. Если СГ и Сз — выпуклые конусы, то их суммой СГ + Сз называется ынон>ество С>+С =(х(х.=-х>+хз, х>ПСГ, х ПСз). Очевидно, сумма двух выпуклых конусов есть также выпуклый конус. Например, сумма двух прямых, проходящих через начало координат (двух выпуклых конусов) есть плоскость, содержащая эти две прямые. Сумма двух полупрямых есть конус, рассмотренный в примере 6. Если СГ и Сз — выпуклые конусы, то их пересечение СГ П Сз определяется как С, () С = (х ) х ~ С, и х и Сз).
Очевидно, пересечоние двух выпуклых конусов есть также выпуклый копус. Например, пересечение двух полупространств в Ез образует выпуклый конус, покааанный па рис. 1.2. Для выпуклого копуса С определим двойственный еыу конус С* следующим образом: Се = (у ( ух ( О для всех х и С). Двойственный конус состоит из векторов, образующих пеострыо углы с векторами из С (рис. 1.3). В примере 1 двойственным конусом С* является плоскость, перпендикулярная к прямой.
В примере 2 двойственный конус Се — полупрострапство (у ) ух ( О), где х — ненулевой воктор, принадлежащий полу- прямой. Выпуклый конус С называется копен>Гопоролсден>ГЫГм, если он является суммой конечного числа полупрямых: С' = (а>) + (а,) +... + (а„). гл. !. основкык понятия Направляющие векторы этих полупрямых называются образую>цими векторами выпуклого конуса. Из определения суммы выпунлых конусов ясно, что любой вектор в конечнопорожденном конусе можно представить как х=-)>а>+... +)„а„ где )>! ) О и ~ г.; = 1, а> — произвольные направляющие векто>=! ры соответствующих полупрямых.
Будем говорить, что вектор х есть выпуклая линейная комбинация образующих векторов а> (1 = 1, ..., и). Если рассматривать векторы а> Ц = 1,..., и) как вектор- столбцы матрицы А, то множество точек конечпопорожденного конуса моя>но описать следующим обра- С = (у ) у = Ах для х ~~ О), |~Г | т. е. каждый вектор у в копусе являотся неотрицательной линейной комбинацией вектор-столбцов матрицы А. Множество Х называется емпуклим, осли вместе с любыми двумя точками этого множества х! и ха в пем содержится и точка )>х! + (1 — 1.) х„О )>: 1.
11онятие выпуклого множества можно сформулировать в более общем виде. Множество Х называется еыпуклым, если вместе с точками х„..., ха из Х множество Х содержит и точку х> з ь х= У )>хи ) !)О, У )>=1, называему>о выпуклой линейной комбинацией точек х,,..., хю Докажем эквивалентность этих двух определений выпуклого множества.
Очевидно, порвое определение является частным случаем второго. Поэтому множество, выпуклое по второму определению, является выпуклым и по первому. Иядукцией по й покажем, что верно и обратное утверждение. При й = 2 определения совпадают. Предполоя>им, что при й — — т из выпуклости по первому определению следуот выпуклость по второму, и докажем это утверждение при й =- т + 1. 1л, кОнусы, вьц1уБлык множкствл и Выпукл!,!з Функции 27 Рассмотрим произвольные точки х„..., хты из Х и любую их выпуклую линейну1о комбинацию: Х=Л1Х1-сЛчхзч ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
