Proučite tekst od 34. do 50. stranice skripte. Dat ću odmah neke komentare.
Prošli put smo završili s Primjerom 3 (str 31-34). Nastavljamo s Primjerom 4 na str. 34.
Primjer je malo kompliciraniji od prethodnog - obratite pažnju: kad uočimo luk na kojem želimo postaviti tok +s - dobiveni ciklus je prilično "dugačak". Pokušajte direktno gledanjem u tablicu (bez skiciranja ciklusa) zaključiti gdje pišete +s, a gdje -s. Bitno je kretati se tablicom naizmjence vodoravno/okomito, prolazeći samo lukovima s pozitivnim tokom (osim naravno prvog polja) s ciljem dolaska na početno polje.
Točka 2.5 je ključna za razumijevanje MODI metode. Kreće se od pojma degeneracije koja je vrlo česta u transportnim problemima (Zadatak 2.8. daje jednostavnu karakterizaciju degeneriranosti).
Rad s degeneriranim problemima opisan je u uvodnom primjeru, što je opravdano Zadatkom 2.1.
Nastavlja se s definicijom bazičnog toka i povezivanjem s pojmom vrha u pripadnom dopustivom (poliedarskom skupu).
U Zadatku 2.2. je dan precizan opis vrhova (degeneriranih i nedegeneriranih) u skupu danom uvjetima Ax=b, x>=0, kako izgledaju i uvjeti u transportnom problemu. Zadatak 2.4. daje paralelu vrhova u transportnom problemu i bazičnih tokova, a pomoću Zadatka 2.5 dolazimo do karakterizacije degeneriranih vrhova kao degeneriranih bazičnih tokova.
Stoga možemo uočiti sličnost MODI metode sa simpleks metodom za opću zadaću linearnog programiranja.
Pomoću Zadatka 2.6 zaključujemo da u nedegeneriranom slučaju metoda daje rješenje u konačno mnogo koraka, dok je u slučaju degeneracije jedino bitno da ne uđemo u beskonačnu petlju u kojoj se vraćamo stalno na ista generirajuća stabla (tj. ne izlazimo iz istog degeneriranog vrha).
Točku završavamo sa Zadatkom 2.9 - bit će važan za kasnije...
Pogledajte zadatke za vježbu sa str. 157-161.
Vezano uz Zadatak 2.7. i pitanje jedinstvenosti rješenja transportnog problema spomenimo čestu situaciju danu u Zadatku 5 iz prvog kolokvija 2016./17. (http://degiorgi.math.hr/forum/viewtopic.php?t=18841). (malo složenije ...) Ideja rješenja bi bila usporediti vrijednost funkcije cilja u nekom drugom dopustivom toku x. Ako je polazni optimalan tok x* nedegeneriran, to je na nekom luku izvan pripadnog (optimalnog) generirajućeg stabla tok x pozitivan pa zaključak c^Tx>c^Tx* dobivamo ako za u,v u (2.1) na str. 24 uzmemo u*,v* koje smo odredili iz optimalnog bazičnog toka x*.
Također, pretpostavku nedegeneriranosti možemo i izostaviti - razmislite... Pokažite primjerom da obrat (u Zadatku 5) ne vrijedi.
U svakom slučaju, ako za optimalan x* neka razlika c_ij-(u_i+v_j) izvan pripadnog generirajućeg stabla je jednaka nuli, uvijek možemo pokušati uključiti taj luk u stablo (+s kao u algoritmu...) - ako je x* nedegeneriran doći ćemo do drugog optimalnog rješenja, a inače se može desiti da je rješenje ipak jedinstveno - pokušajte smisliti primjere u kojima se javlja jedinstvenost, odnosno nejedinstvenost u slučaju degeneriranog x*.
Proučite tekst od 34. do 50. stranice skripte. Dat ću odmah neke komentare.
Prošli put smo završili s Primjerom 3 (str 31-34). Nastavljamo s Primjerom 4 na str. 34.
Primjer je malo kompliciraniji od prethodnog - obratite pažnju: kad uočimo luk na kojem želimo postaviti tok +s - dobiveni ciklus je prilično "dugačak". Pokušajte direktno gledanjem u tablicu (bez skiciranja ciklusa) zaključiti gdje pišete +s, a gdje -s. Bitno je kretati se tablicom naizmjence vodoravno/okomito, prolazeći samo lukovima s pozitivnim tokom (osim naravno prvog polja) s ciljem dolaska na početno polje.
Točka 2.5 je ključna za razumijevanje MODI metode. Kreće se od pojma degeneracije koja je vrlo česta u transportnim problemima (Zadatak 2.8. daje jednostavnu karakterizaciju degeneriranosti).
Rad s degeneriranim problemima opisan je u uvodnom primjeru, što je opravdano Zadatkom 2.1.
Nastavlja se s definicijom bazičnog toka i povezivanjem s pojmom vrha u pripadnom dopustivom (poliedarskom skupu).
U Zadatku 2.2. je dan precizan opis vrhova (degeneriranih i nedegeneriranih) u skupu danom uvjetima Ax=b, x>=0, kako izgledaju i uvjeti u transportnom problemu. Zadatak 2.4. daje paralelu vrhova u transportnom problemu i bazičnih tokova, a pomoću Zadatka 2.5 dolazimo do karakterizacije degeneriranih vrhova kao degeneriranih bazičnih tokova.
Stoga možemo uočiti sličnost MODI metode sa simpleks metodom za opću zadaću linearnog programiranja.
Pomoću Zadatka 2.6 zaključujemo da u nedegeneriranom slučaju metoda daje rješenje u konačno mnogo koraka, dok je u slučaju degeneracije jedino bitno da ne uđemo u beskonačnu petlju u kojoj se vraćamo stalno na ista generirajuća stabla (tj. ne izlazimo iz istog degeneriranog vrha).
Točku završavamo sa Zadatkom 2.9 - bit će važan za kasnije...
Pogledajte zadatke za vježbu sa str. 157-161.
Vezano uz Zadatak 2.7. i pitanje jedinstvenosti rješenja transportnog problema spomenimo čestu situaciju danu u Zadatku 5 iz prvog kolokvija 2016./17. (http://degiorgi.math.hr/forum/viewtopic.php?t=18841). (malo složenije ...) Ideja rješenja bi bila usporediti vrijednost funkcije cilja u nekom drugom dopustivom toku x. Ako je polazni optimalan tok x* nedegeneriran, to je na nekom luku izvan pripadnog (optimalnog) generirajućeg stabla tok x pozitivan pa zaključak c^Tx>c^Tx* dobivamo ako za u,v u (2.1) na str. 24 uzmemo u*,v* koje smo odredili iz optimalnog bazičnog toka x*.
Također, pretpostavku nedegeneriranosti možemo i izostaviti - razmislite... Pokažite primjerom da obrat (u Zadatku 5) ne vrijedi.
U svakom slučaju, ako za optimalan x* neka razlika c_ij-(u_i+v_j) izvan pripadnog generirajućeg stabla je jednaka nuli, uvijek možemo pokušati uključiti taj luk u stablo (+s kao u algoritmu...) - ako je x* nedegeneriran doći ćemo do drugog optimalnog rješenja, a inače se može desiti da je rješenje ipak jedinstveno - pokušajte smisliti primjere u kojima se javlja jedinstvenost, odnosno nejedinstvenost u slučaju degeneriranog x*.
_________________
Marko Vrdoljak
