Univerzitet UNION - Nikola Tesla
Fakultet za poslovne studije i pravo
SEMINARSKI RAD
KVANTITATIVNE METODE
TEMA:
Linearno programiranje
školska 2016 / 2017 godina
Profesor:
Prof. dr Milun Kokanović
Student:
BAKOŠ ILVANA
Smjer, broj indeksa:
OAS Poslovna ekonomija, I0713-16
Datum izrade seminarskog rada:
10.03.2017. god.
SADRŽAJ
Uvod………………………………………………………….3
Opće formuliranje linearnih programa……………………….4
Ekstremne točke i optimalno rješenje………………………..8
Ekonomska motivacija………………………………………11
Metode linearnog programiranja…………………………….15
Grafička (geometrijska) metoda……………………………..15
Software za linearno programiranje…………………………18
Geometrijsko rješavanje linearnog programa……………….18
Zaključak ……………………………………………………19
Literatura ……………………………………………………20
UVOD
2
Opće formuliranje linearnih programa
Formulacija standardnog problema linearnog programiranja glasi : naći ono nenegativno rješenje
( x
1
, x
2
, …, x
n
), ( x
i
0, i = 1, 2, …, n ) sistema linearnih nejednačina ( ograničenja, uvjeta)
a
11
x
1
+ a
12
x
2
+ … + a
1n
x
n
r
1
a
21
x
1
+ a
22
x
2
+ … + a
2n
x
n
r
2
.
.
. .
.
.
. .
a
m1
x
1
+ a
m2
x
2
+ … + a
mn
x
n
r
m
za koje funkcija cilja ili funkcija kriterija
F = F( x
1
, x
2,
…, x
n
) = c
1
x
1
+ c
2
x
2
+ … + c
n
x
n
dostiže maksimalnu vrijednost.
Rješenje ( x
1
, x
2
, …, x
n
), u primjenama, najčešće ima značenje
plana
ili
programa
(proizvodnje, transporta), pa je otuda ovaj problem dobio naziv
"programiranje"
, a naziv
"linearno programiranje"
potječe od toga što su ograničenja varijabli, kao i funkcija cilja
linearni.
Proizvoljno rješenje sistema nejednačina predstavlja tačku n-dimenzionalnog prostora, to jest
(x
1
, x
2
, …, x
n
)
R
n
.
Svako nenegativno rješenje sistema nejednačina naziva se dopustivim ili mogućim rješenjem.
Svaki problem linearnog programiranja spada u jednu od triju kategorija:
1. ima optimalno rješenje
2. neizvediv je, ima višeznačna rješenja
3. skup mogućih rješenja neograničen
Može se reći : problem linearnog programiranja ima rješenje ako veličina F
max
(F
min
) ima konačnu
vrijednost na skupu S dopustivih rješenja. Problem linearnog programiranja nema
rješenja ako je skup S prazan skup ili ako veličina F
max
(F
min
) nema konačnu vrijednost.
Pri određivanju optimalnog rješenja pojavljuju se dva kriterija optimizacije : maksimizacija ili
minimizacija vrijednosti funkcije cilja. Iako postoje dva kriterija optimizacije, problem izbora
4
optimalnog rješenja može se smatrati jedinstvenim, jer se jedan kriterij optimizacije može
zamjeniti drugim, kako to utvrđuje slijedeći teorem :
Teorem :
Dani kriterij optimizacije može se zamijeniti suprotnim, pri čemu zamjena ne utječe na
optimalno rješenje, to jest, ako je za X
*
S ispunjeno
F(X
*
) = max F(X)
Onda je
-F(X
*
) = min [-F(X)] i obrnuto.
Poopćeni linearni program može se izraziti na tri različita načina :
Običnim (kanonskim) zapisom
Zapisom pomoću sume
Matričnim zapisom
a) Obični (standardni) zapis
Kad se potpuno ispiše, program će maksimizacije sa
n
varijabli i
m
ograničenja izgledati :
Maksimizirati
z = c
1
x
1
+ c
2
x
2
+ … + c
n
x
n
uz uvjet
a
11
x
1
+ a
12
x
2
+ … + a
1n
x
n
r
1
a
21
x
1
+ a
22
x
2
+ … + a
2n
x
n
r
2
.
.
. .
.
.
. .
a
m1
x
1
+ a
m2
x
2
+ … + a
mn
x
n
r
m
x
j
0 (j = 1, 2, …, n )
Varijable odlučivanja označene su sa x
j
( za j = 1, 2, …, n), a njihovi koeficijenti u funkciji cilja
sa c
j
( za j = 1,2, …, n) koji su skup zadanih konstanti. S druge strane, oznake r
i
( i = 1, 2, …, m)
– drugi skup konstanti – ograničenja su postavljena na program. Radi ujednačenosti, ali bez
smanjenja ujednačenosti, napisali smo svih m ograničenja kao nejednačina sa oznakom
.
Posebno valja istaknuti da, u slučaju kad se pojavi ograničenje sa oznakom
, uvijek ga možemo
pretvoriti u oblik
jednostavno množeći obje strane nejednakosti sa –1. Konačno, uočimo da su
5
