Trinaesti tjedan 2020 (informacija)

[markov]

Na sastanku u utorak u 10 na Zoom-u vježbamo. Možemo ev. i obraditi dijelove gradiva koji su vam ostali nejasni.

_________________
Marko Vrdoljak

[markov]

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.

_________________
Marko Vrdoljak

[bornic]

Poštovani profesore

Imam pitanje u vezi transportnog problema.

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.

[markov]

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).

_________________
Marko Vrdoljak