|
Šifra modula |
AMAT 320 |
Fakultet |
PMF Sarajevo |
Operaciona istraživanja
NASTAVNI PROGRAM
A. OPŠTI PODACI
|
Fakultet |
Prirodno-matematički fakultet Univerziteta u
Sarajevu |
|
Odsjek |
Odsjek za matematiku |
|
Smjer |
Primijenjena matematika; Teorijska kompjuterska
nauka |
|
Semestar |
Peti |
|
Naziv modula |
Operaciona istraživanja |
|
Tip modula |
Obavezni |
|
Broj kreditnih bodova |
7 |
|
Kontakt sati |
Ukupno |
Predavanja |
Vježbe |
Seminari |
Konsultacije |
|
105 |
45 |
AV30, LV15 |
0 |
15 |
|
Samostalni rad (sati) |
70 |
|
Obavezni prethodno položeni moduli |
Uvod u linearnu algebru; Linearna algebra |
|
Modul relevantan za module |
Napredne tehnike optimizacije |
|
Nastavno osoblje |
|
|
– Nastavnik nosilac modula |
Doc. dr. Haris Gavranović |
|
– Ostali nastavnici |
– |
|
– Asistenti |
Damir Hasić; Almasa Odžak |
B. CILJEVI MODULA
|
Ciljevi modula su
upoznavanje sa osnovnim elementima linearnog programiranje i
primjenama. Studenti će proći sve faze rješavanja jednog konkretnog
problema od modeliranja, rješavanja do komentarisanja probleme.
Izučavaće se kako algebarski tako i geometrijski pristup i značenja
rješenja linearnih programa. Metode implementacije ovih algoritama
sa posebnim naglaskom na efikasnost će biti izložene i
eksperimentalno provjerene. Najvažnije primjene izložene teorije će
biti posebno izučavani. |
C. SPECIFIČNI ZADACI MODULA
|
Kroz navedeni modul studenti
će kroz samostalan rad ili uz pratnju nastavnika rješavati zahtjevne
složene probleme iz stvarnog života koristeći jedan od savremenih
solvera. Posebna pažnja će se obratiti na mjesto matematičara u
analiziranja jednog stvarnog problema i njegovih rješenja.
|
D. OČEKIVANI REZULTATI NASTAVNOG
PROCESA
|
Nakon završetka modula,
studenti će biti u stanju da:
- Razumiju postupak i važnost dobrog
modeliranja
- Razumiju osnove rješavanja
linearnih programa
- Razumiju algebarske i geometrijske
osnove ovih rješenja
- Razumiju i primjenjuju stečena
znanja i na nestandardni, problemima
- Razumiju upotrebu računara kao
sredstva za rješavanje problema optimiziranja
|
E. SADRŽAJ NASTAVNOG PROCESA
|
Br. |
Nastavna jedinica |
Nastavni metod |
Sati rada |
|
Kontakt |
Samostalno |
|
1. |
Matematičko modeliranje i modeliranje linearnih
sistema |
Usmeno izlaganje 3
Vježbe i zadaci 2
Rad na računaru 1 |
7 |
4 |
|
2. |
Osnove simpleks metoda, na koji način početi i
kako završiti simplex, tri moguća tipa rješenja linearnog programa |
– II – |
7 |
5 |
|
3. |
Degenerisana rješenja i cikliranje, Blandovo
pravilo izbora pivota i leksikografsko pravilo |
– II – |
7 |
4 |
|
4. |
Teorija kompleksnosti i simpleks, efikasnost
simpleks metoda |
– II – |
7 |
4 |
|
5. |
Motivacija za dualnost, slabi dualni par
problema, jaki dualni par problema, dualni teorem, teorem o
komplementarnosti viškova, revidirani simplex metod |
– II – |
7 |
5 |
|
6. |
Implementiranje simpleks metoda, LU
faktorizacija, efikasnost, matrična notacija za simpleks metod |
– II – |
7 |
5 |
|
7. |
Generalizovani LP problemi, postoptimalna
analiza linearnih programa, |
– II – |
7 |
5 |
|
8. |
Parametarski linearni problemi |
– II – |
7 |
5 |
|
9 |
Matrične igre |
– II – |
7 |
5 |
|
10. |
Geometrija LP problema, osnove teorije
poliedara i konveksnog optimiziranja, |
– II – |
7 |
4 |
|
11. |
Caratheodory teorem, Farkasova lema, geometrija
dualnosti |
– II – |
7 |
5 |
|
12. |
Problemi protoka u mreži, network simplex metod
(algoritam) |
– II – |
7 |
5 |
|
13. |
Hitchockov problem i problem pridruživanja |
– II – |
7 |
4 |
|
14. |
Najkraći put u mreži i ostali problemi na
mrežama |
– II – |
7 |
5 |
|
15. |
Primal-dual metod |
– II – |
7 |
5 |
F. PROVJERA ZNANJA I OCJENJIVANJE
|
Provjera znanja - kriteriji |
Ocjenjivanje |
|
Kriterij |
Maksimalan broj bodova |
Bodovi za prolaz |
Osvojen broj bodova |
Ocjena (BiH) |
ECTS ocjena |
|
Domaće zadaće |
20 |
10 |
< 55,00 |
5 |
F |
|
Testovi tokom kursa |
40 |
25 |
55,00 – 64,99 |
6 |
E |
|
Laboratorijske vježbe |
10 |
5 |
65,00 – 74,99 |
7 |
D |
|
Pismeni završni ispit |
30 |
15 |
75,00 – 84,99 |
8 |
C |
|
|
|
|
85,00 – 94,99 |
9 |
B |
|
|
|
|
95,00 – 100,00 |
10 |
A |
|
U k u p n o |
100 |
55 |
|
G. LITERATURA
Osnovna literatura:
1. Robert J. Vanderbei : Linear Programming: Foundations
and Extensions (knjiga je dostupna na internetu za free-download u pdf
formatu. Obrađuje većinu gradiva prvog semestra (i mnogo više).
http://www.princeton.edu/~rdvb/Lpbook/
2. A. Scrijever Theory of Linear and Integer Programming
(state of art ali i zahtjevna knjiga sa mnogo teorije)
3. Christos Papadimitriou, Keneth Steigliz :
Combinatorial optimization: Algorithms and Complexity, (jedan dio knjige
obrađuje linearno programiranje i uspostavlja prirodnu vezu sa problemima
diskretne matematike)
Dopunska literatura:
1. Manuals za Xpress (dio materijala će biti podijeljen
na predavanjima a ostali dio može se naći na
www.dashoptimization.co.uk)
2. Wolsey Laurance : Integer programming
3. Nemhauser George, Wolsey Laurance : Integer and
combinatorial optimization