#1: Trinaesti tjedan 2020 Autor/ica: markov, Postano: 12:48 ned, 24. 5. 2020 — Na sastanku u utorak u 10 na Zoom-u vježbamo. Možemo ev. i obraditi dijelove gradiva koji su vam ostali nejasni.
#2: Autor/ica: markov, Postano: 10:20 pon, 25. 5. 2020 — Rješavat ćemo drugi kolokvij od 13.6.2017. (drugu grupu) i prošlogodišnji drugi kolokvij pa bi bilo dobro da o tim zadacima i unaprijed razmislite.
Kada znamo da je rješenje transportnog problema jedinstveno? Primijetio sam da kada postoji više rješenja, da tada postoji brid (i,j) za koji je x[i,j]=0 i c[i,j]-(u[i]+v[j])=0 (u Zadatku 10.13 iz skripte).
Je li to nužan i dovoljan uvjet za nejedinstvenost?
Lijep pozdrav
Borna R.
#4: Autor/ica: markov, Postano: 9:45 čet, 4. 6. 2020 — Dobro ste primijetili. Ista situacija je i kod problema minimizacije troškova toka. Pogledajte i opasku u Trećem tjednu...
Dakle, ako je optimalan tok nedegeneriran i [tex]c_{ij}-u_i-v_j=0[/tex] na nekom luku izvan generirajućeg stabla T, onda imamo drugo rješenje (zapravo i beskonačno mnogo jer je svaka konveksna kombinacija rješenja također rješenje).
Ako je optimalan tok nedegeneriran, i vrijedi gornji uvjet, može se dogoditi da je rješenje jedinstveno, ali i da nije.
No svejedno, postupak je uvijek isti - kad završite s algoritmom (i dobijete optimalan tok), ako pri provjeri uvjeta optimalnosti vidite da je zadovoljen gornji uvjet na nekom luku, dodajte taj luk stablu (+s) kao u standardnom koraku algoritma i vidjet ćete je li rjesenje nejedinstveno (s>0 - u nedegeneriranom slučaju to će uvijek biti - razmislite) ili je pak s=0 (novi tok je jednak starom, ali ima drugu reprezentaciju - drugo stablo T). Naravno, ako je više takvih lukova, treba provjeriti sve, ali i provjeriti što dobivate za novi tok u slučaju s=0 (je li se možda javila neka nova nula - jedna će sigurno biti).
