Operaciona istraživanja    (ETF RIO OI 4870)
 
Opće informacije
Naziv kursa Operaciona istraživanja
Oznaka (šifra) predmeta ETF RIO OI 4870
Studij ETF-B
Odsjek Računarstvo i informatika
Godina 4
Semestar 8
Tip Obavezni
Broj ECTS Bodova 7
Ukupno sati nastave 70
Broj sati predavanja 40
Broj sati vježbi 25
Broj sati tutorijala 5
Cilj kursa - Znanje i vještine koje treba postići student
Kurs integrira znanja stečena u kursu "Osnovi operacionih istraživanja , uvodne teorije i algoritamske metodologije unaprijeđene za rješavanje problema koji su prisutni u socijalnom i industrijskom ambijentu, a cilj je da se na optimalan način upravlja i koordinira aktivnostima pri čemu su raspoloživi resursi ograničeni. Studenti će steći sposobnosti (znanja) da mogu prezentirati realne slučajeve (situacije) u kojima su prisutni problemi optimizacije pomoću modela linarnog programiranja, teorije grafova i numeričke simulacije.Takođe će biti osposobljeni za rješavanje problema, pomoću odgovarajućeg algoritma za optimizaciju ili korištenjem programa za simulaciju.
Program
1. Simulacija diskretnih sistema
1.1. obnavljanje statistike: aleatorne varijable
1.2. proizvodnja pseudo-uzročnih vrijednosti, metoda inverzne transformacije;
1.3. statički i dinamički opis sistema
1.4. metod programiranja događaja
1.5. dijagrami fluksa za simulacione probleme
2. Linearno programiranje
2.1. Osnovne osobine konveksnog programiranja
2.2. obnavljanje zadatka linearnog programiranja i simpleks algoritma
2.3. teorija dualnosti: dualni problem, uslovi ortogonalnosti
2.4. algoritam dualnog simpleksa
2.5. algoritam primal-dual
3.Cjelobrojno linearno programiranje
3.1. jednomodularnost (jednoekstremalnost)
3.2. dualnost u linearnom programiranju
3.3. metoda presjeka ravni Gomorija
3.4. metod branch and bound
3.5. linearno programiranje mješano i binarno
3.6. problem ranca 0-1
3.7. problem branch-and-cut
4. Problemi na grafovima
4.1. obnavljanje teorije grafova
4.2. relacije između minimalnog puta, protokai linearnog programiranja
4.3. unimodularnost incidentne matrice
4.4. hamiltonijani (kola): "prebrojivi" algoritam
5. Teorija kompleksnosti
5.1. klase P i NP; problemi NP kompleksni
5.2. kompleksnost osnovnih problema kombinatorne optimizacije
5.3. dinamičko programiranje
5.4. problemi jake NP-kompleksnosti
6. Branch_and_bound algoritmi (grane i granice)
6.1. šema grananja (branching)
6.2. popuštanja: neprekidnost, lagranžijan, surogat;
6.3. primjena na višestruki problem ranca
6.4. procedura redukcije
6.5. aproksimativni algoritmi: eksperimenalna analiza, vjerovatnost, najgori slučaj
6.6. algoritmi egzaktnog i heurističkog tipa
6.7. metaheuristički algoritmi
Literatura
Obavezna literatura 1. Bilješke i slajdovi s predavanja (moci ce se preuzeti na web siteu Fakulteta).
2. S. Martello, 'Ricerca Operativa LS', Esculapio (progetto Leonardo), Bologna, 2004.
3. S. Martello, D. Vigo, 'Esercizi di Simulazione Numerica', Esculapio (progetto Leonardo), Bologna, 2001.
4. S. Martello, D. Vigo, 'Esercizi di Ricerca Operativa',
Esculapio (progetto Leonardo), Bologna, 2003.
5. C. Papadimitriou, K. Steiglitz, 'Combinatorial Optimization', Prentice Hall, 1982.
6. S. Martello, P. Toth, 'Knapsack Problems: Algorithms and Computer Implementations',Wiley, 1990.
Dopunska literatura
Didaktičke metode
Kurs je struktuiran u lekcije, auditorne i laboratorijske vježbe.
Za vrijeme lekcija se vode diskusije o teoretskim problemima i algoritamskim aspektima iznešenih dokaza.
Za vrijeme vježbi razmatraju se predloženi industrijski slučajevi u kojima su prisutni problemi optimizacije i izvode odgovarajući matematički modeli za numeričku simulaciju.
Za matematičke modele nalaze se rješenja pomoću algoritama datih u lekciji.
Laboratorijskih vježbe (slobodne i fakultativne) se obavljaju uz prisustvo asistenata i demonstratora koji će studente detaljnije upoznati sa primjenom potrebnih softverskih paketa.
Način provjere znanja
Tokom trajanja kursa student prikuplja bodove prema slijedećem sistemu:
- prisustvo satima predavanja, vježbi i tutorijala: 10 bodova, student koji više od tri puta izostane s predavanja,vježbi i/ili tutorijala ne može ostvariti bodove po ovoj osnovi;
- izrada domaćih zadaća: maksimalno 10 bodova; predviđena je izrada od 5 do 10 domaćih zadaća ravnomjerno raspoređenih tokom semestra;
- parcijalni ispiti: dva pismena parcijalna ispita, pri čemu svaki pozitivno ocijenjen parcijalni ispit donosi 20 bodova;
Student koji je tokom trajanja semestra ostvario manje od 20 bodova ponovno upisuje ovaj kurs.
Student koji je tokom trajanja semestra ostvario 40 i više bodova pristupa usmenom završnom ispitu; ovaj ispit sastoji se iz diskusije zadataka s parcijalnih ispita, domaćih zadaća i odgovora na jednostavna pitanja koja se odnose na teme kursa.
Usmeni završni ispit donosi maksimalno 40 bodova. Da bi postigao pozitivnu završnu ocjenu, student na ovom ispitu mora ostvariti minimalno 20 bodova. Student koji ne ostvari ovaj minimum pristupa usmenom dijelu popravnog ispita.
Student koji je tokom trajanja semestra ostvario 20 i više bodova, a manje od 40 bodova, pristupa popravnom ispitu. Popravni ispit struktuiran je na slijedeći način:
- pismeni dio koji je struktuiran na isti način kao i pismeni parcijalni ispit; u okviru ovog ispita student polaže zadatke iz tema za koje nije postigao prolaznu ocjenu (10 i više bodova) polažući parcijalne pismene ispite,
- usmeni dio koji je struktuiran na isti način kao usmeni dio završnog ispita.
Usmenom dijelu popravnog ispita može pristupiti student koji je nakon polaganja posmenog dijela popravnog ispita uspio stvariti ukupan skor od 40 i više bodova; ovaj skor sastoji se od bodova ostvarenih kroz: prisustvo nastavi, izradu domaćih zadaća, polaganje parcijalnih sipita i polaganje pismenog dijela popravnog ispita.
Usmeni popravni ispit donosi maksimalno 40 bodova. Da bi postigao pozitivnu završnu ocjenu student na ovom ispitu mora ostvariti minimalno 20 bodova. Student koji ne ostvari ovaj minimum ponovno upisuje ovaj kurs.
Napomene
1. Za laboratorijske i domaće zadatke moguće je koristiti koristiti softverske pakete za linearno programiranje i potpuno linearno programiranje, kao i jezik za numeričku simulaciju (npr., SIMSCRIPT II.5).