Linearno programiranje-dualni problem

UNIVERZITET U PRIŠTINI

EKONOMSKI FAKULTET

SEMINARSKI RAD

Predmet: Operaciona istraživanja

Tema: Linearno programiranje: Dualni problem

MENTOR: STUDENT:

Mr Radica Bojičić Krstić Jelena 27/12

Kosovska Mitrovica, 2014.

SADRŽAJ

UVOD……………………………………………………………………………………. 2

1. Linearno programiranje………………………………………………………….…….. 3

2. Dualnost u linearnom programiranju……………………………………………….…. 5

2.1. Principi dualnosti...................................................................................................... 6

2.2. Osobine dualnih modela........................................................................................... 7

2.3. Ekonomska interpretacija duala …………………………………………….…….13

ZAKLJUČAK……………………………………………………………………….……15

LITERATURA……………………………………………………………………………16

1. LINEARNO PROGRAMIRANJE

      U savremenim uslovima rukovođenje u privredi, armiji i društvu u celini zahteva rešavanje
složenih   zadataka   koji   imaju   više   alternativnih   rešenja.   Uloga   stručnjaka   u   tim   slučajevima
sastoji se u tome da, polazeći od određenih društvenih i ekonomskih zakona i kriterijuma, ili od
usvojene strategije, odrede ona rešenja koja su za date uslove optimalna. Veliki broj privrednih
aktivnosti se ostvaruje u uslovima ograničenog iznosa resursa, koji se na različite načine mogu
koristiti   za   ostvarivanje   unapred   postavljenog   cilja.   Iz   niza   mogućih   načina   (programa)
korišćenja raspoloživih resursa ekonomski subjekti su veoma zainteresovani da odaberu onaj
najpovoljniji, onaj za koji će se ostvariti najveća moguća efikasnost ukupnih aktivnosti. S toga
optimizacija   ekonomskih   aktivnosti   zauzima   centralno   mesto   u   okviru   ekonomske   analize   i
matematičkog modeliranja ekonomskih problema. Jedan od matematičkih metoda optimizacije
koji je tokom ovog veka doživeo punu afirmaciju, teorijsku razradu i široku primenu je model
linearnog programiranja.

           Problem linearnog programiranja konceptualno je postavio pre II svetskog rata sovjetski
matematičar   Kantorovič,   u   svom   radu   „Matematički   metodi   organizacije   i   planiranja
proizvodnje“   1939.   godine.   Prvu   značajnu   primenu   linearnog   programiranja   u   rešavanju
problema   dijetalne   ishrane   predstavio   je   Stigler   1945.   godine.   Međutim,   glavni   doprinos
teorijskom   razvoju   i   širenju   mogućnosti   primene   linearnog   programiranja   dao   je   George
Dantzing, koji je 1947. godine razvio opšti algoritam rešavanja modela linearnog programiranja,
koji je poznat kao simpleks metod. On je pokazao da se čitav niz problema koji se odnose na
optimizaciju   ljudskih   aktivnosti   u   uslovima   ograničenog   iznosa   resursa   mogu   predstaviti
odgovarajućim jednačinama ili nejednačinama. Poznati naučnici Kupmans, Belman, Ford, Čarns
i  drugi   dali   su,   takođe,   veliki  doprinos  razvoju   linearnog   programiranja   i  njegovoj  primeni.
Linearno programiranje predstavlja model koji se veoma uspešno koristi za rešavanje velikog
broja praktičnih problema na nivou preduzeća, a najčešći među njima su: proizvodno planiranje,
planiranje investicija, planiranje transporta robe i optimalno raspoređivanje kadrova. Ovaj model
se koristi  za  optimizaciju  poslovnih  aktivnosti  na nivou  preduzeća  kao  i  ljudskih  aktivnosti
uopšte. Glavni problem koji se korišćenjem modela linearnog programiranja rešava je zahtev za
određivanjem optimalnog programa korišćenja ograničenog iznosa resursa, s toga ovaj model
predstavlja specijalan oblik modela matematičkog programiranja kao osnovnog oblika zadatka
optimizacije.  Ako se sa stanovišta matematičkog modela osvrnemo na linearno programiranje,
problem se sastoji u tome kako naći minimum ili maksimum jedne linearne funkcije F(X), pri
određenom skupu ograničenja bi zadanih linearnim vezama. Broj nepoznatih i ograničenja može
da bude veoma različit.

Linearno programiranje predstavlja metodu određivanja takve kombinacije uzajamno
povezanih faktora, koje od niza mogućih kombinacija predstavlja najpovoljniju. Drugim rečima,

traži se takva kombinacija koja će, pored toga što će zadovoljiti data ograničenja bi, zadovoljiti i
kriterijum optimalnosti.

Model linearnog programiranja, bez obzira u kom obliku problema se radi (problemu
maksimuma ili problemu minimuma), karakterišu neke zajedničke osobine, odnosno, postoji
određeni broj pretpostavki koje moraju biti zadovoljene da bi određeni model predstavljao model
linearnog programiranja. Osnovne pretpostavke ovog modela su:

1. Linearnost;
2. Izvesnost;
3. Deljivost;
4. Nenegativnost.

Postoje više metoda za rešavanje problema linearnog programiranja, a to su:



Efikasni postupci nalaženja optimalnog rešenja

1) Grafički metod
2) Metod eliminacije



Simpleks metod

1) Bazična rešenja sistema linearnih jednačina
2) Simpleks alogaritam
3) Mešoviti problem maksimuma
4) Problem minimuma



Dualna teorija



Postoptimalna analiza