Okvirna 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. Veštačka početna baza.
  • 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.