<<
>>

15.7. НЕКОТОРЫЕ СВОЙСТВА ВЫПУКЛЫХ МНОЖЕСТВ

Изложим здесь важнейшие результаты теории выпуклых множеств, рассмотренной в разделе 11.5. Кроме того, поскольку к ней относится и понятие линейной зависимости векторов и точек, разобранное в разделе 13.1, приведем сначала основные результаты, полученные в этой области.

Линейная зависимость

Пусть в иг-мерномпространстве имеется п точек р^1), р<2> ,..., р<п) (п > иг).

Любая система к этих точек (например, к первых точек) является линейно зависимой, если можно подобрать такие коэффициенты ps, из которых не все равны нулю, что

SmP=o.

s=i

Если линейная зависимость существует, то одна из точек (соответствующая ненулевому значению ps) может быть представлена в виде линейной комбинации остальных точек. Например, если Ф 0, то

s=2

В противном случае система точек является линейно независимой; это значит, что ни одна из точек не является линейной комбинацией остальных. Основной результат выражается следующим положением: (А). Изпточек р*1), р(2> ,..., р<п> в т-мерном пространстве линейно независимыми могут быть не более чем т точек.

Следовательно, если число точек равно иг + 1, то по крайней мере одна точка должна быть линейно зависимой от остальных, представляя собой линейную комбинацию остальных точек. Однако линейная зависимость может существовать даже между т точками.

Пусть система именно т точек, например р^>, р<2> ,..., р<т), является линейно независимой. Эта система образует базис пг-мерного пространства . в том смысле, что всякую другую точку этого пространства можно представить в виде линейной комбинации точек р*91), р<2) р<т). Система, состоящая из большего числа точек, уже не есть базис, поскольку она не является линейно независимой. Не будет базисом и система, состоящая из меньшего числа точек, так как невозможно линейно выразить через них все остальные точки. Примером базиса, к тому же очень удобным, является совокупность т единичных точек на осях координат, которым можно сопоставить единичные координатные векторы er (г = 1, 2,..., т):

(1,0, 0, .

.., 0); (0, 1, 0, ...,0); ...

В дальнейшем мы с большой пользой применяем следующее положение, вытекающее из основного результата. Выделим из п точек p (г = 1, 2,..., т). Тогда каждую точку из р<8) можно представить в виде линейной комбинации т точек р(г>. Обозначим коэффициенты этой линейной комбинации через xrs. Тогда можно сделать следующий вывод: (Б). Если система точек р<г) (г = 1,2, . ..,т) в т-мерном пространстве является линейно независимой, то всякую точку р(«) (5 = 1,2, . . ., п) в этом пространстве можно представить в виде

т

P(S) = 2 *R3P(R).

r=l

где хГз суть некоторые коэффициенты (г = 1,2, . . ., т\ s = 1, 2, . . .

Следует подчеркнуть, что это верно не только при s > т, но и в том случае, если s есть одно из первых т значений, и р<®) является одной из точек линейно независимой системы. В этом случае все значения жГ8 = 0, кроме хгг = 1.

Свойства выпуклых множеств I. Если в т-мерном пространстве заданы точки р и р<8) (5= 1, 2, . . . . . ., п), то точки = . . ., А,п), которые неотрицательны

(Я8>0), удовлетворяют уравнению

5U,P(8) = P

s=l

и составляют гс-мерное выпуклое точечное множество Г.

Далее, если ЕЕ(2\ . . . суть экстремальные точки множества Г, то в применении теории выпуклых множеств к линейному программированию предполагается, что множество экстремальных точек является конечным, и их число равно к. Тогда выпуклое множество Г есть выпуклая многогранная оболочка (полиэдр), порожденная множеством Е^2\ ..., EW. Допустимые решения задачи линейного программирования изображаются точками выпуклой оболочки Г.

Доказательство. Пусть ЛД1) и i,<2> суть две различные точки множества Г, неотрицательные и удовлетворяющие условию:

2 x=P, s x=P.

s=l s—1

Следовательно, при любом fi (0<р,<1)

S=1

И

Значит, если точки М1) и i/2> принадлежат к множеству Г, то к этому же множеству принадлежит и точка рЛ,(1) + (1 — (х)Л/2)1 и, следовательно, множество Г выпуклое. II.

Линейная функция /(h), определенная в некоторой точке h выпуклого множества Г, имеет максимум в экстремальной точке этого множества.

Далее, если функция / (h) имеет максимум только в одной экстремальной точке Е(1), этот максимум является единственным; если же /(h) максимизируется в нескольких экстремальных точках Е(1\ Е(2), .

.., то в таком случае имеется бесконечное множество максимумов, во всех точках выпуклой оболочки подмножества (части множества Г), порожденной точками Е(1), Е(2\ .... Эти два случая соответствуют существованию единственного оптимального допустимого решения и бесконечного множества оптимальных допустимых решений задачи линейного программирования.

Доказательство. Будем считать /(h) линейной функцией, как это имеет место в линейном программировании. Предположим, что функция /(h) имеет максимум в точке h, которая не является экстремальной. Тогда, по определению экстремальных точек, Е(1), Е(2), . . ., Eik) принадлежат к некоторому выпуклому множеству,

k k ^=2 И'гЕ(г) Для некоторой системы р,г>0, 2 Ит = 1-

Г—і Т= 1

Следовательно, поскольку /(h) есть линейная функция,

max/(*,) = І |іг/(Д<») Г=1 г= 1

если в экстремальной точке Еа) достигается наибольшее значение /.

Следовательно, max / (h) < / (E(V).

Здесь возможен лишь знак равенства, и /(h) имеет максимум в экстремальной точке Е(1\ Те же соображения показывают, что если существует несколько экстремальных точек Еа\ Е(2\ .. ., имеющих одно и то же наибольшее значение /, то все эти значения суть максимумы /(h), причем максимум достигается и в любой точке h, являющейся выпуклой линейной комбинацией этих экстремальных точек. III.

Точка Ь = (Ь1? h2, ..hn) является экстремальной для множества Г тогда и только тогда, когда точки p, имеющие положительные веса (hs>0), составляют линейно независимую систему, выделенную из множества p(s) (5=1,2, .. ., и). Остальные p{s) имеют нулевые веса (hs = 0).

Далее, в соответствии с положениями (А) и (J5) для линейной зависимости экстремальная точка множества Г имеет не более чем т положительных весов и не менее чем (п — т) нулевых весов; если число положительных весов равно в точности т, то всякую точку p(s> можно представить в виде:

т

рш=>2 *rSP°v

г= 1

где р(г) (г = 1, 2, . . ., т) имеет т положительных весов.

Доказательство.

Пусть h есть экстремальная точка множества Г, имеющая к положительных весов h1? h2, . .., hft; остальные h нулевые. Так как точка h принадлежит к множеству Г, то, в соответствии с пунктом 1,

2hsp = p, все h3>0. (1)

s=l

Предположим, что точки р(1\ р(2\ . . ., p(fe) —линейно зависимы, так что

S (Ы><8> = 0, (2)

s=i

где не все значения [л3 равны нулю.

Теперь выберем постоянную с, столь малую, ЧТО и + и Ks — (подобно Ks) будут положительны для s — 1, 2, . .., /с. На основе уравнений (1) и (2):

k k S (*.+ЧОР(" = Р чи s (^-<^)P(S) = P-

S— 1 s=l

Следовательно, и = + и h(2) = i, —ср также принадлежат к множеству Г. Однако

что невозможно, поскольку — экстремальная точка множества Г. Значит, линейная зависимость между р(1), р(2), . . ., p(fe) невозможна; эти точки линейно независимы, что и требовалось доказать.

Докажем обратное предложение. Пусть точки р(1), р(2>, . . ., p(/i>, соответствующие к положительным весам точки X множества Г, суть линейна независимы. Предположим, что І, —выпуклая линейная комбинация двух точек %{1) и V2) множества Г:

ь = + (1 - р) Ь(2) (0< р< 1).

Точки и V2) в совокупности имеют лишь к положительных

весов (остальные веса — нулевые), и поскольку все эти точки принадлежат к множеству Г, то

2*.p(s) = p> 2Ws) = p и =

s=l S=1 S=1

k k

Следовательно, 2 - p(s) = 0 и 2 (К — Wf)) P(s> = что ПРИ

s=l S=1

линейно независимых p(s) возможно лишь в случае, если

Значит, % не может быть выпуклой линейной комбинацией ?двух других точек множества Г, то есть % является экстремальной точкой этого множества,— что и требовалось доказать.

<< | >>

Еще по теме 15.7. НЕКОТОРЫЕ СВОЙСТВА ВЫПУКЛЫХ МНОЖЕСТВ:

  1. Глава 4. Множества и отношения
  2. Глава 8. Теория доказательства: пропозициональные правила
  3. РАЗДЕЛ 4. Кривые безразличия
  4. РАЗДЕЛ 1. Классификация и свойства общественных благ.
  5. РАЗДЕЛ 2. Эффективный объем предоставления общественных благ
  6. II. ЛОГИЧЕСКИЕ ПРЕДПОСЫЛКИ ВСЯКОЙ МЕТОДОЛОГИИ 54.
  7. 11.5. ЛИНЕЙНЫЕ КОМБИНАЦИИ ВЕКТОРОВ. ВЫПУКЛЫЕ МНОЖЕСТВА
  8. 13.3. ЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ
  9. 14.7. ОБЩИЙ СЛУЧАЙ ИГРЫ ДВУХ^УЧАСТНИКОВ НУЛЕВОЙ СУММОЙ
  10. 15.7. НЕКОТОРЫЕ СВОЙСТВА ВЫПУКЛЫХ МНОЖЕСТВ
  11. 15.8. СИМПЛЕКСНЫЙ МЕТОД