7.tex

\section{A lineáris és egészértékű programozás alkalmazása hálózati folyamproblémákra}

Elöszőr is határozzuk meg, hogy mit nevezzünk folyamnak:

\[
	\begin{rcases}
		G(V,E) \mbox{ irányított gráf}                                               \\
		s,t \in V \mbox{ két kitüntet csúcs}                                         \\
		c : E \mapsto \mathbb{R}^+ \mbox{ nem negatív kapacitásfüggvény}             \\
		\rho_x(v) \mbox{ -- } v\mbox{--be belépő élek összege } x \mbox{ szerint}    \\
		\delta_x(v) \mbox{ -- } v\mbox{--ből kilépő élek összege } x \mbox{ szerint} \\
		\mbox{Legyen }x : E \mapsto \mathbb{R}^+ \mbox{ tetszőleges függvény}
	\end{rcases} \parbox[c]{6.2cm}{
		\begin{itemize}
			\item $x$ függvény akkor \emph{folyam}, ha \\ $\forall~v~\in~V - \{s,t\}$--re: \\ $\rho_x(v)=\delta_x(v)$
			\item $x$ megengedett, ha $\forall e \in E$--re $x(e) \leq c(e)$
			\item A folyam értéke: \\ $\delta_x(s)-\rho_x(s)=\rho_x(t)-\delta_x(t)$
		\end{itemize}
	}
\]

Keressük a maximális folyamértéket ($\sum_{e \in s}x(e)=\sum_{e \in t}x(e)$),
ami a forrásból kifutó és a terminálba bejövő értékek összege.

\vspace{0.4cm}
\emph{Tétel. Ford Fulkerson: A maximális folyam értéke megegyezik a minimális vágás értékével.}
\vspace{0.4cm}

A fenti tétel bizonyításhoz a feladatott megfogalmazzuk LP és DP alakban, de
ehhez szükségünk lesz a következő lemmára:

\[
	\begin{rcases}
		\mbox{Adott } x \in E \mapsto \mathbb{R}^+ \\
		\forall v \in V - \{s,t\} \begin{cases}
			                          \delta_x(v) \leq \rho_x(v) \\
			                          \delta_x(s) \leq \rho_x(t)
		                          \end{cases}
	\end{rcases}
	\Rightarrow  x \mbox{ egy folyam}
\]

Azaz a folyamban a pontokban érték elvesztődhet, de nem keletkezik új.
Vegyünk fel $\forall v \in V-\{s,t\}$ csúcshoz egy új terminálba mutató élet,
amelyekhez hozzárendeljük az $x'(e)=\rho_x(v)-\delta_x(v) \geq 0$
egyenlőtlenséget (a belépők többségbe vannak a kilépőkhöz képest, és ami
eltűnik az e új élen távozzik a terminálba). A többi élen maradjon meg a
korábbi értékek, $x(e)=x'(e)$.

Az így konstruált $x$ folyamhoz tartozzik egy $G'$ gráf.  Mivel ez is folyam,
így igaz, hogy:

\[\rho_{x}(t) \geq \delta_{x}(s) = \delta_{x'}(s) \geq \rho_{x'}(t) \geq
	\rho_{x}(t)\].

De itt csak egyenlőség állhat, ezért $\rho_{x'}(t)=\rho_{x}(t)$, ami csak akkor
teljesülhet ha $x$ folyam.

Az LP felíráshoz először is egészítsük ki a gráfot egy $e^*=(t,s)$ pszeudó
éllel, ez lesz később majd a folyam értéke, $\mu$.

\begin{wrapfigure}{l}{0.35\textwidth}
	\begin{center}
		\vspace{-1.3cm}
		\begin{displaymath}
			\underbrace{
				\begin{array}{c|ccc|c|}
					\cline{2-5}
					    &  &   &  & 0      \\
					b_v &  &   &  & \vdots \\
					    &  & B &  & 0      \\
					s   &  &   &  & -1     \\
					t   &  &   &  & 1      \\
					\cline{2-5}
				\end{array}}_{B^*}
			\underbrace{
				\begin{array}{|c|}
					\hline
					x   \\
					\\
					\hline
					\mu \\
					\hline
				\end{array}}_{x^*}
			\leq
			\begin{array}{|c|}
				\hline
				\\
				0 \\
				\\
				\hline
			\end{array}
		\end{displaymath}
		\vspace{-1.3cm}
	\end{center}
\end{wrapfigure}
Az így kapott gráf illeszkedési mátrixa legyen $B^*$. Minden $v \in V - \{s,t\}$
csúcshoz tartozik egy sor, amelyre teljesül a $b_vx\leq 0$ feltétel (azaz a
belépő élek összege nagyobb, mint a kilépőké, mert a $b_vx$ ha kifejtjük
$\delta_x(v) - \rho_x(v) \leq 0 $ amit átrendezve kapjuk, hogy $ \delta_x(v)
	\leq \rho_x(v)$).
Továbbá a forrás és a terminál sorai alapján $\begin{rcases} \delta_x(s)-\mu
		\leq 0 \\
		\mu - \rho_x(t) \leq 0\end{rcases} \Rightarrow \delta_x(s) \leq \mu \leq
	\rho_x(t)$. Ezzel felírtuk az előző lemma összes feltételét, tehát $x$ egy
folyam, ahol e $e^*$ élen a folyam teljes átvitele átfolyik,
$\delta_x(s)=\mu=\rho_x(t)$, és a folyam értéke $\mu$.

\vspace{0.4cm}
\begin{wrapfigure}{L}{0.35\textwidth}
	\begin{center}
		\vspace{-1.3cm}
		\begin{displaymath}
			\underbrace{
				\begin{array}{c|ccc|c|}
					\cline{2-5}
					  &   &  &  &    \\
					  & B &  &  &    \\
					s &   &  &  & -1 \\
					t &   &  &  & 1  \\
					\cline{2-5}
					  &   &  &  & 0  \\
					  & E &  &  & 0  \\
					\cline{2-5}
				\end{array}}_{B^*}
			\underbrace{
				\begin{array}{|c|}
					\hline
					x   \\
					\\
					\hline
					\mu \\
					\hline
				\end{array}}_{x^*}
			\leq
			\underbrace{
				\begin{array}{|c|}
					\hline
					\\
					0 \\
					\\
					\hline
					\\
					c \\
					\\
					\hline
				\end{array}}_{M}
		\end{displaymath}
		\vspace{-1.3cm}
	\end{center}
\end{wrapfigure}
E szerint a maximális folyam felírható mint max$\{ (0, \cdots,0,1)x^* : B^*x^* \leq
	0; x^* \geq 0;$ $x \leq c \}$. Az utolsó feltételt is hozzávesszük a mátrixhoz,
mint az $E$ egy egységvektor és a hozzá tartozó $c$ rész az $M$ vektorban.

A duális feladat megfogalmazható mint egy min$\{ yM :yB^* \geq (0, 0, \cdots, 0,
	1);$ $y \geq 0 \}$ optimalizálás. Láthatjuk, hogy ebből könnyedén nem tudunk egy
vágás fogalmat hozzárandelni. Ezért fejezzük ki ebből $y$--t $\left(
	\pi\left(v\right) | w\left(e\right)\right)$ alakban. Ekkor a duál feladat
megegyezik az alábbi egyenletrendszerrel:

$\begin{cases}
		(1)~\pi(v) \geq 0 \mbox{ és } w(e) \geq 0,                             \\
		(2)~\mbox{minden } e = (u,v) \mbox{ élre }  \pi(u)-\pi(v)+w(e) \geq 0, \\
		(3)~\pi(t)-\pi(s) \geq 1.\end{cases}$

A duális változói közül $\pi$ a csúcsokhoz (mekkora csúcs a potenciálja), $w$ az
élekhez rendelhető (menyibe kerül nekem a szállítás az él mentén). A duális
feladat célja az $m_{\text{DLP}}= \mbox{min} \left\{ \sum_{e\in E}^{}
	w(e)c(e)\right\}$ alak minimalizálása. Állítjuk, hogy ez megegyezik a hálózati
folyam minimális vágásának értékével (legyen ez $m_{\text{C}}$).

A bizonyitáshoz belátjuk, hogy $(A)~m_{\mbox{DLP}} \leq m_{\mbox{C}}$ és, hogy
$(B)~m_{\mbox{DLP}} \geq m_{\mbox{C}}$ amiből következik, hogy $ m_{\mbox{DLP}}
	= m_{\mbox{C}}$.

$(A)$ Bármely adott $m_{\mbox{C}}$ vágáshoz könnyen készíthető olyan $\pi$ és $w$
amelyre az $m_{\text{C}}= \mbox{min} \left\{ \sum_{e\in E}^{} w(e)c(e)\right\}$
következik. Bizonyításként adunk egy módszert ehhez: legyen $S$ (tartalmazza a
forráspontot) és $T$ (tartalmazza a terminál csúcsot) diszjunkt halmazok, ekkor:
$\begin{cases}
		v \in S                 & \Rightarrow \pi(v)=0, \\
		v \in T                 & \Rightarrow \pi(v)=1, \\
		e \in (S,T) \mbox{ él } & \Rightarrow w(e)=1,   \\
		\mbox{másképp}          & \Rightarrow w(e)=0.
	\end{cases}$

Erre teljesül a $m_{\text{C}}= \mbox{min} \left\{ \sum_{e\in E}^{}
	w(e)c(e)\right\}$, amiből adódik az $m_{\mbox{DLP}} \leq m_{\mbox{C}}$, már csak
a másik irányú egyenlőtlenséget kell beállítani.

$(B)$ Az $B^*$ mátrix totálisan unimoduláris, tehát $y$ is egész értékű elemekből
áll (mivel a duális feladatban, min$\left\{ yb:yA=c; y\geq 0 \right\}$, szereplő
$c$ is az). Legyen adott $(\pi,w)$ optimális, egészértékű megoldás, ebből
kiindulva elkészítünk egy másik ugyancsak optimális megoldást, $(\pi',w')$--t
, amely csak $0$ vagy $1$ értékű elemeket tartalmaz:
$\pi'(v)=
	\begin{cases}
		0, & \mbox{ha } \pi(v) \leq \pi(s), \\
		1, & \mbox{egyébként},
	\end{cases}$ és
$w'(e)=
	\begin{cases}
		0, & \mbox{ha } w(e)=0,      \\
		1, & \mbox{ha } w(e) \geq 1.
	\end{cases}$

Ekkor $(\pi',w')$--re $(1)$ és $(3)$ teljesül. A $(2)$-öt indirekt bizonyítjuk.
Tegyük fel, hogy egy adott $e=(u,v)$ él esetén ez nem tejlesül, azaz
$\pi'(u)-\pi'(w)+w'(e)<0$. Ekkor a $0-1$ értékűségük miatt $\pi'(u)=w'(e)=0$ és
$\pi'(v)=1$ esetben valósulna meg. $\pi'$ definíciója miatt ebben az esetben
$\pi(v) > \pi(s) \geq \pi(u)$, ami ellentmondana $(2)$--nek, hiszen $w'$
definíciójábból adodik, hogy $w(e)=0$ (ami azt jelentené, hogy $u$--ból $v$--be
úgy nőtt a potenciál, hogy $w=0$). A megoldás optimális mert $\sum w'(e)c(e)
	\leq \sum w(e)c(e)$, mivel $w'(e) \leq w(e)$. Tehát $(1), (2), (3)$ teljesül és az így
felírott $\pi', w'$ egy helyes átírás.

Most visszatérve az $S$ és $T$ halmazainkra legyen, $S=\{v \in V: \pi'(v)=0\} $
és $T=\{v \in V: \pi'(v)=1\}$. Egy adott $e=(u \in S, v \in T)$ élre $w'(e)=1$.
Minden más élen $w$ csak akkor lehet egy, ha $c(e)=0$, mert egyébként $w'(e)=0$
változtatása után a feltételek továbbra is fennállnának, de a $\sum w'(e)c(e)$
csökkenne. Ezért $S$ és $T$ között feszülő élek alkotta vágás értéke
$m_{\mbox{DLP}}$, így $m_{\mbox{c}} \leq m_{\mbox{DLP}}$.

Ezzel egy általános bizonyítást adtunk a Ford--Fulkerson tételre, amely az így
átfogalmazott alakban általánosabb kérdések megválaszolására is alkalmazható.

\subsection{Minimális költségű folyam keresése}

Minden élhez rendeljünk egy k költséget, amely kifejezi, hogy egy egységnyi folyam
átvitele azon menyibe kerül. Ekkor kitűzhető egy olyan feladat, ami a legalább
$m$ nagyságú folyamok között keres minimális költségűt. Lineáris programozás alakban:

\[ \mbox{min} \left\{kx: B^*x^* \leq 0, x^* \geq 0, x \leq c,\mu \geq m \right\}. \]

Ha az élek kapacitásai egész értékűek, akkor egész értékű folyam is választható.
Ha az élek költsége is egészértékű, akkor ismert hatékony algoritmus megoldására,
Ford--Fulkersontól.

\subsection{Több termékes folyam}

Adott egy $G=(V,E)$ irányított gráf és abban k darab pont pár:
$(s_i,t_i)_{i = \overline{1,k}}$. $G$--t továbbra is képzelhetjük út-- vagy
csőhálózatnak, az $(s_i, t_i)$ pont párok pedig a $k$ darab szállítandó termék
termelő--, illetve fogyasztó helyének felelnek meg. Végül legyen adott egy $c:E
	\mapsto \mathbb{R}^+$ kapacitás függvény.

A feladat egy megoldása abból áll, hogy minden élhez $k$ darab számot fogunk
hozzárendelni, megmondva, hogy az egyes termékből ott éppen mennyi halad át.
Erre az esetre is alkalmazható a lineáris programozás, sőt a legalább két
termékes folyamoknál már az egyetlen ismert hatékony algoritmus ($k=1$--re a
javító utas algoritmus egész értékű megoldást ad polinomiális időben). Az egész
értékű feladat viszont már itt is NP nehéz (mivel a feladatot leíró mátrix nem
totálisan unimoduláris ekkor).