Раздел: Документация
0 ... 31 32 33 34 35 36 37 ... 162 Т15.3. Для любой предельной точки М0 множества X имеется последовательность точек в X, отличных от сходящаяся к Т15.4. Доказать утверждение 15.4. TI5.5. Доказать следствие 15.1. Т15.6. Доказать следствие 15.2. TI5.7. Доказать следствие 15.3. Т15.8. Доказать утверждение Т15.3. Ответы, указания, решения Т15.1. Обратное утверждение не всегда верно. Контрпример: пусть X - круг в пространстве Af~ с выколотым центром Тогда предельная точка, не являющаяся граничной и внутренней. Обратное утверждение верно, если Xзамкнуто. Т15.3. Пусть {е„} - произвольная последовательность положительных чисел, схо-дяшаяся к нулю. Тогда в каждойточки найдется хотя бы одна точ- каМ„ шзХ, отличная отМ0, откуда {М„\ -» М0, таккак {Б,,} 0. Т15.4. Указания. Воспользоваться следующим: пусть М- изолированная в.Xточка, а {Мц} - произвольная последовательность точек вХ, сходящаяся к М\ тогда найдется точка такая, что все следующие за ней точки последовательностибудут совпадать с Указание: воспользоваться теоремой Указание: воспользоваться утверждением, что пересечение любого числа замкнутых множеств является также замкнутым. Указание: воспользоваться тем, что линейные функции непрерывны. Если точка являетсяв X, то очевидна и последовательность точек из X, сходящаяся к это последовательность.... Пусть теперь предельная точка множества X, Выберем произвольную числовую последовательность различных положительных чисел, сходящуюся к нулю. По определению предельной точки, в каждойточки существует бесконечно много точек из Выберем среди них точку Мк, отличную от Л/. Так как {Ej,}--> 0, то и {Мк}->М, что доказывает существование сходящейся к последовательности точек из X. Пусть теперь некоторая последовательность {М*} точек из Xсходится к А/. Предположим также, что М не является предельной точкой множестваX. Это означает существование некоторой б-окрестности точки М, в которой может оказаться только конечное или пустое множество точек из X. Если в этой окрестности нет точек из X, помимо точки М (возможно, принадлежащей X), то положим б = е. В противном случае выберем среди них отличную от точку N, ближайшую к и положим равным расстоянию между и N. Очевидно, 5-окрестность точки не содержит точек из X, кроме, быть может, точки Нопоэтому найдется такая точка что все следующие за ней точки Mr+],Mri окажутся в 5-окрестности точки М. Это возможно, только если точки ММг- з, ... совпадают с М, т. е. МЖ, следовательно, М является изолированной в X. Глава 16 find Строение множества планов задачи линейного программирования Рассмотрим следующую задачу условной оптимизации: целевая функция fix\,Xi, х„) = DXT-> max, а множество планов задается системой j/LY1 =С JJT >0 где D - (с/,..., с/Д jV-(д:],.., л"„), А - (16.1) (16.2)
Иногда вместо записи АХ = Сбудем использовать одну из векторных форм (3.2): jr, +...+ .v„A„ =с(16.3) где С1 = (С[, Ст), 6/ = {ри,, Язь", 0,„t), А = 1, п. В этой задаче и целевая функция / и множество планов задаются линейными функциями (соответственно соотношениями (16.1) и (16.2)) и поэтому данная задача называется задачей линейного программирования (сокращенно ЛП). Множество планов задачи является полиэдром. Существуют различные формы записи задачи ЛП, которые являются эквивалентными в том смысле, что с помощью несложных равносильных преобразований нетрудно перейти от одной формы записи к другой. С практической точки зрения различия между этими формами теряют принципиальное значение благодаря эффективным компьютерным методам решения задач ЛП. Однако для теоретических исследований удобно использовать каноническую форму, приведенную выше. Лемма 16.1. Пусть в условии (16.2) матрица С имеет хотя бы один ненулевой элемент. Тогда точка а является вершиной полиэдра планов, определяемых условиями (16.2), если и только если столбцы матрицы .4, соответствующие ее положительным координатам, линейно независимы. Доказательство. Не теряя общности, будем считать, что положительными являются первые координат точки =0, ... , 0) (Это предположение будем использовать и дальше, специально его не оговаривая). Из условия, наложенного на С, вытекает, что Для точки а равенствозапишется в виде a ib, +... + a"Tb/=c. Пусть первые г столбцов матрицы А линейно независимы, но точка а не является вершиной полиэдра. Тогда (см.существуют такие различные планы Р - ф\, Р„) и у = (уь у„), что ос = Л.р + (I - )удля некоторого числа л. 6 (0, 1). Отсюда имеем систему равенств: 0 = >.р,- 2+ (1 ~k)ytl 0 = Хр„+(1 -Х)т„ Поскольку X> 0, 1 - X> О, Р; > 0, у, > 0, / = г + 1, п, то из этих равенств следует, что Р/ =у i = 0, / = г + 1, п. Поэтому р = (рь Рз, .... Рг, 0, ...,0),У = (у,, y2.....Yr, 0.....0),"0,6, +.+.р".=с , у,Ь( +... +Yrbr=c. Вычтем почленно последние два равенства: (Pi -У)Ь +... + (рг-уг)=0? Отсюда ввиду линейной независимости системы векторов В],...,Вг следует, что 0, - у, = 0, ...,Р,.-уг=0 (следствие 5.3). Поэтому точки а, Р, у совпадают. Получено противоречие. Пусть теперь векторы-столбцы Ь,,линейно зависимы, но точка а является вершиной полиэдра планов, В этом случае из следствия 5.3 вытекает, что система уравнений >>,£, +... + угЬ=0 имеет ненулевое решение (Рь р,.). Обозначим через Р = (Рь Р„ 0, 0) точку из Af. Покажем, что точки а±и.р являются решением системы АХТ = С при любом числе ц. Действительно, согласно теореме 3.1, А{ a ± цР)т=Лат+цЛ/?т= С ± цО = С. Так как > 0, 1, ... , то можно подобрать настолько близким к нулю (но неравным нулю), что все координаты точек окажутся неотрицательными. В этом случае +различные планы задачиНо 0.5(а+ р)- Р) = а, т.е. точка а не может быть вершиной полиэдра планов (см. задачу Получено противоречие. Лемма доказана. В случае, когда 0, к вершинамописанным предыдущей леммой, добав- ляется точка а = (0, 0,... , 0) (см. задачу 0 ... 31 32 33 34 35 36 37 ... 162
|
