zadaca iz OI

[AnaP]

1. zadacu iz OI mozete pronaci na
http://web.math.hr/~anaprlic/web/DZ.pdf

Svatko je dobio svoje zadatke. Ime i prezime je naznačeno na vrhu stranice.

Za drugi zadatak koristite IOR Tutorial kojeg mozete skinuti ovdje

http://highered.mcgraw-hill.com/sites/0073017795/student_view0/index.html

Mozete koristiti i bilo koji drugi softver.

Ispišite sve međukorake. Kod MODI metode ne morate crtati tablicu svaki put, dovoljno je zapisati na papir vrijednosti dualnih varijabli, koja varijabla postaje bazična, koja prestaje biti bazična i preko kojih polja ide zatvoreni put u tablici te vrijednost funkcije cilja barem za prvih 10 iteracija (ukoliko algoritam ne zavrsi ranije) svakog od pocetna tri bazna dopustiva rjesenja.

Rok za predaju je 31.3.2010. u 11 sati (zadacu donesite na vjezbe).

Ana Prlic

[AnaP]

Onaj zadatak kojeg sam danas dala na vjezbama nosi dodatna 2 boda. Imajte na umu da ce svaki kolokvij nositi 20 bodova, a ne 100, tako da ova dva boda i nisu tako mala stvar

[Gost]

Kako u IOR mozemo doc do modi metode?

[AnaP]

[AnaP]

Dodatni zadatak koji je dan na vjezbama je rijesen pa ponuda za dodatne bodove vise ne vrijedi. No, svakako bi bilo zgodno da ga i ostali pokusaju rijesiti ako imaju vremena. Zgodna je cinjenica da se transportni problem moze shvatiti kao problem asignacije i obratno jer onda imate dva algoritma za svaki transportni problem i za svaki problem asignacije (oba problema mozete rjesavati Madjarskom metodom i simplex metodom, gdje se optimalnost testira pomocu MODI metode).

Na zadatku iz zadace ste se uvjerili kako se problem asignacije puno brze rjesava Madjarskom metodom nego MODI metodom, jer kad se problem asignacije shvati kao transportni problem, onda imamo jako veliku degeneraciju zbog koje je (obicno) potrebno puno vise koraka nego u Madjarskoj metodi.

Jednako tako, transportni problem se obicno brze rjesava simplexom nego Madjarskom metodom jer kad transportni shvatimo kao problem asignacije, povecavamo velicinu tablice, ovisno o ukupnoj ponudi, odnosno potraznji.

[Gost]

postoji li mogućnost da i ostali studenti saznaju rješenje zadatka?

[AnaP]

*Rješenje za opću formulaciju:*

Matrica troškova potrebna za definiciju problema asignacije formira se tako da se svaki trošak cij (iz matrice troškova transportnog problema) zamijeni blok-matricom dimenzije ai x bj čiji su svi elementi jednaki upravo cij te se tako dobije matrica dimenzije ukupna_ponuda x ukupna _ponuda (suma ai-eva), odnosno ukupna_potražnja x ukupna_potražnja (suma bj-otova) (s obzirom da se u primjeru radilo o zatvorenom transportnom problemu). Time je u potpunosti definiran problem asignacije (uzimajući u obzir da su varijable odlučivanja iz {0,1}).

Ovo rjesenje sam danas dobila mailom.

[AnaP]

Rezultati prve zadace su u zadnjem stupcu tablice.

[AnaP]

Drugu zadacu mozete naci na
http://web.math.hr/~anaprlic/web/DZ2.pdf
Rok za predaju rjesenja je 26.05.2010 u 11 sati (na vjezbama).
U isto to vrijeme ce biti i rok za predaju trece zadace koju cu objaviti naknadno (zadatak ce biti vezan uz cjelobrojno programiranje).

Ana Prlic

[AnaP]

Treca zadaca: http://web.math.hr/~anaprlic/web/DZ3.pdf
Rok za predaju je 26.05. u 11 sati. Sve svoje tvrdnje detaljno obrazlozite.

Ana Prlic

[AnaP]

Četvrta zadaca: http://web.math.hr/~anaprlic/web/DZ4.pdf
Rok za predaju je 07.06. Sve svoje tvrdnje detaljno obrazlozite.

Ana Prlic

[Nikola]

Možemo li kod metode grananja i ograđivanja u 4. zadaći i kolokviju koristiti zadatak iz 3. zadaće? Odnosno odmah zaključiti da se maksimum u grani x_{i}<=k postiže za x_{i}=k, a u grani x_{i}>=k+1 za x_{i}=k+1?

[AnaP]

[Gost]

Možemo li na kolokviju raditi simplex metodu kao što smo radili u uvodu u optimizaciju????

[AnaP]

[AnaP]

Kada u ponedjeljak imate kolokvij? Htjela bih da predaja zadaca bude ili prije ili poslije toga da ne dolazite samo radi zadace na faks. Netko mi je bio rekao kada se odrzava kolokvij, ali sam zaboravila



Ana Prlic

[marijap]

u 15h nam je kolokvij i traje 2h...

[AnaP]

Ok, hvala.

Zadacu mozete predati u 14:45 u mom uredu (soba 103).

[AnaP]

Ovo su ukupni rezultati zadaca i kolokvija.
http://web.math.hr/~anaprlic/web/popis_studenata_0910.html
Stupac vezan uz aktivnost na nastavi cu popuniti tek kad dobijem podatke prof. Neralica o dolascima na predavanja. Ukoliko ima nekih pitanja u vezi bodovanja zadaca, najlakse je da to obavimo u srijedu nakon zavrsnog.

Profesor mi je javio da cete na zavrsnom ispitu imati tri pitanja i da ce vrijeme rjesavanja biti 90 minuta. Rezultati ce biti u srijedu 23. 6. u
12 sati, a tada ce biti i eventualni usmeni (ako netko ne prodje zavrsni).

[Nikola]

Je li završni u srijedu, 16.6. u 9 h kao što piše na rasporedu? I da li svi zajedno (istovremeno) pišemo?