В.А. Артамонов - Линейная алгебра для экономистов (1129135), страница 2
Текст из файла (страница 2)
Пусть K выпукло и P, Q ∈ K. По−−→−−→упражнению 1.33 конус K содержит точку O + ( 21 OP + 12 OQ) и14В. А. Артамоновпоэтому содержит точку−−→ −−→1 −−→ 1 −−→O + 2( OP + OQ) = O + (OP + OQ).22−−→Обратно, если выполнено указанное условие, то O + αOP , O +−−→(1 − α)OQ ∈ K в силу определения 1.3. Таким образом, по предположению−−→−−→O + αOP + (1 − α)OQ ∈ K,т. е. [P, Q] ⊆ K. Итак, конус K выпуклый.¤Определение. Конус K с вершиной O порождается точками A1 , .
. . , Am , если он состоит из всех точек вида O +P −−→i λi OAi , где λi > 0. Конус K конечнопорожден, если он порождается некоторым конечным множеством точек.Предложение 1.5. Конечнопорожденный конус являетсязамкнутым выпуклым множеством.Доказательство. В силу предложения 1.4 конус K является выпуклым. Докажем его замкнутость. Пусть конус Kс вершиной в точке O порождается точками A1 , . . . , Am . Рассмотрим точку−−−→−−−→O + λ1 OAi1 + · · · + λk OAik ∈ K, λj > 0.(1)−−−→−−−→Предположим, что векторы OAi1 , . . .
, OAik линейно зависимы−−−→−−−→и α1 OAi1 + · · · + αk OAik = 0. Без ограничения общности можнопредполагать, что, например, α1 > 0. Выберем индекс t так,чтобы θ = αλtt было бы минимальным положительным числомсреди всех αλtt , где λt из (1), αt > 0. Тогда в (1) получаем−−−→−−−→O + λ1 OAi1 + · · · + λk OAik =−−−→−−−→O + (λ1 − θα1 )OAi1 + · · · + (λk − θαk )OAik ,причем все коэффициенты λj − θαj > 0, и один из этих коэффициентов равен нулю. Таким образом, точка (1) лежитв конусе, порожденном Ai1 , .
. . , Ait−1 , Ait+1 , . . . , Aim . Отсюдавытекает, что каждая точка из K лежит в некотором конусеKj1 ,... , js , порождаемом точками Aj1 , . . . , Ajs , причем векторы−−−→−−−→e1 = OAj1 , . . . , es = OAjs независимы. Дополним эти векторыЛинейные неравенства15до базиса e1 , . . .
, en всего линейного пространства и возьмемточку O в качестве начала координат. Тогда в этой системе координат конусе Kj1 , ... , js задается неравенствами и уравнениями x1 > 0, . . . , xs > 0, xs+1 = · · · = xn = 0. Следовательно,конус Kj1 , ... , js замкнут. Так как исходный конус K являетсяобъединением конечного числа замкнутых конусов, то он самзамкнут.¤Теорема 1.6. Пусть K – конус с вершиной в O, порождаемый точками A1 , . .
. , Am и точка A не лежит в K. Существует такая линейная функция f , что f (x) > 0 для всехx ∈ K, f (O) = 0, и f (A) < 0.Доказательство. По предложению 1.5 конус K выпуклый и замкнутый. По теореме 1.1 существует ближайшая к Aточка B ∈ K. Пусть e1 , . . . , en – базис, и f = x1 – линейнаяфункция, построенная в теореме 1.1. Покажем, что f (O) = 0.Пусть это не так, т. е. f (O) > 0.
Рассмотрим плоскость OAB(см. Рис. 1.2). Тогда ∠OBA тупой. Следовательно, перпендикуляр, опущенный из A на прямую OB пересекает ее в точке C,лежащей на луче OB, причем точки C и O лежат на этом лучепо разные стороны от B.t`````O```Ke16```````t`t``B ¥ C ````¥¥¥A t¥```Рис. 1.216В. А. Артамонов−−→−−→Отсюда OC = λOB, λ > 1, и поэтому C ∈ K. Но |AC| <|AB|, что противоречит выбору B. Полученное противоречиедоказывает теорему.¤Предложение 1.7. Пусть K – конус с вершиной O, порожденный точкамиA1 , . . . , Am ∈ An .(2)Пусть N – компактное выпуклое множество, не пересекающееся с K.
Тогда существует такая линейная функция f , чтоf (x) > 0 для всех x ∈ K, и f (y) < 0 для всех y ∈ N .Доказательство вытекает из предложения 1.5 и теоремы 1.2.Определение. Выпуклым многогранником, порожденнымточками (2), называется наименьшее выпуклое множество, содержащее эти точки.Обозначим через conv{A1 , . . . , Am } множество всех точеквида()mX−−→−−−→O + λ1 OA1 + · · · + λm OAm | λi > 0,λi = 1 ,i=1nгде O ∈ A .Предложение 1.8.
Пусть M – выпуклый многогранник,порожденный точками из (2). ТогдаM = conv{A1 , . . . , Am }.Доказательство. Положим N = conv{A1 , . . . , Am }. Тогда N содержит все точки Ai при 1 6 i 6 m. Кроме того, оновыпукло. Действительно, если 0 6 α 6 1 и заданы две точки−−→−−−→O + λ1 OA1 + · · · + λm OAm ∈ N,−−→−−−→O + µ1 OA1 + · · · + µm OAm ∈ N,то точка−−→−−−→O + [αλ1 + (1 − α)µ1 ] OA1 + · · · + [αλm + (1 − α)µm ] OAmтакже лежит в N , поскольку все коэффициенты αλj + (1 − α)µjнеотрицательны и в сумме дают 1. Итак, M ⊆ N .Линейные неравенства17Докажем обратное включение N ⊆ M индукцией по m.Случай m = 1 очевиден, ибо тогда M = N = {A1 }.
Пусть дляm − 1 утверждение доказано. Рассмотрим произвольную точку−−→−−−→O + λ1 OA1 + · · · + λm OAmиз N . Можно считать, что 1 > λm > 0. Пусть µ = λ1 + · · · +λm−1 . По предположению 1 > µ > 0. В силу индукционногопредположения точкаλ1 −−→λm−1 −−−−−→O + OA1 + · · · +OAm−1µµλлежит в M , поскольку все коэффициенты µj неотрицательны−−−→и в сумме дают 1. По условию Am = O + OAm ∈ M .
Следовательно, в силу выпуклости M получаем, что M содержит−−→−−−→O + λ1 OA1 + · · · + λm OAm =µ¶−−−→λ1 −−→λm−1 −−−−−→O+µOA1 + · · · +OAm−1 + (1 − µ)OAm .µµ¤Определение. Пусть задана система аффинных (линейных) неравенствf1 (x) > 0, . . . , fm (x) > 0,(3)Эта система совместна, если она имеет решение. Аффинное(линейное) неравенство f > 0 является следствием (3), еслидля любого x ∈ An из того, что выполнено (3) вытекает f (x) >0.Теорема 1.9 (Фаркаш). Аффинное (линейное) неравенство f > 0 является следствием совместной системы аффинных (линейных) неравенств (3) тогда и только тогда, когдасуществуют такие неотрицательные числа c0 , . . .
, cm , чтоf = c0 + c1 f1 + · · · + cm fm .Доказательство. Достаточно показать, что следствие fимеет указанное представление. Зафиксируем систему координат O, e1 , . . . , en Pв An . Тогда каждую аффинную функцию а(X) = a0 +i ai Xi можно отождествить с точкой18В. А. Артамонов(a0 , . . . , an ) ∈ Rn+1 . Пусть при этом отождествлении функциямf = u0 + u1 X1 + · · · + un Xn ,fi = ai0 + ai1 X1 + · · · + ain Xn ,i = 1, . . .
, m,сопоставляются, соответственно, точкиf 7→ (u0 ,u1 , . . . , un );f1 7→ (a10 , a11 , . . . , a1n );....................................fm 7→ (am0 , am1 , . . . , amn ).Все функции g, представимые в виде c0 +c1 f1 +· · ·+cm fm , ci > 0,образуют конус K в Rn+1 с вершиной в нуле, порождаемыйточками(a10 , a11 , . . . , a1n ),............(am0 ,(1,am1 , . . . ,0,... ,amn ),0)Пусть f ∈/ K. По теоремеPn 1.6 существует такая линейная функция v(y0 , . .
. , yn ) = i=0 vi yi на Rn+1 , что v(z) > 0 для всехz∈K иv(u0 , . . . , un ) < 0.(4)В частности, v(1, 0, . . . , 0) = v0 > 0. Предположим сначала,что v0 > 0. Для любого i = 1, . . . , m имеемfi (v0−1 v1 , . . . , v0−1 vn ) = v0−1 v(a10 , . . . , a1n ) > 0.Так как f является следствием, тоf (v0−1 v1 , . . . , v0−1 vn ) = v0−1 v(u0 , . . . , un ) > 0,что противоречит (4).Итак, v0 = 0. При этомnXaij vj > 0,j=1nXj=1uj vj < 0.i = 1, . . .
, m;(5)(6)Линейные неравенства19Так как система неравенств (3) совместна, то существует такойвектор (x1 , . . . , xn ) ∈ An , чтоXfi (x1 , . . . , xn ) = ai0 +aij xj > 0, i = 1, . . . , m.(7)iВыберем такое вещественное число µ > 0, чтоf (x1 + µv1 , . . . , xn + µvn ) =XXu0 +ui xi + µ(ui vi ) < 0.i(8)iЭто возможно в силу (6). Для любого i = 1, . .
. , m по (5) и (7)имеемfi (x1 + µv1 , . . . , xn + µvn ) =Xfi (x1 , . . . , xn ) + µ(aij vj ) > 0,jчто противоречит (8). Но тогда f > 0 не является следствиемнеравенств (3).¤Следствие 1.10. Система линейных неравенств (3)несовместна тогда и только тогда, когда существуют такиеPm неотрицательные числа c0 , . . . , cm , что c0 > 0 и c0 +i=0 ci fi = 0.PДоказательство. Пусть fi (x) = ai0 + j aij xj . Рассмотрим в An+1 систему линейных неравенствXaij xj > 0.ai0 x0 +jОна совместна, поскольку нулевой вектор является ее решением. Для любого решения (x0 , . . .
, xn ) этой системы имеем x0 6−10. Действительно, если бы x0 > 0, то набор (x−10 x1 , . . . , x0 xn )являлся бы решением исходной системы неравенств, что невозможно. Итак, неравенство −x0 > 0 является следствием исходной системы неравенств. Поэтому в силу теоремы ФаркашаXX−x0 = c00 +ci (ai0 x0 +aij xj ), c00 , ci > 0.(9)ijСравнивая свободные члены в левой и правой частях (9) полу¤чаем c00 = 0.
Остается в (9) положить x0 = 1.20В. А. АртамоновИз теоремы Фаркаша 1.9 и следствия 1.10 вытекаетСледствие. Пусть A – матрица размера m × n, x – столбец неизвестных высоты n и b – столбец свободных членов высоты m. Тогда либо система неравенств Ax+b > 0 совместна,либо существует такой столбец c > 0 высоты m, что t Ac = 0и t bc < 0.Доказательство. ПустьA = (aij ), t b = (b1 , . . . , bm ), t x = (x1 , . . . , xn ),Pfi (x) = j aij xj + bj , i = 1, .
. . , m.Система неравенств Ax + b > 0 имеет вид (3). Если эта системанесовместна, то существует такой столбец c =t (c1 , . . . , cm ) > 0,и положительное число c0 , чтоPPP0 = с0 + i ci fi = c0 + i ci (bi + j aij xj ) =PPc0 + i bi ci + ij ci aij xj = c0 + t bc + t cAx.(10)Так как вектор x произволен, то (10) эквивалентноtbc < t bc + c0 = 0,tAc = 0.¤2. Теорема фон Неймана и ее приложенияПредложение 1.11. Пусть множество N ⊆ An – компактно и выпукло, N 0 – компактное выпуклое множество аффинных функций на An . Предположим, что для любой точкиa ∈ N найдется такая функция f ∈ N 0 , что f (a) > 0.
Тогдасуществует такая функция f0 ∈ N 0 , что f0 |N > 0.Доказательство. Обозначим через K – множество всехлинейных функций на An , принимающих на N неотрицательные значения. Тогда K является замкнутым выпуклым конусомв линейном пространстве всех линейных функций.Лемма 1.12. Пусть b ∈ An и f (b) > 0 для всех f ∈ K.Тогда b ∈ N .Линейные неравенства21Доказательство. Если бы b ∈/ N , то по теореме 1.1 существовала бы такая аффинная функция f , что f |N > 0 и f (b) < 0.Эта функция f принадлежит K. Получается противоречие сусловием леммы.¤Продолжим доказательство предложения.
Предположим,что K ∩ N 0 = ∅. Выберем в An систему координат O, e1 , . . . , en .КаждаяP аффинная функция f представляется в виде f (x) =a0 + i ai xi . ПоPпредложению 1.7 существует такая линейнаяnфункция h(z) = Pi=0 bi zi на пространстве аффинных функцийnна An , что h(f ) = i=0 bi ai > 0 для всех f ∈ K и h(g) < 0 длявсех g ∈ N 0 . Так как функция f = 1 лежит в K, то h(1) = b0 > 0.−1−1Если b0 > 0, то рассмотримPn −1 точку−1b = (b0 b1 , . . . , b0 bn ) ∈nA . Тогда f (b) = a0 + i=1 b0 bi ai = b0 h(f ) > 0 для всех f ∈ K0и g(b) = b−10 h(g) < 0 для всех g ∈ N .
По лемме 1.12 получаемb ∈ N причем g(b) < 0 для всех g ∈ N 0 , что противоречитусловиям предложения.Pn Предположим теперь, что b0 = 0. В этом случае h(f 0) =i=1 bi ai > 0 для всех f ∈ K и h(g) < 0 для всех g ∈ N . Вчастности, точка b = (b1 , . . . , bn ) 6= (0, . . . , 0). Возьмем точку z = (z1 , . . . , zn ) ∈ N . Для любого µ > 0 и любого f ∈ KполучаемnnXXf (z + µb) = a0 +ai zi + µai bi > 0.i=1i=1По лемме 1.12 точка z + µb ∈ N для всех µ > 0. Но это противоречит компактности N , поскольку b 6= 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
