Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 6
Текст из файла (страница 6)
е. при Л = 1. Если показать, что минимум расстояния от точки Ь до отрезка Ла + (1 — Л) с достигается при 0 < Л < 1, то теорема будет доказана. Для этого рассмотрим квадрат функции) (Л) ( — оо Л ': оо ), выражагощей расстояние от точки Ь до прямой Ла — ' (1 — Л) с, — со < Л < оэ. (Эта функция на отрезке Ла+ (1 — Л) с, 0 < Л < 1, совпадает с ~ (х).) !л. БАзисн!йк, ЛОпустимые и ОптимАльпыг Рвшвния 33 Таким образом, минимум !' (Х) достигается при Х ( 1. Пусть Х= Лэ — зпачепие параметра, при котором ! (х) достигает минимума.
Если О - Хэ ( 1, то точка Хэа + (1 — Хэ) с принадлежит множеству С, что противоречит предположению о наличии минимума фупкции !'(х) в точке а. Если я1е Хэ ( О, то точка Хэа + + (1 — Хе) с ле1кит па пРоДол1конии отРезка ас и мо!кет не пРинадлежать л1ножеству С . Но поскольку функциями' (Х) — выпуклая и она принимает минимальное значение при Хэ ( О, то 1э (1) ) ) /' (О), т. е. ! (а) ) ! (с), что опять-таки противоречит предположепи!о о существовании минимума ~ (х) в точке а. Таким обраЗом, точка с не может лежать по ту же сторону от гиперплоскости Н, что и точка Ь.
° Опорной эиперплоскостью выпуклого множества называется такая гипорплоскость, которая содержит по крайней мере одну точку этого множества и все точки данного множества расположены в одном из полупрострапств, порождаемых гиперплоскостью. 1.5. Базисныет допустимые и оптимальные решения Нас интересует отыскапие неотрицательных решений системы линейпых неравенств (или системы липейных уравнений, полученной эквивалентными прообразовапиями, рассмотренными в 3 1.2). Поскольку нас будут интересовать только такие задачи линейного программирования, у которых существует копечное оптимальное решение, предположим, что выпуклое мноя1ество, задаваемое системой ли11ейпых ограничепий, замкнуто и ограничено.
Так как любая точка замкнутого ограниченного выпуклого множества представима в виде выпуклой линейной комбипации крайних точек этого множества, покажем, что крайние точки соответствуют так называемым базисным реи1епилм. Пусть дана система линейных уравнений Ах = Ь (А есть (т !С п)-матрица). Говорят, что система пикейных уравнений (1) совместна, если она имеет по крайной мере одно решение. Система (1) называется избыточной, если одно из уравнений моя!но выразить в виде линейной комбинации остальных.
Система (1) несовместна, если ранг матрицы А равеп г, а ранг матрицы [А, Ь] больше г. Если система (1) пеизбыточна и совместна, то ранг А равен и (т ( и). Если !и ) п и система пеизбыточна, то регпепий пег. Далее мы будем предполагать, что система совместна и неизбыточна. Иначе говоря, предполагается, что выбрана неизбыточпая подсистема уравнений, эквивалентная данной. Пусть А =- (В, Ы), где  — певырои1депкая квадратная матриЦа, и пУсть х = !хв~ хк), гДе хв — воктоР с !и кол1понентаэ1и 3 т.ху гл. ь основнык понятия и хя — вектор с п — т компонентами. Тогда, если положить хз —— В 'Ъ и хя = О, получим решение системы Ах = Ъ, называемое базисным решением.
Компоненты вектора хз называются базиснами переменными, а компоненты хя — яебазисвыми переменными. Базисное решение называется оырожденнызг, если одна или более компонент вектора хз равна пулю. Вектор-столбцы матрицы В нааываются базисными векторами. Иногда будем говорить, что т независимых столбцов матрицы В образуют базис. Дадим общее определение базисного решения системы (1), где А есть (лг х и)-матрица (ид ~ и).
Решение х системы (1) называется базисным решением, если вектор-столбцы, соответствующие ненулевым компонентам х, линейно неаависимы. Идея бааисных решений окааызается полезной применительно к системам линейных неравенств. Мы могли бы, конечно, добавив слабые переменные, превратить неравенства в уравнения и затем применить к ним данное выше определение. Однако моясно рассмотреть неравенстза непосредственно.
Система линейных неравенств совместна, если она имеет хотя бы одно решение. Если одно из неравенств системы является следствием других, то система иабыточна. Пусть Ах ) Ь, х - .О— система линейных неравенств, где А есть (т х и)-матрица. Таким образом, в системе имеется т + и неравенств. Если система совместна, то опа определяет непустое выпуклое мноигество.
Базисным допустимым решением является крайняя точка выпуклого мнонгества, в которой по крайней мере и из и + лг неравенств выполняются как равенства. Более того, эта точка удовлетворяет и остальным т неравенствам. Каждое неравенство определяет замкнутое полупрострапство но одну сторону от гиперплоскости. Если в крайней точке пересекается более и гиперплоскостей, зта точка дает вырожденное базисное решение. Это один из способов, геометрически поясняющих понятие вырожденности. Если точка удовлетворяет л неравенствам как равенствам, а остальным неравенствам не удовлетворяет, то она представляет собой точку пересечения и гиперплоскостей, не принадлежащую выпуклому мнои'еству.
Рассмотрим систему неравенств — хг-'г 2хг~ 8, х, ч хг(10, 2х1+ хг -16, х, (6, х1 >О, х «О. Выпуклое множество, определяемое этой системой неравенств, показано на рис. 1.6. Заметим, что в точке хг = 6, х, = 4 пересе- 4 З. БАЗИСНЫЕ, ДОПУСТИМЫЕ И ОПТИМАЛЬНЫЕ РБШННИЯ 3Ь каются три гиперплоскости, т. е. неравенство 2х4 + х, ( 16 является следствием неравенств х, ( 6 и х, + хг ( 10. Точка, получаемая при решении системы двух уравнений — х, + 2хг = 8 и х, + хг = 10, является невырожденным решением. Точка, лежащая на пересечении х, = 6 и х, = О, также является невырожденным решением. Но если выбрать из трех уравнений любые два, то их решение будет всегда выровненным. Представим рассмотренные неравенства в виде равенств, введя неотрицательные переменные: — х4-~-2хз )-г4 =8, х,+ хз +гз =10, 2х4+ хз 1г, =16, х 4 -!-г =6, 4 х4, хг)0, г4, гз, гз, г4)0.
Заметим, что пересечение гиперплоскостей — х, + 2х, = 8 и х, + хг = 10 дает точку х, = 4, х, =. 6, г4 = О, г, = О, гг — — 2, г, = 2. Пересечение гвперплоскостей х, = 6 и х, = 0 задается решением т, = 6, х, = О, М г4=14,г,=4, ге=4, З,=О, В обоих случаях имеется по четыре ненулевых компоненты вти решения невыро4кденьь 4 левых компоненты, следова- х, тельно, решение вырождено. Очевидно, если система (1) Р и с.
1.6. имеет решепие, а вектор-столбцы матрицы А обраауют линейно зависимую систему, то любой вектор атой системы можно представить в виде линейной комбинации остальных. Исключив таким образом линейно зависимые векторы, мы получим базисное решение. Этот результат оформим в виде следующей теоремы. Тхогвмл 1.8. Если система линейных ураене44ий имеет решение, гко она имеет и базисное решение. Решение системы линейных уравнений называется допустимым, Если все его компоненты неотрицательны.
Докажем важное обобтцение теоремы 1.8. гл. !. основныв понятия 66 Твогвмл 1.9. Если система, линейных уравнений обладает допустимым решением, то она ил!лет и базисное допустимое решение. Доклзаткльство. Рассмотрим систему ~~ х;а;=Ь, з.— ! х,)О (?=1, ..., и), (2) Доказательство проведем индукцией но,?с — числу столбцов ар При й = 1 теорема очевидна. Допустим, что она справедлива для й ( и, и дока кем теорему для и =- п.
По условию теоремы существует допустимое решение хе = (х'„..., ха) системы (2). Если хоть одно х,' = О, то мы сразу приходим к случаю й ( и — 1. Поэтому будем считать, что все х, ') О. Итак, ч~', хза,=Ь, х,')О, ?=1, ..., п. (2а) з=! Если система векторов аз, ..., а линейно независима, то решение х' является базисным и теорема доказана. Если же векторы аз,..., а„линейно зависимы, то существуют такие числа Лп пе все равные нулю, что ~~~ Лта~ = О, з 1 (3) . 0= шах —,' =- —," ) О. (4) еЯ х! ! Умножая (3) на — и вычитая полученное разепство из (2а), приходим к равенству (б) В силу (4) выраязение (5) есть представление вектора Ь в виде неотрицательной линейной комбинации векторов аз, причем Можно считать, что среди чисел Л; есть положительные (в про- тивном случае дбстаточно умножить (3) на — 1).
Среди положи- тельных Лз выберем то, при котором отношение —, будет, макл! симальпым. Е?е теряя общности„можно считать, что зто будет —, Лзз Обозначим его через О. Очевидно, 0)О, поскольку Л„и х,', поло- жительны. Итак, ! 5, ВАзисные, допустимык и оптимАльн1*1к Рвшения 37 коэффициент при аа равен нулю. Отсюда т. е.
из (2а) следует существование допустимого решения системы (2) при й ( и — 1. Остается воспользоваться, индуктивным предположением. Индукции завершена и теорема доказана. ° Ткогкмл 1.10. Совокупность всех допустимых решений системы (1) есть выпуклое множество "). )Доклздткаьство. 1Пусть (х! 1и ) хз — произвольные допустимые решения, т. е. Ах, = Ь, хе~0; Ах, = Ь, хз)~0.
Тогда для О ( А С 1, Ах! + (1 — А) х, )~ О, поскольку каждое слагаемое пеотрицательно. Более того, А (Хх! + (1 — Х) х,) = ХАх! + (1 — Х) Ах,= Ь, т. е. Хх! + (1 — Х) х, — такеке допустимое решение. Теорема доказана. ° Покажем теперь, что базисное допустимое решение соответствует крайней точке выпуклого многогранника. В и-мерном пространстве Е" рассмотрим выпуклый многогранник Т: Т= (Х)а!Х(Ь1, 1=1, ..., т), т еП. (6) Мпозкество гр с=' Т пазываотся р-мерной гранью многогранника Т, если 1) гр совпадает с множеством решений системы Ах=Ь ,ранга (п — р), получающейся из (6) превращением соответствующих неравенств в равенства; 2) любое другое условие из (6), выполняющееся на гр как равенство, линейно зависит от системы Ах = Ь. Грань нулевой размерности многогранника Т называется вершиной; это соответствует размерности р = О.
Таким обрааом, необходимым и достаточным условием существования вершины в Т 1) Посксльху узловая задачи линейного ярограмипровапвя всегда можно записать з виде свстемы линейных уравнений, все переменные хоторой нсотрвцательвы, то теорему 1,10 можно сформулировать и тзю ыпожзстзо решение задачи линейного программирования выпукло.— Прил. дед.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
