Ispitna pitanja – Laboratorija za operaciona istraživanja “Jovan Petrić”

1. Konveksnost skupa, definicije duži, konveksne kombinacije i ekstremne tačke.
2. Globalni i lokalni optimum, konveksnost funkcije i optimum konveksne funkcije.
3. Osnovna svojstva opšteg zadatka LP.
4. Opšti oblik zadatka LP i svođenje na standardni oblik.
5. Bazna rešenja (dopustiva, susedna, degenerisana).
6. Geometrijska interpretacija simpleks metode. Veza sa algoritmom lokalnog pretraživanja.
7. Svođenje na kanonski oblik opšteg problema LP i određivanje početnog baznog dopustivog rešenja (metoda velikog M).
8. Uloga kanonskog oblika LP u postupku nalaženja optimalnog rešenja simpleks metodom.
9. Određivanje novog kanonskog oblika tj. nalaženje boljeg susednog baznog dopustivog rešenja.
10. Mogući ishodi simpleks metode: jedinstveno optimalno rešenje i prazna dopustiva oblast (grafička i algebarska interpretacija).
11. Mogući ishodi simpleks metode: višestruko optimalno rešenje i neograničena funkcija cilja (grafička i algebarska interpretacija).
12. Konačnost i računska složenost (definicija) simpleks metode.
13. Mogući načini formiranja dualnog zadatka LP (preko simetričnog i preko opšteg oblika).
14. Osnovna svojstva dualnosti problema LP: svojstvo simetrije primala i duala, slaba dualnost i ograničenost — dopustivost.
15. Osnovna svojstva dualnosti problema LP: jaka dualnost i komplementarnost optimalnih rešenja.
16. Ekonomska interpretacija dualnog problema.

27. Zatvoreni i otvoreni problem TP: opis problema i matematički modeli.
28. Osnovni koraci algoritma za rešavanje problema TP i njegove osobine.
29. Metode za određivanje početnog baznog dopustivog rešenja problema TP, njihove osobine i osnovne ideje (ne koraci rešavanja).
30. Dualni zadatak TP, utvrđivanje optimalnosti rešenja.
31. MM: Transportni zadaci sa ograničenim propusnim sposobnostima.
32. MM: Minimizacija vremena transporta.
33. MM: Transport proizvodnje. (LP -- gl. 4)
34. MM: Izbor izvršilaca aktivnosti.

35. Definicije grafa i mreže i vrste grafova ((ne)usmeren, (ne)povezan).
36. Definicije stepena čvora i preseka grafa.
37. Definicije osnovnih grafovskih struktura: put, elementarni put i dužina puta.
38. Definicije osnovnih grafovskih struktura: stablo, razapinjuće stablo i dužina stabla.
39. Definicije osnovnih grafovskih struktura: kontura, Hamiltonova kontura i dužina konture.
40. Problem određivanja najkraćeg puta između dva zadata čvora u mreži: model i složenost rešavanja.
41. Problem određivanja minimalnog razapinjućeg stabla: model i složenost rešavanja.
42. Problem trgovačkog putnika i pristupi njegovom rešavanju -- grafovska interpretacija.
43. Problem trgovačkog putnika i pristupi njegovom rešavanju -- matematički model.
44. Problem rutiranja vozila i pristupi njegovom rešavanju -- grafovska interpretacija.
45. Problem rutiranja vozila i pristupi njegovom rešavanju -- matematički model.
46. Karakteristični problemi celobrojnog programiranja (generalno). Problem ranca.
47. Metoda grananja i ograničavanja.

1. Konveksnost skupa i funkcija i definicija globalnog i lokalnog optimuma.
2. Opšti oblik zadatka LP i njegova osnovna svojstva.
3. Standardni oblik LP i njegova bazna rešenja (dopustiva, susedna, degenerisana).
4. Osnovni koraci simpleks metode i njene osnovne osobine.
5. Kanonski oblik problema LP i njegova primena u rešavanju problema LP.
6. Test optimalnosti dopustivog baznog rešenja na osnovu odgovarajućeg kanonskog oblika problema LP.
7. Određivanje novog kanonskog oblika tj. nalaženje boljeg susednog baznog dopustivog rešenja.
8. Postupak dobijanja početnog kanonskog oblika problema LP i određivanje odgovarajućeg baznog rešenja.
9. Mogući ishodi simpleks metode: jedinstveno optimalno rešenje i neograničena funkcija cilja (grafička i algebarska interpretacija).
10. Mogući ishodi simpleks metode: višestruko optimalno rešenje i prazna dopustiva oblast (grafička i algebarska interpretacija).
11. Konačnost i računska složenost (definicija) simpleks metode.
12. Mogući načini formiranja dualnog zadatka LP (preko simetričnog i preko opšteg oblika). Svojstvo simetrije primara i duala.
13. Osnovna svojstva dualnosti problema LP: slaba dualnost i komplementarnost optimalnih rešenja.
14. Osnovna svojstva dualnosti problema LP: jaka dualnost i ograničenost — dopustivost.
15. Interpretacija dualnog problema u slučaju optimizacije raspodele ograničenih resursa.

26. Zatvoreni i otvoreni problem TP: opis problema i matematički modeli.
27. Osnovni koraci algoritma za rešavanje problema TP i njegove osobine.
28. Metode za određivanje početnog baznog dopustivog rešenja problema TP, njihove osobine i osnovne ideje (ne koraci rešavanja).
29. Dualni zadatak TP, utvrđivanje optimalnosti rešenja.
30. MM: Transportni zadaci sa ograničenim propusnim sposobnostima.
31. MM: Minimizacija vremena transporta.
32. MM: Transport proizvodnje. (LP -- gl. 4)
33. MM: Izbor izvršilaca aktivnosti.

34. Definicije grafa i mreže i vrste grafova ((ne)usmeren, (ne)povezan).
35. Definicije stepena čvora i preseka grafa.
36. Definicije osnovnih grafovskih struktura: put, elementarni put i dužina puta.
37. Definicije osnovnih grafovskih struktura: stablo, razapinjuće stablo i dužina stabla.
38. Definicije osnovnih grafovskih struktura: kontura, Hamiltonova kontura i dužina konture.
39. Problem određivanja najkraćeg puta između dva zadata čvora u mreži: model i složenost rešavanja.
40. Problem određivanja minimalnog razapinjućeg stabla: model i složenost rešavanja.
41. Problem trgovačkog putnika i pristupi njegovom rešavanju -- grafovska interpretacija.
42. Problem trgovačkog putnika i pristupi njegovom rešavanju -- matematički model.
43. Problem rutiranja vozila i pristupi njegovom rešavanju -- grafovska interpretacija.
44. Problem rutiranja vozila i pristupi njegovom rešavanju -- matematički model.
45. Karakteristični problemi celobrojnog programiranja (generalno). Problem ranca.
46. Metoda grananja i ograničavanja.