Univerzitet u Prištini
Ekonomski fakultet
Kosovska Mitrovica
SEMINARSKI RAD
Predmet:
OPERACIONA ISTRAŽIVANJA
Tema:
LINEARNO PROGRAMIRANJE –
DUALNI PROBLEM
Mentor:
Student:
Doc. dr Radica Boji
č
i
ć
Nataša Simi
ć
2/19281
Kosovska Mitrovica, 2017.
Ekonomski Fakultet u Prištini
1
SADRŽAJ:
UVOD ........................................................................................................................................................... 2
1. LINEARNO
PROGRAMIRANJE
........................................................................................................ 3
1.1
OPŠTA SVOJSTVA PROBLEMA LINEARNOG PROGRAMIRANJA ................................... 4
2. DUALNI PROBLEM LINEARNOG PROGRAMIRANJA ................................................................ 6
2.1. TEORIJA
DUALNOSTI............................................................................................................... 7
2.2. TEORIJA
OPTIMALNOSTI
...................................................................................................... 11
2.3. EKONOMSKA
MOTIVACIJA
..................................................................................................
17
LITERATURA ........................................................................................................................................... 21
Ekonomski Fakultet u Prištini
3
1.
LINEARNO PROGRAMIRANJE
Jedan od matemati
č
kih metoda optimizacije, koji je doživeo punu afirmaciju i široku primenu, je
model
Linearnog programiranja
. Linearno programiranje predstavlja, sasvim sigurno, jednu od
najvažnijih grana matemati
č
kog modeliranja koja se primenjuje u razli
č
itim oblastima nauke i
zauzima zna
č
ajno mesto u primeni kontrole upravljanja razli
č
itih procesa i sistema, naro
č
ito
tamo gde je potrebno izvršiti optimizacije odre
đ
enih parametara, unutar zadatih ograni
č
enja,
postaviti nove kriterijume odli
č
uvanja u izboru investicija, tržišta ili proizvodnje. Mnoge odluke
operacionog menadžmenta podrazumevaju pokušaj optimalnog koriš
ć
enja resursa-mašina, radne
snage, novca, vremena, koji se koriste, da bi se proizveo neki proizvod (npr.mašine, ode
ć
a,
hrana), ili u servisu (projekti).
Linearno programiranje služi za modeliranje problema kod kojih je potrebno prona
ć
i optimalno
rešenje, tj. ono rešenje za koje se postiže najbolja vrednost nekog cilja me
đ
u svim mogu
ć
im
alternativnim rešenjima problema, pri
č
emu svako rešenje mora da zadovoljava zadate uslove
(ograni
č
enja).
Termin “programiranje“ je ovde sinonim za planiranje, odnosno odre
đ
ivanje
optimalnog (najboljeg) plana. To zna
č
i odre
đ
ivanje vrednosti promenljivih, takvih da daju
optimalnu vrednost funkcije cilja, pri tom zadovoljavaju
ć
i uslove (ograni
č
enja), iskazanim kroz
linearne funkcije, linearne jedna
č
ine ili nejedna
č
ine i dodatnim skupom prirodnih ograni
č
enja da
vrednosti promenljivih ne mogu biti negativne.
Stvarni po
č
etak istraživanja na
č
ina rešavanja, pa samim tim metoda i primena linearnog
programiranja, vezana je za ime ruskog matemati
č
ara ekonomiste L.V. Kantorovi
č
a i njegov
rad
“Matemati
č
ke metode u organizaciji i planiranju proizvodnje“
1
,
objavljenim neposredno
pred Drugi svetski rat, 1939.godine. Me
đ
utim, glavni doprinos u razvoju ovog matemati
č
kog
modela, i širenju mogu
ć
nosti primene linearnog programiranja, dao je Georg Dantzing, kada je
1947. tokom svog istraživa
č
kog rada u Pentagonu, u svom delu
“Maksimiziranje linearne forme
podvrgnute ograni
č
enjima u vidu sistema linearnih jedna
č
ina/nejedna
č
ina
“
2
razvio opšti
algoritam rešavanja modela linearnog programiranja, bez obzira na broj parametara koji
u
č
estvuju, a koji je poznat pod imenom
Simpleks metod
.
Nastao za potrebe ameri
č
ke armije, Simpleks metod, daje osnovu za uvo
đ
enje linearnog
programiranja kao matemati
č
kog model, kojim se mogu rešavati veoma složeni problemi.
1
L.V. Kantorovich ,
"Mathematical Methods of Organizing and Planning Production" Management Science
, Vol. 6,
No. 4 (Jul., 1960). Kantorovich je ro
đ
en 19. januara 1912. u ruskoj jevrejskoj porodici. Radio je za sovjetsku vladu
na zadatku optimizacije proizvodnje, i 1939. je došao sa matemati
č
kom tehnikom koja je sada poznata kao linearno
programiranje. Za svoj rad, Kantorovichu je 1949. godine je dodeljena Staljinova nagrada.
2
George Bernard Dantzig,
“Linear Programming and Extensions“, (1963) , Princeton University Press.
Ameri
č
ki
matemati
č
ki nau
č
nik koji je zna
č
ajno doprineo u oblastima operacionih istraživanja, ra
č
unarstvu, ekonomiji i i
statistici. George Dantzig je radio na planiranju metoda za Vazduhoplovne snage ameri
č
ke vojske tokom Drugog
svetskog rata, i razvio opšti algoritam linearnog programiranja, tzv. Simpleks metod.
Ekonomski Fakultet u Prištini
4
Uporedo su razvijani i odgovaraju
ć
i komercijalni paketi koji implementiraju ovaj metod
(Nojman, Kun i dr.), koji se pokazuju vrlo delotvornim u modeliranju, analizi i rešavanju
č
itavog
niza problema i u “nematemati
č
kim“ disciplinama: ekonomiji, transportu, saobra
ć
aju i sli
č
no.
Takva orijentacija ima za cilj upotpunjavanje dosadašnjih metodoloških istraživanja i otvaranje
novih mogu
ć
nosti za rešavanje najsloženijih ekonomskih problema.
1.1
OPŠTA SVOJSTVA PROBLEMA LINEARNOG PROGRAMIRANJA
Pri rešavanju raznih konkretnih zadataka, kao što su organizacija proizvodnje, transporta,
upravljanje zalihama, organizacija trgovine, planiranje vojnih operacija i sl. name
ć
e se potreba
da se takvi zadaci prethodno matemati
č
ki modeliraju, te da se nakon toga traži njihovo rešenje.
Mnogi ekonomski problemi, mogu se matemati
č
ki izraziti kao problem iznalaženja minimuma
(ili maksimuma) linearne funkcije:
, ,
,
, ,
,
na skupu rešenja nekog sistema linearnih nejedna
č
ina i jedna
č
ina
1,2,
,
1,2,
,
Ovakav problem se naziva
problem lineranog programiranja.
U ovom slu
č
aju, operiše se s velikim brojem parametara/veli
č
ina, na koja se name
ć
e veliki broj
ograni
č
enja. Taj skup vrednosti, koji zadovoljava unapred postavljen sistem ograni
č
enja, naziva
se
skup planova
ili
dopustivi skup rešenja.
Dopustivi skup rešenja, može imati beskona
č
no
mnogo elemenata, pa se i name
ć
e pitanje, koje je rešenje optimalno u datoj situaciji?
U samom matemati
č
kom modelu, postoji odre
đ
ena funkcija, koja se naziva
funkcija kriterijuma
ili
funkcija cilja.
Neka je, npr.organizacija proizvodnje
zadatak koji treba rešiti, pri
č
emu je
jedan od prirodnih kriterijuma jeste dobit koja se postiže. Optimalna je ona organizacija koja
daje maksimalnu dobit, i ovu funkciju kriterijuma treba maksimizirati, dok je npr. zadatak
organizacije transporta odre
đ
ene rode od proizvo
đ
a
č
a do potroša
č
kih centara, tada je kriterijum
minimalna cena transporta i ovu funkciju kriterijumu treba minimizirati. U svakom slu
č
aju, radi
se o njenoj optimalnoj vrednosti, koja se ozna
č
ava sa
, pri
č
emu,
zna
č
i
ili
, što zavisi od konkretne situacije.
Slede
ć
i slu
č
ajevi opisuju detaljnije osobine LP-a:
Preduze
ć
e ima skladišta na razli
č
itim lokacijama širom zemlje. Za zadati skup potroša
č
kih
zahteva za njegovim proizvodima, preduze
ć
e bi želelo da odredi koje skladište bi trebalo, koliko
proizvoda i kojim potroša
č
ima da isporu
č
i, da bi ukupni troškovi transporta bili minimizirani.
Marketing menadžer, teži da najbolje alocira stalni reklamni budžet izme
đ
u razli
č
itih alternativa
Ekonomski Fakultet u Prištini
6
Ukoliko neka od navedenih pretpostavki nije zadovoljena, onda ili se radi o specijalnom obliku
modela LP-a, ili dati model ne predstavlja model LP.
Postoji više metoda za rešavanje problema linearnog programiranja, a to su:
¾
Efikasni postupci nalaženja optimalnog rešenja
•
Grafi
č
ki metod
•
Metod eliminacije
¾
Simpleks metod
•
Bazi
č
na rešenja sistema linearnih jedna
č
ina
•
Simpleks algoritam
•
Mešoviti problem maksimuma
•
Problem minimuma
•
Dualni problem linearnog programiranja
•
Postoptimalna analiza
2.
DUALNI PROBLEM LINEARNOG PROGRAMIRANJA
Koncept dualiteta
predstavlja jedno od najvažnijih otkri
ć
a u LP-u. Prema tom konceptu svaki
problem LP ima sa sobom povezan jedan drugi problem nazvan
dual
. Osnovna karakteristika
optimalnog, primarnog modela i njegovog duala, ogleda se u postavljanju cilja optimizacije
problema koji se rešava. Npr. ukoliko optimizacija u primarnom modelu usmerena ka
odre
đ
ivanju maksimalne funkcije cilja
,
u odgovaraju
ć
em dualnom modelu, cilj optimizacije
postavljenog problema
ć
e biti odre
đ
ivanje minimalne funkcije cilja
, i obrnuto. Uzajamni
odnosi izme
đ
u originalnog problema i njegovog duala pokazuju se ekstremno zna
č
ajnim,
naro
č
ito u analizi osetljivosti.
Analiza osetljivosti je važan deo gotovo svake studije LP, budu
ć
i da je ve
ć
ina vrednosti
parametara originalnog modela samo procena budu
ć
ih uslova. Pored toga, odre
đ
ene vrednosti
parametara mogu predstavljati menadžerske odluke, a u tom slu
č
aju izbor vrednosti parametara
može biti klju
č
ni problem, koji treba obraditi kroz analizu osetljivosti.
Naime, svaki zadatak LP-a, možemo transformisati u njemu odgovaraju
ć
i dualni problem, pa se i
mnogi problemi LP-a, jednostavnije i lakše rešavaju transformacijom primarnog modela na dual.
Analizom odnosa izme
đ
u primarnog modela i duala, bavi se
teorija dualnosti
, koja se zasniva na
slede
ć
im principima:
•
Ako je primarni problem maksimum funkcije cilja, onda je njegov dual problem minimuma, i
obrnuto–u dualnom problemu funkciju cilja ozna
č
avamo sa i treba je minimizirati tj. odrediti
,
