Optimizacijske metode

Primer.

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

  a [label=5, xlabel=<<font color="blue">20</font>>]
  b [label=-5, xlabel=<<font color="blue">15</font>>]
  c [label=-3, xlabel=<<font color="blue">0</font>>]
  d [label=-2, xlabel=<<font color="blue">21</font>>]
  e [label="", xlabel=<<font color="blue">27</font>>]
  f [label=2, xlabel=<<font color="blue">26    </font>>]
  g [label=3, xlabel=<<font color="blue">28</font>>]

  a -> b [style=invis]
  a -> c [style=invis]
  b -> a [taillabel=5, xlabel=2, color=red, constraint=false]
  c -> a [taillabel=20, label=3, color=red, constraint=false]
  c -> b [taillabel=5, label="0+5 < 15", color=green, fontcolor=black constraint=false]
  b -> d [taillabel=6, xlabel=<<font color="blue">f</font>>, label=3, color=red, style=dashed]
  c -> e [taillabel=11, label="0+11 < 27", xlabel=<<font color="blue">e</font>>, color=blue, fontcolor=black]
  d -> e [taillabel=1, label="21+1 < 27", color=green, fontcolor=black, constraint=false]
  d -> f [taillabel=5, label=5, color=red]
  e -> g [taillabel=1, label=3, color=red]
  f -> e [taillabel="1     ", xlabel="3     ", color=red, constraint=false]
  g -> f [taillabel=1, constraint=false]
}

Povezavam na ciklu spremenimo razvoz za $3$:

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

  a [label=5, xlabel=<<font color="blue">36</font>>]
  b [label=-5, xlabel=<<font color="blue">31</font>>]
  c [label=-3, xlabel=<<font color="blue">16</font>>]
  d [label=-2, xlabel=<<font color="blue">21</font>>]
  e [label="", xlabel=<<font color="blue">27</font>>]
  f [label=2, xlabel=<<font color="blue">26    </font>>]
  g [label=3, xlabel=<<font color="blue">28</font>>]

  a -> b [style=invis]
  a -> c [style=invis]
  b -> a [taillabel=5, xlabel=5, color=red, constraint=false]
  c -> a [taillabel=20, label=0, xlabel=<<font color="blue">f</font>>, color=red, style=dashed, constraint=false]
  c -> b [taillabel=5, label="16+5 < 31", xlabel=<<font color="blue">  e</font>>, color=blue, fontcolor=black, constraint=false]
  b -> d [taillabel=6]
  c -> e [taillabel=11, label=3, color=red]
  d -> e [taillabel=1, label="21+1 < 27", color=green, fontcolor=black, constraint=false]
  d -> f [taillabel=5, label=2, color=red]
  e -> g [taillabel=1, label=3, color=red]
  f -> e [taillabel="1     ", xlabel="0     ", color=red, constraint=false]
  g -> f [taillabel=1, constraint=false]
}

Izstopna povezava je imela razvoz $0$ - razvozi se ne spremenijo, spremeni se le drevo in razvozne cene (izrojen korak):

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

  a [label=5, xlabel=<<font color="blue">26</font>>]
  b [label=-5, xlabel=<<font color="blue">21</font>>]
  c [label=-3, xlabel=<<font color="blue">16</font>>]
  d [label=-2, xlabel=<<font color="blue">21</font>>]
  e [label="", xlabel=<<font color="blue">27</font>>]
  f [label=2, xlabel=<<font color="blue">26    </font>>]
  g [label=3, xlabel=<<font color="blue">28</font>>]

  a -> b [style=invis]
  a -> c [style=invis]
  b -> a [taillabel=5, xlabel=5, color=red, constraint=false]
  c -> a [taillabel="20        ", constraint=false]
  c -> b [taillabel=5, label=0, color=red, constraint=false]
  b -> d [taillabel=6]
  c -> e [taillabel=11, label=3, color=red]
  d -> e [taillabel=1, label="21+1 < 27", xlabel=<<font color="blue">  e</font>>, color=blue, fontcolor=black, constraint=false]
  d -> f [taillabel=5, label=2, color=red]
  e -> g [taillabel=1, label=3, color=red]
  f -> e [taillabel="1     ", xlabel=<0    <font color="blue">f</font>>, color=red, style=dashed, constraint=false]
  g -> f [taillabel=1, constraint=false]
}

Še en izrojen korak:

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

  a [label=5, xlabel=<<font color="blue">26</font>>]
  b [label=-5, xlabel=<<font color="blue">21</font>>]
  c [label=-3, xlabel=<<font color="blue">16</font>>]
  d [label=-2, xlabel=<<font color="blue">26</font>>]
  e [label="", xlabel=<<font color="blue">27</font>>]
  f [label=2, xlabel=<<font color="blue">31    </font>>]
  g [label=3, xlabel=<<font color="blue">28</font>>]

  a -> b [style=invis]
  a -> c [style=invis]
  b -> a [taillabel=5, xlabel=5, color=red, constraint=false]
  c -> a [taillabel="20        ", constraint=false]
  c -> b [taillabel=5, label=0, color=red, constraint=false]
  b -> d [taillabel=6]
  c -> e [taillabel=11, label=3, color=red]
  d -> e [taillabel=1, label=0, color=red, constraint=false]
  d -> f [taillabel=5, label=2, xlabel=<<font color="blue">f</font>>, color=red, style=dashed]
  e -> g [taillabel=1, label=3, color=red]
  f -> e [taillabel="1     ", constraint=false]
  g -> f [taillabel=1, label="28+1 < 31", xlabel=<<font color="blue">  e</font>>, color=blue, fontcolor=black, constraint=false]
}

Povezavam na ciklu spremenimo razvoz za $2$:

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

  a [label=5, xlabel=<<font color="blue">26</font>>]
  b [label=-5, xlabel=<<font color="blue">21</font>>]
  c [label=-3, xlabel=<<font color="blue">16</font>>]
  d [label=-2, xlabel=<<font color="blue">26</font>>]
  e [label="", xlabel=<<font color="blue">27</font>>]
  f [label=2, xlabel=<<font color="blue">29        </font>>]
  g [label=3, xlabel=<<font color="blue">28</font>>]

  a -> b [style=invis]
  a -> c [style=invis]
  b -> a [taillabel=5, xlabel=5, color=red, constraint=false]
  c -> a [taillabel=20, label="16+20 > 26", fontcolor=black, constraint=false]
  c -> b [taillabel=5, label=0, color=red, constraint=false]
  b -> d [taillabel=6, label="21+6 > 26", fontcolor=black]
  c -> e [taillabel=11, label=3, color=red]
  d -> e [taillabel=1, label=2, color=red, constraint=false]
  d -> f [taillabel=5, label="26+5 > 29", fontcolor=black]
  e -> g [taillabel=1, label=5, color=red]
  f -> e [taillabel="1  ", xlabel="29+1 > 27      ", fontcolor=black, constraint=false]
  g -> f [taillabel=1, label=2, color=red, constraint=false]
}

Ni več kandidatov za vstop - dobili smo optimalno rešitev s ceno $$ \sum_{e \in E} c_e x_e = 5 \cdot 5 + 5 \cdot 0 + 11 \cdot 3 + 1 \cdot 2 + 1 \cdot 5 + 1 \cdot 2 = 67. $$ Preverimo še optimalno vrednost dualnega problema: $$ \sum_{v \in V} b_v y_v = 5 \cdot 26 + (-5) \cdot 21 + (-3) \cdot 16 + (-2) \cdot 26 + 0 \cdot 27 + 2 \cdot 29 + 3 \cdot 28 = 67 $$