Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja I – 2. Wielościany – MIM UW

Zagadnienia

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.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.