Optimizacijske metode

Opomba. Če je $y_u + c_{uv} < y_v$ in je $C$ cikel v $H$, ki vsebuje $uv$, to pomeni, da je $$ \sum_{e \in C \text{ prema}} c_e - \sum_{e \in C \text{ obratna}} c_e < 0. $$

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

  a [xlabel=a]
  b [xlabel=b]
  c [xlabel=c]
  d [xlabel=d]
  e [xlabel=e]

  a -> b
  a -> c [style=dashed, color=blue]
  d -> b [constraint=false]
  c -> d [style=invis]
  c -> e
  d -> e [constraint=false]
}

$$ \begin{aligned} y_b &= y_a + c_{ab} \\ y_d &= y_b - c_{db} \\ &= y_a + c_{ab} - c_{db} \\ y_e &= y_d + c_{de} \\ &= y_a + c_{ab} - c_{db} + c_{de} \\ y_c &= y_e - c_{ce} \\ &= y_a + c_{ab} - c_{db} + c_{de} - c_{ce} \\[1ex] y_a + c_{ac} &< y_a + c_{ab} - c_{db} + c_{de} - c_{ce} \\ 0 &> c_{ac} + c_{ce} - c_{de} + c_{db} - c_{ab} \end{aligned} $$ Ko razvoz na premih povezavah povečamo za $p$ in ga na obratnih povezavah zmanjšamo za $p$, se cena poveča za $$ p (c_{ac} + c_{ce} - c_{de} + c_{db} - c_{ab}) $$ oziroma v splošnem za $$ p \left(\sum_{e \in C \text{ prema}} c_e - \sum_{e \in C \text{ obratna}} c_e\right). $$ Če je $p > 0$, se cena torej zmanjša.

Opomba. Če ne moremo izbrati izstopne povezave, so vse povezave na $C$ preme in velja $\sum_{e \in C} c_e < 0$. Našli smo negativen cikel, problem razvoza je torej neomejen.

Trditev. Če velja $\forall uv \in E: \ y_u + c_{uv} \ge y_v$ (z enakostjo pri vseh povezavah $uv \in E'$ vpetega drevesa $T = (V, E')$), je rešitev optimalna.

Dokaz. Naj bo $x'$ še ena dopustna rešitev. Potem velja $$ \forall uv \in E: \ (y_u + c_{uv} - y_v) x_{uv}' \ge (y_u + c_{uv} - y_v) x_{uv} = 0, $$ saj

• če $uv \in E'$, potem $y_u + c_{uv} - y_v = 0$, in
• če $uv \not\in E'$, potem $x_{uv} = 0$, $(y_u + c_{uv} - y_v) x_{uv}' \ge 0$.

Če seštejemo za vse povezave, dobimo $$ 0 \le \sum_{uv \in E} c_{uv} x_{uv}' - \sum_{uv \in E} (y_v - y_u) x_{uv}' = c^\top x' - (A^\top y)^\top x' = c^\top x' - y^\top A x' = c^\top x' - y^\top b \le c^\top x' -c^\top x $$ Velja torej $c^\top x' \ge c^\top x$.

Opomba. Tudi pri simpleksni metodi za omrežja lahko pride do ciklanja. Temu se lahko izognemo z uporabo Cunninghamovega pravila:

• izberemo koren $r \in V$;
• ko izbiramo izstopno povezavo v ciklu $C$ z vstopno povezavo $e = uv$, določimo vozlišče $z$ na $C$, ki leži na poteh (v drevesu - brez $e$) od $r$ do $u$ oziroma $v$, in za izstopno povezavo izberemo prvega kandidata na $C$ od $z$ naprej v smeri $uv$.

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

  r -> a
  a -> b [style=invis]
  b -> a [constraint=false]
  b -> z
  z -> c [color=green]
  z -> d
  c -> e [style=invis]
  e -> c [constraint=false]
  d -> f [label=e, color=blue, fontcolor=blue]
  e -> g [color=green]
  g -> f [label=f, fontcolor=blue, color=green, style=dashed, constraint=false]

  d [xlabel=u]
  f [xlabel=v]
}

Kako pridemo do začetne dopustne rešitve oziroma dokažemo, da je problem nedopusten? Uporabimo dvofazno simpleksno metodo na omrežjih. Definiramo pomožni problem:

• Izberemo koren $r \in V$.
• Za vsako vozlišče $v \in V \setminus \{r\}$:
  • če $b_v \ge 0$ in povezava $rv$ ne obstaja, jo dodamo;
  • če $b_v < 0$ in povezava $vr$ ne obstaja, jo dodamo.
• Dobimo nov graf $\tilde{G} = (V, \tilde{E})$. Dodanim povezavam (iz $\tilde{E} \setminus E$) pravimo umetne povezave, povezavam iz $E$ pa prvotne povezave.
• Definiramo nove cene $\tilde{c}$, in sicer
  • prvotne povezave $e \in E$ imajo ceno $\tilde{c}_e = 0$, in
  • umetne povezave $e \in \tilde{E} \setminus E$ imajo ceno $\tilde{c}_e = 1$.

Ta problem je vedno dopusten:

• $x_{rv} = b_v$ za vse $v \in V \setminus \{r\}$ z $b_v \ge 0$,
• $x_{vr} = -b_v$ za vse $v \in V \setminus \{r\}$ z $b_v < 0$,
• $x_e = 0$ za vse ostale povezave $e \in \tilde{E}$.

Kirchhofovi zakoni:

• $v \ne r$, $b_v \ge 0$: $x_{rv} = b_v$
• $v \ne r$, $b_v < 0$: $-x_{vr} = b_v$
• $v = r$: $-\sum_{\substack{v \ne r \\ b_v \ge 0}} x_{rv} + \sum_{\substack{v \ne r \\ b_v < 0}} x_{vr} = -\sum_{\substack{v \ne r \\ b_v \ge 0}} b_v + \sum_{\substack{v \ne r \\ b_v < 0}} (-b_v) = -\sum_{v \ne r} b_v = b_r$

Prvotni problem je dopusten natanko tedaj, ko je optimalna vrednost pomožnega problema enaka $0$. Ker so vse cene v pomožnem problemu nenegativne, je problem omejen.

Primer. Dokaži, da je problem nedopusten.

digraph G {
  rankdir=TD
  nodesep=1
  ranksep=1

  a [label=1]
  b [label=-3]
  c [label=-2]
  r [label=0, xlabel="r  "]
  d [label=4]

  a -> c [style=invis]
  a -> r [taillabel="    1"]
  b -> a [taillabel=3, constraint=false]
  b -> r [taillabel="4    "]
  b -> d [taillabel=2]
  c -> a [taillabel=" 1", headport=sw, constraint=false]
  c -> r [taillabel=2, constraint=false]
  d -> r [taillabel=1, constraint=false]
}

Narišimo graf za pomožni problem in določimo začetno drevesno rešitev.

digraph G {
  rankdir=TD
  nodesep=0.5
  ranksep=1
  edge [fontcolor=red,labelfontcolor=black]

  a [label=1, xlabel=<<font color="blue">1</font>>]
  b [label=-3, xlabel=<<font color="blue">0</font>>]
  c [label=-2, xlabel=<<font color="blue">0</font>>]
  r [label=0, xlabel=<<font color="blue">0</font>>]
  d [label=4, xlabel=<<font color="blue">1</font>>]

  a -> c [style=invis]
  a -> r [taillabel="\n 0"]
  b -> a [taillabel=0, xlabel=<<font color="blue">e</font>>, color=blue, constraint=false]
  b -> r [taillabel="0    ", label=3, color=red]
  b -> d [taillabel=0, color=green]
  c -> a [taillabel=" 0", color=green, constraint=false]
  c -> r [taillabel=0, label=2, color=red, constraint=false]
  d -> r [taillabel="         0", constraint=false]
  r -> a [taillabel="1   ", label=1, xlabel=<<font color="blue">f      </font>>, style=dashed, color=red, constraint=false]
  r -> d [taillabel=1, label=4, color=red, constraint=false]
}

digraph G {
  rankdir=TD
  nodesep=0.5
  ranksep=1
  edge [fontcolor=red,labelfontcolor=black]

  a [label=1, xlabel=<<font color="blue">0</font>>]
  b [label=-3, xlabel=<<font color="blue">0</font>>]
  c [label=-2, xlabel=<<font color="blue">0</font>>]
  r [label=0, xlabel=<<font color="blue">0</font>>]
  d [label=4, xlabel=<<font color="blue">1</font>>]

  a -> c [style=invis]
  a -> r [taillabel="\n 0"]
  b -> a [taillabel=0, label=1, color=red, constraint=false]
  b -> r [taillabel="0    ", label=2, xlabel=<<font color="blue">f</font>>, style=dashed, color=red]
  b -> d [taillabel=0, xlabel=<<font color="blue">e  </font>>, color=blue]
  c -> a [taillabel=0, constraint=false]
  c -> r [taillabel=0, label=2, color=red, constraint=false]
  d -> r [taillabel="         0", constraint=false]
  r -> a [taillabel="1  ", constraint=false]
  r -> d [taillabel=1, label=4, color=red, constraint=false]
}

digraph G {
  rankdir=TD
  nodesep=0.5
  ranksep=1
  edge [fontcolor=red,labelfontcolor=black]

  a [label=1, xlabel=<<font color="blue">1</font>>]
  b [label=-3, xlabel=<<font color="blue">1</font>>]
  c [label=-2, xlabel=<<font color="blue">0</font>>]
  r [label=0, xlabel=<<font color="blue">0</font>>]
  d [label=4, xlabel=<<font color="blue">1</font>>]

  a -> c [style=invis]
  a -> r [taillabel="\n 0"]
  b -> a [taillabel=0, label=1, xlabel=<<font color="blue">f</font>>, style=dashed, color=red, constraint=false]
  b -> r [taillabel="0    "]
  b -> d [taillabel=0, label=2, color=red]
  c -> a [taillabel=0, xlabel=<<font color="blue">e</font>>, color=blue, constraint=false]
  c -> r [taillabel=0, label=2, color=red, constraint=false]
  d -> r [taillabel="         0", constraint=false]
  r -> a [taillabel="1  ", constraint=false]
  r -> d [taillabel=1, label=2, color=red, constraint=false]
}

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

  edge [fontcolor=red,labelfontcolor=black]

  a [label=1, xlabel=<<font color="blue">0</font>>]
  b [label=-3, xlabel=<<font color="blue">1</font>>]
  c [label=-2, xlabel=<<font color="blue">0</font>>]
  r [label=0, xlabel=<<font color="blue"> 0</font>>]
  d [label=4, xlabel=<<font color="blue">1</font>>]

  a -> c [style=invis]
  a -> r [taillabel="\n0"]
  b -> a [taillabel=0, constraint=false]
  b -> r [taillabel="0    "]
  b -> d [taillabel=0, label=3, color=red]
  c -> a [taillabel=0, xlabel=1, color=red, constraint=false]
  c -> r [taillabel=0, label=1, color=red, constraint=false]
  d -> r [taillabel="         0", constraint=false]
  r -> a [taillabel="1  ", constraint=false]
  r -> d [taillabel=1, label=1, color=red, constraint=false]
}

Ni več kandidatov za vstop - imamo optimalno rešitev pomožnega problema. Ker ta vključuje umetno povezavo s pozitivnim razvozom, je prvotni problem nedopusten.

Opomba. Če je $\sum_{v \in V} b_v > 0$, ne moremo zadostiti vsem potrebam. Če je $\sum_{v \in V} b_v < 0$, dodamo umetno vozlišče $s \not\in V$ ("skladišče") in povezavo od vseh izvorov (vozlišč $v \in V$ z $b_v < 0$) do $s$ s ceno $0$ ter določimo $b_s = -\sum_{v \in V} b_v$.

Izrek o celoštevilskih rešitvah. Dan je problem razvoza s celoštevilskimi vrednostmi $b_v$ ($v \in V$).

1. Če obstaja dopustna rešitev, obstaja tudi celoštevilska dopustna rešitev.
2. Če obstaja optimalna rešitev, obstaja tudi celoštevilska optimalna rešitev.

Dokaz. Naredimo dvofazno simpleksno metodo na omrežjih. Na vsakem koraku imamo celoštevilsko rešitev; če je problem dopusten, dobimo celoštevilsko dopustno rešitev. Tedaj naredimo še drugo fazo, na vsakem koraku imamo celoštevilsko rešitev. Če pridemo do optimalne rešitve, bo ta celoštevilska.