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 – 4. Geometryczna metoda sympleks – MIM UW

Zagadnienia

4. Geometryczna metoda sympleks

4.1. Twierdzenia strukturalne

Zajmiemy się teraz innym opisem wielościanów.

Twierdzenie 4.1 (Twierdzenie strukturalne)

1) Niech p_{{1}},p_{{2}},...,p_{{t}} oraz \alpha _{{1}},\alpha _{{2}},...,\alpha _{{k}} należą do R^{{n}}. p_{i} traktujemy jako punkty, zaś \alpha _{j} jako wektory. Wówczas zbiór

S=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\ |\ \sum _{{i=1}}^{{t}}r_{{i}}=1,\  r_{{i}}\geq 0,\  s_{{j}}\geq 0\right\}.

jest wielościanem.

2) Jeżeli W jest wielościanem to istnieją takie punkty p_{{1}},p_{{2}},...,p_{{t}} oraz wektory \alpha _{{1}},\alpha _{{2}},...,\alpha _{{k}}, że W=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\ |\ \sum _{{i=1}}^{{t}}r_{{i}}=1,\  r_{{i}}\geq 0,\  s_{{j}}\geq 0\right\}.

3) Jeżeli W jest wielościanem z wierzchołkiem, gdzie p_{{1}},p_{{2}},...,p_{{t}} jest zbiorem wierzchołków W, zaś \alpha _{{1}},\alpha _{{2}},...,\alpha _{{k}} jest zbiorem wektorów kierunkowych krawędzi nieograniczonych, to W=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\ |\ \sum _{{i=1}}^{{t}}r_{{i}}=1,\  r_{{i}}\geq 0,\  s_{{j}}\geq 0\right\}.

Twierdzenie to ma skomplikowany dowód więc przedstawimy go dopiero po wprowadzeniu teorii dualności.

Z twierdzenia strukturalnego wynika, że każdy wielościan można przedstawić w postaci sumy algebraicznej dwóch zbiorów. Gdy W=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\ |\ \sum _{{i=1}}^{{t}}r_{{i}}=1,\ \forall _{{1\leq i\leq t}}\  r_{{i}}\geq 0,\ \forall _{{1\leq j\leq k}}\  s_{{j}}\geq 0\right\} to W=T+S, gdzie T=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}\ |\ \sum _{{i=1}}^{{t}}r_{{i}}=1,\ \forall _{{1\leq i\leq t}}\  r_{{i}}\geq 0\right\} jest wielościanem klasycznym zaś S=\left\{ p_{1}+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\ |\ \forall _{{1\leq j\leq k}}\  s_{{j}}\geq 0\right\} jest stożkiem.

Aby przybliżyć twierdzenie przedstawimy przykład gdy W jest sympleksem:

Przykład 4.1

Niech p_{0},p_{1},\cdots,p_{n} będzie układem punktów z R^{n} w położeniu ogólnym takim, że \det\left[\begin{array}[]{cc}p_{0}&1\\
p_{1}&1\\
\vdots&\vdots\\
p_{n}&1\end{array}\right]>0. Wówczas W=Conv\,\{ p_{0},p_{1},\cdots,p_{n}\} jest wielościanem opisanym układem n+1 nierówności:

0) \det\left[\begin{array}[]{ccccc}x_{1}&x_{2}&\cdots&x_{n}&1\\
&&p_{1}&&1\\
&&\vdots&&\vdots\\
&&p_{n}&&1\end{array}\right]\geq 0

1) \det\left[\begin{array}[]{ccccc}&&p_{0}&&1\\
x_{1}&x_{2}&\cdots&x_{n}&1\\
&&p_{2}&&\\
&&\vdots&&\vdots\\
&&p_{n}&&1\end{array}\right]\geq 0

\vdots

n) \det\left[\begin{array}[]{ccccc}&&p_{0}&&1\\
&&p_{1}&&1\\
&&\vdots&&\vdots\\
&&p_{{n-1}}&&1\\
x_{1}&x_{2}&\cdots&x_{n}&1\end{array}\right]\geq 0.

Ponadto zbiorem wierzchołków W jest \{ p_{0},p_{1},\cdots,p_{n}\} zaś krawędziami są odcinki łączące dowolne dwa wierzchołki.

Niech q\in\mathbb{R}^{n} będzie dowolnym punktem. Ponieważ ciąg (p_{0},p_{1},\cdots,p_{n}) jest bazą punktową \mathbb{R}^{n} więc istnieje taki układ wag (r_{0},r_{1},\cdots,r_{n}), (\sum _{{i=0}}^{{n}}r_{{i}}=1), że q=\sum _{{i=0}}^{{n}}r_{{i}}p_{{i}}. Badamy kiedy punkt q spełnia j - tą nierówność.

\det\left[\begin{array}[]{ccc}p_{0}&&1\\
\vdots&&\vdots\\
p_{{j-1}}&&1\\
q&&1\\
p_{{j+1}}&&1\\
\vdots&&\vdots\\
p_{n}&&1\end{array}\right]=\det\left[\begin{array}[]{ccc}p_{0}&&1\\
\vdots&&\vdots\\
p_{{j-1}}&&1\\
\sum _{{i=0}}^{{n}}r_{{i}}p_{{i}}&&\sum _{{i=0}}^{{n}}r_{{i}}\\
p_{{j+1}}&&1\\
\vdots&&\vdots\\
p_{n}&&1\end{array}\right]=

teraz dla i\neq j od j-tego wiersza macierzy odejmujemy wiersz i-ty pomnożony przez r_{i}.

=\det\left[\begin{array}[]{ccc}p_{0}&&1\\
\vdots&&\vdots\\
p_{{j-1}}&&1\\
r_{{j}}p_{{j}}&&r_{{j}}\\
p_{{j+1}}&&1\\
\vdots&&\vdots\\
p_{n}&&1\end{array}\right]=r_{{j}}\cdot\det\left[\begin{array}[]{cc}p_{0}&1\\
p_{1}&1\\
\vdots&\vdots\\
p_{n}&1\end{array}\right].

Ponieważ przyjęliśmy \left[\begin{array}[]{cc}p_{0}&1\\
p_{1}&1\\
\vdots&\vdots\\
p_{n}&1\end{array}\right]>0, więc punkt q spełnia j - tą nierówność wtedy i tylko wtedy gdy r_{j}\geq 0. Zatem punkt q\in W wtedy i tylko wtedy, gdy spełnia wszystkie n+1 nierówności.

Ponieważ dla każdego j punkt p_{j} spełnia wszystkie za wyjątkiem j - tej nierówności jako równania więc jest wierzchołkiem. Więcej wierzchołków nie ma gdyż n nierówności ze zbioru n+1 elementowego można wybrać na n+1 sposobów. Podobnie n-1 nierówności można wybrać na \left(\begin{array}[]{c}n+1\\
n-1\end{array}\right)=\frac{n(n+1)}{2} sposobów, czyli tyle ile jest par wierzchołków.

Rozpoczynamy od badania wielościanów podobnych do stożków. Wprowadźmy zatem formalną definicję.

Definicja 4.1

S-wielościanem nazywamy wielościan który ma dokładnie jeden wierzchołek.

Stwierdzenie 4.1

Ściana s-wielościanu jest s-wielościanem.

Niech S będzie ścianą s-wielościanu W. Na mocy twierdzenia 3.5 ściana S ma wierzchołek i jest to jedyny wierzchołek.

Stwierdzenie 4.2

Jeżeli s-wielościan W ma więcej niż jeden punkt to ma krawędź nieskończoną.

Niech \{ p\}=W\cap\partial H będzie wierzchołkiem W zaś q dowolnym innym punktem s-wielościanu. Teraz S=W\cap(\partial H+\overrightarrow{p,q}) jest wielościanem zawierającym q, a nie zawierającym p. S ma wierzchołki na mocy wniosku 3.4. Niech q_{1} będzie wierzchołkiem S. Wówczas q_{1} leży na przecięciu brzegów n liniowo niezależnych półprzestrzeni opisujących S. Jednym z nich jest \partial H+\overrightarrow{p,q} a pozostałe n-1 opisują W. Zatem q_{1} należy do krawędzi W i \overrightarrow{p,q_{1}} jest wektorem krawędzi nieskończonej.

Lemat 4.1

Niech p będzie punktem wielościanu W. Jeżeli wektor \beta spełnia warunek:

\forall _{{r\geq 0}}\; p+r\beta\ \in W to \forall _{{q\in W}}\forall _{{r\geq 0}}\; q+r\beta\ \in W.

1) Niech W=\left\{ x\in R^{n}\,|\,\alpha\bullet x\,\leq b\right\} będzie półprzestrzenią. Teraz:

\forall _{{r\geq 0}}\;\alpha\bullet(p+r\beta)\leq b

\forall _{{r\geq 0}}\;\alpha\bullet p+r\alpha\bullet\beta\leq b

\forall _{{r\geq 0}}\; r\alpha\bullet\beta\leq b-\alpha\bullet p

to implikuje \alpha\bullet\beta\leq 0

\forall _{{r\geq 0}}\ \alpha\bullet(q+r\beta)=\alpha\bullet q+r\alpha\bullet\beta\leq\alpha\bullet q\leq b

2) Niech W=\bigcap _{{\, i=1}}^{{\, t}}H_{i} będzie przecięciem półprzestrzeni. Jeżeli \forall _{{r\geq 0}}\; p+r\beta\ \in W, to \forall _{i}\forall _{{r\geq 0}}\; p+r\beta\ \in H_{i}, a z kroku 1) \forall _{i}\forall _{{q\in H_{i}}}\forall _{{r\geq 0}}\; q+r\beta\ \in W. Zatem \forall _{{q\in W}}\forall _{{r\geq 0}}\; q+r\beta\ \in W.

Uwaga. Lemat pozostaje prawdziwy gdy założenie ”W jest wielościanem” zastąpimy ”W jest zbiorem wypukłym i domkniętym”.

Twierdzenie 4.2

Niech W\in\mathbb{R}^{n} będzie s-wielościanem. Wówczas W=\left\{ p+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\ |\  s_{{j}}\geq 0\right\} gdzie p jest wierzchołkiem W zaś \alpha _{{1}},\alpha _{{2}},...,\alpha _{{k}} jest zbiorem wektorów kierunkowych krawędzi nieograniczonych.

Z lematu 4.1 wynika inkluzja W\supseteq\left\{ p+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\ |\  s_{{j}}\geq 0\right\}

Dowód przeciwnej inkluzji przeprowadzimy przez indukcję względem wymiaru W.

1^{0} Jeżeli dim\, W=0 to Wjest punktem i dowód jest oczywisty.

2^{0} Niech p będzie wierzchołkiem s-wielościanu W=\bigcap _{{\, i=1}}^{{\, t}}\, H_{i} zaś q dowolnym innym punktem W. Niech \alpha będzie wektorem krawędzi nieskończonej.

1) Jeżeli q należy do krawędzi o wektorze kierunkowym \alpha to q=p+r\alpha dla pewnego r\geq 0.

2) Przypuśćmy, że q nie należy do żadnej krawędzi. Prosta l=\{ q+r\alpha\,|\, r\in R\} przecięta z W daje półprostą. Nazwijmy jej początek q_{1}. Istnieje teraz j\leq t takie, że q_{1}\in\partial H_{j}. Ściana W\cap\partial H_{j} ma mniejszy wymiar niż W więc z założenia indukcyjnego q_{1}=p+\sum _{{i=1}}^{{k}}s_{{i}}\alpha _{{i}} dla pewnych s_{{j}}\geq 0 i wektorów kierunkowych krawędzi nieograniczonych \alpha _{{1}},\alpha _{{2}},...,\alpha _{{k}}. Zatem q=q_{1}+s\alpha=p+\sum _{{i=1}}^{{k}}s_{{i}}\alpha _{{i}}+s\alpha ma żądane przedstawienie.

Lemat 4.2

Niech punkt p będzie wierzchołkiem wielościanu W. Wówczas istnieje wielościan W_{p} spełniający warunki:

a) Punkt p jest wierzchołkiem wielościanu W_{p}.

b) W\subset W_{p}.

c) Jeżeli k_{i} jest krawędzią wielościanu W_{p}, to s_{i}=k_{i}\cap W jest krawędzią wielościanu W.

Niech W=\bigcap _{{i=1}}^{{\  t}}\, H_{i} będzie przecięciem półprzestrzeni, gdzie H_{i}=\{ x\,|\,\alpha _{i}\bullet x\,\leq b_{i}\}. Przenumerowując półprzestrzenie w razie potrzeby możemy przyjąć, że p\in\partial H_{i}\Leftrightarrow 1\leq i\leq k.

Zdefiniujmy W_{p}=\bigcap _{{i=1}}^{{\  k}}\, H_{i}.

Wtedy W\subseteq W_{p} i p jest jedynym wierzchołkiem W_{p}, gdyż na mocy twierdzenia 3.2 p jest wierzchołkiem W\Leftrightarrow rz\left[\begin{array}[]{c}\alpha _{{1}}\\
\vdots\\
\alpha _{{k}}\end{array}\right]=n \Rightarrow p jest wierzchołkiem W_{p}.

Niech teraz k_{i}=\{ p+r\alpha\,|\, r\geq 0\} będzie krawędzią wielościanu W_{p}. Wówczas k_{i}=W_{p}\cap\partial H, dla pewnej półprzestrzeni H zawierającej W_{p}. Ponieważ p\in W\cap\partial H\subset W_{p}\cap\partial H więc wystarczy wykazać, że ściana W\cap\partial H do której należy p nie jest jedno punktowa. Dla każdego j>k istnieje \varepsilon _{j}>0 taki, że \|\varepsilon _{j}\alpha\|<\varrho(p\,;\partial H_{j}) . Przyjmując \varepsilon=min\{\varepsilon _{j}\,|\, j>k\} otrzymujemy p+\varepsilon\alpha\in H_{i} dla i>k. Zatem p+\varepsilon\alpha\in W oraz p+\varepsilon\alpha\in W\cap\partial H.

4.2. Geometryczny algorytm metody sympleks

Definicja 4.2

Rozważmy zagadnienie PL

Max\left\{ x_{0}=c\bullet x\,:x\in W\right\}

Niech p będzie wierzchołkiem W, zaś \alpha wektorem kierunkowym krawędzi wychodzącej z wierzchołka p

\left\{ p+t\alpha\,|\, t>0\right\} lub \left\{ p+t\alpha\,|\, t\in[0,r]\right\} jest krawędzią.

Krawędź tą nazywamy:

poprawiającą gdy c\bullet\alpha>0,

neutralną gdy c\bullet\alpha=0,

pogarszającą gdy c\bullet\alpha<0.

W przypadku zadania Min\left\{ x_{0}=d\bullet x\,\,|\, x\in W\right\} krawędź nazywamy:

poprawiającą gdy d\bullet\alpha<0,

neutralną gdy d\bullet\alpha=0,

pogarszającą gdy d\bullet\alpha>0.

Twierdzenie 4.3

Jeśli z wierzchołka p wielościanu W nie wychodzi żadna krawędź poprawiająca to p jest punktem optymalnym zadania PL

Inaczej mówiąc, dla zadań typu Max\left\{ x_{0}=c\bullet x\,|\  x\in W\right\}.

Jeżeli p jest wierzchołkiem wielościanu W i jeśli dla każdego wektora \alpha, kierunkowego dla krawędzi wychodzącej z p, iloczyn skalarny c\bullet\alpha \leq 0 to \forall _{{q\in W}} c\bullet p\,\geq c\bullet q\,.

Niech W_{p} będzie wielościanem z lematu 4.2. Wówczas na mocy twierdzenia 4.2 W_{p} jako s - wielościanem można opisać

W_{p}=\{ p+\sum _{{i=1}}^{{\, m}}r_{{i}}\alpha _{{i}}\,|\  r_{{i}}\geq 0\}, gdzie \alpha _{{1}},\alpha _{{2}},...,\alpha _{{m}} są wszystkimi wektorami kierunkowymi krawędzi W_{p} a więc wektorami kierunkowymi krawędzi wielościanu W wychodzących z p.

Weźmy dowolny punkt q\in W. Wtedy q\in W_{p}=p+\sum _{{i=1}}^{{\, m}}r_{{i}}\alpha _{{i}}.

Zatem

x_{0}(q)=c\bullet q\,=c\bullet(p+\sum _{{i=1}}^{{m}}r_{{i}}\alpha _{{i}})=c\bullet p\,+\sum _{{i=1}}^{{\, m}}r_{{i}}\bullet\alpha _{{i}}\leq c\bullet p=x_{0}(p).

Wniosek 4.1

Jeśli zadanie PL ma rozwiązanie i wielościan będący obszarem dopuszczalnym ma wierzchołek to istnieje wierzchołek obszaru dopuszczalnego, który jest punktem optymalnym.

Wniosek 4.2

Badając krawędzie wychodzące z wierzchołka p możemy rozstrzygnąć, czy jest to punkt optymalny.

Geometryczny algorytm metody sympleks.
Dany wielościan opisany układem t nierówności w R^{{n}}. Dany
wierzchołek p (startowy).
x= zmienna (punkty)
\alpha= zmienna (wektory)
0) \  x:=p
1)  Budujemy tablicę T złożona z kandydatów na krawędzie
wychodzące z wierzchołka x
2) Dopóki T\neq\emptyset wykonujemy
3) Wybieramy krawędź   k z T i usuwamy
4) Jeżeli k jest  krawędzią
poprawiającą to:
5) Jeżeli k jest  krawędzią
nieskończoną to STOP: zadanie nieograniczone.
6) Jeżeli k jest krawędzią skończoną to:
7) Znajdujemy jej drugi koniec q
 \ \qquad x:=q i wracamy do punktu 1)
8)  T=\emptyset STOP: x jest wierzchołkiem optymalnym.
Uwaga 4.1

Algorytm sympleks jest skończony, gdyż wielościan ma skończoną liczbę wierzchołków i krawędzi.

Przykład 4.2

Badamy zadanie Max\  x_{0}=3x_{1}-2x_{2}, gdzie

\left\{\begin{array}[]{r}x_{1}-x_{2}\leq 2\\
x_{2}\leq 5\end{array}\right.

\ \  x_{1}\geq 0,\  x_{2}\geq 0

Jako wierzchołek startowy weźmiemy punkt (0,0).

Jest on opisany układem

\left\{\begin{array}[]{c}x_{1}=0\\
x_{2}=0\end{array}\right. pochodzącym z dwóch ostatnich nierówności.

Wychodzą z niego dwie krawędzie w kierunku wektora (1,0) - poprawiająca i w kierunku wektora (0,1) - pogarszająca.

Wybieramy krawędź (0,0)+t(1,0) i szukamy ograniczenia na t podstawiając do pozostałych nierówności. \left\{\begin{array}[]{c}t\leq 2\\
0\leq 5\\
t\geq 0\end{array}\right.

Więc t\in[0,2] i drugim końcem krawędzi jest wierzchołek (2,0) opisany układem \left\{\begin{array}[]{r}x_{1}-x_{2}=2\\
x_{2}=0\end{array}\right.

pochodzącym z pierwszej i ostatniej nierówności. Opuszczając pierwszą równość otrzymamy krawędź, którą przyszliśmy a więc z punktu widzenia wierzchołka (2,0) krawędź pogarszającą. Opuszczamy równanie x_{2}=0.

Równanie x_{1}-x_{2}=2 opisuje prostą \{(2+t,t);\; t\in R\}.

Wstawiamy do pozostałych nierówności i otrzymujemy:

\left\{\begin{array}[]{r}t\leq 5\\
t+2\geq 0\\
t\geq 0\end{array}\right..

Więc t\in[0,5] i drugim końcem krawędzi jest wierzchołek (7,5) opisany układem \left\{\begin{array}[]{c}x_{1}-x_{2}=2\\
x_{2}=5\end{array}\right.

pochodzącym z pierwszej i drugiej nierówności. Zauważmy, że funkcja celu wzrosła z 2 do 3\cdot 7-2\cdot 5=11 więc krawędź była poprawiająca.

Z wierzchołka (7,5) wychodzą dwie krawędzie, pogarszająca, którą przyszliśmy i leżąca na prostej opisanej równaniem x_{2}=5. Wstawiając do pierwszej nierówności otrzymujemy x_{1}-5\leq 2. Więc wektorem kierunkowym jest (-1,0). Jest to krawędź pogarszająca i stąd (7,5) jest wierzchołkiem optymalnym.

Zadania

Ćwiczenie 4.1

Niech W\in\mathbb{R}^{3} będzie wielościanem opisanym układem:

\begin{array}[]{c}x_{1}-2x_{2}+x_{3}\leq 3\\
2x_{1}-3x_{2}-3x_{3}\leq 2\\
3x_{1}-5x_{2}-2x_{3}\leq 5\end{array}

x_{1}\geq 0, x_{2}\geq 0, x_{3}\in R

a) Dla każdego z punktów: A=\left(0,0,0\right) , B=\left(0,0,3\right) , C=\left(1,1,1\right) , D=\left(4,1,1\right) wylicz najmniejszy wymiar ściany W do której ów punkt należy.

b) Opisz wszystkie krawędzie W zawierające punkt A=\left(0,0,0\right).

Ćwiczenie 4.2

Opisz prosty algorytm metody sympleks na przykładzie zadania:

Max x_{0}=3x_{1}+2x_{2}-7x_{3} , gdy:

x_{1}+2x_{2}-3x_{3}\leq 3

2x_{1}+8x_{2}-4x_{3}\leq 8

2x_{1}-3x_{2}-7x_{3}\leq 9

x_{1}\geq 0, x_{2}\geq 0, x_{3}\geq 0

Ćwiczenie 4.3

Niech W będzie niepustym wielościanem zawartym w K(\theta,50) - kuli o środku w początku układu współrzędnych i promieniu 50 zawartej w R^{{20}}. Badamy graf G niezorientowany, którego wierzchołki są wierzchołkami W zaś krawędzie są krawędziami W.

a) Udowodnij, że G jest skończonym grafem spójnym.

b) Udowodnij, że G jest drzewem wtedy i tylko wtedy gdy W ma co najwyżej jedną krawędź.

Ćwiczenie 4.4

Niech p będzie wierzchołkiem optymalnym zadania PL o obszarze dopuszczalnym W. Wiemy, że spośród krawędzi wychodzących z p tylko jedna krawędź k jest neutralna. Udowodnij, że k jest zbiorem punktów optymalnych.

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.