Ispitna pitanja iz predmeta Operaciona istraživanja 1

Prva grupa pitanja: Rešavanje problema LP

  • 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.

Druga grupa pitanja: Matematičko modeliranje

  • 16. Struktura matematičkih modela i njihova veza sa realnim sistemom.
  • 17. MM: Osnovni MM planiranja ishrane.
  • 18. MM: Podela obradive površine na kulture.
  • 19. MM: Optimalan plan setve na dislociranim njivama.
  • 20. MM: Optimizacija proizvodnje krmnih smeša.
  • 21. MM: Izbor optimalnog asortimana.
  • 22. MM: Optimizacija utroška materijala.
  • 23. MM: Upravljanje zalihama.
  • 24. MM: Usklađivanje programa proizvodnje.
  • 25. MM: Optimalno proširenje kapaciteta.

Treća grupa pitanja: Transportni problem

  • 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.
  • 22. MM: Transport proizvodnje. (LP -- gl. 4)
  • 33. MM: Izbor izvršilaca aktivnosti.

Četvrta grupa pitanja: Kombinatorna optimizacija

  • 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.

Ispitna pitanja za studente koji su slušali OI1 po starom programu:

  • 1. Konstrukcija matematičkih modela
  • 2. Matematički model opšteg problema LP
  • 3. Geometrijsko tumačenje problema LP
  • 4. Opšti oblik problema LP i njegova svojstva
  • 5. Standardni oblik problema LP i njegova bazna rešenja
  • 6. Geometrijska interpretacija simpleks metode
  • 7. Kanonski oblik problema LP i određivanje početnog baznog rešenja
  • 8. Kriterijum optimalnosti, kriterijum ulaska i kriterijum izlaska promenljive iz baze
  • 9. Određivanje novog kanonskog oblika i novog dopustivog rešenja
  • 10. Veštačka početna baza za primenu Simpleks metode
  • 11. Dualni model problema LP, pravila za formiranje duala
  • 12. Mogući ishodi simpleks metode
  • 13. Svojstva slabe i jake dualnosti
  • 14. Svojstvo komplementarnosti optimalnih rešenja primala i duala
  • 15. Model zatvorenog i otvorenog transportnog problema i njegove osobine
  • 16. Metode za određivanje polaznog dopustivog rešenja transportnog problema
  • 17. Metoda potencijala i njeno tumačenje preko teorije dualnosti
  • 18. Transportni zadatak sa ograničenim propusnim sposobnostima
  • 19. Problem minimizacije vremena transporta
  • 20. Izbor izvršilaca aktivnosti projekta
  • 21. Optimizacija železničkog transporta
  • 22. Model LP za optimizaciju transporta proizvodnje
  • 23. Model izbora lokacije (dvofazni transport)
  • 24. Primena LP u ishrani – osnovni model
  • 25. Model LP za podelu obradive površine na kulture
  • 26. Model LP za optimizaciju plana setve na dislociranim njivama
  • 27. Model LP za optimizaciju proizvodnje krmnih smeša
  • 28. Model LP za optimizaciju sastava kupolne peći
  • 29. Model LP za izbor optimalnog asortimana za slučaj ograničenja više kategorija resursa
  • 30. Model LP optimizaciju utroška materijala
  • 31. Primena LP u uskladjivanju programa proizvodnje
  • 32. Primena LP u upravljanju zalihama
  • 33. Opšta postavka i klasifikacija zadataka NLP (lokalni i globalni ekstremum)
  • 34. Bezuslovna optimizacija. Određivanje stacionarnih tačaka i ispitivanje njihove prirode
  • 35. Klasični problem uslovnog ekstremuma. Metoda eliminacije promenljivih
  • 36. Klasični problem uslovnog ekstremuma. Određivanje stacionarnih tačaka Lagranžove funkcije i ispitivanje njihove prirode
  • 37. Opšti slučaj NLP. Metode izravnavajućih funkcija
  • 38. Konveksnost skupa i funkcija. Ispitivanje konveksnosti funkcije. Problem konveksnog programiranja
  • 39. Kun-Takerova teorema
  • 40. Metoda kaznenih funkcija. Spoljašnje i unutrašnje kaznene funkcije
  • 41. Približne metode za rešavanje problema bezuslovne optimizacije
  • 42. Celobrojno programiranje. Neki karakteristični zadaci celobrojnog programiranja