Úkol: Letecká společnost zajišťuje několik pravidelných linek mezi evropskými městy. Dostanete detailní informace o množině letů $\cal L$. Zajímalo by nás, kolik nejméně letadel je potřeba k zajištění všech letů $\cal L$.
Příklad leteckého řádu je v následující tabulce.

 

číslo letu počátek cíl
OK652 Praha (6am) Londýn (8am)
LX2008 Milano (7am) Vídeň (10am)
BA101 Londýn (9am) Madrid (11am)
AL504 Milano (10am) Franfurt (11am)
LH2451 Frankfurt (1pm) Budapešť (3pm)
KL404 Barcelona (6pm) Budapešť (9pm)

Lety $i$ a $j$ mohou být obslouženy stejným letadlem pokud je cílové letiště $i$ stejné jako počáteční letiště $j$, a pokud je mezi oběma lety dostatek času na provedení údržby (úklid, doplnění paliva, apod). Další možností je, že letadlo přeletí z cílového letiště $i$ na počáteční letiště $j$. To ovšem zabere více času a prostoj mezi oběma lety musí být výrazně delší. Přelety stojí výrazně méně než koupě dalšího letadla. Následující tabulka obsahuje příklad $3$ letů, které mohou být obslouženy stejným letadlem.

 

číslo letu počátek cíl
OK652 Praha (6am) Londýn (8am)
BA101 Londýn (9am) Madrid (11am)
KL404 Barcelona (6pm) Budapešť (9pm)

Modelování problému: Závislosti mezi jednotlivými lety budeme modelovat orientovaným grafem $G$. Lety budou tvořit vrcholy grafu a mezi dvěma vrcholy $i$ a $j$ povede orientovaná hrana, pokud letadlo obsluhující let $i$ může obsloužit i let $j$. Orientované hrany dodržují časovou souslednost. Hrana $ij$ mimo jiné znamená, že let $i$ předchází letu $j$. Orientovaný graf $G$ je acyklický, protože například časy odletu jednotlivých letů určují topologické uspořádání vrcholů.

Následující obrázek zachycuje modelový graf $G$ pro množinu letů $\cal L$ z předchozího příkladu.



Otázka, jestli množina letů $\cal L$ jde obsloužit pomocí $k$ letadel, odpovídá otázce, jestli v grafu $G$ existuje $k$ vrcholově disjunktních cest pokrývajících všechny vrcholy (cesta pokrývá vrchol, pokud přes něj vede).1

Řešení: Chceme zjistit, jestli v modelovém grafu $G$ existuje nejvýše $k$ vrcholově disjunktních cest, které pokryjí všechny vrcholy. Problém převedeme na výpočet cirkulace. Hlavní myšlenkou je, že podél každé cesty $P_\alpha$ odpovídající přeletům letadla $\alpha$ pošleme jednotkový tok. Pomocný graf $H$ zkonstruujeme následovně:

  • Pro každý let $i$ vytvoříme dva vrcholy $u_i, v_i\in V(H)$. První odpovídá odletu a druhý příletu. Do grafu $H$ ještě přidáme zdroj $s$ a stok $t$. Požadavky vrcholů nastavíme na $d(s)=-k$, $d(t)=k$ a $d(x)=0$ pro všechny ostatní vrcholy $x\in V(H)$. 
  • Každý let $i$ musí být obsloužen. Proto mezi $u_i$ a $v_i$ přidáme hranu a nastavíme její horní i dolní limit na tok na $1$. Tedy $l(u_iv_i)=1$ a $c(u_iv_i)=1$.
  • Pokud může být let $i$ a posléze i let $j$ obsloužen stejným letadlem, tak do $H$ přidáme hranu $v_iu_j$ a nastvíme její horní limit na tok $1$. Dolní limit necháme nenastaven. Tedy $c(v_iu_j)=1$ a $l(v_iu_j)=0$.
  • Protože každé letadlo může zahájit letový den letem $i$, tak do $H$ přidáme hranu $su_i$ s horním limitem $1$ a dolním $0$.
  • Podobně každé letadlo může skončit den letem $j$ a proto do $H$ přidáme hranu $v_jt$ s horním limitem $1$ a dolním $0$.
  • Může se stát, že nám na obsloužení všech letů bude stačit méně letadel. Proto přidáme hranu $st$ s horním limitem $k$ a dolním $0$, po které přebytečná letadla přetečou z $s$ do $t$.



Lemma: Lety ${\cal L}$ lze obsloužit pomocí $k$ letadel právě tehdy pokud v pomocném grafu $H$ existuje cirkulace.
Důkaz: Předpokládejme, že lety ${\cal L}$ lze obsloužit pomocí $k‘ \leq k$ letadel. Nechť ${\cal L}(\alpha)$ jsou lety přiřazené letadlu $\alpha$. Rozvrh letadla $\alpha$ odpovídá orientované cestě $P_\alpha$ v grafu $H$, která začíná v $s$, prochází hrany $u_iv_i$ obsluhovaných letů $i\in {\cal L}(\alpha)$ a končí v $t$, Podél této cesty $P_\alpha$ pošleme jednotkový tok. Pokud letadlu $\alpha$ nebyl přiřazen žádný let, tak pošleme jednotkový tok z $s$ rovnou do $t$ po hraně $st$. Požadavky ve vrcholech grafu $H$ jsou splněny, protože máme $k$ letadel a každé letadlo začíná v $s$ a končí v $t$. Limity na tok po hranách jsou rovněž splněny, protože každý let byl obsloužen nějakým letadlem.

Pro důkaz druhé implikace uvažme přípustnou cirkulaci v grafu $H$. Protože všechny limity na hranách jsou celočíselné, tak existuje přípustná cirkulace, která je celočíselná. Tok po každé hraně kromě hrany $st$ je buď $0$ a nebo $1$. Tok po hraně $st$ může být až $k$. Jediný vrchol, který se chová jako zdroj, je $s$. Podobně jediný stokový vrchol je $t$. Z toho důvodu můžeme cirkulaci rozdělit na $k$ jednotkových toků. Ty odpovídají $k$ dijsjunktním $(s,t)$-cestám v $H$. Výjimkou jsou cesty po hraně $st$. Protože hrana $u_iv_i$ má horní i dolní limit $1$, tak každá hrana $u_iv_i$ leží v právě jedné cestě. Každý jednotkový tok odpovídá jednomu letadlu a hrany $u_iv_i$ přes které tok prochází určují lety, které letadlu přiřadíme.

Poznámka: O proti reálnýmu rozvrhování letadel jsme si problém docela zjednodušili. (i) Ve skutečnosti nestačí rozvrhovat pouze letadla, ale každému letadlu musíme přiřadit posádku. Posádka přináší další omezení, protože musí dodržovat pravidelný odpočinek (to letadla nemusí). (ii) Také bychom chtěli maximalizovat zisk. Proto bychom se chtěli vyhnout některým přeletům prázdných letadel. Každé hraně grafu $H$ přiřadíme cenu přeletu a budeme hledat cirkulaci, která minimalizuje celkovou cenu hran, po kterých něco teče. To vede na problém toků minimální ceny (mincost flows), které se “naštěstí” umí také dobře počítat (bližší informace čtenář najde v [CCPSCombOpt]).

Poznámka: Úloha se dá vyřešit i bez cirkulací. Můžeme ji přímo převést na toky v sítích — viz cvičení [ref]priklad_minimalni_pokryti_cestami[/ref] v sekci [ref]cviceni_aplikace_toku_v_sitich[/ref].