POSLOVNA INFORMATIKA
UVOD U LINEARNO PROGRAMIRANJE
(vježbe)
Autor: Ante Panjkota
Šibenik, svibanj 2006.
V I S O K A Š K O L A Z A
T U R I S T I
K I M E N A D Ž M E N T
U Š I B E N I K U
Sadržaj:
PREDGOVOR:
1
1
UVOD U LINEARNO PROGRAMIRANJE
2
VRTKA ZA PROIZVODNJU VRATA I PROZORA
LINEARNO PROGRAMIRANJE I EXCEL
4
ZADACI ZA VJEŽBU
42
2
1. UVOD U LINEARNO PROGRAMIRANJE
1 UVOD U LINEARNO PROGRAMIRANJE
U razli itim financijskim analizama est slu aj je da je potrebno minimizirati ili maksimizirati
neku linearnu funkciju. Naj eš e tu podrazumijevamo smanjenje troškova ili pove anje
profita. Naravno, želje su u tom slu aju usmjerene prema njihovim ekstremima, tj.
minimalnim troškovima i maksimalnom profitu. Da bismo pristupili traženju ekstrema, prvo
trebamo definirati našu linearnu funkciju, koja je op enito oblika:
Z = c
1
x
1
+c
2
x
2
+c
3
x
3
+c
4
x
4
+…+c
n
x
n
Gdje su:
X
j
= 1, 2, 3, ….., n
varijable, koje u ovom slu aju zovemo varijable odluke
Gornju funkciju nazivamo
funkcija cilja
. Kako ve ina svjetskih analiti ara pesimisti ki gleda na
financijske probleme, to se stvarni problemi uglavnom svode na minimiziranje spomenute
funkcije. S druge strane matemati ki je ugodnije raditi s problemima traženja maksimuma.
Ovdje ne mislimo da je traženje maksimuma matemati ki jednostavnije od traženja
minimuma, ve je rije
isto o pozitivisti kom pogledu matemati ara na stanje stvari koji
prevladava od kraja 19. st. na ovamo. Ina e sasvim je sve jedno kako emo problem postaviti
sa strane ekonomskog modeliranja minimizacija troškova odgovara maksimiranju profita
(bar u ve ini slu ajeva), a sa strane matemati kog pristupa traženje minimuma funkcije f je
analogno traženju maksimuma funkcije –f.
Dobro pitanje Bartola i na pravom mjestu. Ako op enito pogledamo linearnu funkciju realne
varijable na cijelom podru ju njezine definicije (domene) tada uo avamo da nema govora o
E, malo sutra – kako možeš
govoriti o maksimumu i
minimumu linearne funkcije, a
na slici do vidiš kako izgleda?
x
y
f(x) =ax + b
3
1. UVOD U LINEARNO PROGRAMIRANJE
ekstremima. Me utim, ako funkciju ograni imo na odre eno podru je u tom slu aju možemo
govoriti o traženju ekstrema. Da bi bilo malo jasnije o emu govorimo pogledajmo malo op u
definiciju linearnog programiranja.
1.1 Formulacija problema
Sve probleme linearnog programiranja op enito formuliramo na sljede i na in:
min ili max
funkcije
Z = c
1
x
1
+c
2
x
2
+c
3
x
3
+c
4
x
4
+…+c
n
x
n
(1)
Uz zadovoljenje sljede ih ograni enja:
a
11
x
1
+a
12
x
2
+a
13
x
3
+…+a
1n
x
n
b
1
a
21
x
1
+a
22
x
2
+a
23
x
3
+…+a
2n
x
n
b
2
a
31
x
1
+a
32
x
2
+a
33
x
3
+…+a
3n
x
n
b
3
.
.
.
a
m1
x
1
+a
m2
x
2
+a
m3
x
3
+…+a
mn
x
n
b
m
(2)
Gdje su a
ij
, b
i
i c
j
konstante ………… i=1,….,m; j=1,….,n; m,n N
Neka ograni enja mogu biti prili no jednostavna
recimo da neka varijabla odluke ne može
poprimiti negativnu vrijednost. Drugi slu ajevi ograni enja mogu biti razli iti i ne moraju se
svesti samo na nejednakost manje ili jednako ( ), ve može biti ista jednakost (=) ili ve e ili
jednako ( ). Svako ograni enje je linearna kombinacija varijabli odluke i možemo ga
op enito zapisati u obliku:
a
i1
x
1
+a
i2
x
2
+a
i3
x
3
+…+a
in
x
n
b
i
ili a
i1
x
1
+a
i2
x
2
+a
i3
x
3
+…+a
in
x
n
b
i
ili a
i1
x
1
+a
i2
x
2
+a
i3
x
3
+…+a
in
x
n
=
b
i
(3)
Naj eš i slu aj je da sve varijable odluke poprimaju ne negativne vrijednosti, pa još ovim
ograni enjima možemo dodati uvjet:
x
1
, x
2
, x
3
, … x
n
0
(4)
5
1. UVOD U LINEARNO PROGRAMIRANJE
Linearno programiranje od sredine prošlog stolje a predstavlja
standardni pristup koji je uštedio stotine tisu a, pa i milijuna dolara
velikom broju kompanija i to ne samo velikih. Njegova primjena se sve
više širi i na druga podru ja izvan okvira ekonomije. Da biste dobili predodžbu o
korisnosti i upotrebljivosti spomenute metode dovoljno je re i da se u današnje
vrijeme približno 65% svih svjetskih znanstvenih prora una na ra unalima vezuje
u manjoj ili ve oj mjeri za linearno programiranje ili njezine izvedenice.
Nakon prethodnog kratkog matemati kog uvoda, dobro je malo šire rije ima
opisati o emu se ovdje radi. Ukratko, ve ina primjena uklju uje op i problem
preraspodjele ograni enih resursa izme u me usobno zavisnih aktivnosti na
najbolji mogu i na in
tzv. optimalni na in. Preciznije, kod ovog problema se vrši
odre ivanje stupnja pojedinih aktivnosti koje troše zajedni ke, limitirane resurse.
Izbor stupnja pojedine aktivnosti tako odre uje koliko e svakog resursa biti
potrošeno tom aktivnoš u. Raznolikost primjera kod kojih je mogu e primijeniti
ovaj opis je velika
primjerice poljoprivredna proizvodnja nekog proizvoda
prema potrebama izvoza i doma eg tržišta, odre ivanje rasporeda prijevoza
tereta neke brodske kompanije, utvr ivanje putanje robota pri varenju auto
karoserije itd.
Linearno programiranje koristi ve opisani matemati ki model da bi riješio stvarne
probleme kakve smo naveli. Pridjev linearno se odnosi na matemati ku funkciju
modela (funkciju cilja) koja treba biti linearna. Rije programiranje ne ozna ava
ra unalno programiranje, ve je više sinonim za planiranje. Prema tome linearno
programiranje uklju uje planiranje aktivnosti u cilju dobivanja optimalnog
rezultata, odnosno rezultata koji prema matemati kom modelu poga a zadani cilj
na najbolji mogu i na in izme u svih raspoloživih alternativa.
Nakon, ovog opisa i matemati kog uvoda pravi uvid u linearno programiranje ete
dobiti rješavanjem jednog konkretnog primjera.
1.2 Primjer (Tvrtka za proizvodnju vrata i prozora)
Tvrtka "Di bi propuha sad ga nema" bavi se proizvodnjom prozora i vrata. Njezin proizvodni
dio sastoji se od tri pogona
prvog u kojem se izra uju aluminijski okviri, drugog u kojem
se izra uju PVC okviri i tre eg u kojem se vrši finalno montiranje staklenih površina na okvire
vrata i prozora.
Zbog pada zarade menadžment tvrtke je odlu io da prenamjeni proizvodnu liniju. Proizvodnja
neprofitabilnih proizvoda bit e u potpunosti obustavljena (dok profitabilni i dalje ostaju u
Ovaj materijal je namenjen za učenje i pripremu, ne za predaju.
