Operaciona istraživanja

OPERACIONA ISTRAŽIVANJA

1. Koji ekonomski problemi mogu biti predmet modeliranja korišćenjem metoda LP
2. Postupak korišćenja modela operacionih istraživanja u procesu poslovnog odlučivanja
3. Objasniti opšti oblik modela matematičkog programiranja
4. Objasniti osnovne pretpostavke modela LP
5. Koje su karakteristike standardnog problema maksimuma
6. Zašto se u model LP uvode dodatne promenljive i koje je njihovo ekonomsko značenje
7. Koje su osnovne karakteristike skupa mogućih rešenja
8. Dokazati da je skup mogućih rešenja konveksan skup
9. Koje rešenje modela LP predstavlja bazično a koje optimalno rešenje
10. Dokazati   da   se   optimalno   rešenje   zadataka   standardnog   problema   maksimuma   nalazi   u   jednoj   od 

ekstremnih tačaka skupa mogućih rešenja

11. Kada se primenjuje grafički metod određivanja rešenja u modelu LP i koji je postupak njegove primene
12.  Simpleks metod-objasniti osnovne karakteristike metoda, uporediti ga sa grafičkim metodom i objasniti 

simpleks kriterijume za promenu vektorske baze

13. Izvesti simpleks kriterijum za promenu vektorske baze kod standardnog problema maksimuma
14. Koje su osnovne karakteristike mešovitog problema maksimuma-objasniti razliku između standardnog i 

mešovitog problema maksimuma

15. Dodatne i veštačke promenljive-objasniti sličnosti i razlike
16. Problem   minimuma-objasniti   osnovne   karakteristike,   postupak   rešavanja   i   mogućnosti   primene   u 

ekonomskim istraživanjima

17. Objasniti značaj i osnovne karakteristike dualnog problema
18. Na koji način se formuliše dualni problem nekog modela LP
19. Kakva međuzavisnost postoji između promenljivih primarnog i dualnog problema
20. Kakav odnos postoji između vrednosti funkcija cilja primarnog i dualnog problema za bilo koje njihovo 

moguće rešenje. Dokazati

21. Kakav je odnos između vrednosti funkcija cilja primarnog i dualnog problema za njihova optimalna 

rešenja. Dokazati

22. Kakav je odnos između optimalnih vrednosti dodatnih promenljivih primarnog i  realnih promenljivih 

dualnog problema i obrnuto. Dokazati i objasniti

23. Ekonomsko tumačenje dualnih promenljivih-dokazati i objasniti
24. Objasniti osnovne karakteristike i značaj primene simpleks tabele
25. Objasniti način formiranja i značenje pojedinih elemenata inicijalne simpleks tabele
26. Objasniti način izračunavanja elemenata simpleks tabele u postupku određivanja optimalnog rešenja 

zadatka LP

27. Navesti i objasniti kriterijum za promenu strukture vektorske baze (ulazak i izlazak promenljivih iz baze)
28. Šta je problem degeneracije zadatka LP i koje su njegove posledice
29. Na osnovu čega se utvrđuje potojanje višestrukog optimalnog rešenja u zadatku LP (grafički i analitički)
30. Analitički i grafički objasniti slučaj zadatka LP u kome ne postoje moguća rešenja
31. Dati analitičku i grafičku  interpretaciju zadatka LP u kome ne postoje konačne vrednosti promenljivih i  

funkcije cilja

32. Dualni simpleks metod
33. Celobrojno programiranje-opšta formulacija zadatka i metodi za rešavanje
34. Gomorijevo ograničenje i potpuno celobrojno programiranje
35. Grafički metod  i dokaz teoreme kod celobrojnog linearnog programiranja
36. Delimično celobrojno programiranje 
37. Teorema kod celobrojnog programiranja
38. Postoptimalna analiza
39. Promena vektora c u postoptimalnoj analizi
40. Promena vektora ograničenja u postupku postoptimalne analize

1

41. Promena matrice A u postupku postoptimalne analize
42. Parametarsko programiranja-formulacija zadatka i geometrijska interpretacija
43. Geometrijska interpretacija i grafičko rešenje zadatka parametarskog programiranja
44. Varijabilnost koeficijenata u funkciji cilja kod parametraskog programiranja
45. Hiperbolično (RLP) programiranje- opšti oblik zadatka
46. Dokazati teoremu o monotonosti funkcije cilja kod hiperboličnog programiranja
47. Dokazati da funkcija cilja RLP dostiže ekstremnu vrednost u ekstremnoj tački skupa mogućih rešenja
48. Grafički metod za rešavanje zadatka kod hiperboličnog programiranja (opšti oblik)
49. Grafički metod-slučaj funkcionala bez slobodnog člana
50. Grafički metod-slučaj funkcionala sa slobodnim članom
51. Martošev metod za rešavanje problema hiperboličnog programiranja
52. Čarns-Kuperov metod za rešavanje problema hiperboličnog programiranja
53. Osnovna teorema hiperboličnog programiranja
54. Za koje potrebe se koristi transportni problem i koji su osnovni elementi modela TP
55. Opšti oblik transpotnog problema
56. Dokazati teoremu o jednakosti ponude i tražnje kod TP
57. Dokazati da matrica koeficijenata sistema ograničenja kod TP ima r=m+n-1
58. Zašto se u modelu transporta bazično rešenje obrazuje od m+n-1 promenljivih
59. Koji metodi se koriste za određivanje početnog bazičnog rešenja kod transportnog problema
60. Koji je razlog pojavljivanja i kako se manifestuje problem degeneracije kod TP? Kako se on prevazilazi
61. Stepping stone metod
62. Metod potencijala
63. Objasniti otvoreni model transporta i postupak njegovog rešavanja
64. Osnovni pojmovi i pretpostavke teorije transportnih mreža
65. Transportni problem na mreži sa neograničenim kapacitetom komunikacija
66. Transportni problem na mreži sa ograničenim kapacitetom komunikacija
67. Teorija igara-osnovne karakteristike i vrste igara
68. Objasniti osnovne karakteristike proste matrične igre. Princip minimaksa, sedlasta tačku i optimalne čiste 

strategije

69. Matrične igre sa mešovitim strategijama
70. Rešavanje mešovitih matričnih igara
71. Rešavanje igre reda 2x2
72. Rešavanje igara (2,n) i (m,2)
73. Redukcija matrice plaćanja
74. Rešavanje igara korišćenjem LP

Osnovna literatura:
1.Rakočević S., Backović M., ”OPERACIONA ISTRAŽIVANJA” Ekonomski fakultet, Podgorica, 2003.

2

pogodno odabranim matematickim i statistickim relacijama. Prema tome, ovakav pristup u procesu 
donosenja poslovnih odluka koristi se u sledecim uslovima:

-

Poslovni problem je kompleksan i postoji veliki broj faktora koji uticu na rezultat realizacije 
donijete odluke;

-

Postoji mogucnost obezbedjenje neophodnih podataka za matematicko i statisticko predstavljanje 
poslovnog problema;

-

Osnovni ciljevi realizacije posmatrane odluke mogu se kvantitativno izraziti;

-

Postoji mogucnost definisanja odgovarajuceg matematickog modela koji predstavlja dobru 
aproksimaciju postavljenog problema.
Osnovni  cilj koriscenja modela kvantitativne analize u procesu donosenja poslovnih odluka 
sadrzan je u zahtjevu da se donosiocu odluka omoguci dobijanje egzaktne informacione osnove za 
izbor optimalnih resenja poslovnih problema.
Postupak koriscenja kvantitativnih modela za potrebe donosenja optimalnih poslovnih odluka 
realizuje se u nekoliko faza:

-

Formulisanje problema 

koja predstavlja početnu i najznačajniju fazu kvantitativne analize, u 

okviru koje se mora precizno definisati suština problema koji treba riješiti. Ovo je i ujedno najteza 
faza ukupne kvantitativne analize, zbog čega se i kaze da dobro formulisan problem mozemo 
smatrati polovonom procesa primjene modela za donošenje optimalnih poslovnih odluka. 
Formulacija problema je proces koji se odvija sve do konacnog dobijanja resenja koja se mogu 
koristiti za poslovno odlucivanje. To znaci da pocetno definisan problem moze biti modifikovan u 
toku realizacije narednih faza.

-

Definisanje modela

 predstavlja fazu u okviru koje stručnjaci moraju definisati takav model koji na 

najboli moguci način aproksimira prethodno formulisani problem. Definisanje modela zahtijeva 
veoma kompleksnu analizu koja mora obuhvatiti sve karakteristike problema i izraziti sve 
medjuzavisnosti koje postoje izmedju sastavnih djelova problema. Odnosi izmedju promjenjljivih u 
modelu mogu biti izrazeni preko jednacina, nejednacina, funkcija ili na neki drugi nacin, sto zavisi 
od karaktera samog modela. Osim toga , veoma vazan aspekt u definisanju modela predstavlja 
vremenska momponente njegove primjene. Naime, neke od karakteristika (ogranicenja, ciljevi, 
okruzenje i s.) problema mogu se u vremenu znacajno mijenjati, model mora biti definisan tako da 
omogucuje permanentno inoviranje osnovnih podataka kao i samog oblika modela.

-

Priprema podataka

 je faza u okviru koje se moraju obezbijediti svi oni podaci koji su neophodni 

za rešavanje definisanog modela. Čak ni idealno definisan model ne znači ništa ukoliko nismo u 
mogućnosti da formiramo informacionu osnovu potrebnu za njegovu primjenu. Zbog toga se faza 
definisanja modela i faza prikupljanja podataka najčešće paralelno odvijaju – medjusobno su 
uslovljene. Osim toga stalne izmjene uslova poslovanja namecu potrebu da prikupljanje podataka 
predstavlja permanentan proces, na osnovu kojeg se obezbedjuje vremenski uspjesno koriscenje 
definisanog modela.

-

Rešavanje modela

 je faza u okviru koje se praktično vrši verifikacija prethodnih faza kvantitativne 

analize, pri čemu se prije svega ocjenjuje validnost modela i njegova upotrebljivost za konkretne 
potrebe. Ukoliko rešavanjem konkretnog modela dobijemo moguća rešenja koja zadovoljavaju 
ograničavajuće uslove i matematički izražen cilj realizacije konkretne odluke, onda takva rešenja 
možemo smatrati optimalnim i koristiti ih kao povoljnu alternativu poslovne odluke. U suprotnom 
slucaju, moramo se vratiti na prethodne faze kvantitativne analize i izvrsiti prilagodjavanje modela.

-

Korišćenje rešenja

 je završna faza  i potpuna verifikacija korisnosti i ispravnosti kvantitativne 

analize, u poslednjoj fazi se dobijena rešenja koriste za potrebe donošenja  optimalnih poslovnih 

4

odluka. U okviru ove faze dobijena rešenja se prihvataju od strane menadžera kao dobra orjentacija 
za poslovno odlučivanje i vrši se njihova transformacija u poslovnu strategiju.

3) Matematičko programiranje predstavlja oblast matematike čiji je predmet razmatranja teoriski i 

numerički potupak odredjivanja ekstremne vrijednosti funkcije više promjenjljivih, u kojima 
postoje ograničenja mogućih vrijednosti promjenjljivih. Matematičko programiranje je veoma 
pogodno za modeliranje različitih ekonomskih aktivnosti koje se realizuju u uslovima ograničenih 
resursa.
Opšti oblik matematičkog programiranja mozemo postaviti u obliku zahtjeva za odredjivanjem 
vrijednosti promjenjljivih 

x1, x2,....xn

, koje zadovoljavaju  

m

  nejednačina i jednačina oblika

                               gi

(x1,x2...xn)

 {≤ , = , ≥ } bi          i=1,....m

        -sistem ograničenja

i za koje se ostvaruje maksimalna ili minimalna vrijednost funkcije 

                              Z= f (x1, x2,...xn)

                                                 -funkcija cilja.

U ovako postavljenom modelu  prepostavljamo da su funkcije

 (gi i f)

 poznate, dok vrijednosti 

(bi)

predstavljaju unaprijed zadata ograničenja. U svakom od ogranicenja pojavljuje se ili jednacina ili 
jedan od dva oblika nejednacina.
Ukoliko su u sistemu ograničenja svi uslovi predstavljeni u vidu jednačina, takav oblik problema 
predstavlja klasičan problem optimizacije.
Ukoliko sistem ograničenja  i odgovarajuću f-ju cilja predstavimo u razvijenom obliku, model 
matematičkog programiranja je:

         (max)Z = f (x1, x2,...xn)
        g1 (x) = g1 (x1, x2,...xn) ≤ b1
        g2 (x) = g2 (x1, x2,...xn) ≤ b2
               ...............................
        gm (x) = gm (x1, x2,...xn) ≤ bm

gdje smo pretpostavili odredjivanje maksimalne vrijednosti f-je cilja 

Z

, u uslovima kada su sva 

ograničenja predstavljena nejednačinama sa znakom 

≤ .

             Sve vrijednosti promjenjljivih  

x = (x1, x2,...xn)

  za koje su zadovoljene sve nejednačine 

sistema ograničenja obrazuju skup mogućih rešenja modela. Cilj resavanja zadatka matematickog 
programiranja jeste odredjivanje one kombinacije vrijednosti promjenjljivih iz skupa mogucih 
resenja za koje f-ja cilja ostvaruje ekstremnu vrijednost. Takvo resenje koje obeljezavamo   

x*=(x1*, x2*, ... xn*), 

predstavlja optimalno resenje zadatka matematickog programiranja.

4)  Osnovne pretpostavke modela linearnog programiranja su:
-

Linearnost

 koja podrazumijeva postojanje linearnih zavisnosti izmedju promjenjljivih u zadatku 

linearnog programiranja. Ova prepostavka zadovoljena je tako što su f-ja cilja i odgovarajući uslovi 
u modelu linearnog programiranja izraženi linearnim funkcijama. Kao posledica linearnosti u 
modelu linearnog programiranja zadovoljene su takodje dvije osnovne prepostavke, 

proporcionalnost i aditivnost. 

Proporcionalnost podrazumijeva posojanje proporcionalnog odnosa 

u modelu linearnog programiranja izmedju inputa i outputa, dok osobona aditivnosti podrazumijeva 
da se ukupna vrijednost f-je cilja moze dobiti kao zbir vrijednosti pojedinih aktivnosti koje 
predstavljaju sastavne elemente modela linearnog programiranja.

-

Izvjesnost

, podrazumijeva da su svi parametri modela LP unaprijed jednoznačno odredjeni, što 

znači da su koeficijenti f-je cilja i sistema ograničenja odredjeni i ne mijenjaju se  u toku rešavanja 
modela. S obzirom na ovu osobinu, model linearnog programiranja smatramo deterministickim 
modelom.

5

7) Sve vrijednosti promjenjljivih za koje su zadovoljene nejednačine (jednačine) sistema ograničenja 

predstavljaju tkz. moguca resenja, odnosno obrazuju 

skup mogucih rešenja

. Osnovne 

karakteristike skupa mogućih rešenja su:
-

da je to ograničen i zatvoren skup, 

-

da može biti i prazan skup u sličaju kada su postavljeni uslovi kontradiktorni, odnosno kada ne 
postoji nijedna tačka  

x = (x1, x2,...xn)

  za koju su zadovoljeni svi uslovi (ogranicenja) zadatka,

-

 Skup mogućih rešenja obrazovan je od tačaka koje zadovoljavaju sve nejednačine (jednacine)  
sistema ograničenja,

-

Veoma bitna karakteristika skupa mogućih rešenja je i da je on konvekstan skup.

8) Skup mogućih rješenja zadatka linearnog programiranja je konveksan skup

Dokaz:

 Da bi dokazali tvrdjenje naše teoreme potrebno je da pokažemo da konveksna kombinacija 

svaka dva moguća rješenja, takođe predstavlja moguće rješenje. Zbog toga, uzmimo da 

  i 

predstavljaju moguća rješenja problema, na osnovu čega je

i        

Posmatrajmo sada tačku   

x

 koja predstavlja konveksnu kombinaciju tačaka  

x'

  i  

x”

odnosno

,

Ukoliko sada tačku  

x

  uvrstimo u sistem jednačina problema, imamo

Na osnovu čega vidimo da tačka  

x

  predstavlja moguće rješenje zadatka linearnog

programiranja, tj. da sve konveksne kombinacije mogućih rješenja takođe predstavljaju
moguća rješenja. Skup mogućih rješenja je 

konveksan skup

, što je trebalo dokazati.

9) Uvodjenjem dodatnih promjenjljivih, sistem od  

m

  jednacina sa  

n(n=p+m)

 nepoznatih, pri cemu 

je  

m < n

 . Iz linearne algebre je poznato  da ukoliko matrica  

A 

 ima rang  

m

  (maksimalan broj 

linearno nezavisnih vektor kolona) mozemo uzeti da su bilo koje  

n - m

 promjenjljive jednake nuli, 

a zatim odredjivati vrijednosti ostalih promjenjljivih. Bilo koje tako odredjeno rešenje problema 
maksimuma, predstavlja 

bazično rešenje

. Ukoliko takvo rešenje zadovoljava i uslov nenegativnosti 

ono predstavlja 

bazično moguće rešenje

, dok bazično moguće rešenje

 x*= (x1*, x2*,...xk*) 

, 

predstavlja optimalno rešenje zadatka standardnog problema maksimuma ukoliko imamo da je  

Z(x*) ≥ Z(x’)

 , za bilo koje moguće rešenje  

x’

 . Drugim riječima, rešenje zadatka kod standardnog 

problema max je optimalno ukoliko je moguće i ukoliko daje maksimalnu vrijednost f-je cilja.

10) Optimalno rješenje zadatka linearnog programiranja nalazi se u ekstremnoj

tački konveksnog skupa mogućih rješenja.

Dokaz: 

Kako je skup mogućih rješenja konveksan, ograničen skup postoji konačan broj
(pretpostavimo k) ekstremnih tačaka koje ćemo oznaciti sa  

x1,x2,...xk 

. Neka

je  

x*

  tačka za koju funkcija cilja ostvaruje maksimum, odnosno za koju imamo da je

z(x*) ≥ z(x)

  za svako moguće rješenje 

 x

.

Ako je  

x* 

 ekstremna tačka konveksnog skupa mogućih rješenja, teorema je dokazana.

             Pretpostavimo suprotno, tj da 

 x*

  nije ekstremna tačka skupa mogućih rješenja. Tada tačku

7