\documentclass[a4paper,12pt]{article} \usepackage[slovene]{babel} \usepackage[cp1250]{inputenc} \usepackage[T1]{fontenc} \usepackage{amsfonts} \usepackage{amssymb} \usepackage[dvips]{graphicx} \newtheorem{defn}{Definicija} \newtheorem{lema}{Lema} \newtheorem{trd}{Trditev} \newtheorem{posl}{Posledica} \newenvironment{dokaz}{\noindent\textbf{Dokaz: }}{\hfill$\Box$\bigskip} % Ukaz za znak realnih števil \newcommand{\RR}{{\mathbb R}} % ************************************** % ***** Osnovni podatki ***** % ************************************** \begin{document} \begin{center} {\Large\bf Poliedri} \\ Ines Pogačar \\ {\small 27. oktober 2009, 5. november 2009 (popravek)} \end{center} \vspace{1cm} % ************************************** % ***** Jedro ***** % ************************************** Pri linearnem programiranju imamo opravka s končnim sistemom neenakosti in končno spremenljivkami, torej je množica dopustnih rešitev presek končno mnogo zaprtih polprostorov. \begin{defn} Množica rešitev linearne neenakosti $$ a_1x_1+a_2x_2+\dots+a_nx_n \leq b, $$ kjer je vsaj en koeficient $ a_i $ neničeln, je (zaprt) \textbf{polprostor} v $ \RR^n $. \end{defn} \begin{defn} \textbf{Konveksni polieder} v $ \RR^n $ je množica oblike $$ P = \{x\in\RR^n : Ax \leq b\} $$ za neko matriko $ A \in \RR^{m×n} $ in neki vektor $ b\in\RR^m $, oziroma je presek končno mnogo zaprtih polprostorov. Omejenemu konveksnemu poliedru pravimo tudi konveksni \textbf{politop}. \end{defn} Množica dopustnih rešitev pri linearnem programu je torej konveksni polieder. Vsak polprostor je konveksen, zato je množica iz zgornje definicije res konveksna. V nadaljevanju se bo vse nanašalo na konveksne poliedre, zato bomo pridevnik ``konveksen'' izpuščali. \textbf{Dimenzija} poliedra $P$ je najmanjša dimenzija afinega podprostora, ki vsebuje $P$. Polieder $P\subset\RR^n$ je dimenzije $n$ natanko tedaj, ko nima prazne notranjosti. \begin{defn} Naj bo $ P = \{x : Ax \leq b\} $ neprazen polieder. Če je $c$ vektor, za katerega je vrednost $ \delta = \max\{c^Tx : x \in P\} $ končna, potem množici $\{x : c^Tx = \delta\}$ pravimo \textbf{oporna hiperravnina} poliedra $P$. \vspace{5pt} \noindent \textbf{Lice} $F \subseteq P$ je polieder sam ali pa presek $P$ z neko oporno hiperravnino. \vspace{5pt} \noindent Točka $x \in P$ je \textbf{oglišče} poliedra $P$, če je $\{x\}$ lice. \end{defn} \vspace{10pt} \noindent V konveksnem poliedru je pojem ekstremne točke ekvivalenten oglišču. Iz definicije lica sledi, da je tudi samo lice (konveksni) polieder. Polieder $P\subset\RR^n$ ima lahko lica (ki niso $P$) dimenzije manjše od $n$. \begin{trd} \label{T1} Naj bo $ P = \{x \in \RR^n : Ax \leq b\} $ polieder in $F \subseteq P$. Potem so naslednje trditve ekvivalentne: \begin{enumerate} \item[{(a)}]$F$ je lice poliedra $P$. \item[{(b)}]Obstaja vektor $c$, da je $ \delta = \max\{c^Tx : x \in P\} $ končna in $F = \{x\in P : c^Tx = \delta\}$. \item[{(c)}]$F = \{x\in P : A'x = b'\} \neq \emptyset$ za kak podsistem $A'x \leq b'$ sistema $Ax\leq b$. \end{enumerate} \end{trd} \begin{dokaz} $(a) \Rightarrow (b)$: Očitno po definiciji. $(c) \Rightarrow (b)$: Če je $F = \{x\in P : A'x = b'\}$ neprazna, naj bo $c$ vsota vrstic matrike $A'$ in $\delta$ vsota komponent vektorja $b'$. Po kratkem izračunu opazimo, da za vsak $x\in P$ velja $c^Tx\leq \delta$ in $F = \{x\in P : c^Tx = \delta\}$. $(b) \Rightarrow (c)$: Privzamemo točko $(c)$. Naj bo $A'x \leq b'$ maksimalni podsistem sistema $Ax\leq b$, da velja $A'x = b'$ za vsak $x \in F$ in $A''x \leq b''$ ostanek sistema $Ax\leq b$. Dokazati moramo, da $A'x = b'$ velja le za $x \in F$. Opazimo, da za vsako neenakost $a_i''x\leq \beta_i''$ sistema $A''x \leq b''$ ($i=1, \dots , k$) obstaja točka $x_i \in F$, ki zadošča strogi neenakosti $a_i'' x < \beta_i''$, saj bi sicer za vse točke iz $F$ veljala enakost $a_i''x = \beta_i''$, kar pa je v protislovju s tem, da je $A'x \leq b'$ maksimalen. Definirajmo $x^* := \frac{1}{k} \sum_{i=1}^k x_i$, ki je težišče teh točk. Potem je lahko videti, da je $x^* \in F$ in $a_i''x^* < \beta_i''$ za vsak $i \in \{1, \dots , k\}$. Vzemimo $y \in P\setminus F$. Potem je $c^Ty < \delta$. Definirajmo $z := x^*+\varepsilon (x^*-y)$ za nek majhen $\varepsilon > 0$, konkretno, naj bo manjši od $ \frac{\beta_i'' - a_i'' x^*}{a_i''(x^*-y)}$ za vsak tak $i \in \{1, \dots , k\}$, da je $a_i'' x^* > a_i'' y$. Ker sta $c^Tx^*-c^Ty$ in $\varepsilon$ pozitivna, je $$c^Tz = c^Tx^* + \varepsilon (c^Tx^*-c^Ty) > \delta ,$$ in sledi, da $z \notin P$. Potem obstaja neenakost sistema $Ax\leq b$, da velja $a^Tz > \beta$, oziroma $$a^Tx^* + \varepsilon (a^Tx^*-a^Ty) > \beta ,$$ kar pomeni, da mora biti $a^Tx^* > a^Ty$. Ta neenakost ne more pripadati sistemu $A''x \leq b''$, sicer bi za zgornjo mejo števila $\varepsilon$ vzeli $\frac{\beta - a^Tx^*}{a^T(x^*-y)}$: $$a^Tz = a^Tx^* + \varepsilon (a^Tx^*-a^Ty) < a^Tx^* + \frac{\beta - a^Tx^*}{a^T(x^*-y)} a^T(x^*-y)=\beta .$$ Torej neenakost pripada $A'x \leq b'$. Ker je $a^Tx^*-a^Tz$ negativno in $\frac{1}{\varepsilon}$ pozitivno, je $$a^Ty = a^Tx^*+\frac{1}{\varepsilon}(a^Tx^*-a^Tz) < \beta .$$ Dokazali smo, da za vsak $y\in P\setminus F$ obstaja neenakost sistema $A'x\leq b'$, da velja neenakost $a^Ty < \beta$, torej $A'y\neq b'$. \end{dokaz} \vspace{10pt} Relacija ``je lice'' je tranzitivna: \begin{posl} Naj bo $P$ polieder in $F$ njegovo lice. Potem je $F$ spet polieder in množica $F'\subseteq F$ je lice poliedra $P$, če in samo če je lice poliedra $F$. \end{posl} \begin{defn} Naj bo $P$ polieder. \textbf{Glavno lice} poliedra $P$ dimenzije $n$ je lice največje dimenzije, ki ni cel $P$, torej dimenzije $n-1$. \\[5pt] Pravimo, da neenakost $c^Tx\leq \delta$ \textbf{določa} glavno lice, če je $c^Tx \leq \delta$ za vsak $x\in P$ in je $\{x\in P : c^Tx= \delta\}$ maksimalno lice poliedra $P$. \end{defn} \begin{trd}\label{T2} Naj bo $P\subseteq \{x \in \RR^n : Ax=b\}$ neprazen polieder dimenzije $n-rang(A)$. Naj bo $A'x\leq b'$ minimalen sistem neenakosti, da $P= \{x : Ax=b, A'x\leq b'\}$. Potem vsaka neenakost sistema $A'x\leq b'$ definira neko glavno lice in vsako glavno lice je določeno z neko neenakostjo sistema $A'x\leq b'$. \end{trd} \begin{dokaz} Če je $P=\{x \in \RR^n : Ax=b\}$, nima glavnih lic in trditev velja. Naj bo $A'x\leq b'$ minimalen sistem neenakosti, da $P= \{x : Ax=b, A'x\leq b'\}$, $a'^Tx \leq \beta'$ ena od teh neenakosti in $A''x\leq b''$ preostanek sistema $A'x\leq b'$. Vzemimo tak vektor $y$, da velja $Ay=b$, $A''y\leq b''$ in $a'^Ty > \beta'$. Tak vektor obstaja, ker neenakost $a'^Tx \leq \beta'$ ni odvečna v sistemu. Naj bo $x\in P$ tak, da $a'^Tx < \beta'$. Definirajmo $z:= x + \frac{\beta'-a'^Tx}{a'^Ty-a'^Tx}(y-x)$. Velja, da $a'^Tz = \beta'$, torej leži v hiperravnini, ki se poliedra dotika v $F$. Pokazati moramo še, da $z \in P$, to je, da zadošča še ostalim neenakostim, torej sistemu $A''x \leq b''$: \begin{eqnarray*} A''z & = & (1-\frac{\beta'-a'^Tx}{a'^Ty-a'^Tx})A''x + \frac{\beta'-a'^Tx}{a'^Ty-a'^Tx}A''y \\ & \leq & (1-\frac{\beta'-a'^Tx}{a'^Ty-a'^Tx})b'' + \frac{\beta'-a'^Tx}{a'^Ty-a'^Tx}b'' = b'' . \end{eqnarray*} Res velja, ker $0<\frac{\beta'-a'^Tx}{a'^Ty-a'^Tx} < 1$. Tako je $F:= \{x \in P: a'^Tx=\beta' \} \neq \emptyset$ lice dimenzije $dim(P)-1$ in $F \neq P$, ker $x \in P\setminus F$, torej je glavno lice. Iz trditve \ref{T1} sledi, da je vsako glavno lice določeno z neko neenakostjo sistema $A'x\leq b'$. \end{dokaz} \vspace{8pt} Še en pomemben razred lic v poliedru so minimalna lica. \begin{defn} \textbf{Minimalna} so lica, ki ne vsebujejo drugih lic. \end{defn} \begin{trd}\label{T3} Naj bo $P=\{x\in\RR: Ax\leq b\}$ polieder. Neprazna podmnožica $F\subseteq P$ je minimalno lice poliedra $P$ natanko tedaj, ko je $F=\{x \in \RR^n: A'x = b'\}$ za kak podsistem $A'x\leq b'$ sistema $Ax\leq b$. \end{trd} \begin{dokaz} $\Rightarrow$: Če je $F$ minimalno lice poliedra $P$, po trditvi \ref{T1} obstaja podsistem $A'x\leq b'$ sistema $Ax\leq b$, da je $F=\{x \in P: A'x = b'\}$. Izberimo $A'x \leq b'$ maksimalen. Naj bo $A''x\leq b''$ minimalen podsistem $Ax\leq b$, da je $F=\{x : A'x = b', A''x \leq b''\}$. Radi bi dokazali, da $A''x \leq b''$ ne vsebuje nobene neenakosti. Pa privzemimo nasprotno: naj bo $a''x\leq \beta''$ neenakost iz sistema $A''x \leq b''$. Ker ni odvečna za opis množice $F$, je po trditvi \ref{T2} množica $F':=\{x: A'x=b', A''x \leq b'', a''x=\beta''\}$ maksimalno lice poliedra $F$, definirano z neenakostjo $a''x\leq \beta''$. Po pravilu tranzitivnosti je $F'$ tudi lice poliedra $P$, kar je v nasprotju s tem, da je $F$ minimalno. $\Leftarrow$: Bodi $F=\{x: A'x=b'\}\subseteq P$ za nek podsistem $A'x\leq b'$ sistema $Ax\leq b$. Po trditvi \ref{T1} je $F$ lice $P$. Očitno $F$ nima drugih lic razen sebe, torej je minimalno. \end{dokaz} \begin{posl} \label{P1} Za polieder $P=\{x: Ax\leq b\}$ so vsa minimalna lica dimenzije $n-rang(A)$. Pri politopih so to natanko oglišča. \end{posl} \vspace{10pt} \begin{large}\textbf{Bazne rešitve}\end{large} \vspace{15pt} Pri reševanju linearnega problema $$ \max \, c^Tx, \quad \textrm{pri pogojih} \quad Ax \leq b, \quad x\geq 0 $$ z metodo simpleksov po uvedbi dopolnilnih spremenljivk za vsak slovar dobimo sistem $[\,A \, \,I\,]x=b$, kjer je $x=(x_1, x_2, \dots , x_{m+n})^T$ in matrika $[\,A \, \,I\,]$ velikosti $m×(n+m)$. \begin{defn} Naj bo $B \subseteq \{1, 2, \dots , m+n\}$ moči $m$. Označimo z $A_B$ $m×m$ podmatriko matrike $[\,A \, \, I\,]$, sestavljeno iz stolpcev iz $B$. Spremenljivke, indeksirane z elementi množice $B$, tvorijo \textbf{bazo}, če je $A_B$ obrnljiva. \vspace{5pt} \noindent \textbf{Dopustna bazna rešitev} je dopustna rešitev $x$, za katero obstaja baza $B$, da so $x_i = 0$ za vse $i\in N:=\{1, 2, \dots , m+n\} \setminus B$. \end{defn} \begin{trd} Naj bo $x \in P$, kjer je $P$ množica dopustnih rešitev linearnega programa $$\max \,c^Tx, \quad \textrm{pri pogojih} \quad Ax \leq b, \quad x\geq 0 .$$ Potem je $x$ oglišče poliedra $P$ natanko tedaj, ko je dopustna bazna rešitev. \end{trd} \begin{dokaz} Naj bo $x$ dopustna bazna rešitev. Potem obstaja baza $B$, da so $x_i = 0 $ za vsak $i\in N$. Če je $x_i=0$, kjer je $i \in N$, dopolnilna, nam to pove, da v neki neenakosti sistema $Ax \leq b$ velja enakost, če pa je originalna spremenljivka, pa to pomeni, da enakost velja v neki neenakosti pogoja $x\geq 0$. Torej imamo v skupnem sistemu $$\left[ \begin {array} {c} \,\\ A\\ \,\\ -I\\ \,\\ \end {array} \right] \left[ \begin {array} {c} x_1\\ \vdots\\ x_n\\ \end {array} \right] \leq \left[ \begin {array} {c} \,\\ b\\ \,\\ 0\\ \,\\ \end {array} \right]$$ $n$ neenakosti z $n$ spremenljivkami, ki zadoščajo enakostim. Po trditvi \ref{T3} je $\{x\}$ minimalno lice, ki je po posledici \ref{P1} dimenzije $0$, torej je $x$ oglišče. Naj bo sedaj $x$ oglišče, ki ima $k$ neničelnih komponent. V bazo damo tiste spremenljivke, ki so v vektorju $x$ neničelne. Ker je matrika $[\,A \, \, I\,]$ ranga $m$, lahko bazi dodamo še $m-k$ spremenljivk tako, da bodo stolpci neodvisni. To bo dopustna baza. Pripadajočo dopustno bazno rešitev dobimo, če postavimo dodane spremenljivke na $0$. \end{dokaz} %\begin{trd} %Naj bo $$max \, c^Tx, \quad \textrm{pri pogojih} \quad Ax=b, \quad x\geq 0$$ linearni program. Potem velja: %\begin{enumerate} %\item[{(a)}] Če obstaja vsaj ena dopustna rešitev in je kriterijska funkcija navzgor omejena na množici dopustnih %rešitev, potem obstaja optimalna rešitev. %\item[{(b)}]Če obstaja optimalna rešitev, potem obstaja dopustna bazna rešitev, ki je optimalna. %\end{enumerate} %\end{trd} %\vspace{10pt} % ************************************** % ***** Bibliografija ***** % ************************************** \begin{thebibliography}{99} \setlength{\itemsep}{0pt} \bibitem{k1} B. H. Korte, J. Vygen: {\em Combinatorial optimization: Theory and Algorithms}, Springer, Berlin-Heidelberg, 2006 \bibitem{k2} G. B. Dantzig, M. N. Thapa:{\em Linear Programming: Theory and extensions}, Springer, Berlin-Heidelberg, 1997 \bibitem{k3} J. Matoušek, B. Gärtner:{\em Understanding and using linear programming}, Springer, Berlin-Heidelberg, 2007 \end{thebibliography} \end{document}