Programowanie Liniowe i Metoda Simpleks

6.1   Własności geometryczne. Niech $V$ będzie przestrzenią wektorową rzeczywistą oraz $U\subset V$ będzie jej wektorową przestrzenią. Połóżmy $x\in V$ i niech $\beta_{i}\in V^{*}$, $i=\overline{1,m}$, $c\in V^{*}$ będą funkcjonałami liniowymi, ograniczonymi na $V$, oraz liczby $b_{i}\in \mathbb{R}^{1},\,i=\overline{1,m}$.
Następny problem, właśnie jego rozwiązanie :

$$\max_{x\in U}c(x)\longrightarrow ? \,,$$ (6.1)

gdzie dla $j=\overline{1,m}$

$$\beta_{j}(x)\,\leq\,b_{j},\qquad x\in U,$$ (6.2)

nazywamy programowaniem liniowym .

Następne twierdzenie daje geometryczne rozwiązanie problemu (), ().

6.2   Twierdzenie Niech $\overline{x}\in P$, gdzie $P$ jest poliedrem zdefiniowanym przez (). Wtedy punkt $\overline{x}\in P$ jest rozwiązaniem (), gdy zachodzi taka równość:

$$c\,=\,\sum_{j\in J(\overline{x})}\mu_{j}\beta_{j}\,+\,\overline{c}$$ (6.3)

dla niektórych $\mu_{j}\geq 0$, $\overline{c}\in U^{\perp}$, gdzie $J(\overline{x}):=\big\{\beta_{j}{(\overline{x})}=b_{j}, \quad j= \overline{1,m} \big \}$,
$U^{\perp}:=\big\{\alpha\in V^{*} :\alpha(x)=0\, \forall x\in U \big\}$

Dowód będzie wnioskiem z własności problemu dualnego do (), ().

6.3   Definicja. Punkt $x\in P$ będziemy nazywać $E$-punktem, gdy zachodzi taka własność:

$$U\,\bigcap_{j\in J(x)} Ker \beta_{j}\,:=\,H_{J(x)}\,=\,U\, \bigcap_{ j=\overline{1,m}} Ker \beta_{j}\,:=\,H_{x}.$$ (6.4)

6.4   Definicja. $E$-punkt $x\in P$ nazywamy niezdegenerowanym, gdy zachodzi taka równość :

$$card J(x)\,=\,dim \big(U / H_{x}\big).$$ (6.5)

6.5   Definicja. Poliedr $P$ () nazywamy prostym, gdy każdy $E$-punkt jest niezdegenerowany

Następne twierdzenie kojarzy $E$-punkty poliedra $P$ oraz jego punkty skrajne.

6.6   Twierdzenie. Niech poliedr $P$ jest zdefiniowany przez (). Wtedy zbiór wszystkich $E$-punktów poliedra $P$ jest taki sam jak zbiór punktów skrajnych poliedra $P$.

$\lhd$ Niech $x\in P$ będzie $E$-punktem $P$, oraz zachodzi równość:

$$x\,=\,\lambda y\,+\,(1-\lambda)z,\qquad \lambda\in (0,1),$$ (6.6)

gdzie $z,y \in P$. Jest jasne, że mamy równość:
$\beta_{j}(x)= \lambda \beta_{j}(y)+(1-\lambda)\beta_{j}(z)=b_{j}\Longrightarrow \beta_{j}(y)=\beta_{j}(z)=b_{j},\,j\in J(x)$,
ponieważ $\beta_{j}(y),\beta_{j}(z)\leq b_{j}$, oraz

$$x-y \in V, \quad x-z \in V.$$ (6.7)

Innymi słowy $\beta_{j}(x-y)=\beta_{j}(x-z)=0$ dla wszystkich $j\in J(x)$. Na mocy definicji () mamy, że

$$H_{J(x)}\,=\,U\bigcap_{j\in J(x)}\big\{Ker \beta_{j}\big\}\,=\,H_{x}\,=\,\{0\}.$$

ponieważ $card J(x)=dim U,\,\bigcap_{j=\overline{1,m}}Ker \beta_{j}= \{0\}$. Ostatnia równość oznacza, że poliedr $P$ jest obszarem zwartym tj. ograniczonym, co zakładamy.
Stąd otrzymujemy, że ograniczenia funkcjonałów $\beta_{j} :V \rightarrow \mathbb{R},\,j\in J(x)$, na $U$ generują przestrzeń $U^{*}$. To daje wtedy oczywiście

$$x-y\,=\,0\,=\,x-z$$ (6.8)

Równości () oznaczają, że $x=y=z$, tj. punkt $x\in P$ jest skrajnym!
Odwrotnie, gdy $x\in P$ jest punktem skrajnym poliedra $P$, wtedy istnieje punkt $z\neq 0$, $z\in H_{J(x)}$, jeśli $x\neq E(P)$! Jasne, że

$$x=\frac{1}{2}(x-z)+\frac{1}{2}(x+z)$$

oraz punkty $x\neq z\in P$, co jest sprzeczym z założeniem skrajności punktu $x\in P$, to znaczy, że $x\in E(P)$ i $z\equiv 0,\, H_{J(x)}=\{0\}$ co dowodzi twierdzenie $\rhd$

6.7   Uwaga Wyżej w postaci uwikłanej skorzystaliśmy z takiego twierdzenia.

6.8   Twierdzenie Wypukły poliedr $P$ dla układu nierówności

$$\beta_{j}(x)\leq b_{j}, \, j=\overline{1,m},$$ (6.9)

gdzie $x\in \mathbb{R}^{n}$, może być przedstawiony w postaci

$$P=M+K,$$

gdzie $M$ jest ograniczonym wielościanem w $\mathbb{R}^{n}$ oraz $K$ jest wypukłym stożkiem wielościennym, złożonym z rozwiązań odpowiedniego układu nierówności jednorodnych: $\beta_{j}(x)\leq 0$, $j=\overline{1,m}$.

$\lhd$ Rozważmy odpowiedni do () następny układ nierówności

$$\beta_{j}(x)-b_{j}\tau \leq 0,\, -\tau \leq 0,$$ (6.10)

gdzie $\tau \in \mathbb{R}_{+}$ jest nową współrzędną, wspólnie ze zmiennymi $x\in \mathbb{R}^{n}$. Jest oczywistym, że układ () wydziela w przestrzeni $\mathbb{R}^{n+1}$ zbiór - $V$-stożek rozwiązań $(x,\tau )\in \mathbb{R}^{n+1}$. Niech teraz stożek $V\subset \mathbb{R}^{n+1}$ jest przecięty hiperpłaszczyzną o równaniu $\tau = 1$.

Jeżeli $\overline{x}=(x,1)$ należy tej warstwie przekroju $\tau = 1$, to $x\in P$. Odwrotnie, jeżeli $x\in P$, to $\overline{x}=(x,1)$ należy do przekroju stożka $V$.

Wypukły stożek $V$ jest wielościenny to znaczy jezt złożony z wypukłych kombinacji skończonego zbioru punktów. Ponieważ dla wszystkich punktów jego ostatnia współrzędna jest $\tau \geq 0$, to tworzące elementy tego stożka są dwóch rodzajów:

1. $$\overline{p_{i}}=(p_{i},\tau_{i}),\, i=\overline{1,z},\, \tau_{i}>0$$

2. $$\overline{q_{j}}=(q_{j},0),\, j=\overline{1,s},\, \tau_{j}=0$$ (6.11)

   
   

Punkty rodzaju 1) będą istnieć koniecznie, ponieważ $V\subset \{ \tau =1 \}$. Oczywi-ście, można uważać, że wszystkie $\tau_{i} \equiv 1, \, i=\overline{1,r}$, skalując punkty z 1).

Tak więc, każdy punkt $\overline{x} \in V$ ma następującą reprezentację:

$$\overline{x}=\sum_{j=1}^{r}\lambda_{j}\overline{p_{j}}+\sum_{j=1}^{s}\mu_{j}\overline{q_{j}}$$ (6.12)

Na hiperpłaszczyźnie $\{\tau =1\}$ są tylko punkty $\overline{x} \in V$ dla których, oczywiście $\sum_{j=1}^{r}\lambda_{j}=1$. To zanczy, że poliedr $P$ jest wyczerpany wszystkimi możliwymi kombinacjami typu

$$x=\sum_{j=1}^{r}\lambda_{j}p_{j}+\sum_{j=1}^{s}\mu_{j}q_{j}$$ (6.13)

gdzie

$$\sum_{}^{}\lambda_{j}=1, \qquad \lambda_{i},\mu_{i}\in\mathbb{R}_{+}^{1}, \quad i=\overline{1,s} \, j=\overline{1,r}$$ (6.14)

Zbiór punktów $\{u=\sum_{j=1}^{r}\lambda_{j}p_{j}:\,\, \lambda_{i}\in\mathbb{R}_{+}^{1}, \sum_{j=1}^{r}\lambda_{j}=1\}$ tworzy wypukły wielo-ścian $M=conv\{p_{1},\ldots,p_{r}\}$, a punkty $v\,=\sum_{j=1}^{s}\mu_{j}q_{j}, \, \mu_{j}\in\mathbb{R}_{+}^{1},\, j=\overline{1,s}$, tworzą wypukły stożek $K=conv\{q_{1},\ldots,q_{s}\}$. Tak więc, otrzymaliśmy poszukiwane rozłożnie $P=M+K$ $\rhd$

6.9   Twierdzenie (o istnieniu) Jeżeli zbiór wartości dopuszczalnych problemu programowania liniowego

$$\inf_{x \in \mathbb{R}^{n}} c(x)\longrightarrow ?,\qquad \beta_{j}(x)\leq b_{j}, \,\, j=\overline{1,m}, \,$$ (6.15)

jest niepusty oraz $\underset{x \in \mathbb{R}^{n}}{\inf} c(x)>-\infty$, wówczas rozwiązanie () istnieje.

$\lhd$ Dowód. Rozważmy zbiór $K\subset\mathbb{R}^{m+1}$, złożony z wektorów
$(\alpha ,z)\in\mathbb{R}^{1}\times\mathbb{R}^{m}$, takich że dla każdego $(\alpha ,z)\in\mathbb{R}^{1}\times\mathbb{R}^{m}$ istnieje wektor $x\in \mathbb{R}^{n}$, taki że $c(x)\leq\alpha,\, \beta_{j}(x)\leq z,\, j=\overline{1,m}$. Oczywiście, że $K$ jest stożkiem.

6.10   Lemat Stożek $K$ jest skończenie zgenerowany.

Musimy pokazać, że $K=conv\{\xi_{1},\ldots ,\xi_{n+m+1}\}$, gdzie $\xi_{j}\in\mathbb{R}^{m+1}$,
$j=\overline{1,n+m+1}$. Zdefiniujmy wektory:

$$\xi_{j}=(c^{(j)},\beta_{1}^{j},\beta_{2}^{j},\ldots ,\beta_{m}^{j})^{T}, \quad j=\overline{1,n}\, ,$$ (6.16)

$$\xi_{n+k}=(0,0,\ldots ,\delta_{j}^{k},\ldots ,0) \quad j=\overline{1,m+1} \, ; \, k=\overline{1,m+1}$$

Oczywiście, że wszystkie $\xi_{j}\in K, \, j=\overline{1,n+m+1}$, tj $conv\{\xi_{1},\ldots ,\xi_{n+m+1}\}\subset K$.
Niech teraz $\xi=(\alpha,z)\in K$. Wtedy dla pewnego $x\in \mathbb{R}^{n}$ i niektórych $\widetilde{x}_{j+n+1}\in\mathbb{R}^{1}$,
$j=\overline{0,m},$ spełnione są relacje:

$$c(x)+\widetilde{x}_{n+1}=\alpha ,\,\, \beta_{j}(x)+\widetilde{x}_{j+n+1}=z_{j}$$ (6.17)

dla $j=\overline{1,m}$. Ale () dokładnie oznacza że

$$\xi =(\alpha ,z)=\sum_{j=1}^{n}x_{j}\xi_{j}+\sum_{j=n+1}^{n+m+1}\widetilde{x}_{j}\xi_{j}$$ (6.18)

tj. $\xi\in conv\{\xi_{1},\xi_{2},\ldots ,\xi_{n+m+1}\}$, albo

$$K\subset conv\{\xi_{1},\xi_{2},\ldots ,\xi_{n+m+1}\}=K.$$ (6.19)

6.11   Lemat Stożek $K$ jest domknięty.

$\lhd$ Połóżmy teraz $A:\mathbb{R}^{N}\rightarrow\mathbb{R}^{n}$, gdzie $A\lambda :=\sum_{j=1}^{N}\lambda_{j}x_{j}$ dla $\lambda\in\mathbb{R}^{N},\, x_{j}\in\mathbb{R}^{N}$,
$j=\overline{1,N}$.

Oczywiście $A\in \mathcal{L}(\mathbb{R}^{N},\mathbb{R}^{N})$ i obraz $A\mathbb{R}^{N}:=L\subset\mathbb{R}^{n}$ - skończenie wymiarowa podprzestrzeń w $\mathbb{R}^{n}$. Na mocy Twierdzenia Banacha o operatorze odwrotnym, istnieje ograniczony odwrotny operator $A_{r}^{-1}:L\rightarrow\mathbb{R}^{N}$, taki że dla $\forall x\in L$ $A\circ A_{r}^{-1}(x)=x$ oraz $\Vert A_{r}^{-1}x\Vert\leq c\Vert x\Vert$, $c>0$. Niech teraz $\hat{x}\in \overline{K}\backslash K$,
$\overline{x}\neq 0$; wtedy istnieje ciąg $\{\lambda^{(k)}\in\mathbb{R}^{N}:k\in\mathbb{Z}_{+}\}$, taki, że
$A\lambda^{(k)}:=x^{(k)}\rightarrow\overline{x}\in\overline{K}\backslash K$. Dalej, istnieje taka liczba $k_{\epsilon}>0$, że przy $k>k_{\epsilon}$ zachodzi $\Vert x^{(k)}\Vert< \Vert\overline{x}\Vert(1+\epsilon),\,\, \forall \epsilon >0$.

Ponieważ dla $k>k_{\epsilon}$

$$\Vert x^{(k)}\Vert=\Vert A_{r}^{-1}x^{(k)}\Vert\leq c\Vert x^{(k)}\Vert\leq c\Vert\overline{x}\Vert(1+\epsilon)$$ (6.20)

ciąg $\Vert\lambda^{(k)}\Vert,\, k\geq k_{\epsilon}$, jest ograniczony, to można wybrać podciąg $\{\lambda^{(k_{s})}\,:\,s\in\mathbb{Z}_{+}\}$ taki, że $\underset{s\rightarrow\infty}{\lim}\lambda^{(k_{s})}=\overline{\lambda}\in\mathbb{R}^{N}$. Dalej mamy: (ponieważ operator $A$ jest ciągły!) $A\overline{\lambda}:=\underset{s\rightarrow\infty}{\lim}\sum^{N}_{j=1}(\lambda... ...{j})=\underset{s\rightarrow\infty}{\lim}x^{(k_{s})}=\overline{x}\in\overline{K}$.

Ostatnia równość znaczy że $\overline{x}=A\overline{\lambda}\in K$, tj. stożek $K$ jest domknięty $\rhd$

Z warunku istnienia dopuszczalnego elementu $x\in \mathbb{R}^{n}$, istnieje element stożka $K$ w postaci $(c(x),b)\in K$. Oprócz tego mamy, że
$\underset{x \in \mathbb{R}}{\lim}\,c(x)>-\infty$. To znaczy w szczególności, że $\exists\alpha\in\mathbb{R}$ że $c(x)\geq\alpha$ dla $\alpha >-\infty$. Tak więc, zbiór $A:=\{\alpha\in\mathbb{R}:(\alpha ,b)\in K\}$ jest niepusty i
$\overline{\alpha}=\inf\{\alpha :\alpha\in A\}>-\infty$. Stąd $(\overline{\alpha},b)\in\overline{K}=K$ (lemat ), tj. istnieje taki element $\overline{x}\in\mathbb{R}^{n}$, dla którego $c(\overline{x})\leq\overline{\alpha},\,\, A\overline{x}\leq b$, co rozwiązuje problem () $\rhd$

6.12   Metoda simpleks - Algorytm rozwiązania problemu kanonicznego
Problem kanoniczny ma postać:

$$\sup_{x \in \mathbb{R}} c(x) - ?, \quad \beta_{j}(x)=b_{j},\,\, j=\overline{1,m}, \quad x\geq 0.$$ (6.21)

Zdefiniujmy także: $\hat{\beta}:=\{\beta_{j}^{(k)}:k=\overline{1,m}\},\,\beta_{j}(x):=\sum_{k}\beta_{j}^{(k)}x_{k}$
Krok 1 Znaleźć punkt skrajny $x^{(0)}=(x_{1},x_{2},\ldots ,x_{m};0,0,\ldots ,0)\in\mathbb{R}^{n},\, x_{j}>0$,
$j=\overline{1,m}$, ze zbioru elementów dopuszczalnych. (Jak szukać $\overline{x}^{(0)}\in\mathbb{R}^{n}$ będzie niżej powiedziane)
Krok 2 Zbudować simpleks - tablicę dla tego punktu $x^{(0)}\in\mathbb{R}^{n}$ (PATRZ TABLICA)
Krok 3 Zbadać simpleks - tablicę:

i)

jeśli wszystkie $\Delta_{j}\geq 0$, to $x^{(0)}\in\mathbb{R}^{n}$ jest rozwiązaniem problemu ().

ii)

jeśli przy niektórym $j\in\overline{1,n},\,\Delta_{j}<0$ i $x^{(j)}\leq 0$, to wartość problemu jest $\underset{x \in P}{\sup} c(x)=+\infty$, gdzie $x^{(j)}=\hat{\beta}^{-1}\beta^{(j)},\, j=\overline{m+1,n}$.

iii)

Niech w rzędzie $\Delta$ są ujemne liczby, a odpowiednie kolumny $x^{(j)}$ złożone z liczb dodatnich.
Połóżmy $\min\Delta_{j}=\Delta_{j_{0}}<0$. Oczywiście że $m+1\leq j_{0}\leq n$. kolumna z indeksem $j_{0}$ nazywana wtedy rozwiązywalną.

Jeśli $\min\Delta_{j}$ jest osiągalny przy kilku wartościach $j$, to w jakości kolumny rozwiązywalnej wybieramy dowolną z-taką samą wartością $\min\Delta_{j}\,=\,\Delta_{j_{0}}$.
Oznaczmy
$\vartheta_{i}:=\frac{x_{i}}{x_{i}^{(j_{0})}}$ dla $x_{i}^{(j_{0})}>0,\, i=\overline{1,m},\, \vartheta_{i_{0}}:=\min \{\vartheta_{i}:x_{i}^{(j_{0})}>0,\, i=\overline{1,m}\}>0$.
Wiersz wektora $a^{(i_{0})}$ nazywany jest rozwiązywalnym. (Jeśli $\min\vartheta_{i}$ jest osiągalny przy kilku indeksach $i\in\{\overline{1,m}\}$ to wybieramy dowolny wiersz odpowiedniego wektora.) Wtedy element $x_{i_{0}}^{(j_{0})}$ wektora $x^{(j_{0})}$ nazywany jest elementem rozwiązywalnym tablicy
.

				$c$						$c^{(1)}$			...			$c^{(m)}$			$c^{(m+1)}$			...			$c^{(j_{0})}$			...			$c^{(n)}$
	baza						$b$			$\beta^{(1)}$			...			$\beta^{(m)}$			$\beta^{(m+1)}$			...			$\beta^{(j_{0})}$			...			$\beta^{(n)}$			$\vartheta$
	$a^{(1)}$			$c^{(1)}$			$x_{1}$			1			...			0			$x_{1}^{(m+1)}$			...			$x_{1}^{(j_{0})}$			...			$x_{1}^{(n)}$			$\vartheta_{1}$
	...			...			...			...			...			...			...			...			...			...			...			...
	$a^{(i_{0})}$			$c^{(i_{0})}$			$x_{i_{0}}$			0			...			0			$x_{i_{0}}^{(m+1)}$			...			$x_{i_{0}}^{(j_{0})}$			...			$x_{i_{0}}^{(n)}$			$\vartheta_{i_{0}}$
	...			...			...			...			...			...			...			...			...			...			...			...
	$a^{(m)}$			$c^{(m)}$			$x_{m}$			0			...			1			$x_{m}^{(m+1)}$			...			$x_{m}^{(j_{0})}$			...			$x_{m}^{(n)}$			$\vartheta_{m}$
	$z$						$c(x^{(0)})$			$c^{(1)}$			...			$c^{(m)}$			$c(x^{(m+1)})$			...			$c(x^{(j_{0})})$			...			$c(x^{(n)})$
	$\Delta = z-c$									0			...			0			$c(x^{(m+1)})-c^{(n+1)}$			...			$c(x^{(j_{0})})-c^{(j_{0})}$			...			$c(x^{(n)})-c^{(n)}$

TABLICA 1

Dalej należy wyłączyć z wektorów bazowych wektor $\beta^{(j_{0})}$. Wartość funkcjnału na nowym punkcie skrajnym $x^{(1)} \in \mathbb{R}^{n}$ z nowymi numerami bazowymi
$(1, \ldots , i_{0}-1, j_{0}, i_{0}+1, \ldots , m)$ rośnie na $(-\vartheta_{i_{0}}\Delta_{j_{0}})$.
Krok 4 Zbudować nową tablicę simpleku dla nowej bazy
$\{\beta^{(1)},\beta^{(2)},\ldots ,\beta^{(i_{0}-1)},\beta^{(j_{0})},\beta^{(i_{0}+1)},\ldots ,\beta^{(m)}\}$, tzn. mamy właściwie rozwinąć wektory $b, \beta^{(j)}, \, j=1,\ldots ,n$ względem nowej bazy, wymienionej wyżej.
Nową tablicę simpleksu konstruujemy przy pomocy poprzedniej.

Elementy tablicy $\{x_{i}^{(j)}:\, i=\overline{1,m}\}$, $j=\overline{1,m}$, stojące pod wektorami
$b,a^{(1)},\ldots ,a^{(n)}$ nie leżące w kolumnie rozwiązywalnej lub w rozwiązywalnym wierszu poprzedniej tablicy simpleksu mogą być wyliczone przy pomocy takiej reguły prostokąta:

Rys. 1

z liczby $x_{i}^{(j)}$ odjąć produkt $x_{i_{0}}^{(j)}$ na $x_{i}^{(j_{0})}$, podzielony przez $x_{i}^{(j_{0})}$. Wtedy elementy wierrza rozwiązywalnego mają postać: $\{\widetilde{x}_{i_{0}}^{(j)}:=x_{i_{0}}^{(j)}/x_{i_{0}}^{(j_{0})}\, :\, j=\overline{1,m}\}$. Jest jasne, że w kolumnie rozwiązywalnej $\widetilde{x}_{i_{0}}^{(j_{0})}=1$, a reszta wartości równa zero. Dalej zaczynamy ponownie badać tablicę simpleksu, otrzymaną wyżej.

6.13   Przykład Rozwiązać niezdegenerowany problem programowania liniowego w postaci kanonicznej:

$$\underset{P}{\sup}(2x_{1}+x_{2}+x_{3}-x_{4}) - ?,$$

$$\{x_{i}\geq 0,\,i=\overline{1,4},\,\, x_{1}-x_{2}+x_{3}=1,\,\, 2x_{1}+x_{2}+x_{4}=3\}=P$$

przy zadanym skrajnym punkcie $x^{(0)}=(0,0,1,3)$

Rozwiązanie. Wektory bazowe $\beta^{(3)}=(1,0),\,\beta^{(4)}=(0,1)$. Mamy tablicę simpleksu:
.

	$c$		2	1	1	-1	$\vartheta$
		$b$	$\beta^{(1)}$	$\beta^{(2)}$	$\beta^{(3)}$	$\beta^{(4)}$
$\beta^{(3)}$	1	1	1	-1	1	0
$\beta^{(4)}$	-1	3	2	1	0	1	$3\rightarrow$
$z$		-2	-1	-2	1	-1
$z-c$			-3	-3	0	0

TABLICA 2

Z tablicy 2 widzimy, że w jakości kolumny rozwiązywalnej można wziąść kolumny $\beta^{(1)}$ lub $\beta^{(2)}$. Weźmy kolumnę $\beta^{(2)}$. Wtedy mamy $\vartheta =3$, a wiersz rozwiązywalny weźmy jako $\beta^{(4)}$. Zmieniamy w bazie wektor $\beta^{(4)}$ wektorem $\beta^{(2)}$, i dla nowej bazy konstuujemy nową tablicę simpleksu:
.

	c		2	1	1	-1	$\vartheta$
baza		$b$	$\beta^{(1)}$	$\beta^{(2)}$	$\beta^{(3)}$	$\beta^{(4)}$
$\beta^{(3)}$	1	4	3	0	1	1
$\beta^{(2)}$	1	3	2	1	0	1
$z$		7	5	1	1	2
$z-c$			3	0	0	3

TABLICA 3

Widzimy z tablicy 3 że $z-c\geq 0$, tak więc punkt $\overline{x}=(0,3,4,0)$ będzie rozwiąza-niem naszego problemu, dając $\underset{P}{\sup}c(x)=7$.

Aby uzasadnić metodę simpleks ważne są następujące lematy.

6.14   Lemat Punkt dopuszczalny $\overline{x}$ problemu kanonicznego jest punktem skrajnym wtedy i tylko wtedy, gdy w macierzy wektorów $\widetilde{\beta}=(\beta^{(1)},\beta^{(2)},\ldots ,\beta^{(n)})$ kolumny, odpowiadające niezerowym współrzędnym wektora $\overline{x}$ są liniowo niezależne

$\lhd$ Dowód niewprost.
Konieczność Niech $\overline{x}\in P$ jest punktem skrajnym. Przypuśćmy że odpowiednie kolumny macierzy $\overline{\beta}$ są liniowo zależne, tj. przy $\overline{x}=(x_{1},\ldots ,x_{k},0)\in\mathbb{R}^{n}_{+}$ mamy równość:

$$\sum^{k}_{j=1}\lambda_{j}\beta^{(j)}=0$$

tj. $\widetilde{\beta}\lambda=0$. Ponieważ wektor $\overline{x}\in\mathbb{R}^{n}_{+}$ spełnia równanie $\widetilde{\beta}\overline{x}=b$, otrzymujemy że $\widetilde{\beta}(\overline{x}+s\lambda)=b$ dla małych $s\in\mathbb{R}^{1}$. To znaczy że wektor $\overline{x}\in\mathbb{R}^{n}$ nie jest skrajnym. A to znaczy, że wektory $\beta^{(1)},\beta^{(2)},\ldots ,\beta^{(k)}$ są niezależne.
Teraz przypuśćmy, że $\overline{x}\in\mathbb{R}^{n}_{+}$ jest punktem dopuszczalnym, oraz wektory $\beta^{(j)},\, j=\overline{1,k}$, są liniowo niezależne. Przy warunku, że $\overline{x}\in\mathbb{R}^{n}$ nie jest punktem skrajnym, istnieją punkty $y \neq z\in\mathbb{R}^{n}$, takie że $\overline{x}=\alpha y+(1-\alpha )z$ przy niektórym $\alpha\in (0,1)$. Z tej równości widzimy, że wektory $y$ i $z\in\mathbb{R}^{n}_{+}$ mają te same niezerowe współrzędne co wektor $\overline{x}\in\mathbb{R}^{n}_{+}$. Ponieważ $\widetilde{\beta}y=b,\,\, \widetilde{\beta}z=b$, to $\widetilde{\beta}(y-z)=0$ co oznacza, że $\sum_{j=1}^{k}\beta^{(j)}(y_{j}-z_{j})=0$, tj. wektory $\beta^{(j)},\, j=\overline{1,k}$, liniowo zależne co zaprzecza założeniu. Tak więc $\overline{x}\in\mathbb{R}^{n}_{+}$ jest punktem skrajnym $\rhd$

6.15   Lemat Dla problemu niezdegenerowanego kaźdy punkt dopuszczalny ma nie mniej niż $m\in\mathbb{Z}_{+}$ dodatnich współrzędnych.

$\lhd$ Dowód niewprost.
Przypuśćmy, że istnieje punkt dopuszczalny, który ma mniej niż $m\in\mathbb{Z}_{+}$ dodatnich współrzędnych. Dla pewności będziemy uważać, że to pierwsze $k\leq m$ współrzędne. Rozważmy zbiór $\widetilde{P}$ rozwiązań układu $\widetilde{\beta}y=b,\, y\in\mathbb{R}^{k}_{+}$, gdzie $\widetilde{\beta}=(\beta^{(1)},\beta^{(2)},\ldots ,\beta^{(k)})\in Hom(\mathbb{R}^{k})$.
Niech $\widetilde{y}\in\mathbb{R}_{+}^{k}$ jest punktem skrajnym zbioru $\widetilde{P}$, który oczywiście istnieje. Wtedy oczywiście punkt $\overline{y}=(\widetilde{y};0)\in\mathbb{R}_{+}^{n}$ jest punktem skrajnym zbioru $P$, u którego mniej niż $m\in\mathbb{Z}_{+}$ dodatnich wspólrzędnych. Ostatecznie sprzeczne z niezdegenerowalnością problemu $\rhd$

6.16   Wniosek Dla problemu niezdegenrowanego punkt dopuszczalny ma dokładnie $m\in\mathbb{Z}_{+}$ dodatnich współrzędnych wtedy i tylko wtedy, gdy ten punkt jest punktem skrajnym zbioru $P$ punktów dopuszczalnych.

Następne twierdzenie uzasadnia metodę simpleks.

6.17   Twierdzenie Niech $\overline{x}^{(0)}=(\overline{x}^{(0)}_{1},\overline{x}^{(0)}_{2},\ldots ,\overline{x}^{(0)}_{m};0)\in\mathbb{R}^{n}_{+}$ jest punktem skrajnym dla problemu niezdegenerowanego kanonicznego () programowania liniowego. Wtedy:

i)

jeśli wszystkie $\Delta\geq 0$ to $\overline{x}^{(0)}\in\mathbb{R}^{n}_{+}$ jest rozwiązaniem problemu()

ii)

jeśli dla niektórego $j$ wartość $\Delta_{j}<0$ oraz $x^{(j)}\in\mathbb{R}^{m}_{+}$, to wartość problemu () jest $\underset{P}\,{\sup} c(x)=+\infty$

iii)

jeśli nie zachodzą i) oraz ii) wtedy punkt $\overline{x}^{(1)}\in \mathbb{R}_{+}^{n}$ jest nowym punktem skrajnym dla punktów dopuszczalnych $P$, przy czym wartość funkcjonału $c :\mathbb{R}^{n}\longrightarrow\mathbb{R}^{1}$ w () wzrośnie na $-\vartheta_{i_{0}}\Delta_{j_{0}}$, a rozwinięcie wektorów $\overline{x}^{(1)},\,\,\beta^{(j)}\in\mathbb{R}^{n},\, j=\overline{1,n}$, prowadzi się zgodnie z metodą simpleks opisaną wyżej.

DODATEK

6.18   Lemat (Knastera - Kuratowskiego - Mazurkiewicza) Niech $V \subset \mathbb{R}^{n}$ jest dowolnym zbiorem. Postawimy w odpowiedniość każdemu punktowi $x\in V$ domknięty zbiór $F(x)\subset\mathbb{R}^{n}$ w taki sposób, że spełnione są warunki:

i)

dla jednego punktu $\hat{x}_{0}\in V$ zbiór $F(\hat{x}_{0})$ jest zwarty

ii)

dla każdego skończonego zbioru $\{x_{1},x_{2},\ldots ,x_{k}\}\subset V$ wypukła powłoka punktów $\{x_{1},x_{2},\ldots ,x_{k}\}$ jest zawarta w $\bigcup_{j=1}^{k}F(x_{j})$. Wtedy

$$\bigcap_{x\in V}F(x)\neq\varnothing$$ (6.22)

Według dowodu H. Bresisa: Ponieważ zbiory $G(x):=F(\hat{x})\cap F(x)$ są wszystkie zwarte, to dla dowodu tego że $\underset{x\in V}{\bigcap}G(x)$ jest niepuste, wystarczy pokazać, że rodzina $\{ F(x):x\in V\}$ posiada własność przecięcia skończonego: dla wszystkich podzbiorów skończonych $\{x_{1},x_{2},\ldots ,x_{k}\}\subset V$ przecięcie

$$F(\hat{x}_{0})\bigcap_{j=\overline{1,k}}F(x_{j})\neq\varnothing.$$ (6.23)

Przypuśćmy, że () nie spełniono, tj. istnieje podzbiór $\{\hat{x}_{1},\hat{x}_{2},\ldots ,\hat{x}_k{}\}\subset V$, że

$$\bigcap_{j=\overline{0,k}}F(\hat{x}_{j})=\varnothing$$ (6.24)

Jeżeli $H_{j}:=\mathbb{R}^{n}\backslash F(\hat{x}_{j}),\,\, j=\overline{0,k}$, wtedy oczywiście $\bigcup_{j=\overline{0,k}}H_{j}=\mathbb{R}^{n}$(!)
Weźmy teraz rozbicie jedynki $\psi_{j}\,:\,supp \,\psi_{j}\subset H_{j}\longrightarrow\mathbb{R},\,\, j=\overline{0,k}$, skojarzone z otwrtym pokryciem $\{H_{j}\subset\mathbb{R}^{n}:j=\overline{0,k}\}$, tj. takie, że

$$\sum_{j=\overline{0,k}}\psi_{j}=1,\,\, supp\psi_{j}\subset H_{j},\,\, j=\overline{0,k}.$$

Rozważmy teraz takie odwzorowanie $\varphi:V\longrightarrow\mathbb{R}^{n}$ : dla każdego $x\in V$

$$\varphi(x)=\sum_{j=0}^{k}\psi_{j}(x)\hat{x}_{j}.$$ (6.25)

Oczywiście $\varphi(x)$ należy do powłoki wypukłej $K$ punktów $\{x_{1},x_{2},\ldots ,x_{k}\}\subset V$ oraz odwzorowuje $K$ w siebie. Na mocy twierdzenia Brauera o punkcie stałym istnieje punkt $\overline{x}\in K$, taki że

$$\overline{x}=\sum_{j=\overline{0,k}}\psi_{j}(\overline{x})\hat{x}_{j}.$$ (6.26)

Rozważmy wartości $\psi_{j}(\overline{x}),\,\,j=\overline{0,k}$, (ponumerowane we właściwy sposób):

$$\psi_{j}(\overline{x})\left\{ \begin{array}{ll} \neq 0, & j=\overline{0,s} \\ =0, & j=\overline{s+1,k}, \end{array}\right.$$ (6.27)

tak więc punkt $\overline{x}\in conv\{\hat{x}_{0},\hat{x}_{1},\ldots ,\hat{x}_{s}\}$. Ponieważ na mocy naszych założeń $\overline{x}\in\bigcup_{j=\overline{0,s}}F(\hat{x}_{j})$, co znaczy że $\overline{x}\in F(\hat{x}_{j_{s}})$ dla pewnego $j_{s}\in\overline{0,s}$. Wtedy $\overline{x}\notin H_{j_{s}}$, tj. $\psi_{j_{s}}(\overline{x})=0$, co zaprzecza (). Tym samym $\bigcap_{x\in V}F_{j}(x)\neq\varnothing$ , co potrzebne było udowodnić $\rhd$

6.19   Twierdzenie (Brauera F.) Niech $f:B\longrightarrow\mathbb{R}^{n},\,\, B=\{x:\Vert x\Vert\leq 1\}$,
$x\in\mathbb{R}^{n},\, f\in C^{0}(B)$ oraz $f(\partial B)\subset B$. Wtedy $f$ ma punkt stały.

$\lhd$ Rozważmy odwzorowanie $\varphi(x):=f(x)+x$ i jego wartości na $\partial B$. Przypuszczamy, że $\varphi(x)\neq 0$ na $\partial B$. Wtedy wektor $\varphi{x}$ nie będzie się nigdzie równał zeru na brzegu $\partial B$, skąd widizmy że dla każdego elementu $\lambda\in\mathbb{R}_{+}^{1}$ będzie zachodzić nierówność. Dla $x\in\partial B$

$$(x-f(x))+\lambda x\neq 0,\,\,\lambda\geq 0$$ (6.28)

albo

$$f(x)\neq(1+\lambda)x,\,\, x\in\partial B$$ (6.29)

Rzeczywiście, niech przy $\overline{\lambda}>0$ będzie w () równość, tj. $f(x)=(1+\overline{\lambda})x$,
$x\in\partial B$, co znaczy, że $\Vert f(x)\Vert>1$ co jest sprzeczne z warunkiem $f:B\subseteq B$, skąd $\Vert f(x)\Vert\leq 1$. Tym samym () zachodzi dla wszystkich $\lambda\geq 0$. Wyliczając indeks $deg(\varphi,B;0)=deg(\varphi_{t},B;0)\Big\vert _{t\in[0,1]}\Longrightarrow \\... ...ghtarrow deg(I,B;0)=1\,, \varphi_{t}(x)=t\varphi(x)\,+\,(1-t)x,\,\, t\in[0,1],$ otrzymujemy, że istnieje punkt $\overline{x}\in B\backslash\partial B$, taki, że $\varphi(\overline{x})=0$ albo $f(\overline{x})=\overline{x}$, tj. punkt stały w $B$. $\rhd$