Zagadnienia

2.1 Przestrzenie afiniczne
2.2 Wielościany

2. Wielościany

2.1. Przestrzenie afiniczne

Zbiorowi ciągów $n$ elementowych o współczynnikach rzeczywistych $\mathbb{R}^{n}$ można nadać strukturę przestrzeni liniowej wprowadzając dodawanie ciągów ( wektorów ) i mnożenie przez liczby. Można też nadać strukturę przestrzeni afinicznej wprowadzając następujące działanie zwane środkiem ciężkości lub kombinacją afiniczną.

Definicja 2.1

Układem wag nazywamy taki ciąg liczb rzeczywistych $r_{1},r_{2},\ldots,r_{t}$ , że $\sum _{{i=1}}^{t}r_{i}=1$ . Niech $p_{1},p_{2},\ldots,p_{t}$ będzie ciągiem punktów z $\mathbb{R}^{n}$ . Środkiem ciężkości punktów $p_{i}$ o wagach $r_{i}$ nazywamy punkt $p=\sum _{{i=1}}^{t}\, r_{i}p_{i}$ .

Branie środka ciężkości ma następujące własności:

1) $1p=p$

2) $\sum _{{i=1}}^{t}\ r_{i}p_{i}=\sum _{{i=1}}^{t}\ r_{i}p_{i}+0q$

3) Jeżeli $p_{j}=\sum _{{i=1}}^{t}\ r_{{i,j}}q_{i}$ i $a=\sum _{{j=1}}^{k}\ s_{j}p_{j}$ to $a=\sum _{{j=1}}^{k}\ s_{j}\sum _{{i=1}}^{t}\ r_{{i,j}}q_{i}\ =\ \sum _{{i=1}}^{t}\ \left(\sum _{{j=1}}^{k}\ s_{j}r_{{i,j}}\right)\ q_{i}$ .

Definicja 2.2

Podprzestrzenią afiniczną nazywamy podzbiór $\mathbb{R}^{n}$ zamknięty ze względu na branie środków ciężkości.

Twierdzenie 2.1

Niech W będzie niepustym podzbiorem $\mathbb{R}^{n}$ . Wówczas równoważne są warunki:

1) W jest przestrzenią afiniczną.

2) W jest postaci $W=p+V=\{ p+\alpha\ |\ \alpha\in V$ , gdzie $p\in W$ i $V$ jest podprzestrzenią liniową $\mathbb{R}^{n}$ .

3) W jest zbiorem rozwiązań pewnego układu równań liniowych.

Definicja 2.3

Układem bazowym przestrzeni afinicznej $W=p+V$ nazywamy ciąg $(p\,;\alpha _{1},\alpha _{2},...,\alpha _{n})$ , gdzie ciąg $(\alpha _{1},\alpha _{2},...,\alpha _{n})$ jest bazą przestrzeni liniowej $V$ .

Każdy układ bazowy wyznacza izomorfizm afiniczny przestrzeni $W$ na $\mathbb{R}^{n}$ zadany wzorem: $\varphi(p+\sum _{{i=1}}^{n}\ a_{i}\alpha _{i})=(a_{1},a_{2},...,a_{n})$ .

Definicja 2.4

Niech $T$ będzie niepustym podzbiorem przestrzeni afinicznej $R^{n}$ . Symbolem $af(T)$ oznaczać będziemy podprzestrzeń afiniczną rozpiętą przez $T$ , czyli zbiór wszystkich środków ciężkości punktów z $T$ .

To znaczy. Jeżeli $p_{0}\in T$ to $af(T)\ =p_{0}+lin\{\overrightarrow{p_{0},p}\,|\, p\in T\}=\\ \left\{ p_{0}+\sum _{{i=1}}^{k}a_{i}\overrightarrow{p_{0},p_{i}}\ |\ p\in T\right\}=\left\{\sum _{{i=0}}^{k}a_{i}p_{i}\ |\ p\in T,\sum _{{i=0}}^{k}a_{i}=1\right\}$ . gdzie ciąg $a_{0},a_{1},...,a_{k}$ jest układem wag.

Uwaga 2.1

Z dowolnego ciągu liczb rzeczywistych $(a_{1},a_{2},...,a_{k})$ można zrobić układ wag $(a_{0},a_{1},a_{2},...,a_{k})$ przyjmując $a_{0}=1-\sum _{{i=1}}^{k}a_{i}$ .

Definicja 2.5

Wymiarem zbioru T nazywamy wymiar przestrzeni $af(T)$ .

Definicja 2.6

Niech $T$ będzie niepustym podzbiorem przestrzeni afinicznej $R^{n}$ . Symbolem $Conv(T)$ zbiór wszystkich środków ciężkości punktów z $T$ o wagach nieujemnych.

To znaczy. Jeżeli $p_{0}\in T$ to $Conv(T)\ =\left\{\sum _{{i=0}}^{k}a_{i}p_{i}\,|\, p_{i}\in T,\sum _{{i=0}}^{k}a_{i}=1,a_{i}\geq 0\right\}=\\ =\left\{ p_{0}+a_{0}\overrightarrow{p_{0},p_{0}}+\sum _{{i=1}}^{k}a_{i}\overrightarrow{p_{0},p_{i}}\ |\ p_{i}\in T,\sum _{{i=0}}^{k}a_{i}=1,a_{i}\geq 0\right\}=\\ =\left\{ p_{0}+\sum _{{i=1}}^{k}a_{i}\overrightarrow{p_{0},p_{i}}\ ,|\ p_{i}\in T,\sum _{{i=1}}^{k}a_{i}\leq 1,a_{i}\geq 0\right\}$ .

Przykład 2.1

Uwypukleniem trzech punktów $A=(0,0)$ , $B=(0,2)$ i $C=(5,2)$ jest trójkąt $\triangle ABC=Conv(\{ A,B,C\})=\{ a_{1}A+a_{2}B+a_{3}C\ |\ a_{1}+a_{2}+a_{3}=1,a_{i}\geq 0\}=\{(5a_{3},2a_{2}+2a_{3})\ |\ a_{1}+a_{2}+a_{3}=1,a_{i}\geq 0\}=\{(0,0)+a_{2}(0,2)+a_{3}(5,2)\ |\ a_{2}+a_{3}\leq 1,a_{i}\geq 0\}$

Twierdzenie 2.2

$Conv(T)$ jest najmniejszym zbiorem wypukłym zawierającym $T$ .

1) Wypukłość.

Niech $p=\sum _{{i=0}}^{k}\; a_{i}p_{i}$ oraz $q=\sum _{{i=0}}^{k}\; b_{i}p_{i}$ będą dwoma punktami z $Conv\ T$ . Zatem $p_{i}\in T$ , $\sum _{{i=0}}^{k}a_{i}=1=\sum _{{i=0}}^{k}b_{i}$ oraz $a_{i}\geq 0,\ b_{i}\geq 0$ . Dowolny punkt odcinka $[p,q]$ jest postaci $(1-t)p+tq$ , gdzie $t\in[0,1]$ . Teraz $(1-t)p+tq=(1-t)\sum _{{i=0}}^{k}\; a_{i}p_{i}+t\sum _{{i=0}}^{k}\; b_{i}p_{i}=\sum _{{i=0}}^{k}\left((1-t)a_{i}+tb_{i}\right)p_{i}\in Conv(T)$ , gdyż $\sum _{{i=0}}^{k}\left((1-t)a_{i}+tb_{i}\right)=1$ i współczynniki są nieujemne.

2) Minimalność.

Niech $X$ będzie zbiorem wypukłym zawierającym $T$ . Pokażemy przez indukcję względem długości zapisu kombinacji wypukłej, że każdy punkt z $Conv(T)$ należy do $X$ .

Niech $p=\sum _{{i=0}}^{k}\; a_{i}p_{i}\in Conv\ T$ , gdzie $p_{i}\in T$ , $\sum _{{i=0}}^{k}a_{i}=1$ oraz $a_{i}\geq 0$ .

$1^{0}$ $k=0$ . Wtedy $p=p_{0}\in T\subset X$ .

$2^{0}$ Krok indukcyjny. Zakładamy, że $k>0$ i każda kombinacja wypukła długości $<k$ należy do $X$ .

Punkt $p$ przedstawiamy w postaci kombinacji wypukłej $p=\sum _{{i=0}}^{k}\; a_{i}p_{i}=a_{0}p_{0}+(1-a_{0})q$ , gdzie $q=\sum _{{i=1}}^{k}\;\frac{a_{i}}{1-a_{0}}p_{i}$ . Ponadto punkt $q\in X$ z założenia indukcyjnego. Gdyby $1-a_{0}=0$ to $p=p_{0}$ .

∎

Definicja 2.7

Hiperpłaszczyzną $V$ podpierającą zbiór wypukły $W\subset\mathbb{R}^{n}$ w punkcie $p$ nazywamy taką podprzestrzeń afiniczną $V$ , że: $dimV=n-1$ , $p\in V$ , $W$ leży po jednej stronie $V$ to znaczy istnieje taka półprzestrzeń $H$ zawierająca $W$ , że $V=\partial H$ jest brzegiem i $p\in\partial H$ . Inaczej mówiąc $V$ jest opisana równaniem

$V=\left\{ x\in\mathbb{R}^{n}\,|\,\alpha\bullet x=b\right\}$ ,

gdzie $\alpha\in R^{{n}}$ i $b\in R$ są takie, że $\forall _{{x\in W}}\;\;\alpha\bullet x\leq b$ oraz $\alpha\bullet p=b$ .

Twierdzenie 2.3

Jeżeli $W$ jest zbiorem wypukłym i domkniętym i $p\in\partial W$ ( $p$ należy do brzegu $W$ ) to istnieje hiperpłaszczyzna podpierająca zbiór $W$ w punkcie $p$ .

Niech $p\in\partial W$

Istnieje zatem ciąg punktów $p_{{1}},p_{{2}},...$ $\not\in W$ taki że $\varrho(p_{{i}},p)<\frac{1}{i}$ .

Z każdym z tych punktów związujemy pewną hiperpłaszczyznę rozdzielającą wyznaczoną przez wektory $\alpha _{i}$ oraz liczby $b_{i}$ spełniające warunki:

1 ${}^{{\circ}}$ $p_{{i}}\bullet\alpha _{{i}}\,>b_{{i}}$

$2^{{\circ}}\qquad\forall _{{q\in W}}\quad q\bullet\alpha _{i}\,\leq b_{i}$

( $\left\{ x\in\mathbb{R}^{n}\,|\, x\bullet\alpha _{i}\,\leq b_{{i}}\right\}$ jest półprzestrzenią zawierającą W, której brzeg jest hiperpłaszczyzną rozdzielającą $p_{{i}}$ oraz $W$ )

3 ${}^{{\circ}}\qquad\alpha _{{i}}\bullet\alpha _{i}\,+b_{{i}}^{{2}}$ $=1$

Przyjmijmy $\overline{\alpha _{{i}}}=\left(\alpha _{{i}},b_{i}\right)\in\mathbb{R}^{{n+1}}$ .

Zbiór $\overline{\alpha _{{1}}}$ , $\overline{\alpha _{{2}}}$ , … jest zwarty w kuli jednostkowej $K(0,1)\subset R^{{n+1}}$ . Ponieważ $K(0,1)$ jest zwarta, to w ciągu $\overline{a_{{i}}}$ możemy wybrać podciąg zbieżny (ze względów redakcyjnych przyjmujemy, bez zmniejszenia ogólności, że $\overline{\alpha _{{i}}}$ jest zbieżny ).

Oznacza to, że zbieżne też są ciągi $\alpha _{{i}}$ oraz $b_{i}$ .

Przyjmijmy:

$\underset{i\rightarrow\infty}{lim}$ $\alpha _{{i}}=\alpha$

$\underset{i\rightarrow\infty}{lim}$ $b_{{i}}=b$

Ponadto $\underset{i\rightarrow\infty}{lim}$ $\overline{\alpha _{{i}}}=\overline{\alpha}\;$ implikuje $\left\|\overline{\alpha}\right\|=1$ .

Badamy $H=\left\{ x\,|\,\alpha\bullet x\,\leq b\right\}$ .

Dla dowolnego punktu $q\in W$ $\alpha _{i}\bullet q\,\leq b_{i}$ więc $\alpha\bullet q\,\leq b$ (bo nierówności tępe zachowują się przy przejściu do granicy). Więc $W\subseteq H$ .

Aby wykazać, że $\partial H$ jest hiperpłaszczyzną podpierającą $W$ w punkcie $p$ wystarczy pokazać $\alpha\bullet p=b$ . Ponieważ $p\in W$ więc $\alpha\bullet p\,\leq b$ . Ponadto $p\bullet a\,=\underset{i\rightarrow\infty}{lim}p\bullet a_{i}\,\geq\quad\underset{i\rightarrow\infty}{lim}\ b_{{i}}=b$

∎

2.2. Wielościany

Definicja 2.8

Wielościanem (uogólnionym) w $\mathbb{R}^{{n}}$ nazywamy część wspólną skończonej rodziny półprzestrzeni.

W szczególności zbiór pusty $\emptyset$ i $\mathbb{R}^{{n}}$ jako przecięcie pustej rodziny półprzestrzeni są wielościanami.

Ponieważ każdy zbiór wypukły i domknięty jest przecięciem półprzestrzeni, patrz twierdzenie 1.7, więc może być aproksymowany wielościanami z dowolną dokładnością. Szukanie ekstremów funkcji tylko na wielościanach nie jest więc poważnym ograniczeniem.

Tak jak trójkąt jest trójkątem niezależnie czy traktujemy go jako podzbiór płaszczyzny, przestrzeni 3 - wymiarowej czy większej tak też następne twierdzenie pokazuje, że pojęcie wielościanu nie zależy od wymiaru przestrzeni.

Twierdzenie 2.4

Definicja wielościanu nie zależy od przestrzeni w której go rozpatrujemy. W szczególności jeżeli $W$ jest niepustym podzbiorem w przestrzeniach afinicznych $V_{1}\subset V_{2}$ . Wówczas $W$ jest wielościanem w $V_{1}$ wtedy i tylko wtedy, gdy $W$ jest wielościanem w $V_{2}$ .

Przyjmijmy $V_{1}\simeq\mathbb{R}^{n}$ i $V_{2}\simeq\mathbb{R}^{t}$

$\Rightarrow$

Wprowadźmy układ bazowy $(p;\alpha _{1},\alpha _{2},...,\alpha _{n})$ przestrzeni $V_{1}$ i rozszerzamy go do układu bazowego $(p;\alpha _{1},\alpha _{2},...,\alpha _{n},\alpha _{{n+1}},...,\alpha _{t})$ przestrzeni $V_{2}$ . Teraz jeżeli $W=\bigcap _{{i=1}}^{k}H_{i}$ , gdzie $H_{i}\subset V_{1}$ są opisane nierównościami $H_{i}=\{ x\,|\,(a_{{i,1}},a_{{i,2}},...,a_{{i,n}})\bullet x\,\leq b_{{i}}\}$ to w przestrzeni $V_{2}$ zbiór $W$ jest opisany układem nierówności: $(a_{{i,1}},a_{{i,2}},...,a_{{i,n}},0,...,0)\bullet x\,\leq b_{{i}}$ dla $1\leq i\leq k$ oraz $x_{j}\leq 0$ i $-x_{j}\leq 0$ dla $n+1\leq j\leq t$ .

$\Leftarrow$ Niech $W=\bigcap _{{i=1}}^{k}H_{i}$ , gdzie $H_{i}$ są półprzestrzeniami $V_{2}$ . Teraz $W=\bigcap _{{i=1}}^{k}\left(H_{i}\cap V_{1}\right)$ a oczywistym jest, że $H_{i}\cap V_{1}$ może być półprzestrzenią w $V_{1}$ lub całą przestrzenią $V_{1}$ .

∎

Definicja 2.9

Ścianą zbioru wypukłego $W$ nazywamy zbiór $W\cap V$ gdzie $V$ jest hiperpłaszczyzną podpierającą.

Wymiarem ściany nazywamy liczbę $j=dim\ af(W\cap V).$

Wierzchołkiem nazywamy taki punkt $p\in W$ , że istnieje półprzestrzeń H taka, że $W\subset H\$ i $\{ p\}=\partial H\cap W$ .

Uwaga 2.2

Zwykle wierzchołkiem nazywać będziemy nie tylko zbiór $\{ p\}$ ale także punkt $p$ .

Krawędzią $K$ nazywamy ścianę wymiaru 1. Dokładniej $K=\partial H\cap W$ jest krawędzią gdy jest podzbiorem prostej mającym więcej niż 1 element. ( $H$ jest półprzestrzenią i $W\subset H$ ).

Twierdzenie 2.5

Rozpatrujemy zadanie optymalizacji liniowej:

$Max\ x_{0}=c\bullet x\,$ , gdzie $x\in W$ i $W$ jest opisane układem nierówności: $\left\{\begin{array}[]{c}\alpha _{{1}}\bullet x\,\leq b_{{1}}\\ \alpha _{{2}}\bullet x\,\leq b_{{2}}\\ \vdots\\ \alpha _{{t}}\bullet x\,\leq b_{{t}}\end{array}\right.$ .

Niech $p\in W$ będzie takim punktem, że $\alpha _{{i}}\bullet p\,=b_{{i}}$ , dla $i=1,2,...,j$ oraz $\alpha _{{i}}\bullet p\,<b_{{i}}$ , dla $i>j$ . Wówczas:

1) Jeżeli dla pewnych liczb rzeczywistych $r_{1}\geq 0,r_{2}\geq 0,...,r_{j}\geq 0$

$c=\sum _{{i=1}}^{j}\ r_{i}\alpha _{i}$ to $p$ jest punktem optymalnym tego zadania.

2) Jeżeli $p$ jest punktem optymalnym tego zadania to $\partial H=\left\{ x\in R^{n}\ |\, c\bullet x\,=c\bullet p\,\right\}$ jest hiperpłaszczyzną podpierającą $W$ w punkcie $p$ .

ad 1) Niech $q\in W$ . Wtedy $x_{0}(q)=c\bullet q=\sum _{{i=1}}^{j}\ r_{i}\alpha _{i}\bullet q\leq\sum _{{i=1}}^{j}\ r_{i}b_{i}=\sum _{{i=1}}^{j}\ r_{i}\alpha _{i}\bullet p=x_{0}(p)$ . Więc punkt $p$ jest optymalny.

ad 2) Niech $q\in W$ . Wtedy $x_{0}(q)\leq x_{0}(p)$ , co daje $c\bullet q\leq c\bullet p$ . Zatem $q\in H=\left\{ x\in R^{n}\ |\, c\bullet x\,\leq c\bullet p\,\right\}$ i $p\in\partial H=\left\{ x\in R^{n}\ |\, c\bullet x\,=c\bullet p\,\right\}$ .

∎

Uwaga 2.3

Jednym z podstawowych twierdzeń teorii dualności jest:

$p$ jest punktem optymalnym tego zadania wtedy i tylko wtedy gdy dla pewnych liczb rzeczywistych $r_{1}\geq 0,r_{2}\geq 0,...,r_{j}\geq 0$ zachodzi $c=\sum _{{i=1}}^{j}\ r_{i}\alpha _{i}$ .

Uwaga 2.4

Twierdzenie 2.5 pozwala łatwo budować funkcję celu taką, by zbiorem punktów optymalnych była zadana ściana.

Przedstawimy teraz kilka prostych własności ścian.

Stwierdzenie 2.1

Niech $S=W\cap\partial H$ będzie ścianą wielościanu W.

Jeżeli $S\neq W$ to $dim\ S<dim\ W$ .

Niech $q\in W\setminus S$ . Ponieważ $\partial H$ jest przestrzenią afiniczną więc $af(S)\subset\partial H$ i $q\not\in\partial H$ . Zatem $af(S)\neq af(W)$ co implikuje $dim\ S<dim\ W$ .

∎

Lemat 2.1

Niech $S_{1},S_{2},...,S_{t}$ będą ścianami wielościanu $W\subset\mathbb{R}^{n}$ . Wówczas $S=\bigcap _{{\, i=1}}^{{\, t}}\ S_{i}$ jest ścianą $W$ lub zbiorem pustym.

Niech $S_{i}=W\cap\partial H_{i}$ , gdzie $H_{i}=\left\{ x\in\mathbb{R}^{{n}}\,|\,\alpha _{i}\bullet x\,\leq b_{i}\right\}$ . Definiujemy półprzestrzeń $H=\{ x\in R^{{n}}\,|\,\sum _{{i=1}}^{{t}}\alpha _{{i}}\bullet x\,\leq\sum _{{i=1}}^{{t}}b_{{i}}\}$ . Oczywiście jeżeli $q\in W$ to $\forall _{i}\;\alpha _{{i}}\bullet x\,=b_{{i}}$ implikuje $q\in H$ . Ponadto $S\subset\partial H$ .

Niech teraz $q\in\partial H\cap W$ wtedy warunki $\forall _{{i\leq t}}\ \alpha _{{i}}\bullet q\,\leq b_{{i}}$ oraz $\sum _{{i=1}}^{{t}}\alpha _{{i}}\bullet q\,=\sum _{{i=1}}^{{t}}b_{{i}}$ implikują $\alpha _{{i}}\bullet q\,=b_{{i}}$ dla $i\leq t$ . Zatem $S=\partial H\cap W$ .

∎

Lemat 2.2

Niech $K\subset H$ będzie j-wymiarową kulą o środku p zawartą w półprzestrzeni $H$ . Jeżeli $p\in\partial H$ to $K\subset\partial H$ .

Niech $q\in K\cap H\quad q\notin\partial H$ . Przyjmijmy:

$H=\left\{ x\in\mathbb{R}^{n}\,|\,\alpha\bullet x\,\leq b\right\}$ wtedy $\alpha\bullet q\,<b$ i $\alpha\bullet p\,=b$ .

Ale $p=\frac{1}{2}q+\frac{1}{2}q^{{\prime}}\quad$ dla pewnego $q^{{\prime}}\in K$

Dochodzimy do sprzeczności, gdyż z jednej strony

$q^{{\prime}}\in K\subset H$ implikuje $\alpha\bullet q^{{\prime}}\leq b$

zaś z drugiej strony

$\alpha\bullet q^{{\prime}}=\alpha\bullet(2p-q)=2\alpha\bullet p\,-\alpha\bullet q\,=2b-\alpha\bullet q\,>b$ .

∎

Definicja 2.10

Niech $H=\left\{ x\in\mathbb{R}^{{n}}\,|\,\alpha\bullet x\,\leq b\right\}$ będzie półprzestrzenią. Półprzestrzenią dopełniającą nazywamy półprzestrzeń $H^{-}=\left\{ x\in\mathbb{R}^{{n}}\,|\,\alpha\bullet x\,\geq b\right\}$

Stwierdzenie 2.2

Jeżeli H jest półprzestrzenią to $H\cup H^{-}=\mathbb{R}^{n}$ i $H\cap H^{-}=\partial H=\partial H^{-}$ .

Stwierdzenie to prowadzi bezpośrednio do wniosku.

Wniosek 2.1

Niech $W=\bigcap _{{i=1}}^{t}H_{i}\ \subset\mathbb{R}^{n}$ będzie wielościanem. Wówczas, dla każdego j, $S=W\cap\partial H_{j}=W\cap H_{j}^{-}$ jest ścianą wielościanu $W$ lub zbiorem pustym.

Wniosek 2.2

Niech $W=\bigcap _{{i=1}}^{t}\ H_{i}$ zaś $S=W\ \cap\ \bigcap _{{i=1}}^{s}\ H_{i}^{-}$ będzie niepustym podzbiorem. Wówczas S jest ścianą $W$ .

$S=W\ \cap\ \bigcap _{{i=1}}^{s}\ H_{i}^{-}=\bigcap _{{i=1}}^{s}\left(W\cap\ H_{i}^{-}\right)$ jest przecięciem ścian a więc ścianą na mocy lematu 2.1.

∎

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Optymalizacja I