c_ij = v_j - u_i / • ∈ C⁺

.

:

c_ks =v_s - u_k /•( ) ∈ C^-

Każdy składnik występuje tu dokładnie 2 razy.

c_rs•  = v_s•  - u_r • δ_rs• 

c_rj =v_j - u_r /•(- 

c_rj =v_j - u_r /• 





c_ks =v_s - u_r /•(- 

Dodając stronami mamy:

Stąd widać, że jeżeli δ_rs>0,to funkcja celu maleje, a gdy δ _rs=0 , to funkcja celu nie zmienia się.

Założymy teraz, że mamy rozwiązanie optymalne cykliczne. Wtedy w kroku III wyrzucamy jedną klatkę, żeby nie było cyklu ( i wartość funkcji celu nie może zmaleć, bo rozwiązanie jest optymalne). Wtedy to rozwiązanie będzie acykliczne.

Zatem rozwiązania zadania transportowego należy szukać wśród rozwiązań acyklicznych. Rozwiązań cyklicznych jest skończona ilość.

Funkcja celu jest słabo malejąca.

z'=z-δ_rs

u_j-u_i≥c_ij

δ_rs = min {v_j - u_i - c_ij }<0

PROBLEMY SIECIOWE

1. Problem największego przepływu.

Załóżmy, że dany jest graf skierowany S=<P,U> - jest to para <P,U>, gdzie P- zbiór wierzchołków, U - zbiór tuków skierowanych bez pętli i cykli.

s- źródło \

t- ujście / wyróżnione wierzchołki

Pozostałe wierzchołki nazywamy węzłami pośrednimi

Jest to graf skierowany.

f(<3,4>)=f_ij ≥0

f(<4,3>) - to nie ma sensu

Na zbiorze łuków U określamy dwie funkcje f i x, które mają wartości rzeczywiste nieujemne.

f(<i,j>)=f_ij

x(<i,j>)==x_ij

f_ij- interpretujemy jako przepustowość łuku <i,j>

x_ij -interpretujemy jako przepływ po łuku <i,j>

Def.1.

Siecią transportową G_k nazywamy trójkę ( < P,U>,f,x)

Def.2.

Przepływem dopuszczalnym v, w sieci transportowej G_t nazywamy dowolną funkcję rzeczywistą x określoną na zbiorze tuków dopuszczalnych ( z U) spełniającą następujące warunki:

(1) 0≤x_ij≤f_ij dla <i,j>∈U

(2)

(3)
i≠s,i≠t

tzn., ze w węźle nie ma żadnych przypływów ani odpływów

(4)

Zagadnienie maksymalnego przepływu sprowadza się do wyznaczenia przepływu dopuszczalnego v spełniającego warunki (1)-(4), dla którego funkcja celu z =max v.

Jest to zadanie programowania liniowego. Zawsze jest rozw dopuszczalne - jest nim zero.

Ze względu na (1) zawsze istnieje rozw optymalne ( może ich być więcej).

Zbiór rozwiązań dopuszczalnych jest ograniczony.

Przykład:

(*)

Rozwiązanie jest dopuszczalne (bo do każdego węzła wpływa ile wypływa)

Przepływ v=3. Można go zwiększyć.

Teraz v=4 ( bo 3+1=4)

(*) można zapisać jako zadanie programowania liniowego)

z=v→max

x₁₂ + x₁₃ = v

-x₁₂ + x₂₄ = 0

-x₁₃ + x₃₄ + x₃₅ = 0

-x₂₄ - x₃₄ + x₄₆ + x₄₅ = 0

-x₃₅ - x₄₅ + x₅₆ = 0

-x₄₆ - x₅₆ = -v

Zmiennych jest tyle ile łuków.

X₁₂ ≤3

X₁₃ ≤4

X₂₄ ≤4

X₃₄ ≤5

X₃₅ ≤3

X₄₅ ≤2

X₄₆ ≤2

X₅₆ ≤4

X_ij ≥0

Jeżeli mamy n wierzchołków i m łuków, to zmiennych jest m+1 , a ograniczeń m+n.

ALGORYTM FORDA-FULKERSONA

Mamy G_t {<P,U>,f,x} , P dzielimy na P' i P ” , s∈ P', t∈ P”

Def.3.

Przekrojem w sieci G_t nazywamy zbiór łuków

s:={ <i,j>∈U: i∈P' ∧j∈P”} gdzie P' i P” spełniają następujące warunki:

P'∩P”=∅, P'∪P”=P , s∈P', t∈P” oraz dla każdego <i,j>∈U zachodzi i,j∈P' albo i,j∈P” albo i<∈P' ∧j∈P”

Dla przekroju s możemy zdefiniować przepustowość

Możemy również dla przekroju s* ( przekrój o minimalnej przepustowości) mówić o f(s*) - minimalna przepustowość.

P'={1,2} P”={3,4,5,6}

S₁ = {<2,4>,<1,3>} f(s₁)=8

S₁ = {<4,6>,<5,6>} f(s₂)=6

Natomiast para <2,4> <3,4> nie tworzy przekroju, bo możemy iść <1,3>,<3,5>,<5,6>

Def.4.

Łukiem nienasyconym nazywamy łuk <i,j> taki, że f_ij - x_ij >0.

Łukiem użytecznym nazywamy łuk <i,j> taki, że x_ij>0.

Łuk użyteczny może być nasycony lub nienasycony.

Łuk nasycony musi być użytecznym.

<i,j> łuk

{i,j} krawędź

<1,2>,<2,4>,<4,6> ścieżka

{1,2},{2,4},{4,6} łańcuch

Def.5.

Łańcuchem powiększającym nazywamy łańcuch Q={i₁,i₂},{i₂,i₃},...,{i_r-1,i_r} , i₁=s , i₂ = t

składający się z łuków nienasyconych lub użytecznych.

DKR

Q⁺ - skierowany zgodnie od s do t nienasycony

Q^- - skierowany niezgodnie od s do t użyteczny

Tw.1.

Przepływ v w sieci G_t jest maksymalny, jeżeli sieć nie zawiera łańcucha powiększającego wartość przepływu (i⁺,v_i)(i^-,v_i) j i→j cechowanie węzłów.

+ - gdy zgodnie z orientacją łuku

- - przeciwnie do orientacji łuku

v_i - o ile możemy zwiększyć przepływ

---