Problem razvoza

  • Primer. Imamo 3 mesta, v mestu proizvedejo 7 enot mleka, v ga porabijo 4 enote, v pa ga porabijo 3 enote.

  • Prevoz po cesti ima določeno ceno na enoto:

  • Kako najceneje prenesti mleko od proizvajalcev do porabnikov?

Predstavitev z grafom

Možni rešitvi

  • Rešitev 1:

    Cena:

  • Rešitev 2:

    Cena:

Pogoji

  • Imamo usmerjen utežen graf , kjer je množica vozlišč in množica usmerjenih povezav, ter uteži na vozliščih () in uteži na povezavah (), kjer:

    • , če je v vozlišču poraba , in
    • , če je v vozlišču proizvodnja .

  • Predpostavimo .

  • Iščemo za vsako povezavo , tako da velja Kirchhoffov zakon:

  • Radi bi minimizirali ceno .

Primer

  • V našem primeru:

  • To je linearni program, lahko ga rešimo z dvofazno simpleksno metodo.

  • Spoznali bomo prilagojen algoritem: simpleksna metoda na omrežjih.

Problem razvoza kot linearni program

  • Naj bo incidenčna matrika usmerjenega grafa , tj., , kjer je

    č

    ter in vektorja uteži vozlišč in povezav.

  • Potem lahko problem razvoza zapišemo kot

Dual problema razvoza

  • Ekvivalenten zapis :

  • Dual problema razvoza je potem

  • Ekvivalentno ga lahko zapišemo kot

Dualno dopolnjevanje

  • Ker ima matrika vrednosti v stolpcu, ki ustreza povezavi , vrednosti in v vrsticah, ki ustrezata vozliščema oziroma , in drugod, lahko dual problema razvoza zapišemo tudi kot

  • Opazimo, da če je dopustna (optimalna) rešitev , potem je tudi () dopustna (optimalna) rešitev , saj velja

  • Vemo tudi (dualno dopolnjevanje): če sta in dopustni rešitvi za oziroma , potem sta tudi optimalni natanko tedaj, ko velja

Primer

  • Rešitev 1 je dopustna, ni pa optimalna:

  • Rešitev 2 je dopustna in tudi optimalna:

Dualno dopolnjevanje, drugič

Kdaj je sistem () rešljiv?

Dualno dopolnjevanje, drugič (2)

  • Problem so cikli!
  • Tak sistem enačb je vedno rešljiv na drevesu (tj., povezanem grafu brez ciklov).
    • V drevesu je med vsakima vozliščema natanko ena pot.

Drevesna dopustna rešitev

  • Definicija. Dopustna rešitev za problem razvoza na grafu je drevesna dopustna rešitev, če v grafu obstaja vpeto drevo , da velja za vsak .

  • Trditev. Če ima problem razvoza dopustno rešitev, ima tudi drevesno dopustno rešitev.

Preme in obratne povezave

Definicija. Naj bo usmerjen graf in cikel v , ki vsebuje povezavo . Potem je povezava v ciklu (glede na povezavo ) prema, če kaže v isto smer kot , in obratna sicer.

Dokaz obstoja DDR

  • Naj bo dopustna rešitev za problem razvoza na grafu .
  • Naj bo in .
  • Definirali bomo zaporedje , tako da v -tem koraku dobimo tako, da iz odstranimo eno povezavo in določimo novo dopustno rešitev tako, da velja za vsako povezavo , dokler ne dobimo vpetega drevesa .
  • Denimo, da ima graf cikel , in naj bo povezava na z najmanjšo vrednostjo .

Dokaz obstoja DDR (2)

  • Določimo novo dopustno rešitev

    in novo množico povezav .

  • Opazimo, da velja , in za vsako povezavo .

Dokaz obstoja DDR (3)

Rešitev ustreza pogojem in je dopustna, saj še vedno velja Kirchhoffov zakon:

Primer

Spremembe razvozov

Enoličnost DDR

  • Opomba. Drevo določa dopustno rešitev, če ta obstaja.

  • Naj bo list v drevesu in povezava v s krajiščem .

  • Potem je enolično določen.

  • Postopek ponovimo za drevo , dokler imamo še kakšno povezavo.

Simpleksna metoda na omrežjih

  • 1. Začnemo z neko drevesno dopustno rešitvijo (jo uganemo; kasneje sistematično) na vpetem drevesu : za vsako povezavo .
  • 2. Rešimo sistem (vrednosti , so razvozne cene).
    • Preverimo, ali velja za vsako povezavo .
      • Če velja, je optimalna rešitev (po dualnem dopolnjevanju).

Simpleksna metoda na omrežjih (2)

  • 2. Rešimo sistem (nadaljevanje).
    • Sicer obstaja povezava , za katero velja .
      • Ta povezava (vstopna povezava) je v natanko enem (edinem) ciklu v grafu .
      • Naj bo obratna povezava v glede na z najmanjšo vrednostjo (izstopna povezava).
      • Razvoz povečamo za na premih povezavah na glede na (obratnih glede na ) in zmanjšamo za na obratnih povezavah na glede na (premih glede na ).
      • V novi rešitvi ima povezava ničeln razvoz in jo odstranimo iz drevesa.
    • Če obratne povezave na ni, potem je problem neomejen.
  • 3. Ponavljamo, dokler ne pridemo do optimalne rešitve (ali ugotovimo, da je problem neomejen).

Primer

Primer (2)

Določimo začetno drevesno dopustno rešitev, razvozne cene in kandidate za vstop ter izberemo vstopno in izstopno povezavo:

Primer (3)

Povezavam na ciklu spremenimo razvoz za :

Primer (4)

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

Primer (5)

Še en izrojen korak:

Primer (6)

Povezavam na ciklu spremenimo razvoz za :

Primer (7)

  • Ni več kandidatov za vstop - dobili smo optimalno rešitev s ceno

  • Preverimo še optimalno vrednost dualnega problema:

Korak simpleksne metode na omrežjih

Opomba. Če je in je cikel v , ki vsebuje , to pomeni, da je

Korak simpleksne metode na omrežjih (2)

  • Ko razvoz na premih povezavah povečamo za in ga na obratnih povezavah zmanjšamo za , se cena poveča za

    oziroma v splošnem za

  • Če je , se cena torej zmanjša.

  • Opomba. Če ne moremo izbrati izstopne povezave, so vse povezave na preme in velja .

    • Našli smo negativen cikel, problem razvoza je torej neomejen.

Optimalnost končne rešitve

  • Trditev. Če velja (z enakostjo pri vseh povezavah vpetega drevesa ), je rešitev optimalna.

  • Dokaz. Naj bo še ena dopustna rešitev. Potem velja

    saj

    • če , potem , in
    • če , potem , .

  • Če seštejemo za vse povezave, dobimo

  • Velja torej .

Ciklanje

  • Opomba. Tudi pri simpleksni metodi za omrežja lahko pride do ciklanja.

  • Temu se lahko izognemo z uporabo Cunninghamovega pravila:

    • izberemo koren ;

    • ko izbiramo izstopno povezavo v ciklu z vstopno povezavo , določimo vozlišče na , ki leži na poteh (v drevesu - brez ) od do oziroma , in za izstopno povezavo izberemo prvega kandidata na od naprej v smeri .

Dvofazna simpleksna metoda na omrežjih

  • 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 .
    • Za vsako vozlišče :
      • če in povezava ne obstaja, jo dodamo;
      • če in povezava ne obstaja, jo dodamo.
    • Dobimo nov graf . Dodanim povezavam (iz ) pravimo umetne povezave, povezavam iz pa prvotne povezave.
    • Definiramo nove cene , in sicer
      • prvotne povezave imajo ceno , in
      • umetne povezave imajo ceno .

Dvofazna simpleksna metoda na omrežjih (2)

  • Ta problem je vedno dopusten:

    • za vse z ,
    • za vse z ,
    • za vse ostale povezave .

  • Kirchhofovi zakoni:

    • , :
    • , :
    • :

  • Prvotni problem je dopusten natanko tedaj, ko je optimalna vrednost pomožnega problema enaka .

  • Ker so vse cene v pomožnem problemu nenegativne, je problem omejen.

Primer

Dokažimo, da je problem nedopusten.

Primer (2)

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

Primer (3)

Primer (4)

Primer (5)
  • 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.

Neuravnotežena povpraševanje in ponudba

  • Opomba. Če je , ne moremo zadostiti vsem potrebam.
  • Če je , dodamo umetno vozlišče ("skladišče") in povezavo od vseh izvorov (vozlišč z ) do s ceno ter določimo .

Izrek o celoštevilskih rešitvah

  • Dan je problem razvoza s celoštevilskimi vrednostmi ().

    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.

Dvojno stohastične matrike

  • Definicija. Matrika je dvojno stohastična, če velja () ter () in ().

  • Primer dvojno stohastične matrike:

Permutacijske matrike

  • Definicija. Matrika je permutacijska matrika, če je v vsaki vrstici in v vsakem stolpcu natanko ena enica.

  • Primeri za :

  • Imamo permutacijskih matrik velikosti .

  • Permutacijske matrike so dvojno stohastične.

Permutacijske in dvojno stohastične matrike

  • Trditev. Naj bo dvojno stohastična matrika. Potem obstaja permutacijska matrika , tako da velja ().

  • Dokaz. Naj bo usmerjen graf z množico vozlišč in množico povezav .

  • Postavimo še , () in ().

  • Dobljeni problem razvoza je dopusten, saj obstaja dopustna rešitev z ():

Nadaljevanje dokaza

  • Ker obstaja dopustna rešitev , obstaja tudi celoštevilska dopustna rešitev :

    kjer je v zgornjih vsotah natanko eden od enak , ostali pa so enaki .

  • Tako lahko dobimo permutacijsko matriko , kjer je , če je , in sicer.

  • Očitno potem velja ().

  • Tako permutacijsko matriko lahko najdemo z dvofazno simpleksno metodo na omrežjih.

Primer

Kőnigov izrek o plesnih parih

  • Definicija. Naj bo neusmerjen graf.

    • Množici pravimo prirejanje, če nobeni dve povezavi iz nimata skupnega krajišča (tj., ).
    • Prirejanje je popolno prirejanje, če je vsako vozlišče grafa krajišče povezave iz (tj., ).

  • Kőnigov izrek o plesnih parih.

    • Naj bo dvodelen regularen graf (tj., lahko zapišemo , tako da , ter ).
    • Potem obstaja popolno prirejanje v grafu .

Kőnigov izrek o plesnih parih (2)

Opomba. Če imamo deklet in fantov ter vsako dekle pozna fantov in vsak fant pozna deklet, potem lahko vsako dekle pleše s fantom, ki ga pozna.

Dokaz

  • Naj bo in .

  • Definirajmo matriko z

  • Matrika je dvojno stohastična, saj velja

Dokaz (2)

  • Po prejšnji trditvi obstaja permutacijska matrika , tako da

  • Matrika določa popolno prirejanje :

Problem razvoza z omejitvami

  • Imamo usmerjen utežen graf , kjer je množica vozlišč in množica usmerjenih povezav, ter uteži na vozliščih (), tako da velja , uteži na povezavah (), in omejitve na povezavah ().

  • Problem lahko zapišemo kot linearni program

    kjer je incidenčna matrika grafa .

  • Uporabili bomo podoben algoritem kot pri problemu razvoza.

Optimalnost rešitve

  • Definicija. Naj bo dopustna rešitev problema razvoza z omejitvami. Potem je (pri rešitvi ) povezava prazna, če velja , in nasičena, če velja .

  • Definicija. Naj bo dopustna rešitev problema razvoza z omejitvami. Rešitev je drevesna dopustna rešitev, če obstaja vpeto drevo v grafu , da velja (torej, povezave izven drevesa so prazne ali nasičene).

  • Trditev. Naj bo drevesna dopustna rešitev problema razvoza z omejitvami za vpeto drevo v grafu ter razvozne cene (tj., ). Če za vsako povezavo velja

    potem je optimalna rešitev.

Dokaz

  • Naj bo dopustna rešitev problema razvoza z omejitvami. Potem velja

    saj

    • če , potem ,
    • če in , potem , in
    • če in , potem in .

  • Če seštejemo za vse povezave, dobimo

  • Velja torej .

Simpleksna metoda na omrežjih za PRO

  • 1. Začnemo z neko drevesno dopustno rešitvijo na vpetem drevesu : ali za vsako povezavo .
  • 2. Rešimo sistem (tj., poiščemo razvozne cene).
    • Preverimo, ali za vsako povezavo velja in oziroma in . Če velja, je optimalna rešitev (po prejšnji trditvi).

Simpleksna metoda na omrežjih za PRO (2)

  • 2. Rešimo sistem (nadaljevanje).
    • Sicer obstaja povezava (vstopna povezava - v edinem ciklu v grafu ), za katero velja:
      • in : nastavimo ter premim povezavam povečamo razvoz za , obratnim pa zmanjšamo za ; ali
      • in : nastavimo ter premim povezavam zmanjšamo razvoz za , obratnim pa povečamo za .
    • Naj bo povezava v , za katero je dosežena vrednost (izstopna povezava). V novi rešitvi je prazna ali nasičena in jo odstranimo iz drevesa.
    • Če je , potem je problem neomejen.
  • 3. Ponavljamo, dokler ne pridemo do optimalne rešitve (ali ugotovimo, da je problem neomejen).

Primer

Primer (2)

  • Ker vstopi nasičena povezava, imamo .

  • Izstopna povezava je obratna, tako da bomo na njej povečali razvoz na in jo tako zasitili.

  • Ker vstopi prazna povezava, imamo .

  • Izstopna povezava je prema, tako da bomo na njej povečali razvoz na in jo tako zasitili.

  • Ni več kandidatov za vstop - dobili smo optimalno rešitev s ceno

Ista vstopna in izstopna povezava

  • Opomba. Lahko se zgodi, da je , torej je ista povezava tako vstopna kot izstopna.

  • Tedaj preide iz prazne v nasičeno povezavo ali obratno.

  • Ker vstopi prazna povezava, imamo .

  • Imamo , izstopna povezava je prema in jo tako zasitimo.

Ciklanje pri PRO

Opomba. Cunninghamovo pravilo (preprečuje "ciklanje"):

  • izberemo koren ;
  • ko izbiramo izstopno povezavo v ciklu z vstopno povezavo , določimo vozlišče na , ki leži na poteh (v drevesu - brez ) od do oziroma , in za izstopno povezavo izberemo prvega (zadnjega) kandidata na od naprej v smeri , če je ta prazna (nasičena).

Dvofazna simpleksna metoda za PRO

  • Kako poiščemo začetno drevesno dopustno rešitev oziroma dokažemo, da je problem nedopusten?

  • Uporabimo dvofazno simpleksno metodo na omrežjih za problem razvoza z omejitvami.

  • Definiramo pomožni problem:

    • Izberemo koren .
    • Za vsako vozlišče :
      • če in povezava ne obstaja, jo dodamo; če obstaja in , dodamo še eno tako povezavo;
      • če in povezava ne obstaja, jo dodamo; če obstaja in , dodamo še eno tako povezavo.

Dvofazna simpleksna metoda za PRO (2)

  • Dobimo nov graf . Dodanim povezavam (iz ) pravimo umetne povezave, povezavam iz pa prvotne povezave.

  • Definiramo nove cene , in sicer

    • prvotne povezave imajo ceno , in
    • umetne povezave imajo ceno .

  • Definiramo nove omejitve :

    • prvotne povezave imajo nespremenjene omejitve , in
    • umetne povezave niso omejene: .

  • Pomožni problem je optimalen, optimalna vrednost je natanko tedaj, ko je prvotni problem dopusten.