Optimizacija resursa (ETF RII OR 4755)

Opšte informacije

Naziv kursa

Optimizacija resursa

Oznaka (šifra) predmeta

ETF RII OR 4755

Studij

ETF-B

Odsjek

Računarstvo i informatika

Godina

4

Semestar

7

Tip

Izborni

ECTS

5

Ukupno sati nastave

55

Sati predavanja

30

Sati vježbi

20

Sati tutorijala

5

Cilj kursa - Znanje i vještine koje treba postići student

  Osnovni cilj kursa je upoznavanje sa tehnikama za definiranje heurističkih algoritama u svrhu određivanja rješenja praktičnih problema optimizacije resursa unutar prihvatljivog vremena. Modul ilustrira efikasne tehnike rješavanja kompleksnih problema donošenja odluka koji se pojavljuju u optimizaciji resursa, kako u industriji tako i u uslugama, a naročita pažnja se posvećuje algoritamskim aspektima i implementaciji. Studenti će ovladati sposobnošću dizajniranja i primjene efektivnih heurističkih algoritama za rješavanje realnih kompleksnih problema optimizacije resursa.

Program

  1.Heuristički algoritmi za kompleksne probleme optimizacije: Dizajniranje algoritama. Algoritmi bazirani na tehnikama optimizacije. Algoritmi bazirani na Lagranževoj relaksaciji. Procedure lokalnog pretraživanja.
2.Metaheuristički algoritmi: 'Simulated Annealing', Ttabu Search', Genetički algoritmi, hibridni algoritmi.
3.Algoritmi bazirani na modelu minimalne cijene, za rješavanje problema prekrivanja skupa.
4.Algoritmi za rješavanje problema tipa putujućeg trgovca (TSP), pakovanja (Bin Packing), rutiranja (Vehicle Routing) i prekrivanja skupa (Set Covering).
-Analiza performanse opisanih algoritama.
-Modeliranje diskretnih sistema.
5.Aplikacije: Problemi distribuiranja proizvoda iz skladišta korisnicima. Problem transporta hendikepiranih osoba. Problemi alokacije vozila (autobusi, lokomotive) i određivanja smjena osoblja u kompanijama javnog prevoza. Optimalno upravljanje energetskim sistemima (distribucija gasa, vode električne energije). Problemi određivanja vremenskog rasporeda u transportnim kompanijama. Problemi smjena u call centrima.

Literatura

Obavezna1. Bilješke i slajdovi s predavanja (moci ce se preuzeti na web siteu Fakulteta).
2. P. TOTH, Discreet D. VIGO (edited by) ' The Vehicle Routing Problem', SIAM Monographs on Mathematics and Applications 2002.
3. S. HAMMER, P. TOTH ' Knapsack Problems: Algorithms and Computer Implementations', J. Wiley 1990.
4.. R.K. AHUJA, T.L. MAGNANTI, J.B. ORLIN ' Network Flows: Theory, Algorithms and Applications', Prentice Hall 1993.
5. G. GUTIN, To PUNNEN (edited by) ' The Traveling Salesman Problem
and its Variations', Kluwer 2002.
Preporučena1. COLIN R. REEVES Modern Heuristic Techniques for Combinatorial
Problems, McGraw-Hill Inc. 1995
2. DAVID E. GOLDBERG Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley 1989, 20th Printing November 1999
3. JERRY BANKS, JOHN S. CARSON II, BARRY L. NELSON, DAVID M. NICOL Discrete-Event System Simulation, Prentice Hall 2001

Didaktičke metode

  Kroz predavanja studenti ce se upoznati sa teorijom, zadacima i aplikativnim primjerima u okviru tematskih jedinica. Predavanja se sastoje iz teoretskog dijela, prezentacionih opisnih primjera, geneze i rješavanja određehih zadataka. Na taj nači studenti će imati podloge za primjenom izučenog gradiva u inžinjerske aplikacije. Dodatni primjeri i ispitni zadaci razmatraju se i riješavaju tokom laboratorijskih vježbi. Izvođenje laboratorijskih vježbi i izrada zadaća omogućit će studentima kontinualan rad i provjeru znanja

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. U okviru vježbi koristit će se softverski alati: MATLAB, C/C++ i Java