Zagadnienia

4.1 Twierdzenia strukturalne
4.2 Geometryczny algorytm metody sympleks
- Zadania

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 $W$ jest 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.

Optymalizacja I