В.А. Артамонов - Линейная алгебра для экономистов (1129135), страница 5
Текст из файла (страница 5)
, Am . Можно считать, что dim K =n. Пусть O – начало координат и Aj = (aj1 , . . . , ajn ), где1 6 j 6 m. Заметим, что−−→−−−→n = dim K = dimhOA1 , . . . , OAm i =a11 . . . a1nrank . . . . . . . . . . . . . . .(22)am1 . . . amnПредположим, что B = (b1 , . . . , bn ) ∈/ K. Рассмотрим аффинные функцииXfj (x1 , . . . , xn ) =ajt xt , j = 1, .
. . , m.tg(x1 , . . . , xn )=Xbj xt .tПо теореме Фаркаша неравенство g > 0 не является следствиемсовместной системы неравенств (3). Следовательно, найдетсятакая точка z = (z1 , . . . , zn ) ∈ An , чтоf1 (z) > 0, . . . , fm (z) > 0,g(z) = a < 0.Рассмотрим полиэдр P 0 , задаваемый системой неравенствf1 > 0, .
. . , fm > 0,0−g + a > 0.(23)Полиэдр P непуст, так как он содержит точку z. По теоремеФань Цзы и (22) полиэдр P 0 имеет вершину C = (c1 , . . . , cn ).Среди неравенств (23) n линейно независимых функций должны обращаться в нуль. Если n линейно независимых функцийсреди f1 , . . . , fm обращается в точке C в нуль, то в силу определения функций f1 , .
. . , fm , получаем, что точка C – началокоординат. В этом случае −g(C) + a = a < 0, что невозможно. Итак, только n − 1 независимая функция среди f1 , . . . , fm ,обращается в нуль. Кроме того, −g(C) + a = 0.Линейные неравенства35Рассмотрим уравнение h(x) = c1 x1 + · · · + cn xn = 0. Попостроению n − 1 точка среди A1 , . .
. , Am удовлетворяет этому уравнению. Для остальных точек Aj получаем h(Aj ) > 0.Кроме того, h(B) = g(C) = a < 0. Итак, плоскость Π, задаваемая уравнением h(x) = 0 разделяет K и B, причем Π ∩ Kявляется гранью размерности n − 1. Тем самым эти грани определяют полупространства, пересечением которых является K.Эти полупространства связаны с выбором n − 1 независимойточки среди A1 , . . . , Am и проходят через эти точки и началокоординат.¤Теорема.
Конечнопорожденный многогранник являетсяполиэдром.Доказательство. Пусть M – многогранник, порожденный точками A1 , . . . , Am , и Π – наименьшая плоскость, содержащая M . Можно считать, что Π = An . Вложим An в An+1 ивозьмем точку O ∈ An+1 \ An . Пусть K – конус с вершиной O,порожденный точками A1 , . . . , Am . Заметим, что K ∩ Π выпукло с содержит точки A1 , . . . , Am . Следовательно, M ⊆ K ∩ Π.Покажем, что K ∩ Π ⊆ M .
Выберем в An+1 систему коорди−−→нат с началом в O и с базисом e0 , . . . , en , причем e0 = OA1 , и−−−→−−−−→he1 , . . . , en i = hA1 A2 , . . . , A1 Am i. Тогда Π = A1 + he1 , . . . , en i.Рассмотрим точку−−→−−−→A = O + λ1 OA1 + · · · + λm OAm ∈ K ∩ Π,где λ1 , . . . , λm > 0. Тогда−−→−−−→A = O + λ1 OA1 + · · · + λm OAm =Pm−−−→−−→ PO + ( i=1 λi )OA1 + i>2 λi A1 Ai ∈ Π =−−→A1 + he1 , .
. . , en i = O + OA1 + he1 , . . . , en i.PmОтсюда i=1 λi = 1 и A ∈ M по предложению 1.8. Итак, M =K ∩ Π. Поэтому M задается неравенствами, определяющими Kи уравнениями, определяющими Π.¤36В. А. Артамонов4. УпражненияУпражнение 1.33. Пусть X ∈ An . Доказать, что [A, B]−−→−−→состоит из всех точек вида X + αXA + β XB, где α, β > 0, α +β = 1.Упражнение 1.34. Доказать, что замыкание выпуклогомножества является выпуклым.Упражнение 1.35.
Доказать, что полиэдр является замкнутым выпуклым множеством.Упражнение 1.36. Доказать, что каждое замкнутое выпуклое множество задается системой линейных неравенств.Упражнение 1.37. Каждое ли каждое замкнутое выпуклое множество задается конечной системой аффинных неравенств?Упражнение 1.38. Пусть K – замкнутый конус с вершиной O и L – замкнутый компакт, не пересекающийся с K.
Доказать, что существует такая гиперплоскость, задаваемая линейным уравнением f (x) = 0, что f (O) = 0, f (y) > 0 для всехy ∈ K и f (z) < 0 для всех z ∈ L.Упражнение 1.39. Пусть X – выпуклое подмножество вAn , не содержащее точек с положительными координатами. Доказать, Pчто существует гиперплоскость, задаваемая уравнениемnf (x) = i=1 ai xi = 0, причем ai > 0, i = 1, . . . , n, и f (z) 6 0для всех z ∈ X.Упражнение 1.40. Пусть M = { (x, y) ∈ A2 | x > 0, y >}. Доказать, что M выпукло. Найти ближайшую к A = (0, 5)точку B ∈ M .
Найти гиперплоскость, проходящую через точкуB и разделяющую A и M .1xУпражнение 1.41. Пусть M = { (x, y) ∈ A2 | y > x2 }. Доказать, что M выпукло. Найти ближайшую к A = (1, 5) точкуB ∈ M . Найти гиперплоскость, проходящую через точку B иразделяющую A и M .Упражнение 1.42. Пусть M = { (x, y) ∈ A2 | x2 + 2y 2 61 }. Доказать, что M выпукло. Найти ближайшую к A = (1, 5)Линейные неравенства37точку B ∈ M . Найти гиперплоскость, проходящую через точкуB и разделяющую A и M .Упражнение 1.43. Пусть M ⊆ An , причем любую точкуA ∈ An \ M можно отделить от M гиперплоскостью. Доказать,что M выпукло и замкнуто.Упражнение 1.44. Пусть задан конус K ⊆ An с вершиной в начале координат. Двойственным конусом K ∗ называетсямножество всех таких точек z = (z1 , . . .
, zn ) ∈ An , что t zx 6 0для всех точек x ∈ K. Доказать, что1) K ∗ – выпуклый замкнутый конус;2) K ∗∗ ⊇ K;3) K ∗∗ = K, если K – выпуклый замкнутый конус;4) если K – замкнутый выпуклый конус, не содержащий неотрицательных ненулевых векторов, то K ∗ содержит положительный вектор.Упражнение 1.45. Показать, что конечно порожденныймногогранник компактен.Упражнение 1.46. Точка X выпуклого конуса K с верши−−→ −→ной O называется крайней, если из условия X = O+ 12 (OY +OZ),−−→−−→ −→−−→где Y, Z ∈ K, вытекает OY = λOX, OZ = µOX, где λ, µ > 0.Предположим, что конус K выпуклый и замкнутый.
Будетли крайняя точка в K являться угловой и наоборот. Совпадает ли определение крайней точки с определением из главы 1крайней точки K как выпуклого замкнутого множества?Упражнение 1.47. Пусть конус K с вершиной O порожда−−→ется точками A1 , . . . , An , причем если точки X, −X = O + XOлежат в K, то X = O. Доказать, что K порождается крайнимиточками из множества A1 , . . . , An .Упражнение 1.48. Как и в определении 1.21 Точка полиэдра Π называется крайней, если она не лежит внутри любогоотрезка, концы которого принадлежат полиэдру. Пусть полиэдрΠ ⊆ An задается системой неравенств (3), гдеnXfi (x) = bi +aij xj .j=138В. А.
АртамоновПредположим, что x0 ∈ Π и f1 (x0 ) = · · · = fr (x0 ) = 0, r > 0, иfi (x0 ) > 0 при i > r. Доказать, что x0 является крайней точкойΠ ⇐⇒ ранг матрицыa11 . . . a1n. . . . . . . . . . . . .ar1 . . . arnравен n.Упражнение 1.49. Доказать, что каждый полиэдр Π ⊆An содержит конечное число граней.Упражнение 1.50. Пусть полиэдр P задается неравенствами 0 6 xi 6 1, где i = 1, . .
. , 5. Найти все его грани.Упражнение 1.51. Доказать, что ограниченный полиэдрконечно порожден.Упражнение 1.52. Доказать, что ограниченный полиэдримеет вершины.Упражнение 1.53. Соместна ли система аффинных неравенств1 + 2x − 3y > 0,2 + x − 5y > 0,Будут ли неравенства x+y−10 > 0,системы неравенств (24)?−x + 10y > 0.(24)x+y+10 > 0 следствиямиУпражнение 1.54. Пусть A = (aij ) ∈ Mat(m×n, R) и K ⊆An – множество всех таких точек X, что AX 6 0. Доказать, чтоследующие условия эквивалентны для K:1) ранг A равен n;2) если X, −X ∈ K, то X = O.Упражнение 1.55. Пусть конус K с вершиной O = (0, 0)порождается точками A1 = (1, 2), A2 = (1, 4), A3 = (2, 3). Задать K системой аффинных неравенств.Упражнение 1.56.
Пусть многогранник K порождаетсяточками A1 = (1, 2), A2 = (1, 4), A3 = (2, 3), A4 = ( 34 , 2). ЗадатьK системой аффинных неравенств.Линейные неравенства39Упражнение 1.57. Пусть A = (aij ) ∈ Mat(m × n, R) иc – столбец высоты m. Доказать, что либо существует такойстолбец y > 0 высоты m, что t Ay > c, либо существует такойстолбец x > 0 высоты n, что Ax 6 0, t cx > 0.Упражнение 1.58. Пусть A из упражнения 1.57. Доказать, что существует либо такой столбец y > 0 высоты m, чтоtAy = 0, либо такой столбец x высоты n, что Ax > 0, Ax 6= 0.Упражнение 1.59.
Пусть задан конечно порожденный конус K ⊆ An . Доказать, что1) двойственный конус K ∗ конечно порожден;2) если K ∗ порождается точками B1 , . . . , Bt со столбцами координат b1 , . . . , bt , то K состоит из всех таких точек X состолбцом координат x, что t bi x 6 0, i = 1, . . . , t.Глава 2Элементы линейногопрограммированияОпределение 2.1. Пусть заданы аффинные функцииz(x), f1 (x), .
. . , fd (x) в An . Задача линейного программирования состоит в нахождении максимума аффинной функции z(x)при условииf1 (x) > 0, . . . , fd (x) > 0.Как правило, мы будем предполагать, что ранг линейныхчастей системы функций f1 (x), . . . , fd (x) равен n. Тогда d =m + n, m > 0.
Совершая аффинную замену переменных, можно добиться, чтобы f1 = x1 , . . . , fn = xn . Тогда система неравенств имеет видx1 > 0, . . . , xn > 0;Xfn+i (x) =aij xj > bj ,i = 1, . . . , m.(25)jНеобходимо найти max z, где z = p1 x1 + . . . + pn xn + q. Заметим,что нахождение min z эквивалентно нахождению max(−z).1. Симплекc-метод. Первый вариантЗапишем систему неравенств (25) в следующей эквивалентной форме. Так как yj > 0, то существуют такие неотрицательные числа x1+n , . .
. , xm+n , что неравенства (25) преобразуютсяв систему линейных уравнений и неравенств видаx1 > 0, . . . , xd > 0;Pnj=1 aij xj − xj+n = bj ,41d=n+mi = 1, . . . , m.42В. А. АртамоновТаким образом, меняя обозначения, всегда можно считать, чтосистема ограничений, задающих полиэдр M , имеет видx1 > 0, . .
. , xn > 0;Pnj=1 aij xj = bj ,i = 1, . . . , m,(26)Если в каком-то уравнении из (26) коэффициент bi < 0, то умножим это уравнение на -1. Таким образом, без ограничения общности можно предполагать, что b1 , . . . , bm > 0. Кроме того, запишем целевую функцию z в виде z+am+1,1 x1 +· · ·+am+1,n xn =bm+1 , где am+1,j = −pj , j = 1, . . . , n, и bm+1 = q.Изложим алгоритм решения этой задачи, называемыйсимплекс-методом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
