Optimizacijske metode

Pretoki in prerezi

Primer. Letalo iz San Francisca v New York je polno. Imamo pa proste sedeže na drugih letih:

• San Francisco - Denver: 5 mest
• San Francisco - Houston: 6 mest
• Denver - Atlanta: 2 mesti
• Denver - Chicago: 5 mest
• Houston - Atlanta: 5 mest
• Atlanta - New York: 7 mest
• Chicago - New York: 4 mesta

Koliko dodatnih potnikov lahko prepeljejo?

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1

  SFO [xlabel=s]
  JFK [xlabel=t]

  SFO -> DEN [headlabel=" 5  "]
  SFO -> IAH [headlabel=" 6  "]
  DEN -> ATL [headlabel="2       "]
  DEN -> ORD [headlabel=5]
  IAH -> ATL [headlabel=5]
  ATL -> JFK [headlabel=7]
  ORD -> JFK [headlabel=4]
}

Imamo usmerjen graf $G = (V, E)$ in pretočnosti $d_e$ za vsako povezavo $e \in E$. Iščemo maksimalni pretok: $$ \forall e \in E: \ 0 \le x_e \le d_e $$

Imamo dve posebni vozlišči:

• začetno vozlišče $s$ (angl. source)
• končno vozlišče $t$ (angl. terminal)

Predpostavimo, da v $s$ in iz $t$ ne gre nobena povezava. Za ostala vozlišča veljajo Kirchhoffovi zakoni: $$ \forall w \in V \setminus \{s, t\}: \ \sum_{uw \in E} x_{uw} = \sum_{wv \in E} x_{wv} $$

Seštejmo Kirchhoffove zakone po vseh $w \in V \setminus \{s, t\}$: $$ \begin{aligned} \sum_{w \in V \setminus \{s, t\}} \sum_{uw \in E} x_{uw} &= \sum_{w \in V \setminus \{s, t\}} \sum_{wv \in E} x_{wv} \\ \sum_{\substack{e \in E \\ \operatorname{konec}(e) \ne t}} x_e &= \sum_{\substack{e \in E \\ \operatorname{začetek}(e) \ne s}} x_e \end{aligned} $$

Prostornina pretoka je enaka $$ F \quad = \sum_{\substack{e \in E \\ \operatorname{konec}(e) = t}} x_e = \sum_{\substack{e \in E \\ \operatorname{začetek}(e) = s}} x_e $$

Iščemo pretok z maksimalno prostornino: $$ \begin{alignedat}{2} \max \ \sum_{\substack{e \in E \\ \operatorname{začetek}(e) = s}} x_e \\[1ex] \text{p.p.} \quad \forall w \in V \setminus \{s, t\}&:& \ \sum_{uw \in E} x_{uw} &= \sum_{wv \in E} x_{wv} \\ \forall uv \in E&:& \ 0 \le x_{uv} &\le d_{uv}, \end{alignedat} $$

To je poseben primer problema razvoza z omejitvami: vzamemo $b_v = 0$ ($v \in V$), $c_e = 0$ ($e \in E$) ter dodamo povezavo $ts$ s $c_{ts} = -1$, $d_{ts} = \infty$.

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]
  edge [taillabel=0]

  SFO [xlabel=s]
  JFK [xlabel="t  "]

  SFO -> DEN [xlabel=<&le; 5>]
  SFO -> IAH [xlabel=<&le; 6>]
  DEN -> ATL [xlabel=<&le; 2>]
  DEN -> ORD [xlabel=<&le; 5>]
  IAH -> ATL [xlabel=<&le; 5>]
  ATL -> JFK [xlabel=<&le; 7>]
  ORD -> JFK [xlabel=<&le; 4>]
  JFK -> SFO [taillabel=-1, constraint=false]
}

Ta problem lahko rešimo s simpleksno metodo na omrežjih za problem razvoza z omejitvami.

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  edge [fontcolor=red,labelfontcolor=black]
  node [label="", fontcolor=blue]

  SFO [xlabel=0]
  DEN [xlabel=0]
  IAH [xlabel=0]
  ATL [xlabel=0]
  ORD [xlabel=0]
  JFK [xlabel=0]

  SFO -> DEN [taillabel="       0     ", label=<0 <font color="black">&le; 5</font>>, color=red]
  SFO -> IAH [taillabel=0, label=<0 <font color="black">&le; 6</font>>, color=red]
  DEN -> ATL [taillabel="    0", label=<<font color="black">&le; 2</font>>]
  DEN -> ORD [taillabel=0, label=<0 <font color="black">&le; 5</font>>, color=red]
  IAH -> ATL [taillabel=0, label=<0 <font color="black">&le; 5</font>>, xlabel=<<font color="blue">f</font>>, color=red, style=dashed]
  ATL -> JFK [taillabel=0, label=<0 <font color="black">&le; 7</font>>, color=red]
  ORD -> JFK [taillabel=0, label=<<font color="black">&le; 4</font>>]
  JFK -> SFO [taillabel=-1, xlabel=<e<br></br>   0+(-1) &lt; 0>, color=blue, fontcolor=blue, constraint=false]
}

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  edge [fontcolor=red,labelfontcolor=black]
  node [label="", fontcolor=blue]

  SFO [xlabel=0]
  DEN [xlabel=0]
  IAH [xlabel=0]
  ATL [xlabel=1]
  ORD [xlabel=0]
  JFK [xlabel=1]

  SFO -> DEN [taillabel="       0     ", label=<0 <font color="black">&le; 5</font>>, color=red]
  SFO -> IAH [taillabel=0, label=<5 <font color="black">&le; 6</font>>, color=red]
  DEN -> ATL [taillabel="    0", label=<<font color="black">&le; 2</font>>, color=green]
  DEN -> ORD [taillabel=0, label=<0 <font color="black">&le; 5</font>>, color=red]
  IAH -> ATL [taillabel=0, label=<5 <font color="black">&le; 5</font>>, style=bold]
  ATL -> JFK [taillabel=0, label=<5 <font color="black">&le; 7</font>>, color=red]
  ORD -> JFK [taillabel=0, label=<<font color="black">&le; 4</font>>, xlabel="e = f", color=blue, fontcolor=blue, style=dashed]
  JFK -> SFO [taillabel=-1, label=5, color=red, constraint=false]
}

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  edge [fontcolor=red,labelfontcolor=black]
  node [label="", fontcolor=blue]

  SFO [xlabel=0]
  DEN [xlabel=0]
  IAH [xlabel=0]
  ATL [xlabel=1]
  ORD [xlabel=0]
  JFK [xlabel=1]

  SFO -> DEN [taillabel="       0     ", label=<4 <font color="black">&le; 5</font>>, xlabel=<<font color="blue">f</font>>, color=red, style=dashed]
  SFO -> IAH [taillabel=0, label=<5 <font color="black">&le; 6</font>>, color=red]
  DEN -> ATL [taillabel="    0", label=<<font color="black">&le; 2</font>>, xlabel=e, color=blue, fontcolor=blue]
  DEN -> ORD [taillabel=0, label=<4 <font color="black">&le; 5</font>>, color=red]
  IAH -> ATL [taillabel=0, label=<5 <font color="black">&le; 5</font>>, style=bold]
  ATL -> JFK [taillabel=0, label=<5 <font color="black">&le; 7</font>>, color=red]
  ORD -> JFK [taillabel=0, label=<4 <font color="black">&le; 4</font>>, style=bold]
  JFK -> SFO [taillabel=-1, label=9, color=red, constraint=false]
}

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  edge [fontcolor=red,labelfontcolor=black]
  node [label=""]

  SFO [xlabel=<<font color="blue">0</font>>]
  DEN [xlabel=<<font color="blue">1</font>>]
  IAH [xlabel=<<font color="blue">0</font>>]
  ATL [xlabel=<<font color="blue">1</font>>]
  ORD [xlabel=<<font color="blue">1</font>>]
  JFK [xlabel=<<font color="blue">1</font>>]

  SFO -> DEN [taillabel="       0     ", label=<5 <font color="black">&le; 5</font>>, style=bold]
  SFO -> IAH [taillabel=0, label=<5 <font color="black">&le; 6</font>>, color=red]
  DEN -> ATL [taillabel="    0", label=<1 <font color="black">&le; 2</font>>, color=red]
  DEN -> ORD [taillabel=0, label=<4 <font color="black">&le; 5</font>>, color=red]
  IAH -> ATL [taillabel=0, label=<5 <font color="black">&le; 5</font>>, style=bold]
  ATL -> JFK [taillabel=0, label=<6 <font color="black">&le; 7</font>>, color=red]
  ORD -> JFK [taillabel=0, label=<4 <font color="black">&le; 4</font>>, style=bold]
  JFK -> SFO [taillabel=-1, label=10, color=red, constraint=false]
}

V praksi uporabljamo Ford-Fulkersonov algoritem.

Definicija. Naj bo $x$ dopustna rešitev za problem maksimalnega pretoka na usmerjenem grafu $G = (V, E)$ s pretočnostmi $d_e$ ($e \in E$) ter začetnim vozliščem $s$ in končnim vozliščem $t$. Rečemo, da je $v_0 v_1 \dots v_k$ ($v_i \in V, 0 \le i \le k$) povečujoča pot, če je $v_0 = s$, $v_k = t$ ter, za $1 \le i \le k$,

• $v_{i-1} v_i \in E$ in $x_{v_{i-1} v_i} < d_{v_{i-1} v_i}$ (prema povezava), ali
• $v_i v_{i-1} \in E$ in $x_{v_i v_{i-1}} > 0$ (obratna povezava).

Ideja: vzamemo povečujočo pot. Pretok na tej poti povečamo za $$ p = \min(\{x_e \mid e \in C \text{ obratna}\} \cup \{d_e - x_e \mid e \in C \text{ prema}\}) $$ (tj., povečamo na premih in zmanjšamo na obratnih povezavah).

digraph G {
  rankdir=LR
  node [label=""]

  au [style=invis]
  ad [style=invis]
  bu [style=invis]
  bd [style=invis]
  cu [style=invis]
  cd [style=invis]
  du [style=invis]
  dd [style=invis]
  s [xlabel=s]
  x [style=invis]
  t [xlabel=t]

  au -> a -> ad [label="  +p"]
  bu -> b -> bd [style=invis]
  bd -> b -> bu [label="  -p", constraint=false]
  cu -> c [label="  +p"]
  c -> cd [style=invis]
  cd -> c [label="  -p", constraint=false]
  du -> d [style=invis]
  d -> du [label="  -p", constraint=false]
  d -> dd [label="  +p"]
  s -> x -> t [label="+p"]
}