Теорема Вейля — Мінковського: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
Немає опису редагування |
||
Рядок 16:
=== Твердження для опуклих поліедрів ===
Для [[Опуклий політоп|опуклого поліедра]] <math>P</math> (який задається системою нерівностей <math>Ax \leqslant b</math>) існують такі <math>r</math> векторів <math>
: <math>x = \sum_{i=1}^r \alpha_i
==== Наслідок ====
Якщо опуклий поліедр <math>P</math> є обмеженим, то він є [[Опукла комбінація|опуклою комбінацією]] своїх вершин. Тобто кожна точка записується як <math>x = \sum_{i=1}^r \alpha_i
== Доведення ==
Рядок 35:
Якщо <math>P = \{x\ |\ Ax \leqslant 0\}</math> то із [[Лема Фаркаша|леми Фаркаша]] випливає, що <math>P^d</math> є множиною всіх невід'ємних [[Лінійна комбінація|лінійних комбінацій]] стовпців матриці <math>A^T</math>, тобто <math>P^d = \{y\ |\ y = A^Tz,\ z = \R^m, z \geqslant 0\}</math> і також <math>(P^d)^d = P.</math> Із доведеної теореми Вейля випливає існування матриці <math>B</math> для якої <math>P^d </math> є множиною розв'язків нерівностей <math>B^Ty \leqslant 0.</math> Тоді кожна невід'ємна лінійна комбінація стовпців матриці <math>B</math> належить <math>(P^d)^d = P</math> і згідно леми Фаркаша <math>P</math> є множиною всіх таких комбінацій, тобто <math>P = \{x\ |\ x = Bz,\ z = \R^k, z \geqslant 0\},</math> що завершує доведення.
=== Доведення для опуклих поліедрів ===
Нехай <math>P = \{x\ |\ Ax \leqslant b\}</math> є опуклим поліедром у просторі <math>\R^n.</math> Розглядаючи простір <math>\R^{n+1}</math> і ввівши додаткову змінну можна розглянути поліедральний конус заданий нерівностями <math> Ax - bx_{n+1} \leqslant 0,\ -x_{n+1} \leqslant 0 .</math> Поліедр <math>P</math> є перетином цього конусу із [[Гіперплощина|гіперплощиною]] <math> x_{n+1} = 1.</math>
Згідно варіанту теореми для опуклих конусів кожна точка поліедрального конуса є невід'ємною лінійною комбінацією деякої скінченної множини векторів <math>\mathbf{x}_1, \ldots, \mathbf{x}_{r+s}</math> і ці вектори можна вибрати і упорядкувати так, що у перших <math>r</math> із них останні координати будуть рівні 1, а в останніх <math>s</math> векторів остання координата є рівною 0. Тоді довільна точка конуса є невід'ємною лінійною комбінацією <math>x = \sum_{i=1}^r \alpha_i x_i + \sum_{j=1}^s \beta_j x_{r+j},\quad \alpha_i, \beta_j \geqslant 0. </math> Ця точка належить гіперплощині <math> x_{n+1} = 1</math> тоді і тільки тоді, коли додатково <math>\sum_{i=1}^r \alpha_i = 1, </math> що завершує доведення теореми Мінковського для опуклих поліедрів.
Для теореми Вейля, нехай <math>P</math> є множиною усіх елементів виду <math>x = \sum_{i=1}^r \alpha_i \mathbf{x}_i + \sum_{j=1}^s \beta_j \mathbf{x}_{r+j},\quad \alpha_i, \beta_j \geqslant 0, \sum_{i=1}^r \alpha_i = 1, </math> де всі точки належать простору <math>\R^n.</math> Розглядаючи простір <math>\R^{n+1}</math> і ввівши додаткову змінну можна розглянути опуклий скінченнопороджений конус, що є невід'ємною лінійною комбінацією векторів <math>\tilde \mathbf{x}_i, \tilde \mathbf{x}_{r+j}, </math> де перші n координат усіх цих векторів є рівними відповідним координатам векторів <math>\mathbf{x}_i, \mathbf{x}_{r+j}, </math> остання координата векторів <math>\tilde \mathbf{x}_i,\ i = 1,\ldots,r </math> є рівною 1, а остання координата векторів <math>\tilde \mathbf{x}_{r+j},\ j = 1,\ldots,s </math> є рівною 0. Тоді початковий поліедр є перетином скінченнопородженого конуса і гіперплощини <math> x_{n+1} = 1.</math>
Згідно із варіанту теореми для опуклих конусів. Скінченнопороджений конус також є множиною розв'язків деякої системи нерівностей <math>A'x \leqslant 0</math> від ''n''+1 змінної. Прийнявши <math> x_{n+1} = 1</math> одержується система виду <math>Ax \leqslant b</math> від ''n'' змінних, яка і визначає опуклий поліедр.
== Див. також ==
| |||