Математические модели в экономике

Математические модели в экономике Лектор: проф. Шананин А.А. Москва, 1999 год. Оглавление 1 Модели межотраслевого баланса и теория неотрицательных матриц 1.1 Эмпирическая модель межотраслевого баланса Леонтьева В.В. . . . 1.2 Продуктивная матрица. . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Теорема Фробениуса-Перрона. . . . . . . . . . . . . . . . . . . . . . . 1.4 Неразложимые матрицы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Двойственность в задачах линейного программирования и ее экономическая интерптетация. 2.1 Некоторые сведения из теории линейного программирования. . . . . . . . . . . . 2.2 Модель Кокса–Росса–Рубинштейна. Вычисление цены опциона. . . . . . . . . . . 2.3 Трудовая теория стоимости и ее критика . . . . . . . . . . . . . . . . . . . . . . . 2.4 Оценка эффективности новых технологий . . . . . . . . . . . . . . . . . . . . . . 2.5 Теорема о магистрали Моришимы . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Экономическая интерпретация принципа максимума Понтрягина в моделях экономического роста. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Модели экономической конкуренции. 3.1 Некоторые понятия теории игр. . . . . . . . . . . . . . 3.2 Теоремы Брауэра о неподвижных точках. . . . . . . . . 3.3 Теорема Нэша и модель олигополии Курно. . . . . . . 3.3.1 Модель олигополической конкуренции Курно . 3.3.2 Монополия . . . . . . . . . . . . . . . . . . . . . 3.3.3 Совершенная конкуренция . . . . . . . . . . . . 3.3.4 Модификация функций спроса и предложения. 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 3 7 10 18 18 24 28 34 35 38 41 41 42 49 50 52 54 55 Глава 1 Модели межотраслевого баланса и теория неотрицательных матриц 1.1 Эмпирическая модель межотраслевого баланса Леонтьева В.В. Экономика разбивается на специальные производственные единицы — чистые отрасли. Считается, что одна чистая отрасль выпускает только один продукт, разные отрасли выпускают разные продукты. Выделим n чистых отраслей и заномеруем их и выпускаемую ими продукцию. Леонтьев наблюдал временные ряды выпуска отраслей. xi (t) — валовый выпуск i-й отрасли в период времени t. zij (t) — количество продукции i-й отрасли, которая используется в качестве сырья j-й отраслью в период времени t. T Леонтьев анализировал поведение последователлльности {xi (t), zij (t)}t=0 . Оказалось, что диzij (t) намика довольно причудлива, но отношение xi (t) ≈ aij слабо зависит от времени ⇒ числа aij можно считать константами ( некоторыми характеристиками технических процессов отраслей). Составим матрицу прямых затрат Леонтьева A = kaij k ∈ Rn×n . wi (t) — конечный выпуск i–й отрасли в период времени t. Если не учитывать экспорт и импорт( т.е. считаем экономику замкнутой), то wi (t) = xi (t) − n X zij (t) = xi (t) − j=1 n X aij xj (t) i = 1, n j=1 Запишем полученное равенство в векторном виде : x̄ = (x1 , ..., xn ) — вектор валовых выпусков отраслей, w̄ = (w1 , ..., wn ) — вектор конечных выпусков x̄ − Ax̄ = w̄ — статистическая модель межотраслевого баланса Леонтьева. где w̄ > 0 ( т.е. wi > 0i = 1, n), x̄ > 0. Естественно выяснить, существует ли w̄ > 0 для заданного x̄ и для любого ли w̄ > 0 ∃ x̄? Построим динамическую модель. Будем считать, что затраты делаются на предыдущем по времени шаге: x̄(t) = Ax̄(t + 1) + w̄(t + 1) — динамическая модель. Введем новую переменную s: ˆ , w̄(t) = st w̄ ˆ x̄(t) = st x̄ Очевидно, что s имеет смысл темпа роста (s > 1 – рост, иначе – деградация). Удобно ввести переменную ρ = 1s ˆ = st+1 Ax̄ ˆ + st+1 w̄ ˆ ⇒ ρx̄ ˆ = Ax̄ ˆ + w̄ ˆ ⇒ (ρE − A)x̄ ˆ = w̄ ˆ st x̄ 2 3 1.2 Продуктивная матрица. Определение. Неотрицательная квадратная матрица A называется продуктивной, если ∃ x̄ > 0 : x̄ − Ax̄ > 0 ( A = kaij ki,j=1,n , A > 0 ⇔ ai,j > 0 i, j = 1, n) Продуктивная матрица Леонтьева — матрица самостоятельной экономики, которая может существовать сама (производственная система будет работать). Определение. Будем говорить, что матрица D = kdij ki,j=1,n : dij 6 0 при i 6= j (1.1) продуктивна, если ∃ x̄ > 0 : Dx̄ > 0 Замечание. из второго определения следует первое. Действительно, если D = E −A ⇒ D — продуктивна ⇔ A — продуктивна. Второе определение дало нам возможность рассматривать матрицы вида D = ρE − A. Теорема. Пусть матрица D ∈ Rn×n удовлетворяет (1.1), тогда следующие утверждения эквивалентны: 1. ∃ x̄ > 0 : Dx̄ > 0, 2. ∀w̄ > 0 ∃ x̄ 6 0 : Dx̄ = w̄, 3. Все последовательные главные миноры  d11 · · · det  · · · · · · dk1 · · · матрицы D положительны:  d1k · · ·  > 0 k = 1, n dkk 4. Все главные миноры матрицы D положительны:   di1 i1 · · · di1 ik det  · · · · · · · · ·  > 0 ∀1 6 i1 < i2 < · · · < ik 6 n dik i1 · · · dik ik Доказательство. 1⇒ 3 (индукция по n) n = 1 d11 x1 = w1 > 0, x > 0 ⇒ d11 > 0 ⇒ свойство 3 выполнено. ∃ x1 > 0, ..., xn > 0 : w1 > 0, ..., wn > 0  d11 x1 + d12 x2 + ... + d1n xn = w1    d21 x1 + d22 x2 + ... + d2n xn = w2 .....................................    dn1 x1 + dn2 x2 + ... + dnn xn = wn (1.2) ⇒ d11 = w1 − d12 x2 − ... − d1n xn > 0, т.к. w1 > 0, d12 , ..., d1n 6 0, x2 , ..., xn > 0 ⇒ исключим x1 из всех уравнений, начиная со второго, в системе (1.2):  ∗  d22 x2 + ... + d∗2n xn = w2∗ .................................  ∗ dn2 x2 + ... + d∗nn xn = wn∗ ( i1 d∗ij = dij − dij dd11 i, j = 2, n di1 ∗ wi = wi − w1 d11 i = 2, n d∗ij 6 0 при i 6= j, т.к. dij 6 0 (i 6= j), d1j , di1 6 0, d11 > 0 wi∗ > 0 т.к. w1 , wi > 0, d11 > 0, di1 6 0 ⇒ (1.3) (1.4) 4 ⇒ размерность системы (1.3) n − 1 и выполнено 1 ⇒ по индуктивному предположению все главные миноры матрицы из уравнения (1.3) > 0:  ∗  d22 · · · d∗2k det  · · · · · · · · ·  > 0 k = 2, n d∗k2 · · · d∗kk  d11 det  · · · dk1 ··· ··· ···   ∗ d1k d22 · · ·  = d11 det  · · · dkk d∗k2 ··· ··· ···  d∗2k · · ·  > 0, т.к. d11 > 0 d∗kk (1.5) 3⇒ 2 (индукция по n) n = 1 d11 x1 = w1 , d11 > 0 ⇒ x1 = dw111 ⇒ w1 > 0 ⇒ x1 > 0 ⇒ свойство 2 выполнено. Требуется для всех w1 > 0, ..., wn > 0 найти x1 > 0, ..., xn > 0: выполнено свойство 2. От системы (1.2) перейдем к системе:  d11 x1 + d12 x2 + ... + d1n xn = w1    d∗22 x2 + ... + d∗2n xn = w2∗ ⇒ d∗ij 6 0 при i 6= j, wi∗ > 0 .................................    d∗n2 x2 + ... + d∗nn xn = wn∗ ⇒ для нижних n − 1 строк этой системы выполнено индуктивное предположение: ∃x2 > 0, ..., xn > 0, удовлетворяюще (1.3) ⇒ найдем x1 : d11 > 0 ⇒ x1 = dw111 − d111 (d12 x2 + ... + d1n xn ) > 0, т.к. w1 > 0, d12 , ..., d1n 6 0 2⇒ 1 очевидно 4⇒ 3 очевидно (1⇔2⇔3)⇒ 4 Выберем 1 6 i1 < ... < ik 6 n, составим минор и докажем, что   di1 i1 · · · di1 ik det  · · · · · · · · ·  > 0 dik i1 · · · dik ik (1.6) Рассмотрим перестановку, которая переводит i1 в 1, ..., ik в k :   i1 i2 · · · ik · · · π= 1 2 ··· k ··· π D удовлетворяет 1 ⇔ Dπ удовлетворяет 1π : Dπ x̄π = (Dx̄) ⇒ 1π ⇔ 3π ⇒ положительность k–го последовательного главного минора матрицы Dπ ⇔ (1.6) Замечание. Свойства 3,4 позволяют определить, является ли матрица продуктивной. Эти условия называются условиями Хокинса – Саймона. p̄ = (p1 , ..., pn ) — вектор цен на продукцию отраслей, π̄ = (π1 , ..., πn ) — вектор добавленной стоимости. πi = pi − n P pi aij > 0. Нас интересует j=1 существуют ли pi : πi > 0 Определение. матрица D, удовлетворяющая свойству (1.1), называется прибыльной, если ∃p̄ > 0: DT p̄ > 0. π̄ = (E − AT )p̄ Теорема. 1’. Пусть матрица D = kdi,j ki,j=1,n удовлетворяет условию di,j 6 0, i 6= j. Тогда следующие утверждения эквивалентны: 5 1. ∃~x > 0 : D~x > 0 (свойство продуктивности); 2. ∀w ~ > 0 ∃~x > 0 : D~x = w; ~ 3. Последовательные главные миноры матрицы D положительны; 4. Все главные миноры матрицы D положительны; 5. ∃~ p > 0 : DT p~ > 0 (свойство прибыльности матрицы D); 6. ∀~π > 0 ∃~ p > 0 : DT p~ = ~π ; 7. Последовательные главные миноры матрицы DT положительны; 8. Все главные миноры матрицы DT положительны; 9. ∃ матрица D−1 > 0. Доказательство. По Теореме 1 следует, что условия 1)⇔2)⇔3)⇔4). Выполнение условия (1.1) для матрицы D эквивалентно выполенению условия (1.1) для матрицы DT , т.к. при транспонировании матрицы внедиагональные элементы переходят во внедиагональные. Таким образом, применяя Теорему 1 к матрице DT , получаем, что 5)⇔6)⇔7)⇔8). 3)⇔7), т.к. при транспонировании матрицы ее определитель не меняется, а главные последовательные миноры переходят в главные последовательные миноры. =⇒ 1)⇔2)⇔3)⇔4)⇔5)⇔6)⇔7)⇔8). 9)⇔2), т.к. если ∃D−1 > 0, то ~x = D−1 w ~ > 0, если w ~ > 0. Докажем, что 1),2),3),4),5),6),7),8)=⇒9). Из 3)=⇒ detD > 0 =⇒ D−1 . 2)⇔3)=⇒ выберем w ~ i = (0, . . . , |{z} 1 , . . . , 0). i Из 2) =⇒ ∃~x : ~x = D−1 w ~ i > 0, а т.к. D−1 w ~ i есть i-ый столбец матрицы D−1 , то получаем, что −1 i-ый столбец матрицы D положителен. Измнняя значение i, получаем D−1 > 0 =⇒ 9). Следствие. D = E − A, A = kai,j ki,j=1,n > 0. Рассмотрим числа: ri = n X ai,j , i = 1, n j=1 sj = n X ai,j , = 1, n. i=1 Тогда для продуктивности матрицы A достаточно выполнения одного из условий БрауэраСоллоу: 10 . max ri < 1, i 20 . max sj < 1. j Доказательство. Пусть верно условие 10 . =⇒ выберем ~x = (1, . . . , 1) > 0 и рассмотрим n P w ~ = ~x − A~x. wi = 1 − ai,j = 1 − ri > 0 =⇒ A – продуктивна. j=1 Пусть верно 2 . =⇒ выберем p~ = (1, . . . , 1) > 0 и рассмотрим ~π = p~ −AT p~. πj = 1− n P ai,j = i=1 1 − sj > 0 =⇒ A – прибыльна =⇒ по Теореме 1 ’ матрица A – продуктивна. Замечание. Условия Брауэра-Соллоу не являются необходимыми. Определение. Матрица D называется неотрицательно обратимой, если для нее ∃D−1 > 0. Рассмотрим матрицу D = (ρE − A). 6 Определение. (ρE − A) −1 – резольвента. Частный случай : n = 1, матрица А является числом и при a11 < 1 =⇒ 2 a11 + . . . бесконечно убывающая геометрическая прогрессия. Обобщение : n > 1. 1 1−a11 = 1 + a11 + (E − A)−1 = E + A + A2 + . . . + Ak + . . . , (ρE − A)−1 = ∞ X Ak — ряд Неймана. ρk+1 (1.7) k=0 Если w ~ – желаемый вектор конечных выпусков, то для векторов валовых выпусков получаем: ~x = (E − A)−1 w ~ =w ~ + Aw ~ + A2 w ~ + . . . + Ak w, ~ где Aw ~ – сырье на производство продукции w, ~ A2 w ~ – сырье на производство продукции Aw, ~ и т.д. Определение. (E − A)−1 — матрица полных затрат, где А – матрица прямых затрат. (E − A)−1 ≈ E + A + A2 , т.к. на практике ряд очень быстро сходится. Теорема. 2. Пусть A > 0. Тогда справедливы следующие утверждения: 10 . Если ∃(ρE − A)−1 > 0, то ρ > 0, ряд ∞ X Ak ρk+1 (1.8) k=0 k абсолютно сходится (абсолютно, т.к. слагаемые ρA k+1 > 0) и справедлива формула (1.7) для разложения резольвенты. 20 . Если ρ > 0 и ряд (1.8) сходится, то ∃(ρE − A)−1 > 0 и справедлива формула (1.7). Доказательство. По Теореме1’ из ∃ (ρE − A)−1 > 0 =⇒,что для (ρE − A) верны условия Хокинса-Саймона: ρ − a11 > 0 =⇒ ρ > 0. Рассмотрим частичные суммы: m X Ak . Tm = ρk+1 k=0 Справедливо следующее матричное тождество: (ρE − A)Tm = Tm (ρE − A) = E − Am+1 ρm+1 Докажем это: (ρE − A)Tm = ρTm − ATm = m P k=0 Ak ρk Аналогично: Tm (ρE − A) = E − Умножим (1.9) на (ρE − A)−1 . − m+1 P Ak ρk =E− k=1 Am+1 ρm+1 . =⇒(1.9). Am+1 ρm+1 . >0 Tm >0 z }| { z }| { (ρE − A)−1 Am+1 Am+1 −1 −1 = (ρE − A) (E − ρm+1 ) = (ρE − A) − 6 (ρE − A)−1 . ρm+1 | {z } >0 Т.е. Tm 6 (ρE − A)−1 . Ряд (1.8) состоит из неотрицательных слагаемых =⇒ неравенство: T1 6 T2 6 . . . 6 Tm 6 Tm+1 6 . . . (1.9) 7 Таким образом, последовательность частичных сумм Tm монотонно не убывает и ограниченна сверху.=⇒ ряд (1.8) сходится к T по теореме о существовании предела у монотонной ограниченной последовательности. По определению Tm имеем: Am+1 = ρ(Tm+1 − Tm ) ρm+1 Переходя к пределу, получим: Am+1 = 0. m→∞ ρm+1 lim Перейдем к пределу в равенстве (1.9): (ρE − A)T = T (ρE − A) =⇒ по определению T = (ρE − A)−1 > 0. =⇒ (1.7). 20 . Ряд (1.8) сходится и ρ > 0. =⇒ ∃ T = lim Tm . m→∞ По определению Tm имеем: Am+1 = ρ(Tm+1 − Tm ) ρm+1 Переходя к пределу, получим: Am+1 = 0. m→∞ ρm+1 lim Перейдем к пределу в равенстве (1.9): (ρE − A)T = T (ρE − A) =⇒ по определению T = (ρE − A)−1 > 0. =⇒ (1.7). 1.3 Теорема Фробениуса-Перрона. A~x = λ~x, ~x 6= 0, A > 0. Пример.  1 −1  A= . 1 1 (1 − λ)2 + 1 = 0, λ1,2 = 1 ± i =⇒ собственных векторов в вещественном пространстве нет. Лемма. 1. Пусть A > 0, A−квадратная матрица. Тогда множество M (A) = (ρ | ∃(ρE − A)−1 > 0) = (λ(A), +∞), где λ(A) > 0 некоторое число. Доказательство. 1). M (A) 6= ∅. Выберем произвольный вектор ~x > 0 . ∃θ > 0 число : θ~x > A~x, для этого достаточно [A~ x] θ > max xi i . i =⇒ матрица (θE − A) продуктивна. =⇒ по Теореме1’ ∃(θE − A)−1 > 0 =⇒ θ ∈ M (A). 2). Пусть ρ ∈ M (A) =⇒ ρ > 0. Если есть число η > ρ, то η ∈ M (A). ρ ∈ M (A) =⇒ по Теореме1’ матрица (ρE − A) удовлетворяет условию Хокинса-Саймона =⇒ ρ − a11 > 0 =⇒ ρ > 0. 8 η > ρ. По Теореме1’ матрица (ρE − A) продуктивна, т.е. ∃~c > 0 : ρ~x − A~x > 0 ⇔ ρ~x > A~x =⇒ η~x > ρ~x > A~x =⇒ (ηE − A) продуктивная матрица =⇒ по Теореме1’ η ∈ M (A). 3). Определим число λ(A), как λ(A) = inf ρ > 0. ρ∈M (A) =⇒ или M (A) = [λ(A), +∞), или M (A) = (λ(A), +∞). Докажем, что первый вариант не реализуется. Предположим противное: λ(A) ∈ M (A). =⇒ матрица (λ(A)E−A) неотрицательно обратима.=⇒ по Теореме1’ матрица (λ(A)E − A) продуктивна, т.е. ∃~x > 0 : λ(A)~x > A~x. Т.к. неравенство строгое, то ∃ε > 0 : λ(A)~x − ε~x > A~x. (λ(A) − ε)~x > A~x =⇒ (λ(A) − ε)E − A неотрицательно обратима по Теореме1’. =⇒ λ(A) − ε ∈ M (A) =⇒ противоречие с λ(A) = inf ρ. ρ∈M (A) Лемма. 2. Пусть A > 0 и λ(A) = inf  ρ = inf ρ | ∃(ρE − A)−1 . Тогда существует ρ∈M (A) вектор ~xA > 0, ~xA 6= 0 : A~xA = λA~xA . Доказательство. Зафиксируем ∀w ~ > 0. Определим по формуле функцию: ~y (ρ) = (ρE − A)−1 w, ~ при ρ ∈ M (A). ~y (ρ) > 0, при ρ ∈ M (A). ~y (ρ) монотонно зависит от ρ. 1). ~y (ρ) > ~y (η), при η > ρ > λ(A). → → → → → → ρ− y (ρ) − A− y (ρ) = − ω , η− y (η) − A− y (η) = − ω. → → → → ⇒ ρ− y (ρ) − η − y (η) − A(− y (ρ) − − y (η)) = 0, ⇒ − добавим и вычтем ρ→ y (η) → → − (ρE − A)(− y (ρ) − − y (η)) − (η − ρ)→ y (η) = 0. ⇒ → → → ⇒ (− y (ρ) − − y (η)) = (η − ρ)(ρE − A)−1 − y (η), − так как (η − ρ) > 0, → y (η) > 0, (ρE − A)−1 > 0 → → (− y (ρ) − − y (η)) > 0. Pn → 2). Рассмотрим − y (ρ) = (y1 (ρ), . . . , yn (ρ)), обозначим σ(ρ) = i=1 yi (ρ). Очевидно, что σ(ρ) > 0 при ρ > λ(A). Покажем, что предел lim σ(ρ) = +∞. ρ→λ(A) lim σ(ρ) = σ̂. Рассмотрим последовательность {ρt }∞ t=1 & λ(A), → − тогда существует lim σ(ρt ) = σ̂. Для векторов y (ρt ) справедливо 0 6 yi (ρt ) 6 σ(ρt ) 6 σ̂, Допустим противное, т.е. ρ→λ(A) t→+∞ поэтому существует −̂ → lim yi (ρt ) = yˆi . Обозначим → y = (ŷ1 , . . . , ŷn ). В равенстве ρt − y (ρt ) − t→+∞ → → → → → A− y (ρt ) = − ω перейдем к пределу при t → +∞, получим λ(A)−̂ y − A−̂ y =− ω > 0. По определению λ(A)E − A — продуктивна. Тогда по Теореме 1 существует (λ(A)E − A)−1 > 0, поэтому λ(A) ∈ M (A). Таким образом, получили противоречие, / M (A). Pn т.к. в силу Леммы 1 λ(A) ∈ → 3). Обозначим S = {− x = (x1 , . . . , xn ) 6 0| i=1 xi = 1}. S — симплекс. Рассмотрим 1 − 1 − → → отношение σ(ρ) y (ρ) > 0, σ(ρ) y (ρ) 6= 0. Пусть последовательность {ρt }∞ t=1 & λ(A), из по1 − ∞ → следовательности { σ(ρt ) y (ρt )}t=1 , по лемме Гейне-Бореля, можно выделить сходящуюся под последовательность 1 → − → y (ρt(τ ) ) = − x A ∈ S. lim τ to∞ σ(ρt(τ ) ) 9 → → → Разделим обе части выражения − y (ρt(τ ) ) − A− y (ρt(τ ) ) = − ω на σ(ρt(τ ) ) и перейдем к пределу при τ → ∞. Получим → → λ(A)− x A − A− x A = 0. Теорема ( Фробениус, Перрон). Пусть A > 0 — квадратичная матрица, тогда справедливы утверждения 1) Среди собственных чисел матрицы A есть неотрицательные вещественные числа и наибольшему из них λ(A) соответствует не отрицательный собственный вектор → − x A. 2) Матрица (ρE −A) неотрицательно обратима, тогда и только тогда, когда ρ > λ(A). − → → → 3) Если → y > 0,− y 6= 0 и выполнено неравенство A− y > µ− y , то µ 6 λ(A). 4) Если ω — собственное число матрицы A, то |ω| 6 λ(A). Доказательство. Пусть λ(A) = inf{ρ|ρ ∈ M (A)}, если ρ > λ(A), тогда существует (ρE −A)−1 ⇒ det(ρE − A) 6= 0 ⇒ ρ > λ(A) не являются собственными числами A. Из Лемм 1 и 2 следуют утверждения 1), 2). Докажем утверждение 3). Допустим противное: → − → → ∃− y > 0, → y = 6 0, A− y > µ− y и µ > λ(A). → Тогда по утверждению 2) ∃(µE − A)−1 > 0. Домножим неравенство 0 > (µE − A)− y на неот−1 → − рицательную матрицу (µE − A) . Получим противоречие 0 > y . → − → Докажем утверждение 4). Пусть ∃− z = (z1 , . . . , zn ) 6= 0, zk ∈ C, I A→ z = ω− z . Тогда ωzi = n X aij zj ⇒ |ω||zi | = j=1 n X aij |zj |, (i = 1, . . . , n). j=1 → → → − Введем обозначение − y = (|z1 |, . . . , |zn |), − y > 0, − y 6= 0. Для вектора → y справедливо неравен→ − → − ство |ω| y 6 A y , тогда в силу утверждения 3) |ω| 6 λ(A). Определение. Пусть A > 0, тогда построенное по Теореме 3 число λ(A) называют числом → Фробениуса-Перрона матрицы A, а соответствующий данному числу вектор − x A называют вектором Фробениуса-Перрона матрицы A. → Замечание. В динамической модели Леонтьева допускаются так же режимы − x (t) = 1 t− → s x > 0, для которых матрица ( E − A) — продуктивна (т.е. неотрицательно обраs тима), тогда и только тогда, когда 1s > λ(A) ⇔ 1 λ(A) дает оценку на допустимые темпы роста. 1 λ(A) > s. Таким образом, отношение Свойства числа Фробениуса-Перрона. Пусть A > 0, тогда: 1) λ(A) = λ(A> ). 2) λ(αA) = αλ(A). 3) λ(Ak ) = (λ(A))k . 4) Если A > B и B > 0, то λ(A) > λ(B). 5) Если C — главная подматрица матрицы A, то λ(A) > λ(C). 6) λ(A) = 0 ⇔ ∃k : Ak = 0. Экономический смысл данных свойств: 10 2) Умножение на α соответствует времени за которое мы рассматриваем отрасли. 4) A > B ⇒ матрица прямых затрат A больше, чем B, поэтому технологическая оценка более слабая. 5) Рассмотрим часть прямых отраслей, т.е. выделим фрагмент экономики, поэтому технологическая оценка более слабая. Доказательство. 1) Очевидно. 2) Очевидно (собственные числа матрицы умножаются на число). → → → 3) ∃− x 6= 0 : λ(A)− x = A− x ⇒ ⇒ → A2 − x = ... → Ak − x = → λ(A)A− x ... = → (λ(A))2 − x k− → ⇒ (λ(A))k — собственное число Ak . = (λ(A)) x 1 Пусть выполнено строгое неравенство λ(Ak ) > (λ(A))k , обозначим ρ = (λ(Ak )) k > λ(A). Матрица (ρE − A) — неотрицательно обратима, поэтому (Теорема 1’) (ρE − A) — продуктивна, т.е. → → → → → → → ∃−̂ x > 0 : ρ−̂ x > A−̂ x ⇒ ρ2 −̂ x > A2 −̂ x , . . . , ρk −̂ x > Ak −̂ x. Тогда матрица (ρk E − Ak ) — продуктивна, поэтому (Теорема 1’) (ρk E − Ak ) — неотрицательно обратима. По Теореме Ф.-П. ρk > λ(Ak ) — противоречие, поэтому λ(Ak ) = (λ(A))k . 4) λ(A) = inf{ρ|ρ ∈ M (A)}, λ(B) = inf{ρ|ρ ∈ M (B)}. Покажем, что если A > B, то M (A) ⊆ M (B) ⇔ λ(A) > λ(B). M (A) = {ρ|∃(ρE − A)−1 > 0} = {ρ|(ρE − A) — продуктивна } M (B) = {ρ|∃(ρE − B)−1 > 0} = {ρ|(ρE − B) — продуктивна } → → → → Пусть ρ ∈ M (A) ⇔ ∃−̂ x > 0 : ρ−̂ x > A−̂ x > B −̂ x ⇒ (ρE − B) — продутивна ⇒ ρ ∈ M (B) 5) Если переставить столбцы и строки матрицы, то ее характеристический многочлен не меняется, поэтому достаточно рассмотреть случай, когда A имеет следующий вид   C A12 C − (n1 × n1 ) A= , размер матриц A21 A22 A22 − (n2 × n2 )   C 0 Введем B = , очевидно A > B > 0, тогда по свойству 4) λ(A) > λ(B). Определитель 0 0 det(B − λE) = (−λ)n2 det(C − λEn1 ), поэтому матрица B имеет собственное значение λ = 0 кратностью n2 . λ(C) > 0 ⇒ максимальное собственное значение B будет λ(C), тогда λ(A) > λ(B) = λ(C). 1.4 Неразложимые матрицы. Определение. Пусть A > 0 — квадратная матрица размера n × n. Будем говорить, что матрица A разложима, если ∃J ⊂ {1, . . . , n} = N : J 6= ∅, J 6= N : aij = 0, при i ∈ / J, j ∈ J. Замечание. Если матрица разложима, то существует производственная подсистема, которая может функционировать независимо от остальных отраслей. Определение. Матрица A — разложима, если существует матрица перестановок T такая, что   A11 A12 −1 T AT = . A22 11 Определение. Пусть A > 0 — квадратная матрица. Будем говорить, что A неразлжима, если она не является разложимой или нулевой матрицей размера 1 × 1. Рассмотрим свойства неразложимой матрицы: Предложение. 1. Пусть A = kai,j ki,j=1,n > 0, тогда A является разложимой, если и только если AT является разложимой. Доказательство. Пусть разложима, то есть существует собственное подмножество J такое, что J ⊂ N , J 6= ∅, J 6= N ai,j = 0, i ∈ / J, j ∈ J. Рассмотрим дополнение J C = N \ J. Дополнение обладает следующими очевидными свойствами: J C 6= ∅, J C 6= N . ai,j = 0 при i ∈ J C , j ∈ / JC Рассмотрим транспонированную матрицу AT = kãi,j kni,j=1,n . Перепишем условие в терминах транспонированной матрицы ãi,j = 0, j ∈ / J C , i ∈ J C , следовательно AT разложима. Прежде чем сформулировать второе предложение введем новое понятие: Определение. Вектор ~x называется полуположительным, если: ~x > 0, ~x 6= 0, ~x 6> 0 (то есть существует хотя бы одна нулевая и одна положительная компонента). Предложение. 2. Пусть A = kai,j ki,j=1,n > 0. Для того, что бы матрица A была разложима, необходимо и достаточно, что бы существовало число µ и полуположительный вектор ~x, такие, что выполняется неравенство: A~x 6 µ~x (1.10) Доказательство. Достаточность: Надо доказать, что из существования ~x > 0, ~x 6= 0, ~x 6> 0 следует, что A~x 6 µ~x. Множество J состоит из таких индесов i, для которых выполнено условие xj > 0. J 6= ∅ (так как есть хотя бы один положительный xj ) и J 6= N (так как существует хотя бы один нулевой xj ). n P Из того, что ai,j xj 6 0 и ai,j > 0, xj > 0, следует: ai,j xj = 0, ∀i ∈ / J и j ∈ N , следовательно, j=1 учитывая, что xj > 0 при j ∈ J получим ai,j = 0 i ∈ / J, j ∈ J. Следовательно, A разложима по определению. Необходимость: Пусть матрица A - разложимая. Cледовательно можно перенумеровать строки и столбцы таким образом, что она приобретет блочную структуру. Таким образом, без ограни A  11 A12 чения общности считаем, что матрица A имеет блочную форму. A = >0 A22 К матрице A11 можно применить теорему Фробениуса-Перрона. Пусть существует ~xA11 > 0, ~xA11 6= 0, A11 ~xA11 = λ(A11 )~xA11 Возьмем число Фробениуса- Перрона µ = λ(A11 ).   ~xA11 Вектор ~x = > 0, так как ~xA11 > 0, ~x 6= 0, так как ~xA11 6= 0, ~x 6> 0, так как есть нулевая компонента (A - разложимая). С другой стороны:  A 11  ~x  A12  ~xA11   A11 ~xA11  A11 = = λ(A11 ) A22 То есть A~x = λ(A11 )~x 6 λ(A11 )~x = µ~x , где µ - число Фробениуса-Перрона. Теорема. 4. Пусть матрица A > 0 - неразложимая. Тогда справедливо: 1. λ(A) и любой вектор Фробениуса-Перрона являются положительными (~xA > 0). 12 2. Если ~y - собственный вектор, соответствующий λ(A), то существует Θ такая, что ~xA = Θ~y . Доказательство. 1). Предположим противное: ~xA 6> 0, значит, ~xA является полуположительным. Следовательно, выполняется условие предложения 2: A~xA = λ(A)~xA 6 λ(A)~xA = µ~xA , где µ - число Фробениуса-Перрона. Следовательно, матрица A - разложимая, что приводит к противоречию с условием теоремы. Следовательно ~xA > 0. A 6= 0, A > 0, так как ~xA > 0, значит A~xA 6= 0, следовательно, число Фробениуса-Перрона, определяемое из условия: A~xA = λ(A)~xA - не нулевое. То есть по теореме 3 λ(A) > 0. 2). Пусть ~y - собственый вектор матрицы A. A~y = λ(A)~y , ~y 6= 0. Без ограничения общности будем считать I = {i|yi > 0} 6= 0 (иначе домножим на (−1)). Oпределим Θ: Θ = min [~x[~yA]i]i > 0. i∈I Определим вектор ~z = ~xA − Θ~y . Все его компоненты > 0, так как если: i∈ / I ⇒ [~z]i > [~xA ]i > 0 i ∈ I ⇒ Θ 6 [~x[~yA]i]i ⇔ [~z]i = [~xA ]i − Θ[~y ]i > 0. ∃ı̂ ∈ I: [~z]ı̂ = 0. С другой стороны, если из A~xA = λ(A)~xA вычесть A~y = λ(A)~y , умноженное на Θ, то получим: A~z = A(~xA − Θ~y ) = λ(A)(~xA − Θ~y ) = λ(A)~z . Следовательно, по утверждению 1 теоремы ~z = 0 ⇒ ~xA = Θ~y . Следствие. Пусть A > 0 неразложимая матрица. Тогда: 1. Если существует ~x > 0: ρ~x − A~x > 0, ρ~x − A~x 6= 0, то (ρE − A) неотрицательно обратима, то есть продуктивна. 2. Если (ρE − A) неотрицательно обратима, то существует (ρE − A)−1 > 0. Прежде чем доказать теорему рассмотрим пример: Пример. ρ = 1: По второму утверждению (E − A)−1 - матрица полных затрат. Любая отрасль связана с любой другой, то есть учитываются косвенные затраты. Доказательство. 1). Если матрица A неразложимая, то по предложению 1 и AT неразложимая. По теореме 4: существует вектор Фробениуса-Перрона p~A > 0 такой, что AT p~A = λ(AT )~ pA . 0 < (~ pA , ρ~x − A~x) = ρ(~ pA , ~x) − (A~ pA , ~x) = (ρ − λ(A))(~ pA , ~x). Так как последняя скобка больше нуля, то ρ > λ(A). Значит, по теореме 3, (ρE − A) - неотрицательно обратимая. 2). ~ei = (0, ..., 0, 1, 0, ..., 0) - единица стоит на i-ой позиции. ~x = (ρE − A)−1~ei > 0 ρ~x − A~x = ~ei > 0 ⇒ ~x 6= 0 (так как ~ei 6= 0) ρ~x > A~x. Допустим противное: ~x 6> 0. Значит, по предложению 2, A - разложимая. Следовательно ~x > 0 - противоречие ~x - i-ый столбец (E − A)−1 ⇒ (E − A)−1 > 0 Пример. Сушествует ли предел lim ( ρ1 A)t ? t→∞ Предел существует, если (ρE − A)−1 > 0, что возможно по теореме 3 тогда и только тогда, когда ρ > λ(A).  0 1  λ1,2 = ±1 ⇒ λ(A) = 1 - число Фробениуса- Перрона. Пример. A = 1 0  1 0  A2 = . Таким образом получим: A = A3 = ... = A2n+1 = ...; A2 = A4 = ... = A2n = ... 0 1 Таким образом А - неустойчивая, так как элементы ”мигают”. Определение. Будем говорить, что A > 0 устойчивая, если существует положительное k такое, что Ak > 0 13 Теорема. 5.(Теорема об устойчивых марицах)1 Пусть матрица A > 0 - разложимая. Тогда справедливо: A 1. Если существует предел: lim ( λ(A) )t = B , то столбцы B являются векторами t→∞ Фробениуса-Перрона матрицы A, а строки B являются векторами ФробениусаПеррона матрицы AT . A 2. Предел lim ( λ(A) )t существует тогда и только тогда, когда матрица A является t→∞ устойчивой. A Доказательство. 1) Â = λ(A) , λ(Â) = λ(A) λ(A) = 1. Без ограничения общности обозначим t+1 λ(A) = 1. Рассмотрим матрицу A , при t → ∞. Эту матрицу можно представить двумя способами: а). At+1 = AAt при t → ∞ получим AB = B. Это говорит о том, что любой столбец матрицы B, под действием матрицы A, переходит сам в себя. То есть, собственный вектор с собственным значением, равным единице, матрицы B больше или равен нуля. Таким образом, любой столбец матрицы B является либо вектором Фробениуса-Перрона, либо нулевым столбцом. б). At+1 = At A при t → ∞ получим BA = B ⇔ AT B T = B T . Таким образом, по-доказанному, любая строка матрицы B является или вектором Фробениуса-Перрона матрицы AT , или нулевой строкой. По условию теоремы матрица A - неразложимая. Тогда, по предложению 1, и AT - неразложимая матрица. По теореме 4 справедлива альтернатива: I) Справедливо доказываемое утверждение. II) Матрица B = 0. Убедимся в невозможности второй альтернативы. Возьмем вектор Фробениуса-Перрона матрицы A (такой вектор существует по теореме 4). Пусть ~xA > 0 A~xA = ~xA At ~xA = ~xA B~xA = ~xA > 0 ⇒ B 6= 0 значит, утверждение доказано. 2) Если существует предел при t → ∞, At = B > 0, то существует k такое, что Ak > 0. Предположим, что матрица A - положительная.  ~y (t + 1) = A~y (t) (1.11) ~y (t) > 0 ~y (0) 6= 0, где ~y (t) - состояние динамической системы. Зададимся вопросом: существует ли предел At ? Это аналогично доказательству существования lim ~y (t). t→∞ Так как ~y (t) = At ~y (0), следовательно, существует предел по столбцам матрицы, а значит и для всей матрицы A. Пусть ~xA > 0, A~xA = ~xA . Обозначим: Θi = ~y~xi (t) . Если ~y (t) → ~xA при t → ∞, то надо доказать A сходимость чисел: α(t) = min Θi (t), Θl(t) (t) = α(t) и β(t) = max Θi (t), Θs(t) (t) = α(t) 16i6n 16i6n Введем также следующие обозначения: [~ x A ]i ε = min [~ xA ]j > 0, δ = min ai,j > 0 16i,j6n 16i,j6n Запишем соотношение (1.11): n P P P yi (t+1) = ai,j yj (t) = ai,l(t) [~xA ]l(t) α(t) + ai,j [~xA ]j Θj (t) 6 ai,l(t) [~xA ]l(t) α(t)+β(t) ai,j j=1 j6=l(t) [~xA ]j = ai,l(t) [~xA ]l(t) (α(t) − β(t))+ β(t) n P j6=l(t) ai,j [~xA ]j = ai,l(t) [~xA ]l(t) (α(t) − β(t)) + β(t)[~xA ]i j=1 [~ x ] Θi (t + 1) = yi[~x(t+1) 6 ai,l(t) [~xAAl(t) ]i (α(t) − β(t)) + β(t) 6 εδ(α(t) − β(t)) + β(t) A ]i α(t + 1) 6 εδ(α(t) − β(t)) + β(t) (так как минимум) 1 Такое название теорема имеет в экономической литературе. В теории вероятностей она именуется ”Теорема об эргодичности марковских цепей” 14 β(t + 1) > εδ(α(t) − β(t)) + β(t) (так как максимум) {α(t)} - неубывающая последовательность, а {β(t)} - невозрастающая. То есть α(t + 1) > α(t), β(t + 1) 6 β(t). Как легко заметить, каждая из последовательностей ограничена, а значит, каждая из них имеет предельное значение: α̂ и β̂. Запишем двойное неравенство: 0 6 εδ(β(t) − α(t)) 6 β(t + 1) − β(t), где первое неравенство вытекает из того, что α(t) 6 β(t) (как минимум и максимум). Второе неравенство является следствием рекуррентной формулы для β. Таким образом, исходя из двойного неравенства и того, что обе последовательности сходятся, можно заключить, что они имеют один и тот же предел: α̂ = β̂. Для случая когда A > 0 доказательство аналогичное. 5). Итак, пусть ∃k > 0 такой, что Ak > 0. Положим t = τ (t)k + r(t) (?) где 0 6 r(t) 6 k − 1 lim τ (t) = ∞ и t→∞ Без ограничения общности считаем λ(A) = 1 (так как Ak > 0). Пусть существует lim (Ak )τ (t) = B , t→∞ столбцы матрицы B являются векторами Фробениуса-Перрона матрицы Ak . Покажем, что столбцы матрицы B также являются векторами Фробениуса-Перрона матрицы A. Ak – неразложимая (так как Ak > 0), тогда по теореме 4 её вектор Фробениуса-Перрона единственный с точностью до умножения на положительную константу. Пусть ~xA – вектор Фробениуса-Перрона матрицы A, ~xA > 0, тогда A ~xA A2 ~xA Ak ~xA = ~xA = A~xA = ~xA ··· = ~xA ⇒ ~xA – вектор Фробениуса-Перрона матрицы Ak , отсюда, учитывая, что каждый столбец матрицы B – это вектор Фробениуса-Перрона матрицы Ak , следует, что AB A2 B ········· Ak−1 B = = B B = B С другой стороны, запишем иначе равенство lim (Ak )τ (t) = B в виде t→∞ A Из равенства kτ (t) = B + R(t) , lim R(t) = 0 t→∞ ⇒ гдe lim R(t) = 0. t→∞ lim As R(t) = 0 , t→∞ s = 1...k − 1 Воспользуемся тем, что t представляется в виде разложения (?), и запишем At = Ar(t) Akτ (t) = Ar(t) (B + R(t)) = B + Ar(t) R(t) Заметим, что Ar(t) – одна из следующих матриц : E , если r(t) = 0, A , если r(t) = 1, Ak−1 , если r(t) = k − 1, и, вспомнив, что lim As R(t) = 0 , s = 1 . . . k − 1 , t→∞ получим требуемое : lim At = B t→∞ 15 Замечание. 1. Справедлива следущая теорема. Теорема. . Пусть A – неразложимая матрица. Тогда следующие утверждения эквивалентны: 1. ∃ номер k > 0 : Ak > 0 (свойство устойчивости матрицы A); 2. Если w – собственное число матрицы A (вообще говоря, комплексное) и |w| = λ(A), то w = λ(A). 3. Пусть At = kaij (t)ki,j=1...n , тогда Н.О.Д.{t : a11 > 0} = 1, где Н.О.Д. – наименьший общий делитель. 4. Матрица A не допускает циклического разложения. Определение. Будем говорить, что матрица At = kaij (t)ki,j=1...n > 0 допускает циклическое разложение, если существуют множества G1 , . . . ,Gs (s > 0) такие, что Ss 1) k=1 Gk = {1, . . . ,n}; 2) Gk ∩ Gl = , если k 6= l, где k,l = 1 . . . s; 3) если aij > 0 и j ∈ Gk , то i ∈ Gk+1 (принято соглашение, что Gs+1 = G1 ). Другими словами, если матрица допускает циклическое разложение, то одновременной перенумеровкой столбцов и строк она может быть приведена к следующему блочному виду:                                         G1 z  }| Gs G2 G1  { z }| z { Θ Θ ··· A21 Θ ··· Θ A32 }| A1S  G2    G3   ··· Θ  .. . .. . .. . GS   Θ ··· Θ Θ Θ AS ,S−1 Θ  {                                          Замечание. 2.( связь с теорией вероятности и эргодическими цепями ) Марковская цепь системы может находиться в одном из следующих состояний: {1, . . . ,n} (их конечное число). Рассмотрим случайную величину X(t) ∈ {1, . . . ,n} и Bep{X(t) = i} = Pi (t). 16 Пусть условная вероятность перехода из состояния i в состояние j: Bep{X(t + 1) = j | X(t) = i} = aij > 0 (если эта вероятность не зависит от t, то цепь объявляется однородной). Из этих aij можно составить матрицу A = kaij k, задающую вероятность перехода. Как посчитать распределение вероятности в момент времени t+1, если известно распределение в момент t? По формуле полной вероятности запишем Pi (t + 1) = n X aij Pj (t), j=1 если последнее равенство записать в векторном виде, то получим нашу систему p~ (t + 1) = A p~ (t) (заметим, что матрица A непроизвольная, просуммировав строку матрицы A по столбцам, получим 1 (это следует из определения aij ), то есть λ(A) = 1). Вопросом эргодической теоремы является: к чему стремятся p при t → ∞? В нашей теореме 5 утверждается, что при условии циклической неразложимости ∗ lim p~ (t) = p~ t→∞ p~ ∗ – финальное распределение вероятностей, которое может быть найдено из условия p~ то есть p~ ∗ ∗ = A p~ ∗ , – вектор Фробениуса-Перрона матрицы A. Замечание. 3. Пусть мы рассматриваем валютный рынок, на нём котируются различные виды валюты {1, . . . ,n}. Газета ”Финансовые известия” печатает информацию за сколько обменивается одна валюта на другую. Обозначим коэффициент обмена i-ой валюты на j-ую как aij – количество единиц валюты j, которое можно получить за единицу валюты i. Из этих aij можно составить матрицу A = kaij k > 0, называемую матрицей krossкурсов. Ясно, что, обменивая последовательно i-ую валюту на j-ую, затем j-ую на i-ую, в результате не получим то же самое, то есть aij aji 6= 1 — простейший арбитраж (например, может быть, aij aji 6 1, так как при двойном обмене можем получить меньше) Определение. Будем говорить, что у матрицы kross-курсов A есть арбитражная цепочка, если существует последовательность номеров (i1 ,i2 , . . . ,ik ) такая, что ai1 i2 ai2 i3 · · · aik i1 > 1 Можно усложнить нашу модель: предположим, что во время обмена берётся a налог — процент от сделки, тогда нужно рассматривать iρ1 i2 . Определение. Будем говорить, что у матрицы kross-курсов A есть ρ-арбитражная цепочка, если существует последовательность номеров (i1 ,i2 , . . . ,ik ) такая, что ai1 i2 ai2 i3 · · · aik i1 > ρk . Естественнен следующий возникающий вопрос: какое минимальное ρ нужно взять, чтобы арбитражной цепочки не существовало? Сразу ответить на этот вопрос не удастся, так как для этого нужно было бы проверить 2!Cn2 + · · · + n!Cnn комбинаций. Теорема (Фробениус-Перрон). Пусть ρ – минимальное значение, при котором не существует арбитражных цепочек. Тогда существуют (x1 , . . . ,xn ) > 0 такие, что max aij xj = ρxi j при всех i = 1 . . . n . 17 Теорема (Африат-Вериан). Пусть A = kaij ki,j=1...n > 0. Тогда следующие утверждения эквивалентны: 1) не существует такой упорядоченной цепочки (i1 , . . . ,ik ) ⊂ {1, . . . ,n}, что ai1 i2 ai2 i3 · · · aik i1 > ρk ; 2) существуют такие (x1 , . . . ,xn ) > 0 , что max aij xj 6 ρxi j ∗ при всех i = 1 . . . n . Эта теорема содержит случай ρ = 1 и таким образом даёт нам простой критерий отсутствия арбитражных цепочек, состоящий в следующем: пересчитаем все валюты в единицах некоторой абстрактной валюты. Пусть xi – единица абстрактной валюты. Отсутствие арбитража означает, что если пересчитать i-ую валюту в единицах абстрактной валюты, а потом поменять i-ую на j-ую и снова пересчитать, то получим меньшее число единиц абстрактной валюты. Алгоритм Флойда-Варталла затрачивает на это n3 операций. ∗∗ Рассмотрим идемпотентное полукольцо в алгебре (для него операции сложения и умножения введены соответственно как a ⊕ b = max(a,b) и a b = a · b, а свойство идемпотентности заключается в том, что a ⊕ a = a), тогда утверждение 1) последней теоеремы означает, что ряд E ⊕ ρ1 A⊕ ρ12 A2 ⊕ · · · сходится (он просто обрывается на n-ом шаге). Алгоритм Флойда проверяет условие за n шагов, поэтому теорема! есть теорема Фробениуса-Перрона для этого идемпотентного полукольца. Глава 2 Двойственность в задачах линейного программирования и ее экономическая интерптетация. 2.1 Некоторые сведения из теории линейного программирования. Теорема. (двойственности). Для того, чтобы задача линейного программирования ~c ~x → max A ~x 6 ~b (2.1) (2.2) (здесь ~c ∈ IR n , ~x ∈ IR n , ~b ∈ IR m , A — матрица размерности (m × n) ) имела решение, необходимо и достаточно, чтобы имела решение задача линейного программирования следующего вида ~b ~u → min AT ~u = ~c ~u > ~0 (2.3) (2.4) (2.5) При этом если решения задачи линейного програмирования (2.1) (2.2) и (2.3)–(2.5) существуют, то оптимальные значения функционалов в этих задачах совпадают. Определение. Вектор, удовлетворяющий ограничениям (2.2) или (2.4) (2.5), называют допустимым. Вектор, являющийся решением, называют оптимальным. Задача (2.3) – (2.5) называется двойственной задачей. Рассмотрим следующую задачу: ~c1 ~x1 + ~c2 ~x2 A11~x1 + A12~x2 A21~x + A22~x 1 2 ~x 1 ~c1 ∈ IRn1 , ~c2 ∈ IRn2 , A11 – матрица (m1 × n1 ), A21 – матрица (m2 × n1 ), Ясно, что (2.1) (2.2) и (2.3) – (2.5) Здесь → max 6 ~b1 = ~b (2.6) (2.7) ~0 (2.9) 2 > ~x1 ∈ IRn1 , ~x2 ∈ IRn2 , ~b1 ∈ IRm1 , A12 – матрица (m1 × n2 ), A22 – матрица (m2 × n2 ). являются частными случаями (2.6)–(2.9). 18 (2.8) ~b2 ∈ IRm2 , 19 Теорема. 1(двойственности). Для того, чтобы задача линейного программирования (2.6) – (2.9) имела решение, необходимо и достаточно, чтобы имела решение следующая задача линейного программирования: ~b ~u + ~b ~u 1 1 2 2 T ~ T ~ A11 u1 + A21 u2 AT ~u + AT ~u → 22 2 = ~u 2 > 12 1 > min ~c (2.10) ~c 2 ~0 (2.12) 1 (2.11) (2.13) Здесь ~u1 ∈ IRm1 , ~u2 ∈ IRm2 . При этом если решения задач линейного программирования (2.6) – (2.9) и (2.10) – (2.13) существуют, то оптимальные значения функционалов в этих задачах совпадают. Определение. Задача (2.10) – (2.13) называется двойственной задачей. Перепишем задачу (2.10) – (2.13) следующим образом: −~b1 ~u1 − ~b2 ~u2 −AT11~u1 − AT21~u2 −AT ~u − AT ~u → 22 2 = ~u 2 > 12 1 6 max −~c 1 −~c2 ~0 Эта задача эквивалентна (2.10) – (2.13) в смысле оптимального решения и в то же время является задачей того же вида, что и (2.6) – (2.9), поэтому формально можно построить к ней двойственную: −~c1 ~x1 − ~c2 ~x2 −A11~x1 − A12~x2 −A21~x − A22~x 1 2 ~x 1 → > = min ~ −b1 −~b > ~0 2 Таким образом получили прямую задачу, иначе говоря, задачи (2.6) – (2.9) и (2.10) – (2.13) являются взаимно двойственными. Доказательство. Снова рассмотрим задачу линейного программирования ~c ~x → max A ~x 6 ~b (2.14) (2.15) и перепишем задачу (2.6) – (2.9), представив равенство (2.8) в виде двух неравенств и домножив неравенство (2.9) на ”−”: c~1 x~1 + c~2 x~2 A11~x + A12~x → A21~x1 + A22~x2 −A21~x − A22~x 6 2 6 −~x1 6 1 1 2 6 max ~b 1 ~b 2 −~b2 ~0 Посмотрим на последнюю задачу, как на задачу (2.14) – (2.15), а именно: положим   A11 A12  A21 A22   A= , ~b = (~b1 , ~b2 , − ~b2 , ~0) T , ~c = (~c1 , ~c2 ) T ,  −A21 −A22  −E Θ 20 теперь для задачи (2.14) – (2.15) по теореме двойственности напишем двойственную задачу: ~b ~u → min AT ~u = ~c ~u > ~0 (2.16) (2.17) (2.18) Здесь двойственная переменная ~u = (~y1 , ~y2 , ~y3 , ~y4 ) T , где ~y1 ∈ IRm1 , ~y2 ∈ IRm2 , ~y3 ∈ IRm2 , ~y4 ∈ IRn1 , и матрица  A= AT11 AT21 −AT21 −E AT12 AT22 −AT22 Θ   Распишем покоординатно задачу (2.16) – (2.18): ~b ~y + ~b ~y − ~b ~y 1 1 2 2 2 3 → min AT11 ~y 1 + AT21 ~y 2 − AT21 ~y 3 − ~y 4 = ~c 1 AT12 ~y 1 + AT22 ~y 2 − AT22 ~y 3 = ~c 2 ~y > ~0 , 1 ~y > ~0 4 ~y > ~0 , 2 ~y > ~0 , 3 Избавимся от y4 : из равенства AT11 ~y 1 + AT21 ~y 2 − AT21 ~y 3 − ~y 4 = ~c1 ~y = AT ~y + AT ~y − AT ~y − ~c 11 1 21 2 21 3 4 1 ⇒ и, подставив в неравенство ~y 4 > ~0, получим ~b ~y + ~b ~y − ~b ~y 1 1 2 2 2 3 → min AT11 ~y 1 + AT21 ~y 2 − AT21 ~y 3 − ~c1 > ~0 AT12 ~y 1 + AT22 ~y 2 − AT22 ~y 3 = ~c 2 ~y > ~0 , 1 или ~y > ~0 , 2 ~y > ~0 3 ~b ~y + ~b (~y − ~y ) → 1 1 2 2 3 min AT11 ~y 1 + AT21 (~y 2 − ~y 3 ) > ~c 1 AT12 ~y 1 + AT22 (~y 2 − ~y 3 ) = ~c 2 ~y > ~0 , 1 ~y > ~0 , 2 ~y > ~0 3 Если мы теперь положим ~u1 = ~y1 > ~0 и ~u2 = ~y2 − ~y3 , то в точности получим задачу (2.10) – (2.13), следовательно, справедливость доказываемой теоремы вытекает из предыдущей. Итак, мы рассмотрели прямую и двойственную ей задачу. Прямая задача: ~c1 ~x1 + ~c2 ~x2 → max (2.19) 21 A11 x~1 + A12 x~2 6 b~1 (2.20) A21 x~1 + A22 x~2 = b~2 (2.21) ~x1 > 0 (2.22) b~1 u~1 + b~2 u~2 → min (2.23) AT11 ~u1 Двойственная задача: AT12 ~u1 + AT21 ~u2 > ~c1 (2.24) + AT22 ~u2 = ~c2 (2.25) (2.26) ~u1 > 0 Будем называть пару векторов (~x1 , ~x2 ) допустимым решением прямой задачи, если она удовлетворяет (2.20) – (2.22), и оптимальным решением, если она удовлетворяет (2.19) – (2.22). Аналогично для двойственной задачи. Следствия из теоремы двойственности. Предложение. 1. Если пара векторов (~x1 , ~x2 ) — допустимое решение прямой задачи и (~u1 , ~u2 ) — допустимое решение двойственной задачи, то b~1 u~1 + b~2 u~2 > c~1 x~1 + c~2 x~2 . Доказательство. b~1 u~1 + b~2 u~2 (2.20),(2.21),(2.26) (~u1 , A11 ~x1 + A12 ~x2 ) + (~u2 , A21 ~x1 + A22 ~x2 ) = > = {перегруппируем слагаемые} = (~x1 , AT11 ~u1 + AT21 ~u2 ) + (~x2 , AT12 ~u1 + +AT22 ~u2 ) (2.24),(2.25),(2.22) > ~c1 ~x1 + ~c2 ~x2 Следствие. Если пара (~x1 , ~x2 ) — допустимое решение прямой задачи и (~u1 , ~u2 ) — допустимое решение двойственной задачи, а также выполняется равенство: c~1 x~1 + c~2 x~2 = b~1 u~1 + b~2 u~2 , то пара (~x1 , ~x2 ) является оптимальным решением прямой задачи (то есть удовлетворяет (2.19) – (2.22)), а пара (~u1 , ~u2 ) является оптимальным решением двойственной задачи (удовлетворяет (2.23) – (2.26)). c1 , ~x c2 ) является допустимым решением. Тогда в силу предыдущего Доказательство. Пусть (~x утверждения c1 + c~2 ~x c2 6 b~1 u~1 + b~2 u~2 = {по условию} = c~1 x~1 + c~2 x~2 . c~1 ~x c1 , ~x c2 ) не Получили, что значение функционала для прямой задачи на любой допустимой паре (~x больше значения функционала на паре векторов (~x1 , ~x2 ), взятой из формулировки следствия. Так как прямая задача — задача на максимум, то мы доказали, что (~x1 , ~x2 ) — оптимальная пара. Аналогично доказывается, что пара (~u1 , ~u2 ) — оптимальная. Предложение. 2. Пусть (~x1 , ~x2 ) удовлетворяет (2.20) – (2.22), (~u1 , ~u2 ) удовлетворяет (2.24) – (2.26). Для того чтобы пара (~x1 , ~x2 ) являлась оптимальным решением задачи (2.19) – (2.22) и (~u1 , ~u2 ) являлась оптимальным решением задачи (2.23) – (2.26) необходимо и достаточно, чтобы выполнялись следующие два условия: (u~1 , b~1 − A11 x~1 − A12 x~2 ) = 0 (2.27) (x~1 , c~1 − AT11 u~1 − AT21 u~2 ) = 0 (2.28) 22 Доказательство. Предположим, что выполнены (2.27) и (2.28). Из (2.27) и (2.28) следуют равенства: (u~1 , b~1 ) = (u~1 , A11 x~1 + A12 x~2 ) (x~1 , c~1 ) = (x~1 , AT11 u~1 + AT21 u~2 ). Тогда b~1 u~1 + b~2 u~2 (2.21),(2.27) = (~u1 , A11 ~x1 + A12 ~x2 ) + (~u2 , A21 ~x1 + A22 ~x2 ) = = {перегруппируем слагаемые} = (~x1 , AT11 ~u1 + AT21 ~u2 ) + (~x2 , AT12 ~u1 + +AT22 ~u2 ) (2.25),(2.28) = ~c1 ~x1 + ~c2 ~x2 . То есть доказали, что b~1 u~1 + b~2 u~2 = c~1 x~1 + c~2 x~2 . По следствию отсюда вытекает оптимальность. В обратную сторону. Пусть пары (~x1 , ~x2 ) и (~u1 , ~u2 ) — оптимальные решения. По теореме двойственности оптимальные значения функционалов должны совпадать, то есть b~1 u~1 + b~2 u~2 = c~1 x~1 + c~2 x~2 . Проследим цепочку неравенств в предыдущем утверждении 1. Чтобы обеспечить равенство функционалов (левой и правой частей цепочки), надо потребовать выполнения следующих равенств: ~c1 = AT11 ~u1 + AT21 ~u2 и b~1 = A11 x~1 + A12 x~2 . Эти равенства означают выполнение (2.27) и (2.28). Замечание. (2.27) и (2.28) называют условиями дополняющей нежесткости. Определение. Функцией Лагранжа задачи линейного программирования (2.19) – (2.22) называется функция L(x~1 , x~2 , u~1 , u~2 ) = c~1 x~1 + c~2 x~2 + (b~1 − A11 x~1 − A12 x~2 , u~1 )+ +(b~2 − A21 x~1 − A22 x~2 , u~2 ), 1 u2 ∈ Rm2 . где ~x1 ∈ Rn+1 , ~x2 ∈ Rn2 , ~u1 ∈ Rm + ,~ (заметим, что ~x1 и ~x2 — это переменные прямой задачи, ~u1 , ~u2 — векторы указанной размерности, то есть переменные двойственной задачи в определении не фигурируют.) Можно аналогично построить функцию Лагранжа для двойственной задачи. Позже установим, что функции Лагранжа прямой и двойственной задач совпадают. Определение. Набор векторов 1 ~x∗1 ∈ Rn+1 , ~x∗2 ∈ Rn2 , ~u∗1 ∈ Rm u∗2 ∈ Rm2 + ,~ называется седловой точкой функции Лагранжа L(~x1 , ~x2 , ~u1 , ~u2 ), если выполняются следующие неравенства: L(~x1 , ~x2 , ~u∗1 , ~u∗2 ) 6 L(~x∗1 , ~x∗2 , ~u∗1 , ~u∗2 ) (2.29) L(~x∗1 , ~x∗2 , ~u∗1 , ~u∗2 ) 6 L(~x∗1 , ~x∗2 , ~u1 , ~u2 ) ∀~x1 ∈ Rn+1 , ~x2 n2 ∈ R , ~u1 ∈ 1 Rm u2 + ,~ ∈R (2.30) m2 . 23 (2.29) означает, что по (~x1 , ~x2 ) функция Лагранжа достигает максимума на паре (~x∗1 , ~x∗2 ), (2.30): по (~u1 , ~u2 ) функция Лагранжа достигает минимума на паре (~u∗1 , ~u∗2 ). L(x~1 , x~2 , u~1 , u~2 ) = {перегруппируем} = b~1 u~1 + b~2 u~2 + (x~1 , c~1 − AT11 u~1 − AT21 u~2 )+ +(x~2 , c~2 − AT12 u~1 − AT22 u~2 ) — получили функцию Лагранжа для двойственной задачи. При построении функции Лагранжа необходимо учитывать правило знака: она должна строиться таким образом, чтобы при нарушении ограничения сама функция Лагранжа штрафовалась. Поясним сказанное. Рассмотрим функцию Лагранжа для двойственной задачи, которую только что получили. Правило знака состоит в следующем: 0. Двойственная задача — это задача на минимум, поэтому штрафование функционала состоит в том, что его значение должно увеличиться при нарушении ограничения. 1. Знак при скалярном произведении (~x2 , ~c2 − AT12 ~u1 − AT22 ~u2 ) не играет значения, так как второй сомножитель в этом скалярном произведении отвечает ограничению типа равенства в двойственной задаче (смотри (2.25)). 2. Знак при скалярном произведении (~x1 , ~c1 − AT11 ~u1 − AT21 ~u2 ) играет значениe, так как второй сомножитель в скалярном произведении отвечает ограничению типа неравенства в двойственной задаче (смотри (2.24)). Так как первый сомножитель в этом скалярном произведении неотрицателен (смотри (2.22)), а второй сомножитель при нарушении ограничения (2.24) становится положительным, то есть все скалярное произведение становится при нарушении положительным, то чтобы оштрафовать функцию Лагранжа, надо, чтобы это скалярное произведение дало положительное слагаемое. Следовательно, перед этим скалярным произведением должен стоять знак ’плюс’. Аналогично для функции Лагранжа прямой задачи. Правило знака состоит в следующем: 0. Прямая задача — это задача на максимум, поэтому штрафование функционала состоит в том, что его значение должно уменьшиться при нарушении ограничения. 1. Знак при скалярном произведении (b~2 − A21 x~1 − A22 x~2 , u~2 ) не играет значения, так как первый сомножитель в этом скалярном произведении отвечает ограничению типа равенства в прямой задаче (смотри (2.21)). 2. Знак при скалярном произведении (b~1 −A11 x~1 −A12 x~2 , u~1 ) играет значениe, так как первый сомножитель отвечает ограничению типа неравенства в прямой задаче (смотри (2.20)). Так как второй сомножитель в этом скалярном произведении неотрицателен (смотри (2.26)), а первый сомножитель при нарушении ограничения (2.20) становится отрицательным, то есть все скалярное произведение становится при нарушении отрицательным, то чтобы оштрафовать функцию Лагранжа, надо, чтобы это скалярное произведение дало отрицательное слагаемое. Следовательно, перед этим скалярным произведением должен стоять знак ’плюс’, так оно и есть. Теорема (Куна-Таккера). Пусть ~x∗1 ∈ Rn+1 , ~x∗2 ∈ Rn2 . Для того чтобы пара векторов (~x∗1 ,~x∗2 ) являлась оптимальным решением задачи линейного программирования (2.19) – (2.22) необ1 ходимо и достаточно, чтобы ∃~u∗1 ∈ Rm u∗2 ∈ Rm2 такие, что (~x∗1 , ~x∗2 , ~u∗1 , ~u∗2 ) являлась + ,~ седловой точкой функции Лагранжа (2.20) – (2.22). Доказательство. Для доказательства теоремы воспользуемся утверждением 2. Распишем (2.29): L(x~1 , x~2 , u~∗1 , u~∗2 ) = b~1 u~∗1 + b~2 u~∗2 + (x~1 , c~1 − AT11 u~∗1 − AT21 u~∗2 )+ 24 +(x~2 , c~2 − AT12 u~∗1 − AT22 u~∗2 ) 6 b~1 u~∗1 + b~2 u~∗2 + (x~∗1 , c~1 − AT11 u~∗1 − AT21 u~∗2 )+ +(x~∗2 , c~2 − AT12 u~∗1 − AT22 u~∗2 ) Это неравенство нужно доказать ∀~x1 > 0, ∀~x2 . Сократив одинаковые слагаемые в левой и правой частях неравенства, получим: (~x1 , ~c1 − AT11 ~u∗1 − AT21 ~u∗2 ) + (~x2 , ~c2 − AT12 ~u∗1 − AT22 ~u∗2 ) 6 6 (~x∗1 , ~c1 − AT11 ~u∗1 − AT21 ~u∗2 ) + (~x∗2 , ~c2 − AT12 ~u∗1 − AT22 ~u∗2 ) Докажем, что (2.29) ⇐⇒ (~u∗1 , ~u∗2 ) удовлетворяет (2.24), (2.25), (2.26), (2.28). Если (2.24), (2.25), (2.26), (2.28) выполнены ⇒ (2.29) — выполнено ∀~x1 > 0, ∀~x2 (так как 0 6 0 всегда). Теперь предположим, то выполнено неравенство (2.29) ∀~x1 > 0, ∀~x2 . Будем выбирать ~x1 > 0, ~x2 специальным образом для доказательства (2.24), (2.25), (2.26), (2.28). Докажем (2.25). Возьмем ~x∗1 = ~x1 . Тогда выполняемое неравенство (2.29) можно переписать так: (~x2 , ~c2 − AT12 ~u∗1 − AT22 ~u∗2 ) 6 (~x∗2 , ~c2 − AT12 ~u∗1 − AT22 ~u∗2 ). Пусть (2.25) нарушено по какой-то координате. Рассмотрим (~x2 , ~c2 − AT12 ~u∗1 − AT22 ~u∗2 ) и устремим x2 → +∞ по той координате, по которой нарушено (2.25), а по остальным координатам положим ~x∗2 = ~x2 . Тогда в (2.29) получим противоречие. Следовательно, (2.25) доказано. Докажем (2.24) от противного. Выберем ~x2 = ~x∗2 . Тогда выполняемое неравенство (2.29) можно переписать так: (~x1 , ~c1 − AT11 ~u∗1 − AT21 ~u∗2 ) 6 (~x∗1 , ~c1 − AT11 ~u∗1 − AT21 ~u∗2 ). Аналогично, по координате, по которой нарушается (2.24), положим x1 → +∞, а по остальным ~x∗1 = ~x1 . Тогда в (2.29) получим противоречие. Следовательно, необходимость (2.24) доказана. 1 (2.26) выполняется автоматически, так как в условии теоремы говорится, что ∃~u∗1 ∈ Rm + . T ∗ T ∗ ∗ Докажем (2.28). Известно, что ~x1 > 0 и ~c1 − A11 ~u1 − A21 ~u2 6 0 (так как (2.24) уже доказано). Тогда выберем ~x2 = ~x∗2 , а ~x1 = 0. Предположим, что ~c1 − AT11 ~u∗1 − AT21 ~u∗2 < 0.Тогда в (2.29) получим противоречие: нуль не больше отрицательного числа. Следовательно, ~c1 − AT11 ~u∗1 − AT21 ~u∗2 = 0— а это и есть условие (2.28). Аналогично доказывается, что (2.30) ⇐⇒ (~x∗1 , ~x∗2 ) удовлетворяет (2.20), (2.21), (2.22), (2.27). Для этого надо рассмотреть первое определение функции Лагранжа. 2.2 Модель Кокса–Росса–Рубинштейна. Вычисление цены опциона. Рассмотрим моменты времени t = 0,. . .,n. Рассмотрим один финансовый инструментарий, например, акцию, цена которой в каждый момент времени изменяется. Пусть s(τ + 1) = ξτ · s(τ ), где s(τ )— цена акции в момент τ ,  d ”down” ξτ = u ”up”. И пусть есть рисковый актив, например, наличные деньги, которые можно либо положить в банк и считать его надежным, тогда через некоторое время мы получим прибыль ( наши деньги увеличатся в ρ раз ) или держать их при себе, тогда ρ = 1. Это можно записать так: b(τ + 1) = ρ · b(τ ), где 25 Рис. 2.1: Устройство финансового рынка b(τ )— цена безрискового актива в момент τ . Заметим, что если ρ > u, то выгоднее держать деньги в банке, и акции покупаться не будут; если ρ < d, то, наоборот, выгоднее покупать акции, и тогда вклады в банк поступать не будут. Поэтому d < ρ < u. Разделим эти неравенства на ρ. Тогда получим d u d˜ = < 1 < = ũ, ρ ρ то есть можно исчислять u, d в единицах безрискового актива: ũ, d̃ соответственно и считать тогда ρ = 1. Рассмотрим устройство финансового рынка. Закодируем полученное дерево двоичными разрядами. Количество номеров, которое надо будет использовать для кодировки, равно 2n+1 − 1. Кодировку будем осуществлять таким образом: добавляем к номеру 0, если ”down” и 1, если ”up”. Если t = n и фиксированное, то опцион называется европейским. В момент времени t = n надо выплатить деньги f (j), где j > 2n . Рассмотрим опцион продавца (call option). Опцион продавца — это право на покупку. Тот, кто продает опцион, обязуется продать покупателю опциона акцию через некоторый промежуток времени по определенной цене, равной k, вне зависимости от того, сколько она будет стоить в тот момент. Право на покупку состоит в следующем. Если s(j) < k, то владелец опциона не станет покупать акцию у продавца опциона , поскольку на рынке она стоит дешевле, а пойдет и купит на рынке; если же, напротив, s(j) > k, то владелец опциона обратится к продавцу опциона и получит прибыль: f (j) = (s(j) − k)+ . Рассмотрим опцион покупателя (option put). 26 Опцион покупателя — это право на продажу. Продавец опциона обязуется купить акцию по цене k через некоторый промежуток времени вне зависимости от ее стоимости на рынке в тот момент. Право на продажу заключается в том, что покупатель опциона волен сам выбирать, продавать ему акцию на рынке или продавцу опциона. Если s(j) > k, то он продаст акцию на рынке. Если s(j) < k, то он продаст ее тому, кто выпустил опцион, и тогда потери продавца опциона составят: f (j) = (k − s(j))+ . Тот, кто продает опцион на рынке в t = 0, должен оперировать активами на рынке (либо покупать акции, либо оставлять наличными) таким образом, чтобы в конечный момент времени он смог выплатить f (j). Обозначим β(j) — часть денег, которую он оставляет наличными; γ(j) — часть денег, на которую он покупает акции. Тогда в момент времени j он обладает активами (β(j), γ(j)), называемые портфелем, и его богатство можно оценить так: x(j) = β(j) + γ(j)s(j). В каждый момент времени он может перераспределять свои активы: x(2j) = β(j) + γ(j)s(2j) x(2j + 1) = β(j) + γ(j)s(2j + 1), то есть будет выполняться такое равенство — называемое условием самофинансирования портфеля (β(j), γ(j)): β(2j) + γ(2j)s(2j) = β(j) + γ(j)s(2j) β(2j + 1) + γ(2j + 1)s(2j + 1) = β(j) + γ(j)s(2j + 1) Эти два равенства удобно записать в одно:     i i β(i) + γ(i)s(i) = β +γ s(i) 2 2 , i = 2, . . . ,2n+1 Для терминальных платежей имеем условие: β(j) + γ(j)s(j) > f (j) , j = 2n , . . . ,2n+1 Поставим задачу: какой капитал надо иметь, чтобы удовлетворить выполнение условия самофинансирования и условия для терминальных платежей. Постановка задачи:   β(1) + γ(1)s(1) → min β(i) + γ(i)s(i) = β([ 2i ]) + γ([ 2i ])s(i), i = 2, . . ., 2n+1  β(j) + γ(j)s(j) > f (j), j = 2n , . . ., 2n+1 Это задача линейного программирования, в которой s(2j + 1) = ũ, s(j) s(2j) ˜ = d. s(j) Переменные этой задачи: {β(i), γ(i)}i=1,2n+1 Рассмотрим f (j),β(j)– вложение в j-ом состоянии в безрисковые активы, γ(j) – вложение в j-ом состоянии в акции, x(j) = β(j)b(j) + γ(j)s(j) – стоимость "портфеля".  β(1)b  1 + γ(1)s1 →   

min,  β 2j bj + γ 2j sj = = β (j) bj + γ (j) sj , j = 2, . . . 2n+1 ,    β (j) bj + γ (j) sj > f (j), j > 2n+1 . 27 Построим задачу, двойственную к данной. Первому ограничению припишем переменную p(j), а второму – переменную q(j) и положим p(1) = 1. Выписав функцию Лагранжа и сгруппировав слагаемые, получим двойственную задачу:  P2n+1   j=2n +1 q(j)f (j) → max,    p(j)b(j) = p(2j)b(2j) + p(2j + 1)b(2j + 1), p(j)s(j) = p(2j)s(2j) + p(2j + 1)s(2j + 1), j = 1, . . . 2n+1 ,   n n+1  ,   p(j) = q(j) > 0, j = 2 + 1, . . . 2 p(1) = 1. Воспользуемся тем, что b не зависит от j и выпишем систему  p(j) = p(2j) + p(2j + 1), p(j) = p(2j)dˆ + p(2j + 1)û, j = 1, . . . 2n+1 . Рассмотрим ее относительно p(2j) и p(2j + 1). p(2j) = û − 1 p(j), û − dˆ p(2j + 1) = p∗ = 1 − dˆ p(j). û − dˆ û − 1 . û − dˆ Сделаем замену û = uρ , dˆ = dρ . Тогда u−ρ . u−d Будем интегрировать p∗ как вероятность перехода из одного состояния на другое в предположении, что цена на акции упадет. Так как b(j) – постоянная, положим b(j) = 1. p∗ = x(j) = β(j) + γ(j)s(j), x(2j) = β(2j) + γ(2j)s(2j) = = β(j) + γ(j)s(j) + γ(j)(s(2j) − s(j)) = = x(j) + γ(j)(s(2j) − s(j)), ˆ x(2j + 1) = x(j) + γ(j)(s(2j + 1) − s(j)), s(2j) = ds(j), s(2j + 1) = ûs(j) ⇒ x(2j) = x(j) + γ(j)(dˆ − 1)s(j), x(2j + 1) = x(j) + γ(j)(û − 1)s(j) ˆ ˆ ⇒ (û − 1)x(2j) + (1 − d)x(2j + 1) = (û − d)x(j) ⇒ x(j) = p∗ x(2j) + (1 − p∗ )x(2j + 1). Последнее соотношение говорит о том, что математическое ожидание M (x(t) x(1) , . . . x(t−1) ) = x(t−1) – мартингал. Также оно означает, что из состояния x(j) мы можем попасть в состояние x(2j) с вероятностью p∗ , а в x(2j + 1) с вероятностью 1 − p∗ . Из теоремы двойственности следует n+1 2X p(j)b(j) = β(1)b(1) + γ(1)s(1) j=2n +1 – формула Кокса-Росса-Рубинштейна. Если обязательство имеет вид f (j) = g(s(j)), то многие P состояния будут "склеиваться". n Если было k подъемов и (n − k) падений цены акции, то x0 = k=0 Cnk (p∗ )k (1 − p∗ )n−k g(sk ) – минимальная стоимость портфеля. 28 2.3 Трудовая теория стоимости и ее критика Пример. ~x–вектор валовых выпусков, w–вектор ~ конечных выпусков, A > 0– матрица прямых затрат (продуктивная). Пусть справедлив баланс ~x = A~x + w, ~ w ~ > 0. Обозначим cj – норма затрат труда на выпуск единицы валового продукта в j-ой отрасли, j = 1, . . . n, R – потенциал трудовых ресурсов. В этих обозначениях ~c~x – количество труда, который нужно затратить на выпуск ~x, ~c~x 6 R. Можно выписать систему  ~  ~x = A~x + w, ~c~x 6 R,  w ~ > 0. Зададимся вопросом о выборе пары (~x, w), ~ наилучшей в каком-то смысле. Пусть ~π = (π1 , . . . πn ) – вектор внешних цен.  ~π w ~ → max,    ~x = A~x + w, ~ ~ c ~ x 6 R,    w ~ > 0. Обозначим p~ = (p1 , . . . pn ) – вектор внутренних цен на продукцию, s– ставка заработной платы. Построим двойственную задачу. Составим функцию Лагранжа: L(~x, w, ~ p~, s) = ~π w ~ + h~ p, ~x − A~x − wi ~ + s(R − ~c~x). Перегруппируем слагаемые Лагранжиана L(~x, w, ~ p~, s) = sR + h~x, p~ − AT p~ − s~ci + hw, ~ ~π − p~i. Выпишем двойственную задачу:  sR → min,    p~ = AT p~ + s~c, p~ > ~π ,    s > 0. Условия дополняющей нежесткости к ограничениям прямой задачи s(R − ~c~x) = 0, условия дополняющей нежесткости к ограничениям обратной задачи hw, ~ ~π − p~i = 0. p~ = s(E − AT )−1~c = ~c + AT ~c + . . . + (AT )k~c + . . . – вектор полных трудовых затрат. Нужно показать, что s~c~x = p~w. ~ Из условия дополняющей нежесткости p~w ~ = ~π w, ~ по теореме двойственности ~π w ~ = sR, снова используя условие дополняющей нежесткости, получим требуемое. π Если wi > 0, то πi = pi = sc∗i , s~c∗ = p~ > ~π ⇒ s > c∗j , ∀j. Это означает, что j s = max j πj c∗j ! , то есть выпускается тот товар, для которого внешняя цена и трудовые затраты имеют максимальное отношение. На рисунке 2.2 приведена схема, иллюстрирующая данный пример. 29 Рис. 2.2: Пример. Пусть ~k = (k1 , . . . kn ) – структура потребительского комплекта, ω – уровень жизни.  ~π ω → max,     ~  ~x = A~x + w, ~c~x 6 R,    w ~ > ω~k,   ω > 0. Составим двойственную задачу. L(~x, w, ~ ω, p~, s) = πω + h~ p, ~x − A~x − wi ~ + h~q, w ~ − ~kωi + s(R − ~c~x) = = sR + h~x, p~ − AT p~ − s~ci + hw, ~ ~q − p~i + ω(π − ~q~k). Итак, выпишем двойственную задачу  sR → min,      p~ = AT p~ + s~c, p~~k 6 π,    s > 0,   p~ > 0. Условия дополняющей нежесткости к ограничениям прямой задачи s(R − ~c~x) = 0, h~ p, w ~ − ~kωi. Условия дополняющей нежесткости к ограничениям обратной задачи ω(π − p~~k) = 0. По теореме двойственности πω = sR. Тогда из условий дополняющей нежесткости получим ω~ p~k = ωπ = sR = s~c~x, то есть опять получена схема простого воспроизводства. Схема, изображенная на рисунке 2.3, иллюстрирует данный пример. Пример. Рассмотрим задачу 30 Рис. 2.3: Прямая задача Двойственные переменные  πω → max     x̄ = Ax̄ + w̄ p̄ (вектор цен)    w̄ > ω k̄ q̄ > 0 c̄x̄ 6 R s > 0 (ставка заработной платы)     b̄x̄ 6 Φ µ > 0 (арендная плата за использование капитальных фондов)    ω > 0 Вектор b̄ имеет смысл вектора фондоемкостей. В дальнейшем будет показано, что p̄ = q̄, поэтому q̄ не имеет самостоятельной экономической интерпретации. Построим двойственную задачу, для чего рассмотрим
функцию Лагранжа:
L (x̄, w̄, ω, p̄, q̄, s, µ) = πω
+ (p̄, x̄ − Ax̄ − w̄) + q̄, w̄ − ω k̄ + s (R − c̄x̄) + µ Φ − b̄x̄ = sR +
µΦ + x̄, p̄ − AT p̄ − sc̄ − µb̄ + (w̄, q̄ − p̄) + ω π − q̄ k̄ . Следовательно, двойственная задача будет иметь вид:  sR + µΦ → min     p̄ = AT p̄ + sc̄ + µb̄ ⇒ p̄ > 0  p̄k̄ > π   µ > 0    s > 0 Таким образом, можно найти: p̄ = sc̄∗ + µb̄∗
−1 c̄∗ = E − AT c̄ − вектор полных трудоемкостей
−1 b̄∗ = E − AT b̄ − вектор полных фондоемкостей,
2 b̄∗ = b̄ + AT b̄ + AT b̄ + . . . Из вышесказанного видно, что вектор цен не пропорционален вектору полных трудоемкостей, следовательно, нужно учитывать дополнительно вектор полных фондоемкостей. Рассмотрим условия дополняющей нежесткости: для прямой задачи
p̄, w̄ − ω k̄ = 0 sR = sc̄x̄ µΦ = µb̄x̄ и для двойственной πω = ω p̄k̄ По теореме двойственности πω = sR + µΦ. Верно ли уравнение финансового баланса ω p̄k̄ = µb̄x̄ + sc̄x̄? Воспользовавшись теоремой двойственности и условиями дополняющей 31 Рис. 2.4: Структура модели нежескости, получим ω p̄k̄ = πω = sR + µΦ = sc̄x̄ + µb̄x̄. Однако, разделив собственный капитал трудящихся, мы не разделили финансовый поток ω. Пример. Пусть γ̄ — структура комплекта рабочей силы, R — число таких комплектов. Рассмотрим задачу Двойственные переменные  πω → max    p̄  x̄ = Ax̄ + w̄    q̄ > 0 w̄ = ω k̄ + Rγ̄  c̄x̄ 6 R s>0   b̄x̄ 6 Φ µ>0     ω >    R > 0 В этом примере R является переменной прямой задачи, в то время как в предыдущем примере R = const, остальные обозначения такие же. Функция Лагранжа:

L (x̄, w̄, ω, R, p̄, q̄, s, µ) =
πω + (p̄, x̄ − Ax̄ − w̄) + q̄, w̄ − ω k̄ − Rγ̄ + s (R − c̄x̄) + µ Φ − b̄x̄ =
µΦ + x̄, p̄ − AT p̄ − sc̄ − µb̄ + (w̄, q̄ − p̄) + ω π − q̄ k̄ + R (s − q̄γ̄) . Двойственная задача:  µΦ → min     p̄ = AT p̄ + sc̄ + µb̄ ⇒ p̄ > 0    p̄k̄ > π  p̄γ̄ > s     µ > 0   s > 0. Условия дополняющей нежесткости:
p̄ w̄ − ω k̄ − Rγ̄ = 0 sR = sc̄x̄ µΦ = µb̄x̄πω = ω p̄k̄Rs = Rp̄γ̄. Теорема двойственности: πω = µΦ. Из теоремы двойственности и условий дополняющей нежесткости получим финансовые балансы: для собственников — ω p̄k̄ = µb̄x̄ и для трудящихся Rp̄γ̄ = sc̄x̄. Таким образом, финансовые потоки разделились. 32 Рис. 2.5: Структура модели Декомпозиционные свойства цен. Пример. Взаимодествие отдельных подсистем. Каждую из них будем описывать моделью межотраслевого баланса. Рассмотрим N регионов. Введем следующие обозначения: x̄k — вектор валовых выпусков в k-м регионе; w̄k — вектор конечных выпусков в k-м регионе; ωk — уровень жизни в k-м регионе; Ak — матрица прямых затрат в k-м регионе; b̄k — вектор фондоемкостей в k-м регионе; c̄k — вектор “ресурсоемкостей” в k-м регионе; γ̄k — структура комплектов рабочей силы в k-м регионе; Φk — количество капитальных фондов k-го региона; (Предполагаем, что есть ресурс, который может свободно перераспредляться между регионами). Записав уравнения межотраслевого баланса в k-м регионе, получим следующую задачу линейного программирования:  N P   πk ωk → max    k=1    x̄k = Ak x̄k + w̄k    w̄k > ωk γ̄k (2.31) b̄k x̄k 6 Φk    N  P    c̄k x̄k 6 R     k=1 ωk > 0 ⇐ w̄k > 0, x̄k > 0 для продуктивной Ak πk — веса (важность) регионов. Функция Лагранжа (двойственные переменные, соответственно, p̄k > 0, q̄k > 0, µ̄k > 0, s > 0): 33   N N L {x̄k , w̄k , ωk }k=1 , {p̄k , q̄k , µk }k=1 , s = =   N  N
 P P πk ωk + (p̄k , x̄k − Ak x̄k − w̄k ) + (q̄k , w̄k − ωk γ̄k ) + µk Φk − b̄k x̄k + s R − c̄k x̄k = k=1 = sR + k=1 N P µk Φk + k=1 N  P x̄k , p̄k − k=1 ATk p̄k
 − sc̄k − µk b̄k + (w̄k , q̄k − p̄k ) + ωk (πk − q̄k γ̄k ) . Двойственная задача:  N P   sR + µk Φk → min    k=1   p̄k = ATk p̄k + sk c̄k + µk b̄k  p̄k γ̄k > πk     µk > 0, k = 1, . . . , N   s > 0. (2.32) N Утверждение. Пусть {x̄k , w̄k , ωk }k=1 оптимальное решение задачи линейного программироN вания 2.31, а {p̄k , q̄k , µk }k=1 — оптимальное решение задачи линейного программирования (2.32). Тогда x̄∗k , w̄k∗ ,ωk∗ являются решением задачи линейного программирования (2.33):  πk ωk − s∗ c̄k x̄k → max     x̄k = Ak x̄k + w̄k  w̄k > ωk γ̄k (2.33)   b̄ x̄ 6 Φ  k k k   ωk > 0, а p̄∗k , µ̄∗k — решения задачи, двойственной к (2.33). Смысл этого утверждения заключается в следующем: если взять “кусочек” решения большой задачи, относящийся к k-му региону, то оно окажется оптимальным решением для подзадачи для k-го региона. А вся общая информация содержится в числе s∗ (т.е. если “угадать” s∗ , то можно решать подзадачи вместо исходной задачи). Это свойство называется свойством декомпозиции. Доказательство. Двойственная к (2.33):  µk Φk →    p̄k = p̄ γ̄ >  k k   µk > min ATk p̄k + µk b̄k + s∗ c̄k πk Воспользуемся критерием оптимальности в форме условий дополняющей нежесткости: для (2.31), (2.32) (p̄∗k , w̄k∗ − ωk∗ γ̄k )
= 0, µ∗k, Φk − b̄k x̄∗k =  0, N P ∗ ∗ s R− c̄k x̄k = 0, k=1 ωk∗ (p̄∗k γ̄k − πk ) = 0, k = 1, . . . , N. для (2.33), (2.34) (p̄∗k , w̄k∗ − ωk∗ γ̄k )
= 0, µ∗k , Φk − b̄k x̄∗k = 0, ωk∗ (p̄∗k γ̄k − πk ) = 0, k = 1, . . . , N. (2.34) 34 N Для набора {x̄∗k , w̄k∗ , ωk∗ , p̄∗k , µ∗k }k=1 , s∗ выполняются все условия дополняющей нежесткости. Все ограничения задачи (2.33) встречаются среди ограничений задачи (2.31) и, следовательно, они выполняются. Зафиксировав конкретное k, получим требуемое утверждение. Таким образом, все свелось к проблеме нахождения s∗ . Берем какое-либо s, подставляем в систему, решаем ее и подсчитываем, сколько всего было затрачено ресурсов: если меньше, чем R, то s∗ — занизили, если больше, то s∗ — завысили. 2.4 Оценка эффективности новых технологий Модифицируем рассматриваемую модель. Пусть имеется n продуктов и m технологий по их выпуску. Пусть G ∈ Rn×m — матрица выпусков, A ∈ Rn×m — матрица прямых затрат, x̄ ∈ Rm — вектор интенсивностей технологических способов производства, b̄ ∈ Rm , c̄ ∈ Rm . Поставим задачу:  πω → max     Gx̄ = Ax̄ + w̄      w̄ > ωγ̄ c̄x̄ 6 R (2.35)   b̄x̄ 6 Φ     ω > 0    x̄ > 0 и введем аналогично предыдущим примерам двойственные переменные: p̄ (вектор цен) q̄ > 0 s > 0 (ставка заработной платы) µ > 0 (арендная плата) Обозначим (g- , a- , b- , c- ) — новая технология, x0 — интенсивность ее использования. Тогда получим следующую постановку задачи, учитывающую введенные параметры:  πω → max     ḡ x + Gx̄ = ā- x0 + Ax̄ + w̄     w̄ > ωγ̄    c- x0 + c̄x̄ 6 R (2.36) b- x0 + b̄x̄ 6 Φ     ω > 0     x̄ > 0    x0 > 0 Определение. Будем говорить, что новая технология (g- , a- , b- , c- ) неэффективна, если оптимальные значения функционалов в задаче (2.35) и (2.36) совпадают. Неэффективные технологии нужно отбрасывать. Хотим так организовать эту процедуру, чтобы каждый раз не приходилось решать большую задачу линейного программирования. Составим двойственную задачу к (2.35). Функция
Лагранжа: L (x̄, w̄, ω, p̄, q̄, µ, s) = πω
+(p̄, Gx̄ − Ax̄ − w̄)+(q̄, w̄ − ωγ̄)+s (R − c̄x̄)+ µ Φ − b̄x̄ = sR + µΦ + x̄, GT p̄ − AT p̄ − sc̄ − µb̄ + (w̄, q̄ − p̄) + ω (π − q̄γ̄) . Получим следующую двойственную задачу:  sR + µΦ → min    T T  G p̄ − A p̄ − sc̄ − µb̄ 6 0    p̄γ̄ > π (2.37) µ > 0     s > 0    p̄ > 0 35 Как, проанализировав задачу (2.35) и двойственную к ней задачу (2.37) и не решая (2.36), сказать, эффективна ли технология (g- , a- , b- , c- )? Рис. 2.6: Эффективные и неэффективные технологии Пpедложение. Для того, чтобы новая технология была неэффективной, необходимо и достаточно, чтобы существовало оптимальное решение задачи линейного программирования (2.37) (~ p∗ , µ∗ , s∗ ) такое, что ~g- p~∗ − ~a- p~∗ − µ∗ b- − s∗ c- 6 0. Доказательство. Построим задачу, двойственную к (2.36):  sR + µΦ → min,    T T   G p~ − A p~ − µ~b − s~c 6 0, ~g- p~ − ~a- p~ − µb- − sc- 6 0,    p~~γ > π,   µ > 0, s > 0, p~ > 0. (2.38) (2.39) По теореме двойственности оптимальные значения функционалов в задачах линейного программирования (2.35) и (2.37), (2.36) и (2.39) совпадают. Таким образом, технология неэффективна тогда и только тогда, когда совпадают оптимальные значения функционалов в задачах (2.37) и (2.39). Так как задачи (2.37) и (2.39) отличаются только условием (2.38), то оптимальное решение задачи (2.39) является оптимальным решением задачи (2.37), и для этого решения выполняется условие (2.38). Замечание. Условие (2.38) означает, что если выручка от использования новой технологии меньше издержек, то эта технология неэффективна. Замечание. Комбинация двух неэффективных технологий может оказаться эффективной (см. рис. 2.6). 2.5 Теорема о магистрали Моришимы Рис. 2.7: Магистраль Рассмотрим модель Леонтьева:   A~x(t + 1) 6 ~x(t),  t = 0, . . . , T − 1, ~x(0) = ~x0 , ~x(t) > 0, t = 1, . . . , T. Введем квазиметрику ρ(~x, ~y ) для ненулевых векторов по следующей формуле: ρ(~x, ~y ) = ~x ~y − . k~xk k~y k Как можно видеть, данная квазиметрика — расстояние между направлениями векторов ~x и ~y . Очевидно, что для ρ(~x, ~y ) выполняются следующие свойства: 36 1. Квазиметрика не зависит от длин векторов: ρ(λ~x, µ~y ) = ρ(~x, ~y ), ∀~x 6= 0, y 6= 0, λ > 0, µ > 0. 2. Нулевое квазирасстояние между векторами означает их сонаправленность: ⇐⇒ ρ(~x, ~y ) = 0 ∃λ > 0 : ~x = λ~y . 3. Непрерывность:  ˆ 6= 0,  ~x(τ ) −→ ~x τ →∞  ~y (τ ) −→ ~yˆ 6= 0 ˆ , ~yˆ). ⇒ lim ρ(~x(τ ) , ~y (τ ) ) = ρ(~x τ →∞ τ →∞ 4. Обозначим ˆ) = Cε (~x n ~x 6= 0 o ˆ) < ε . ρ(~x, ~x По свойству 10 Cε будет выпуклым конусом, а при ε < 1 он к тому же будет выпуклым. Определение. Будем говорить, что семейство оптимизационных моделей имеет магистраль ~x∗ , если для всех ε > 0 найдутся моменты времени T0 (ε, A) > 0, T1 (ε, A) > 0 такие, что оптимальные траектории удовлетворяют неравенству ρ(~x(t), ~x∗ ) < ε при T0 (ε, A) 6 t 6 T − T1 (ε, A). Теорема (Моришима). Пусть A — устойчивая матрица, ~c > 0, ~x0 > 0. Тогда вектор Фробениуса–Перрона матрицы A является магистралью для семейства решений  ~c~x → max,    A~x(t + 1) 6 ~x(t), t = 0, . . . , T − 1, (2.40) ~x(0) = ~x0 ,    ~x(t) > 0, t = 1, . . . , T. Доказательство. (1) Так как A — устойчивая матрица, то существует предел At = B. t→∞ λ(A)t lim Покажем, что ∀ε > 0 ∃τ (ε) > 0 такое, что ∀~x0 ∈ Rn \ {0}, ∀t > τ (ε) выполняется ρ(At ~x0 , ~xA ) < ε. Здесь ~xA > 0 — вектор Фробениуса–Перрона матрицы A: A~xA = λ(A)~xA . Пусть ~ei — i-й орт: ~ei = (0, . . . , 0, 1, 0, . . . , 0), тогда по теореме об устойчивой матрице имеем At~ei −→ µ~xA , λ(A)t t→∞ что можно записать в следующем виде (свойство 1): lim ρ(At~ei , ~xA ) = 0. t→∞ По определению предела: ∀ε > 0 ∃τi (ε) > 0 : ∀t > τi (ε) ρ(At~ei , ~xA ) < ε. 37 Положим τ (ε) = max τi (ε). i Пусть ~x0 — произвольный ненулевой вектор; ~x0 = n X (i) (i) x0 ~ei , ~x0 6= 0. x0 > 0, i=1 At ~x0 = n X (i) x0 At~ei . i=1 При t > τ (ε) > τi (ε) из доказанного выше следует, что At~ei ∈ Cε (~xA ), а значит, выбрав ε < 1, мы получим At ~x0 ∈ Cε (~xA ), так как конус Cε выпуклый (свойство 4). (2) Пусть ~x(T ) — вектор, на котором достигается оптимальное значение функционала. Покажем, что ~x(T ) 6= 0. Пусть β > 0, положим ˜ (t) = βλ(A)−t ~xA , ~x тогда ˜ (t + 1) = βλ(A)−t−1 A~xA = βλ(A)−t ~xA = ~x ˜ (t), A~x t = 1, . . . , T − 1. При t = 0 имеем ˜ (1) = βλ(A)−1 A~xA = β~xA 6 ~x0 . A~x ˜ (t) — траектория системы (2.40), причем Выбрав β так, чтобы β~xA 6 ~x0 , получим, что ~x ˜ (T ) = β λ(A)−T ~c~x | {z } >0 ~c~xA |{z} > 0. >0 т.к. ~ c>0, ~ xA >0 Но тогда ˜ (T ) > 0, ~c~x(T ) > ~c~x следовательно ~x(T ) 6= 0. (3) Очевидно, что AT −t ~x(T ) 6 ~x(t), t = 0, . . . , T − 1. Выберем ε0 > 0 настолько малым, чтобы Cε0 (~xA ) ⊆ int Rn+ . Когда T − t > τ (ε0 ), из первого пункта получаем AT −t ~x(T ) ∈ Cε0 (~xA ) ⊆ int Rn+ , следовательно, 0 < AT −t ~x(T ) 6 ~x(t), то есть при t 6 T − τ (ε0 ) выполняется ~x(t) > 0. (4) Построим двойственную задачу к (2.40). Функция Лагранжа: T −1   X T L {~x(t), p~(t)}t=1 = ~c~x(T ) + h~ p(t + 1), ~x(t) − A~x(t + 1)i = t=0 = p~(1)~x(0) + T −1 X h~x(t), p~(t + 1) − A∗ p~(t)i + h~x(T ), ~c − A∗ p~(T )i, t=1 откуда получаем двойственную задачу:   A∗ p~(t) > p~(t + 1),  p~(1)~x0 → min, t = 1, . . . , T − 1, A∗ p~(T ) > ~c. (2.41) Условия дополняющей нежесткости: h~ p(t + 1), ~x(t) − A~x(t + 1)i = 0, ∗ h~x(t), A p~(t) − p~(t + 1)i = 0, t = 0, . . . , T − 1, t = 1, . . . , T − 1. (2.42) (2.43) Из условия (2.43) в силу пункта 3 получаем, что p~(t + 1) = A∗ p~(t), 1 6 t 6 T − τ (ε0 ). (2.44) 38 (5) Матрица A∗ устойчива (это следует из устойчивости A), так что по теореме двойственности получаем p~(1)~x0 = ~c~x(T ) > 0, следовательно, p~(1) 6= 0, и мы можем применить пункт 3 к системе (2.44). Это означает, что существует момент времени T0 > 0 такой, что (A∗ )t p~(1) > 0 при t > T0 . Таким образом, при T0 6 t 6 T − τ (ε0 ) выполняется p(t + 1) = (A∗ )t p~(1) > 0. Но тогда из условия (2.42) получаем, что при тех же значениях t имеет место равенство ~x(t) = A~x(t + 1). (2.45) Так как ~x(t) = AT −τ (ε0 )−t ~x (T − τ (ε0 )) , и ~x (T − τ (ε0 )) > 0, то из пункта 1 получаем   ρ AT −τ (ε0 )−t ~x (T − τ (ε0 )) , ~xA < ε, T0 6 t 6 T − τ (ε0 ) − τ (ε). Полагая T0 (ε) = T0 , T1 (ε) = τ (ε) + τ (ε0 ), получаем утверждение теоремы. 2.6 Экономическая интерпретация принципа максимума Понтрягина в моделях экономического роста. → − Обозначим через ξ (t) — мощности в момент времени t. − → ξ (t) = (ξ1 (t), . . . , ξn (t)) ξi (t) — максимально возможный валовый выпуск в момент времени t. → − Θ (t) — вектор прироста мощностей в момент времени t. Введем матрицу B — матрицу приростных фондоемкостей, i-й столбец которойпоказывает количество продуктов,необходимых для создания единицы мощности в i-й области. → Считаем, что товары потребляются комплектами − γ. Исходя из перечисленных ограничений, построим задачу линейного программирования (A): → − → − → → → x (t) = A− x (t) + B Θ (t) + − ω (t) — сопоставим двойственную переменную − p (t). Будем ее интерпретировать как вектор внутренних цен на товары в момент времени t. → − → → → ω (t) > w(t)− γ — сопоставим с − q (t) > 0. Как и в предыдущих примерах − q (t) совпадет с → − p (t), поэтому не будем его интерпретировать. → − → − → x (t) 6 ξ (t) — сопоставим − ν (t) > 0 — арендную плату. → − → − → − → ξ (t + 1) = ξ (t) + Θ (t) — сопоставим − µ (t + 1) — стоимость мощностей. → − → − c · x (t) 6 R(t) — ограничение по затратам трудовых ресурсов. Сопоставим ему переменную s(t) > 0 — заработную плату. Пусть t = 0, . . . , T − 1 — горизонт планирования. В начале мощности: → − → − → ξ (0) = ξ 0 > 0 — сопоставим − µ (0). Условия неотрицательности: w(t) > 0 → − Θ (t) > 0 → → Накладывать условия неотрицательности на мощности, − ω (t), − x (t) не обязательно, т.к. они выполняются автоматически. Считаем, что цель задачи максимизировать уровень жизни, который записывается функционалом: TP −1 π(t)w(t) −→ max. t=0 Предполагается, что π(t) = (1 + δ)−t . Т.е. δ показывает, на сколько текущее потребление ценится больше, чем будущее. 39 На конечных шагах падает строительство мощностей, но это не правильно, т.к. жизнь горизонтом планирования не ограничивается. Можно учесть потребности в конечный момент времени в виде ограничения: → − → − → ξ (T ) > ξ T — сопоставим − µ T > 0. Для описанной динамической модели построим двойственную задачу. функцию Лагранжа: Составим n oT −1 → − → − → − → L x (t), − ω (t), w(t), Θ (t), ξ (t) ,... t=0 n oT −1  − → → → → → → → . . . ξ (T ), − p (t), − q (t), − µ (t), − ν (t), s(t) ,− µ (T ), − µT = t=0   TP −1 n → − → − → − → − → ω (t) + π(t)w(t) + p (t), x (t) − A x (t) − B Θ (t) − − t=0     → − → → → → → + − q (t), − ω (t) − w(t)− γ + − ν (t), ξ (t) − − x (t) +   o → − → − → − → → → + − µ (t + 1), ξ (t) + Θ (t) − ξ (t + 1) + s(t) (R(t) − − c− x (t)) +     → − → − → − → − → → + − µ (0), ξ 0 − ξ (0) + − µ T , ξ (T ) − ξ T = TP −1 → − → − → → s(t)R(t) + − µ (0) ξ (0) − − µT ξ T+ t=0    TP −1n → − → → → → → → → x (t), − p (t) − A∗ − p (t) − − ν (t) − s(t)− c + − ω (t), − q (t) − − p (t) + t=0     → − → → → → w(t) π(t) − − q (t)− γ + Θ (t), − µ (t + 1) − B ∗ − p (t) +  o   → − → − → → → → → ξ (t), − ν (t) + − µ (t + 1) − − µ (t) + ξ (T ), − µT −− µ (T ) Здесь A∗ — транспонированная матрица A. → → Видно, что − q (t) = − p (t). Используя это, по функции Лагранжа построим двойственную задачу (B): TP −1 → − → − → → s(t)R(t) + − µ (0) ξ 0 − − µ (T ) ξ T −→ min t=0 → − → → → p (t) = A∗ − p (t) + s(t)− c +− ν (t) → − → − p (t) γ > π(t) t = 0, . . . , T − 1 → → B∗− p (t) > − µ (t + 1) → − → − → µ (t) = µ (t + 1) + − ν (t) Начальные условия: → − → µ (T ) = − µT Условия неотрицательности: → − µT > 0 s(t) > 0 → − ν (t) > 0 В частности становится понятно, что стоимость мощностей — это сумма прибыли + выручка, полученная от продажи мощностей в конце. Выпишем условия дополняющей нежесткости: Из  первой задачи: → − → → p (t), − ω (t)− γ =0   → − → − → ν (t), ξ (t) − − x (t) = 0   → − → − → − µ T , ξ (T ) − ξ T = 0   → → s(t), R(t) − − c− x (t) = 0 Из  второй задачи:  → → w(t), − p (t)− γ − π(t) = 0   → − → → Θ (t), B ∗ − p (t) − − µ (t + 1) = 0 40 Предложение. Пусть n− → − → − → → oT −1 → − − x∗ (t), ω ∗ (t), w∗ (t), Θ∗ (t), ξ ∗ (t) , ξ ∗ (T ) — оптимальные решения t=0 задачи линейного программирования (A), n− → − → − → oT −1 − → − → а p∗ (t), s∗ (t), ν ∗ (t), µ∗ (t) , µ∗ (T ), µ∗ T — оптимальное решение двойственной задачи t=0 − → − → − → линейного программирования (B), тогда x∗ (τ ), ω ∗ (τ ), w∗ (τ ), Θ∗ (τ ) являются оптимальным решением следующей задачи линейного программирования (C): − → → − π(τ )w(τ ) + µ∗ (τ + 1) Θ (τ ) −→ max При ограничениях: → − → − → → → x (τ ) = A− x (τ ) + B Θ (τ ) + − ω (τ ) — сопоставим − p (τ ) → − → → ω (τ ) > w(τ )− γ — сопоставим − q (τ ) > 0 → − → c− x (τ ) 6 R(τ ) — сопоставим s(τ ) > 0 → − → − → x (τ ) 6 ξ ∗ (τ ) — сопоставим − ν (τ ) > 0 w(τ ) > 0 → − Θ (τ ) > 0, − → → − где µ∗ (τ + 1), ξ ∗ (τ ) — некоторые фиксированные величины, взятые в момент времени τ . − → → − Т.е. про остальные моменты времени можно знать только µ∗ (τ + 1), ξ ∗ (τ ). Таким образом получили временную декомпозицию. Доказательство. Выпишем двойственную задачу (D): → → − s(τ )R(τ ) + ξ ∗ (τ )− ν (τ ) −→ min → − → → → p (τ ) = A∗ − p (τ ) + s(τ )− c +− ν (τ ) → − → − p (τ ) γ > π(τ ) − → → B∗− p (τ ) > µ∗ (τ + 1) — это показывает, что стоимость мощностей меньше, чем стоимость строительства. → s(τ ) > 0, − ν (τ ) > 0 Условия дополняющей нежесткости задач (C) и (D) входят в условия дополняющей нежесткости задач (A) и (B). Воспользуемся оптимальностью в терминах условий дополняющей нежесткости. →∗ − − → p (τ ), s(τ ), ν ∗ (τ ) — удовлетворяют ограничениям (B), следовательно являются допустимыми. Они также удовлетворяют условиям дополняющей нежесткости для (A), (B), следовательно и для (C), (D). Итак, принцип максимума Понтрягина можно интерпретировать так: надо в каждый момент − → → − времени максимизировать внутренний валовый продукт, зная µ∗ (τ + 1), ξ ∗ (τ ). В рассмотренной модели есть минус: не все цели можно описать одним функционалом. Глава 3 Модели экономической конкуренции. 3.1 Некоторые понятия теории игр. Определение. Игрой в нормальной форме называется n o → − N, {Xi }i∈N , {ui ( x )}i∈N = Γ, где N = {1, . . . , n} — множество игроков (агентов), xi — → стратегия i-го игрока, Xi — множество стратегий i-го игрока. Ситуация − x = (x1 , . . . , xn ) ∈ → → X1 ×. . .×Xn = X. − x — набор выборов, сделанный отдельными игроками, ui (− x ) — функция выигрыша i-го игрока. → Обозначим − x −i = (x1 , . . . , xi−1 , xi+1 , . . . , xn ) ∈ X1 × . . . × Xi−1 , Xi+1 , × . . . × Xn = X−i → Определение. Ситуация − x ∗ = (x∗1 , . . . , x∗n ) ∈ X называется равновесием по Нэшу, если для → − любого игрока i ∈ N выполняется ui (xi , − x ∗−i ) 6 ui (x∗i , → x ∗−i ), ∀xi ∈ Xi Т.е. для каждого игрока при неизменных стратегиях других игроков это была наилучшая ситуация. → Определение. Будем говорить, что некоторая ситуация − x ∗ = (x∗1 , . . . , x∗n ) ∈ X является оптимальной по Парето, если не существует другой реализуемой ситуации такой, что она не хуже. Или другими словами: → ∃− x = (x1 , . . . , xn ) ∈ X : → → ∀i ∈ N ui (− x ) > ui (− x ∗) − → → ∃j ∈ N uj ( x ) > uj (− x ∗) Пример. Дилемма заключенного. Пусть N = {1, 2}, X1 = {C; H}, X2 = {C; H}, где С означает сознаться, а Н — не сознаться. Опишем игру матрицей: C H C (−5, −5) (−10, 0) H (0, −10) (−1, −1) Интепретировать это можно следующим образом: есть два человека, проходящих по одному делу. Если они оба не сознаются, то за недостаточностью улик им дадут по 1 году. Если оба сознаются, то им дадут по 5 лет. Если один из них не сознается, а другой сознается, то сознавшийся выступает в качестве свидетеля, и срок ему не дают, а второй получает 10 лет. (−5, −5) – положение равновесия по Нэшу и оно единственно. Оптимальными по Парето являются ситуации: (0, −10), (−10, 0), (−1, −1) 41 42 Пример (Семейный спор).  (2, 1) (0, 0) (0, 0) (1, 2)  Интерпретация. Супружеская пара стоит перед выбором: Как провести вечер ?. Есть две альтернативы: пойти на футбол или на балет. Муж выбирает вариант из строк, а жена из столбцов. Ясно, что мужа больше интересует футбол (первые строка или стобец), жена же предпочитает футболу балет (вторые строка или стобец). Делается предположение, что ситуация, когда они проводят вечер не вместе, имеет нулевую полезность для обоих. Равновесием по Нэшу будут ситуации: (2, 1), (1, 2). Оптимальными по Парето: (2, 1), (1, 2), но при этом они не эквивалентны, если их рассматривать с позиции каждого из супругов. Для разрешение данной конфликтной ситуации введем еще одно понятие равновесия. Равновесие по Штакельбергу. Надо объявить одного из игроков лидером: ему известна функция полезности другого игрока и, следовательно, известно его поведение в той или иной ситуации. Пусть в последнем примере первый игрок (муж) – лидер. Построим функцию ответов: реакции второго игрока ( жены ) на выбор мужа.  Футбол, если x1 = Футбол x2 (x1 ) = Балет, если x1 = Балет Тогда, зная поведение второго игрока, можно построить функцию полезности первого игрока:  u1 (x1 , x2 (x1 )) = 2, 1, если x1 = Футбол ⇒ (2, 1) – 1 - равновесие по Штакельбергу. если x1 = Балет Она показывает, что, если первый игрок является лидером, то ему выгоднее выбирать первую строку, т.е. футбол. Аналогично для второго игрока ⇒ (1, 2) – 2 - равновесие по Штакельбергу. Пример (игра с нулевой суммой (противоположные интересы)).   ( 1, −1 ) ( −1, 1 ) ( −1, 1 ) ( 1, −1 ) Здесь любая ситуация – равновесие по Парето. Вопрос: существует ли равновесие по Нэшу ? В данном примере нет равновесия по Нэшу ( всегда есть вариант, при котором один из игроков может улучшить свое положение ). 3.2 Теоремы Брауэра о неподвижных точках. Теорема. Пусть X – выпуклый компакт в Rn и f : X → X – непрерывное отображение. → → → → Тогда существует точка x∗ ∈ X такая, что f (x∗ ) =x∗ ( x∗ – неподвижная точка ). Покажем, что все условия в теореме существенны: 1. Откажемся от выпуклости X : X = {(x, y)|x2 + y 2 = 1}. Тогда можно рассмотреть f – поворот относительно (0, 0) и неподвижной точки не будет. 2. Откажемся от замкнутости X : X = [0, ∞). Расмотрение f (x) = x + 1 показывает, что возможен вариант, когда неподвижной точки не существует. 43 3. Пусть f – не является непрерывной. Тогда можно рассмотреть отображение, переводящее все X в точку, а эту точку в другую точку. → → → → Замечание. ∀A > 0 ∃ x A > 0, x A 6= 0 такой, что A x A = λ x A . Докажем это утверждение, используя теорему Брауэра. → Доказательство. Рассмотрим множество X = { x = (x1 ...xn ) > 0 | n P xi = 1} – стандартный i=1 симплекс. → → 1. ∃ x A ∈ X такой, что A x A = 0 ⇒ λ = 0 (ч.т.д.) → → → → → 2. ∀ x ∈ X ⇒ A x 6= 0 ⇒ A x > 0, но A x 6= 0. Определим функцию f ( x ) следу→ ющим образом: [f ( x )]i = → [A x ]i n P → [A x ]j – непрерывная фукнция определенная на X. Чис- j=1 → → литель неотрицателен, а знаменатель строго положителен ⇒ f ( x ) > 0 (f ( x ) 6= 0). n P → [f ( x )]i = 1 ⇒ f : X → X ⇒ по теореме Брауэра существует неподвижная точка: i=1 ! n P → → → → → → → ∃ x A∈ X : f ( x A) = x A и A x A= [A x ]j x A = λ x A j=1 Рассмотрим многозначное отображение f : X → 2Y . Здесь 2Y – множество подмножеств множества Y . → → → → Множество вида Bε ( x ) = { y |k y − x k < ε} – открытый шар. Определение (непрерывность по Коши). Рассмотрим функцию f : X → Y . → → Говорят, что f ( x ) – непрерывна в точке x 0 , если ∀ε > 0 ∃ δ(ε) > 0 такое, что, если → → → → k x − x 0 k < δ(ε), то kf ( x ) − f ( x 0 )k < ε. → → Определение (непрерывность по Гейне). Говорят, что f ( x ) – непрерывна в точке x 0 , → → → → → если ∀{ x t } такой, что lim x t = x 0 имеем, что lim f ( x t ) = f ( x 0 ) t→∞ t→∞ Для многозначных отображений можно рассматривать включения: → → f ( x ) ⊂ f ( x 0 ) + Bε (0) → → f ( x 0 ) ⊂ f ( x ) + Bε (0) → → Определение. Будем говорить, что f ( x ) – полунепрерывна сверху в точке x 0 , если ∀ε > → → → → 0 ∃ δ(ε) > 0 такое, что, если k x − x 0 k < δ(ε), то f ( x ) ⊂ f ( x 0 ) + Bε (0) → → Здесь Bε (0) = { y ∈ Y |k y k < ε} → Определение. Пусть f : X → 2Y . Будем говорить, что f ( x ) – полунепрерывна снизу в → → → → → точке x 0 , если ∀ε > 0 ∃ δ(ε) > 0 такое, что, если k x − x 0 k < δ(ε), то f ( x 0 ) ⊂ f ( x )+Bε (0) Примеры. 1. X = [−1, 1], Y = [−1, 1]. → f(x) = ( 0, [−1, 1], → если x 6= 0 → если x = 0 Здесь есть полунепрерывность сверху, но нет полунепрерывности снизу (в точке 0 ). 44 Рис. 3.1: Пример полунепрерывного сверху, но не снизу отображения 2. X = [−1, 1], Y = [−1, 1]. → ( [−1, 1], 0, f(x) = → если x 6= 0 → если x = 0 Здесь есть полунепрерывность снизу, но нет полунепрерывности сверху (в точке 0 ). → Определение. Пусть f : X → 2Y . Будем говорить, что f ( x ) – замкнутое отображение, → → y ∞ если для любых двух последовательностей { x t }∞ t=1 , { t }t=1 таких, что: → → → ˆ 1. x t ∈ X, lim x t = x ∈ X t→∞ → → → → ˆ ˆ → → ˆ 2. y t ∈ f ( x t ) и lim y t = y выполняется, что y t ∈ f ( x ) t→∞ → → → → Примечание. Множество вида Gf = {( x , y ) ∈ X × Y | y ∈ f ( x )} будем называть графиком отображения. Тогда отображение замкнуто тогда и только тогда, когда график его замкнут. Пример. X = (−∞, ∞), Y = (−∞, ∞).  1 x , если x 6= 0 f (x) = 0, если x = 0 – не является непрерывной. График – замкнутое множество, следовательно, отображение – замкнутое. Предложение. Пусть f : X → 2Y и → → 1. ∀ x ∈ X следует, что f ( x ) – замкнутое множество → 2. f – полунепрерывное сверху отображение в любой точке x ∈ X → Тогда f ( x ) – замкнутое отображение. → → → → y Доказательство. Рассмотрим { x t , y t }∞ t=1 , t ∈ f ( x t ): → → ˆ lim x t = x ∈ X ? → ˆ → ˆ ⇒ y ∈ f(x) → → ˆ lim y t = y ∈ X t→∞ t→∞ 45 Рис. 3.2: Пример замкнутого, но не непрерывного отображения → → → ˆ → → ˆ ˆ Допустим противное: пусть y 6∈ f ( x ) ⇒ в силу замкнутости f ( x ) ⇒ ∃ ε > 0 : { y |k y → ˆ → ˆ − y k < 2ε} ∩ f ( x ) = ∅. A – замкнутое множество ⇒ Y \ A – открытое множество, рассмотрим → → ˆ ˆ окрестность f ( x ) ⇒ в силу полунепрерывности в точке x ⇒ ∃ δ(ε) > 0 такое, что, если → ˆ → → → → → ˆ k x − y k < δ(ε), то f ( x ) ⊆ Y \ A, но ∃ T : ∀t > T ⇒ k x t − x k < δ(ε) ⇒ f ( x t ) ⊆ Y \ A, но → → → → → ˆ ˆ → y t ∈ f ( x t ) ⊆ Y \ A ⇒ k y t − y k > ε при t > T ⇒ противоречие с тем, что lim y t = y t→∞ Замечание. В обратную сторону предложение не верно. Предложение. Пусть f : X → 2Y и Y – компакт. → Если f ( x ) – замкнутое отображение, то: → → 1. ∀ x ∈ X следует, что f ( x ) – замкнутое множество → → 2. f ( x ) – полунепрерывное сверху отображение в любой точке x ∈ X Доказательство. ˆ 1. Gf = {( x , y )| y ∈ f ( x )} – замкнутое множество. ⇒ { x } × Y – замкнутое множество, → → → ˆ ˆ ˆ т.к. Y – компакт. { x } × f ( x ) = Gf ∩ ({ x } × Y ) – замкнутое можество. Рассмотрим → ˆ непрерывное отображение πi : X × Y → Y – проекция ⇒ f ( x ) – замкнутое множество как образ замкнутого множества под действием непрерывного отображения ( проекции ) (ч.т.д.) → → → → → → → → ˆ ˆ ˆ 2. Зафиксируем x ∈ X. Рассмотрим f ( x ). Пусть U – произвольная окрестность f ( x ) в Y . → → → ˆ Множество V = { x |f ( x ) ⊂ U } 6= ∅, т.к. x ∈ V . Вопрос: является ли V – открытым ?. → → Рассмотрим U1 = Y \ U – замкнутое множество. V = { x |f ( x ) ∩ U1 = ∅}. → → Рассмотрим V1 = X \ V = { x |f ( x ) ∩ U1 6= ∅} – является ли замкнутым множеством ?. → → → ˜ ˜ ? → Пусть x t ∈ V1 , lim x t = x ∈ X ⇒ x ∈ V1 . → x t∈ t→∞ → → y t∈ f ( x t) → ˆ ∩ U1 . Поскольку Y – компакт ⇒ существует подпоследова→ ˆ → → ˜ y ∈ Y . В силу замкнутости f ( x ) ⇒ y ∈ f ( x ). В силу замкнутости тельность → ˆ → ˜ U1 ⇒ y ∈ U1 ⇒ f ( x ) ∩ U1 6= ∅. V1 ⇒ ∃ → y t(τ ) → 46 Предложение. Пусть задана функция f : X → 2Y и 1. X — компакт; 2. ∀~x ∈ X ⇒ f (~x) — компакт; 3. f (·) — полунепрерывна сверху. S Тогда множество M = f (~x) является компактом. ~ x∈X Доказательство. Пусть {uαS }α∈Λ — произвольное открытое покрытие множества M, то есть uα — открытые в Y и M ⊂ uα . α∈Λ В силу компактности множества f (~x) для произвольного ~x ∈ X следует, что найдётся Oα (~x) = n [ такая, что uαi f (~x) ⊆ O(~x) ⊂ Y. i=1 Так как f (·) — полунепрерывна сверху, то существует V (~x) — открытая окрестность точки ~x такая, что ˜ ∈ V (~x) ⇒ f (~x ˜ ) ⊆ O(~x). ∀~x S Тогда X ⊆ V (~x), то есть мы получили покрытие множества X. Так как X — компакт, то ~ x∈X мы можем выделить конечное подпокрытие, то есть ∃ V (~x(1) ), . . . , V (~x(t) ) такие, что X⊆ t [ V (~x(τ ) ). τ =1 Таким образом, ∀~z ∈ X ⇒ f (~z) ⊆ t S O(~x(τ ) ). τ =1 Рассмотрим два отображения : f : X → 2Y и g : Y → 2Z и рассмотрим их суперпозицию [ g (f (~x)) = g(~y ). y ∈f (~ ~ x) Для суперпозиции отображений мы также будем пользоваться обозначением g ◦ f : X → 2Z . Y Z Предложение. S Пусть f : X → 2 и g : Y → 2 — два замкнутых отображения, а множество M = f (~x) — компакт. ~ x∈X Тогда g ◦ f — замкнутое отображение. ˆ ∈ X и последовательность ~z(t) ∈ Доказательство. Рассмотрим последовательность ~x(t) → ~x
g f (~x(t)) , причём ~z(t) → ~zˆ ∈ Z. Для доказательства предложения надо показать, что ~zˆ ∈ ˆ) . g f (~x В силу определения операции суперпозиции ∃ ~y (t) ∈ f (~x(t) ) и ~z(t) ∈ g(~y (t) ). Так как последовательность ~y (t) ∈ M , а множество M ⊂ Y — компакт, то можно выделить сходящуюся подпоследовательность. Обозначим её через ~y (t(τ )) и ~y (t(τ )) → ~yˆ ∈ Y . ˆ , причём При t → ∞ соответствующая подпоследовательность ~x(t(τ )) → ~x   ~y (t(τ )) ∈ f ~x(t(τ )) 47 ˆ ). Так как подпоследовательность В силу замкнутости отображения f справедливо ~yˆ ∈ f (~x
(t(τ )) (t(τ )) (t(τ )) ˆ ~z → ~z, и ~z ∈ g ~y , то воспользовавшись замкнутостью отображения g мы получаем, что ~zˆ ∈ g(~yˆ).   ˆ) . Тогда из определения суперпозиции отображений получим, что ~zˆ ∈ g f (~x Теорема (Брауэр). Пусть X — выпуклый компакт в Rn и f : X → X — непрерывное отображение. Тогда у этого отображения существует неподвижная точка, то есть ∃ ~x∗ ∈ X : f (~x∗ ) = ~x∗ . Теорема (Какутани). X — выпуклый компакт в Rn и f : X → 2X . Пусть также выполнено : 1. ∀ ~x ∈ X f (~x) — непустое выпуклое множество 2. f (·) — замкнутое отображение. Тогда ∃ ~x∗ ∈ X : ~x∗ ∈ f (~x∗ ). Доказательство. 1. Так как X — компакт, то для произвольного ε > 0 существует конечная ε – сеть, то есть ∀ε>0 ∃ ~x(1) (ε), . . . , ~x(n) (ε) ∈ X : ∀ ~x1 ∈ X ∃ τ : k~x1 − ~x(τ ) (ε)k < ε. Также в силу компактности множества X, его можно покрыть конечным числом открытых шаров Bε (~x(τ ) ) с центрами ~x(1) (ε), . . . , ~x(t(ε)) (ε) ∈ X, то есть t(ε) X⊆ [   Bε ~x(τ ) (ε) . τ =1
2. Рассмотрим Θτε (~x) = max 0, ε − k~x − ~x(t(ε)) (ε)k . Заметим, что функция Θτε (~x) обладает следующими свойствами : (a) Θτε (~x) — непрерывная функция на X (b) Θτε (~x) > 0 (c) Θτε (~x) >0 ∀ ~x ∈ X ⇐⇒ k~x − ~x(τ ) (ε)k < ε. Определим функцию wετ (~x) по следующей формуле : wετ (~x) = Θτε (~x) . t(ε) P i Θε (~x) i=1 Тогда такая функция будет обладать свойствами : (a) wετ (~x) — непрерывна на X (b) для произвольного ~x ∈ X выполнено : • wετ (~x) > 0 t(ε) P τ • wε (~x) = 1 (является разбиением 1) τ =1 (c) wετ (~x) > 0 ⇐⇒ k~x − ~x(τ ) (ε)k < ε. 48
3. Фиксируем ε > 0 и рассмотрим ~b(τ ) ∈ f ~x(τ ) (ε) , τ = 1, . . . , t(ε) и определим функцию gε (~x) по правилу : t(ε) X ~b(τ ) wτ (~x) . gε (~x) = ε τ =1 Заметим, что : (a) gε (~x) — непрерывная функция
~b(τ ) ∈ f ~x(τ ) (ε) ⊆ X. (b) gε : X → X, Так как множество X — выпукло, то ∀ ~x ∈ X ⇒ gε (~x) ∈ X. Применим теперь к функции gε (~x) теорему Брауэра : ∃ ~x (ε) ∈ X : gε (~x (ε)) = ~x (ε) . ∞ 4. Рассмотрим последовательность {εν }ν=1 , εν > 0 (a) lim εν = 0 ν→∞ (b) gε (~xν ) = ~xν ∈ X (c) lim ~xν = ~x∗ (в силу компактности X) ν→∞ Покажем, что ~x∗ ∈ f (~x∗ ) ~x∗ ∈ f (~x∗ ) + Bδ (0) ~x∗ ∈ f (~x∗ ) + B2δ (0) ∀δ>0 Тогда ~x∗ ∈ f (~x∗ ) = f (~x∗ ) (в силу замкнутости f (·)). 5. f (~x∗ ) + Bδ (0) — выпуклое множество (как сумма выпуклых множеств), S f (~x∗ ) + Bδ (0) = Bδ (~x) — открытое множество. ~ x∈f (~ x∗ ) В силу Предложения 2 : f (·) — полунепрерывна сверху. Тогда получаем, что : ∃ ε(δ) > 0 : k~x − ~x∗ k < ε(δ) ∃ N > 0 : ∀ ν > N, εν < ε(δ) 2 f (~x) ⊆ f (~x∗ ) + Bδ (0) ⇒ ⇒ k~xν − ~x∗ k < ε(δ) 2 Так как ~xν — неподвижная точка отображения gε (·), то справедливо соотношение t(ε Pν ) τ =1 ~xν . Так как wετν (~xν ) > 0 ⇐⇒ (τ ) k~xν − ~xεν k < εν , то ) ) k~x(τ x∗ k 6 k~x(τ xν k + k~xν − ~x∗ k < {пусть ν > N } < εν − ~ εν − ~ wετν (~xν ) > 0 ⇒ ε(δ) ε(δ) + = ε(δ) 2 2   ~b(τ ) ∈ f ~x(τ ) ⊆ f (~x∗ ) + Bδ (0) εν В силу выпуклости [f (~x∗ ) + Bδ (0)] имеем, что   ~xν ∈ f (~x∗ ) + Bδ (0) так как ~xν – выпуклая комбинация ~b(τ ) . Тогда ~x∗ ∈ f (~x∗ ) + Bδ (0) ∀ δ > 0. ~b(τ ) wτ (~xν ) = εν 49 3.3 Теорема Нэша и модель олигополии Курно.  Теорема (Нэш). Пусть Γ = N, {Xi }i∈N , {ui (xi , ~x−i )}i∈N Пусть также — игра в нормальной форме. 1. ∀ i ∈ N Xi — выпуклый компакт 2. ∀ i ∈ N ui (xi , ~x−i ) является непрерывной на X = X1 × X2 × . . . × Xn 3. ∀ i ∈ N, ∀ ~x−i ∈ X−i функция ui (xi , ~x−i ) является вогнутой по xi на множестве Xi . Тогда в игре Γ существует равновесие по Нэшу, то есть ∃ x∗1 ∈ X1 , . . . , x∗n ∈ Xn : ∀ i ∈ N, ∀ xi ∈ Xi ⇒ ui (xi , ~x∗−i ) 6 ui (x∗i , ~x∗−i ). Доказательство. Так как Xi — выпуклые компакты, то и X = X1 × . . . × Xn будет выпуклым компактом. Рассмотрим множество   ϕ (~x−i ) = yi ∈ Xi ui (yi , ~x−i ) = max ui (xi , ~x−i ) . xi ∈Xi Это множество будет непустым подмножеством в Xi . 1. Покажем, что множество ϕ (~x−i ) будет выпуклым. Пусть α = max ui (xi , ~x−i ). Рассмотрим ∀ y˜i , yˆi ∈ ϕ (~x−i ), то есть ui (y˜i , ~x−i ) = α и xi ∈Xi ui (yˆi , ~x−i ) = α. Берём произвольное λ ∈ (0, 1). λy˜i + (1 − λ)yˆi ∈ Xi в силу выпуклости Xi . Тогда α > ui (λy˜i + (1 − λ)yˆi , ~x−i ) > λui (y˜i , ~x−i ) + (1 − λ)ui (yˆi , ~x−i ) = α ⇒ λy˜i + (1 − λ)yˆi ∈ ϕ (~x−i ) . 2. Покажем, что ϕ (~x−i ) — замкнутое отображение, то есть ˆ −i , ~x−i (t) → ~x yi (t) ∈ ϕ (~x−i (t)) , yi (t) → yˆi ∈ Xi ⇒   ˆ −i . yˆi ∈ ϕ ~x Пусть это не так, то есть ˆ −i ) > ui (yˆi , ~x ˆ −i ), ∃ z ∈ Xi : ui (z, ~x а ui (yi (t), ~x−i (t)) > ui (z, ~x−i (t)). В силу непрерывности ui (·) получаем, что ˆ −i ) > ui (z, ~x ˆi ) ui (yˆi , ~x — противоречие. Рассмотрим отображение f : X → 2X , ~x ∈ X, f (~x) = ϕ (~x−1 ) × ϕ (~x−2 ) × . . . × ϕ (~x−n ) . Отображение f (~x) — замкнутое и для ∀ ~x ∈ X является непустым выпуклым множеством. Тогда по теореме Какутани : ∃ (x∗1 , x∗2 , . . . , x∗n ) ∈ X : (x∗1 , x∗2 , . . . , x∗n ) ∈ f (~x∗ ) Эта точка (x∗1 , x∗2 , . . . , x∗n ) и является равновесием по Нэшу. 50 3.3.1 Модель олигополической конкуренции Курно N = {1, ..., n} — множество производителей. X — набор товаров. P (X) — обратная функция спроса, которая показывает, по какой цене производители согласны купить набор товаров X. P (X) удовлетворяет условию: A1 P (X) ∈ C 2 , P 0 (X) < 0, P (0) > 0 ∃M > 0 : P (M ) = 0, M — максимальный объем продажи товара (объем насыщения). Производитель описывается функцией издержек: ci (x) — функция издержек i-го производителя (какие затраты должен сделать производитель что бы выпустить товар в объеме X, имеются ввиду денежные затраты). ci (x) удовлетворяет условию: ∀i ∈ N ci (x) ∈ C 2 dci (x) d2 ci (x) >0 dx > 0, dx2 A2 — выпуклость ci . Основная идея заключается в том, что чем больше товаров мы берем, тем меньше платим. Опишем поведение i-го производителя: xi — выпуск i-го производителя, xi ∈ [0, M ]. n P X= xj — суммарный выпуск. j=1 Выбор стратегии определяет прибыль производителя: n P ui (~x) = P ( xj )xi − ci (xi ) — прибыль i-го производителя (его целевая функция). Можно j=1 заметить, что на прибыль влияет суммарный выпуск. Получили игру в нормальной форме. Компромиссом является равновесие по Нэшу. Теорема. Пусть выполнены условия A1 и A2 и кроме того, будем считать, что функция P (X)X является выпуклой. Тогда в модели Курно существует и единственное равновесие по Нэшу. P.S. Если P (X) вогнута, то и P (X)X вогнута (P 00 (X) 6 0) (P (X)X)00 = P 00 (X)X + 2P 0 (X) =⇒ P 00 (X)X 6 0). Доказательство. Существование [0, M ] — множество стратегий i-го игрока — выпуклый компакт (выполнено 1-ое условие теоремы Нэша). ui (~x) — непрерывная функция по совокупности переменных (x1 , ..., xn ) (выполнено 2-ое условие теоремы Нэша). Покажем, что ui (xi , ~x−i ) вогнута по xi при условии, что стратегии всех остальных игроков фиксированны. Так как существует вторая производная, то надо показать, что она неположительна. n n X X ∂ 2 ui (xi , ~x−i ) d2 ci (xi ) 00 = P ( x )x + 2P ( xj ) − j i 2 ∂xi dx2 j=1 j=1 | {zi } >0 Достаточно доказать, что n n X X P ( xj )xi + 2P ( xj ) 6 0 00 j=1 1. Если P 00 ( n P j=1 xj ) 6 0, то (1) очевидно j=1 (1) 51 2. Если P 00 ( n P xj ) > 0, то можно сделать следующую оценку: j=1 P 00 ( n X n n n n X X X X xj )xi + 2P 0 ( xj ) 6 P 00 ( xj ) xj + 2P 0 ( xj ) 6 {P (X)X — вогнута} 6 0 j=1 j=1 j=1 j=1 j=1 =⇒ по теореме Нэша существует равновесие по Нэшу в модели Курно. Единственность Пусть есть еще одно равновесие по Нэшу (x∗1 , ..., x∗n ). n P Обозначим G = x∗j — суммарный выпуск. j=1 Мы знаем, что ui (x∗i , ~x∗−i ) = max {P (xi + X xi ∈[0,M ] x∗j )xi − ci (xi )} i6=j Без ограничения общности можно считать, что M = ∞ (при xi > M прибыль становится отрицательной ⇒ максимум будет тот же). Производная функции в точке максимума равна нулю: dci (x∗ i) P 0 (G)x∗i + P (G) − dx = 0, еслиx∗i > 0 i∗ dci (xi ) ∗ P (G)xi + P (G) − dxi 6 0, еслиx∗i = 0 Задача дополнительности для i-го производителя: ( i (xi ) P 0 (G)xi + P (G) − dcdx i dc i (xi ) xi [P 0 (G)xi + P (G) − dx ] i 6 = (2) i (xi ) В первом неравенстве P 0 (G)xi < 0 и dcdx > 0. Для i-го производителя его оптимальное i решение является решением задачи дополнительности (∀i). Как устроено решение задачи дополнительности? Есть два варианта: 1. Производитель ничего не выпускает ⇒ он избыточен. 2. Он выпускает ровно столько, что выполняются все условия. Решение (2) определяет функцию xi (G) — определяет однозначно, т.е. она единственна. При i (xi ) i (xi ) > 0 ⇒ P 0 (G)xi + P (G) − dcdx нашем предположении о том, что P 0 (G) < 0 и dcdx i i — монотонно убывает по xi , при G фиксированном, причем в пределе при x → ∞ функция i (xi ) монотонно убывает, то возможны два стремится к −∞. Так как P 0 (G)xi + P (G) − dcdx i варианта: 1. или ∃xi (G) : P 0 (G)xi + P (G) − 2. или xi (G) = 0 dci (xi ) dxi =0 (?) Обозначим: I(G) = {i | xi (G) > 0} — те фирмы которые что-то выпускают. Продифференцируем (?): i (G) P 00 (G)xi (G) + P 0 (G) dxdG + P 0 (G) − =⇒ dxi (G) dG = P 00 (G)xi (G)+P 0 (G) d2 ci − P (G) dx2i | {z } |{z} >0 <0 d2 ci dxi (G) dG dx2i =0 52 Видно, что знаменатель никогда не обращается в ноль. Введем еще два обозначения: i (G) > 0} I+ (G) = {i ∈ I(G) | dxdG dxi (G) 6 0} I− (G) = {i ∈ I(G) | dG I+ (G) — агенты которые при увеличении G ведут себя агрессивно. I− (G) — агенты которые при увеличении G ведут себя пассивно. 00 (G) i (G) Если i ∈ I+ (G), то 0 6 dxdG 6 −1 − xi (G) PP 0 (G) 00 (G) i (G) Если i ∈ I− (G), то − 1 − xi (G) PP 0 (G) 6 dxdG 60 00 P (G)G – вогнута ⇒ P (G)G + 2P (G) 6 0 00 (G) 2 >G , i ∈ I0 (G) ⇒ xi (G) > G − PP 0 (G) 2 {Один агент не может контролировать более половины рынка} =⇒ |I − +(G)| 6 1 Хотим доказать, что G − n P xi (G) = 0, то есть хотим доказать, что эта величина монотонна. i=0 Просуммируем по всем агентам, которые хоть что-то производят: X dxi (G) X dxi (G) 1− >1− dG dG i∈I(G) 1. |I+ (G)| = 0, 2. |I+ (G)| = 0, n P d dG [G − 1− P 3.3.2 xi (G)] > 0 i=1 i∈I+ (G) =⇒ i∈I+ (G) dxi (G) dG 00 (G) > 2 − xi (G) PP 0 (G) >0 решение модели Курно единственно. Монополия Производитель один и он распоряжается всеми производственными мощностями. Введем некоторые обозначения: c(x) = min{ n X ci (xi ) | i=1 n X xi = x, xi > 0, i = 1, ..., n} i=1 — суммарная функция издержек, можно заметить, что каждый выпуск > 0. Монополист хочет максимизировать объем, что бы издержки были минимальными. Эту функцию можно представить в таком виде: M M c(x) = c1 (x) ... cn (x) в выпуклом анализе функция такого вида называется конволюцией. Если c(x) выпукла, то и все ci (x) выпуклы. Усилим требования на ci (x): d2 ci (x) dci (x) > 0, <0 dx dx2 Задача. Доказать, что c(x) дифференцируема. A20 ∀i ∈ N ci (x) ∈ C 2 , Лемма. Пусть x1 (x), ..., xn (x)) решение задачи:  Pn  Pi=1 ci (xi ) −→ min n i=1 xi = x  x1 > 0, ..., xn > 0 тогда, если xj (x) > 0, то dc(x) dcj (xj (x)) = dxj dx 53 Доказательство. Составим функцию Логранжа и воспользуемся теоремой Куно-Таккера: L(~x, λ) = sumni=1 ci (xi ) + λ[x − n X xi ] i=1 dc (x (x)) Если xj (x) > 0, то j dxjj Введем обозначение: =λ I(x) = {i | xi (x) > 0} тогда P P c(x) = ci (xi (x)) + ck (0) i∈I(x) k∈I(x) / P dci (xi (x)) dxi (x) P dxi (x) dc(x) =λ = dx = dxi dx dx i∈I(x) i∈I(x) P P = {x = xi (x) – дифференцируем по x ⇒ 1 = i∈I(x) i∈I(x) ∂xi (x) ∂x } =λ Замечание. Если фирма ничего не выпускает (xj (x) = 0), то предельные издержки должны dcj (0) быть выше чем ( dx > dc(x) dx ). j Лемма. Pn dcj (x∗j ) dcj (x∗j ) dc( i=1 x∗i ) 6 6 max∗ dxj dx dxj j∈I(x) j∈I(x ) min Здесь x∗1 , ..., x∗n — равновесие по Нэшу вмодели Курно, x∗ = n P i=1 x∗i , I(x∗ ) = {j | x∗j > 0}. Доказательство. ( c(x) = min n X ci (xi )| n X ) xi = x, xi 6 0 n X xi ( x∗j ) 6= x∗i i=1 i=1 i=1 Пусть dci (x∗i ) 6 dxi a)xi n P j=1 dci n P xi j=1 !! x∗j , dxi ! x∗j >0 dci (x∗i ) = dxi n P dci j=1 dxi ! x∗j < dci (x∗i ) dxi Из вогнутости следует, что   n X xi  x∗j  < x∗i j=1 b)xi n P j=1 ∀i ∈ I ! x∗j = 0 6 x∗i n X i=1   n n X X xi  x∗j  < x∗i j=1 i=1 54 P (x)x − c(x) −→ max — монополист максимизирует свою прибыль. χµ — решение задачи дополнительности, χµ > 0 : ( c(χ ) P 0 (χµ )χµ + P (χµ ) − dχµ 6 0 χµ [P 0 (χµ )χµ + P (χµ ) − 3.3.3 c(χµ ) dχ ] = Совершенная конкуренция pxi − ci (xi ) −→ maxxi >0 — для каждого производитьеля. p – цены, i = 1, ..., n. p считаем фиксированным, находим xi , x̂i (p) – решение задачи. Определение. pc — назвается ценой совершенной конкуренции, если n X P( x̂i (pc )) = pc i=1 xc = n P x̂i (pc ) — выпуск в условиях совершенной конкуренции. i=1 Задача. Если xc является выпуском в условиях совершенной конкуренции, то P (xc ) = dc(xc ) dx {Предельные издержки установятся на уровне цены} Из этого упражнения следует следующий факт: xµ < xc Доказательство. Рис. 3.3: На рисунке 3.3 дана иллюстрация. P (X) − dc(x) dx — монотонно убывает. Достаточно доказать, что P (xµ ) − xµ < xv ⇐⇒ P (xµ ) − dc(xµ ) >0 xµ А это верно, так как P (xµ ) − dc(xµ ) = −xµ P 0 (xµ ) > 0 xµ dc(xµ ) dxµ > 0 т.к. 55 Рассмотрим {~ p∗ , ~x∗1 , ..., ~x∗m , ~y1∗ , ..., ~yn∗ } : 1) ∀ j = 1, ..., n ~yj∗ ∈ ψ̃j (~ p∗ ) = arg max p~∗ ~y ~ y ∈Yi p∗ ) = arg max{ui (vx) | p~∗ ~x 6 p~∗ w ~ (i) + 2) ∀ i = 1, ..., m ~x∗i ∈ ϕ̃i (~ 3) m X ~x∗i 6 i=1 (~ p∗ , m X m X w ~ (i) + i=1 n X αij π̃j (~ p∗ ), ~x 6 0} ~yi∗ (3.1) j=1 i=1 w ~ (i) + n X P ~yj∗ − j=1 m X ~x∗i ) = 0 (3.2) i=1 3.3.4 Модификация функций спроса и предложения. Теорема (Эрроу–Дебре). Пусть выполнены следующие условия : P1 Yj являются выпуклыми замкнутыми множествами, 0 ∈ Yj (j = 1, ...n) C1 ui (~x) – вогнутая непрерывная на Rl+ ненасыщаемая функция (i = 1, ..., n) C2 w ~ (i) > 0 (i = 1, ..., m) P2 Y = n P Yj – алгебраическая сумма множеств, Y ∩ Rl+ = {0} (условие отсутствия j=1 рога изобилия) P3 Y ∩ (−Y ) = {0} (условие необратимости технологических процессов) C-P m P αij = 1 (j = 1, ..., n) (прибыль производителей полностью распределена между по- i=1 требителями), тогда существует конкурентное равновесие. Рассмотрим для каждого производителя вспомогательное множество : Ỹj = {~y ∈ Yj | m X w ~ (i) + i=1 X ~yk + ~y > 0, ~yk ∈ Yk k 6= j} k6=j — множество наборов, которые могут быть реализованы, используя запасы потребителя и технологии так, что ~y обеспечивается ресурсами. Если реализуется конкурентное равновесие, то ~yj∗ ∈ Ỹj (из (3.1)) ⇒ ограничимся только теми наборами, которые могут быть реализованы, т.е. m n X X X̃ = {~x > 0 | ∃ ~yj ∈ Yj (j = 1, ..., n) w ~ (i) + ~yj > ~x} (3.3) i=1 j=1 Лемма. Множества Ỹj , X̃ являются ограниченными. Доказательство. Достаточно доказать, что Ỹj – ограничено, т.к. в (3.3) w ~ (i) – фиксировано, ~yj – ограничено в силу ограниченности Ỹj ⇒ X̃ – ограничено. Докажем ограниченность всех Ỹj от противного : ∃ ~yj (ν) ∈ Yj m X i=1 w ~ (i) + n X j=1 ~yj (ν) > 0 (3.4) 56 Пусть µ(ν) = max k~yj (ν)k > 0 16j6n ⇒ (3.5) lim µ(ν) = +∞ ν→∞ Поделим (3.4) на µ(ν) m n 1 X (i) X ~yj (ν) w ~ + >0 µ(ν) i=1 µ(ν) j=1 (3.6) ~ y (nu) по построению jµ(ν) 6 1 ⇒ последовательность ограничена, следовательно можно выделить сходящуюся подпоследовательность : ~yj (ν(t)) = ~yˆj t→∞ µ(ν(t)) (3.7) lim По предположению Yj – выпукло :   ~yj (ν(t)) 1 1 1 = ~yj + 1 − 0 ∈ Yj , т.к. 0, ~yj ∈ Yj , 0 < < 1 ( в силу (3.5) ) µ(ν(t)) µ(ν(t)) µ(ν(t)) µ(ν(t)) Yj – замкнуто ⇒ ~yˆj ∈ Yj Переходя к пределу в (3.6), получим n X ~yˆj > 0 (3.8) j=1 По построению µ(ν) по крайней мере при одном j ~j (ν) y µ(ν) =1⇒ существует по крайней мере одно j0 : 1 6 j0 6 n : ~yˆj0 6= 0 (3.9) Воспользуемся предположениями теоремы Эрроу–Дебре. n P По условию P2 (Y ∩ Rl+ = {0}) ~yˆj = 0 j=1 P P Pˆ ~yˆs = ~yˆs + 0∈Y = Yj ⇒ −~yˆs = ~y j + 0 ∈ −Y (по (3.8)) ⇒ ~yˆs ∈ Y ∩ (−Y ) ⇒ по P3 j k6=s j6=s ~yˆs = 0, что противоречит (3.9) Выберем достаточно большой замкнутый параллелепипед E ⊂ Rl Хотим, чтобы Ỹj ⊂ int E, X̃ ⊂ int E, 0 ∈ int E (3.10) E = {~x | ~a 6 ~x~b}, a и b выбирем из (3.10) (это можно сделать, т.к. X̃ и Ỹj – ограничены). Рассмотрим вспомагательные задачи, в которых можество затрат–выпусков ограничено параллелепипедом E. ψj (~ p) = arg max p~~y . Этот максимум достигается, т.к. Yj ∩ E – компакт, p~~y – линейная непреy ∈Yj ∩E ~ рывная функция. πj (~ p) = max p~~y y ∈Yj ∩E ~ Функцию спроса и предложения можно переписать в виде : n P ϕi (~ p) = arg max{ui (~x) | ~x > 0 и p~~x 6 p~w ~ (i) + αij πj (~ p), ~x ∈ E} j=1 Функция избыточного предложения : m m n P P P χ(~ p) = w ~ (i) + ψj (~ p) − ϕi (~ p) i=1 j=1 ∗ i=1 ∗ Лемма. Пусть p~ > 0, p~ 6= 0 такой, что χ(~ p∗ ) ∩ Rl+ 6= ∅, тогда существует конкурентное ∗ равновесие с ценами p~ 57 Доказательство. ∃ ~x∗i ∈ ϕ(~ p∗ ), ~yj∗ ∈ ψ(~ p∗ ) m n m P P P w ~ (i) + ~yj∗ − ~x∗i > 0 i=1 j=1 i=1 {~ p∗ , ~x∗1 , ..., ~x∗m , ~y1∗ , ..., ~yn∗ } является конкурентным равновесием. 1) Докажем, что ~yj∗ ∈ ψ̃j (~ p∗ ) от противного : ~yj∗ ∈ Ỹj ⊆ intE по построению ⇒ ∃ ~y˜j ∈ Yj : p~∗ ~y˜j > p~∗ ~yj∗ ~y (t) = t~yj∗ + (1 − t)~y˜j ⇒ p~∗ ~y (t) > p~∗ ~yj∗ ∀ t ∈ (0, 1] ⇒ ∃ 0 < t < 1: ~y (t) ∈ Yj ∩ E, что противоречит ~yj∗ ∈ ψ(~ p∗ ) ⇒ ~y∈ ψ̃j (~ p∗ ), πj (~ p∗ ) = π̃j (~ p∗ ) 2) Докажем, что ~x∗i ∈ ϕ̃i (~ p∗ ) : n P ˜ > 0, p~∗ ~x 6 p~w ˜ ) > ui (~x∗ ) предположим противное ∃ ~x ~ (i) + αij π̃j (~ p) и ui (~x i j=1 ~x(t) = t~x∗i + (1 − t)~y˜ > 0 t ∈ (0, 1] По неравенству Иенсена для вогнутых функций : ˜ ) > ui (~x∗ ) t ∈ (0, 1] ui (~x(t)) > tui (~x∗i ) + (1 − t)ui (~x i ∗ ~xi ∈ X̃ ⊆ intE ⇒ ∃ 0 < t0 < 1 : ~x(t0 ) ∈ E n P ˜ , ~x∗ – удовлетворяют бюджетным ограничениям ⇒ p~∗ ~x(t) 6 p~∗ w ~∗ + αij π̃j (~ p), т.е. ~x(t) ~x i j=1 тоже удовлетворяет бюджетным ограничениям ⇒ противоречие с те, что ~x∗i ∈ ϕ( p~∗ ), т.к. нашли точку, которая лучше. 3) Если p~∗s > 0, то m P i=1 Неравенство p~∗ ~x∗i n P w ~ (i) [s] + ∗ 6 p~ w ~ i∗ + j=1 n P ~yj∗ [s] − m P i=1 ~x∗i [s] = 0 ∗ αij π̃j (~ p ) превращается в равенство j=1 Задача. Доказать это. ⇒ m P i=1 p~∗ = m P i=1 p~∗ w ~ i∗ + m P n P αij π̃j (~ p∗ ) = i=1 j=1 m P i=1 p~∗ w ~ i∗ + n P (~ p∗ ) = j=1 m P i=1 p~∗ w ~ i∗ + n P j=1 p~∗ ~yj∗ Лемма (Закон Вальраса в широком смысле). Пусть ~u ∈ χ(~ p), где p~ > 0, p~ 6= 0, то p~~u > 0 Задача. Доказать лемму. Лемма (Гейл–Никайдо–Дебре). Пусть S = {(p1 , ..., pl ) > 0| l P ps = 1}, χ: S → 2Γ , где Γ – s=1 выпуклый компакт в Rl . Если 1) ∀ p~ ∈ S χ(~ p) – непустое выпуклое множество; 2) χ – замкнутое отображение; 3) ∀ p~ ∈ S, u ∈ χ(~ p) p~~u > 0 Тогда ∃ p~∗ ∈ S: χ(~ p∗ ) ∩ Rl+ 6= ∅ Доказательство. Вспомним точечное отображение : ∀ p~ ∈ S, ~u ∈ Γ ставится в соответствие вектор из S θi (~ p, ~u) = pi + max(0, −ui ) , l P 1+ max(0, −us ) s=1 i = 1, ..., l (3.11) 58 P P θi = 1, т.к. pi = 1 θ : S × Γ → S непрерывно и однозначно. Декартово произведение θ~ × χ: S × Γ → 2S×Γ ~ p, ~u), χ(~ (θ(~ p)) ⊂ S × Γ θ~ × χ: S × Γ → 2S×Γ непустое выпуклое отображение, θ~ × χ – замкнутое отображение, S × Γ – выпуклый компакт ⇒ по теореме Какутани существует неподвижная точка ∃ p~∗ ∈ S, ~ p∗ , ~u∗ ) = p~∗ , ~u∗ ∈ χ(~ ~u∗ ∈ Γ: θ(~ p∗ ) ⇒ (3.11) примет вид : p∗i + max(0, −u∗i ) = p∗i l P 1+ max(0, −u∗s ) s=1 ⇒ p∗i l X max(0, −u∗s ) = max(0, −u∗i ) (3.12) s=1 Умножим (3.12) на u∗i и просуммируем : 0 6 p~∗ ~u∗ l X max(0, −u∗s ) = s=1 l X u∗i max(0, −u∗i ) = − i=1 l X 2 (max(0, −u∗i )) 6 0 i=1 ⇒ max(0, −u∗i ) = 0 ⇒ u∗i > 0 ∀ i = 1, ..., l ⇒ ~u∗ > 0 ⇒ χ(~ p∗ ) ∩ Rl+ 6= ∅ Задача. Доказать 2). Пример (Эрроу). l = 2, m = 2, n = 1, Y = {0} u1 (x1 , x2 ) = x1, w ~ (1) = (1, 1), u2 (x1 , x2 ) = x1 + x2 , w ~ (2) = (0, 1). Конкурентное равновесие не существует. Пусть существуют равновесные цены p1 и p2 . p2 = 0 ⇒ неограниченный спрос на второй товар у второго потребителя, а его запас ограничен ⇒ равновесия не существует. Теорема (Первая теорема теории благосостояния). Пусть {~ p∗ , ~x∗1 , ..., ~x∗m , ~y1∗ , ..., ~yn∗ } – конкурентное равновесие. Тогда оно оптимально по Паретто, т.е. 6 ∃ ~x1 , ..., ~xm , ~y1 , ..., vyn : 1) ~yj ∈ Yj j = 1, ..., n 2) m P i=1 w ~ (i) + n P j=1 ~yj > m P xi i=1 3) ui (~xi ) > ui (~x∗i ) (i = 1, ..., m) Задача. Доказать эту теорему. ∃ ui0 (~xi ) > ui0 (~x∗i )