1
1. Osnovne pretpostavke modela linearnog programiranja
Postoji određeni broj pretpostavki koje moraju biti zadovoljene da bi određeni model
predstavljao model linearnog programiranja. Najvažnije 4 pretpostavke linearnog programiranja
su :
1) Linearnost.
Pretpostavka linearnosti podrazumeva postojanje linearnih zavisnosti
između promenljivih u zadatku linearnog programiranja. Ova pretpostavka zadovoljena
je tako što su funkcija cilja i ograničavajući uslovi u modelu linearnog programiranja
izraženi linearnim funkcijama. Kao posledica linearnosti u modelu linearnog
programiranja zadovoljene su takođe dve osnovne pretpostavke i to: proporcionalnost i
aditivnost.
Proporcionalnost
podrazumeva postojanje proporcionalnog odnosa u
modelu linearnog programiranja između inputa i autputa. Osobina
aditivnosti
podrazumeva da se ukupna vrednost funkcije cilja ili pojedinih ograničenja može dobiti
kao zbir vrednosti pojedinih aktivnosti koje predstavljaju sastavne elemente modela
linearnog programiranja. Osobina aditivnosti primenjuje se i na ograničavajuće uslove
modela linearnog programiranja – ukupni utrošci određenog resursa u proizvodnji
određuju se kao suma utrošaka pojedinih aktivnosti (proizvoda).
2) Izvesnost.
Svi parametri modela linearnog programiranja su unapred jednoznačno
određeni, što znači da su koeficijenti funkcije cilja i sistema ograničenja deterministički
određeni i ne menjaju se u toku rešavanja modela. S obzirom na ovu osobinu, model
linearnog programiranja smatramo determinističkim modelom.
3) Deljivost.
Ova pretpostavka podrazumeva da promenljive u modelu linearnog
programiranja ne moraju biti celi brojevi. Prema tome, u opštem obliku modela
linearnog programiranja ne postavlja se tzv. uslov celobrojnosti rešenja, što znači da
vrednosti promenljivih mogu biti izražene i u obliku decimalnih brojeva. Ukoliko se,
međutim, iz određenih razloga zahteva celobrojnost promenljivih, onda je u pitanju
specijalan oblik zadatka – model celobrojnog linearnog programiranja.
4) Nenegativnost.
Uslov nenegativnosti promenljivih predstavlja jednu od osnovnih
pretpostavki modela linearnog programiranja. Ova pretpostavka ima svoj metodološki i
ekonomski značaj. Uslov nenegativnosti, pored funkcije cilja i sistema ograničenja,
predstavlja jedan od osnovnih elemenata modela linearnog programiranja.
Ukoliko neka od navedenih pretpostavki nije zadovoljena, onda ili se radi o specijalnom
obliku modela linearnog programiranja ili dati model ne predstavlja model linearnog
programiranja.
Opšti oblik zadatka linearnog programiranja
može se predstaviti u obliku zahteva za
određivanjem vrednosti promenljivih x
1
,x
2
,.......,x
n
, koje zadovoljavaju m nejednačina i
jednačina oblika
g
i
(x
1
,x
2
,.......,x
n
) {≤, =, ≥}b
i
i=1,.....,m
2
i za koje se ostvaruje maksimalna ili minimalna vrednost funkcije
Z = f (x
1
,x
2
,.......,x
n
)
Model linearnog programiranja (kao standardni problem maksimuma) glasi:
(max)Z = C
1
x
1
+ C
2
x
2
+ ........ + C
p
x
p
a
11
x
1
+ a
12
x
2
+ ........ + a
1p
x
p
≤ b
1
a
21
x
1
+ a
22
x
2
+ ........ + a
2p
x
p
≤ b
2
.
.
.
a
m1
x
1
+ a
m2
x
2
+ ........ + a
mp
x
p
≤ b
m
X
1
,X
2
,.......,X
p
≥ 0
Da bi zadatak linearnog programiranja mogao da se reši sve nejednačine moraju se
transformisati u jednačine uvođenjem: 1) dodatnih, 2) veštačkih ili 3) dodatnih i veštačkih
promenljivih; u zavisnosti o kakvom problemu se radi.
Kod standardnog problema maksimuma potrebno je uvesti samo dodatne promenljive
(max)Z = C
1
x
1
+ C
2
x
2
+ ........ + C
p
x
p
+ C
p+1
x
p+1
+ C
p+2
x
p+2
+ ........ + C
p+m
x
p+m
a
11
x
1
+ a
12
x
2
+ ........ + a
1p
x
p
+ x
p+1
= b
1
a
21
x
1
+ a
22
x
2
+ ........ + a
2p
x
p
+ x
p+2
= b
2
.
.
.
a
m1
x
1
+ a
m2
x
2
+ ........ + a
mp
x
p
+ x
p+m
= b
m
X
1
,X
2
,.......,X
p
,X
p+1
,X
p+2
,........,X
p+m
≥ 0
4
Koeficijenti uz dodatne promenljive u funkciji cilja ( C
p+1
,.....,C
p+m
) uvek su jednaki 0, dok
se veštačkim promenljivim dodaju koeficijenti +M (koji označavaju beskonačno veliki broj.
Zadatak problema minimuma (bez obzira da li je reč o standardnom ili mešovitom) rešava
se u 7 koraka,kao i problem maksimuma,na vrlo sličan način:
Koraci simpleks metoda za rešavanje problema minimuma su:
1) Formiranje baze, formiranje matrice i izračunavanje inverzne matrice α
-1
2) Izračunavanje vrednosti bazičnih promenljivih : a) X
b
= α
-1
∙ b ili b) preko koeficijenta
ρ.
3) Izračunavamo koordinate nebazičnih vektora : X
j
= α
-1
∙ A
j
, gde A
j
predstavlja zadate
koordinate nebazičnih vektora.
4) Izračunavamo vrednost funkcije cilja (kriterijuma) : Z = C
b
∙ X
b
, gde C
b
predstavlja
koeficijente bazičnih promenljivih a X
b
se uzima iz drugog koraka.
5) Izračunavamo vrednost funkcija nebazičnih vektora: Z
j
= C
b
∙ X
j
, gde je X
j
vrednost
dobijena u trećem koraku.
6) Prvi simpleks kriterijum (Kriterijum optimalnosti) – Proverava se da li je baza
optimalna
min (C
j
– Z
j
) < 0 , gde su C
j
koeficijenti vezani za nebazične
promenljive
a Z
j
su vrednosti izračunate u prethodnom koraku.
Baza je optimalna ukoliko su sve vrednosti prvog simpleks kriterijuma veće ili
jednake 0. Ukoliko postoji jedna ili više vrednosti koje su manje od nule baza nije
optimalna i tada se bira najveća negativna vrednost i taj vektor se uvodi u novu bazu.
Ukoliko je baza optimalna šesti korak je i poslednji, a ukoliko nije onda se prelazi na
sledeći korak.
7) Drugi simpleks kriterijum : Izvodimo jedan postojeći vektor iz baze po formuli:
ρ= min ( x
i
/x
il
), pod uslovom da je x
il
> 0 , gde x
i
predstavlja vrednost
bazičnih promenljivih (iz 2. koraka) a x
il
su izračunate koordinate vektora
koga smo u prethodnom koraku uveli u bazu.
Jednostavni način za rešavanje problema minimuma jeste preko njemu odgovarajućeg
dualnog modela formulisanog u vidu standardnog problema maksimuma pa će u sledećem
primeru biti objašnjena ta procedura (Jedina razlika je u 6. koraku kada mora biti zadovoljen
uslov max (C
j
– Z
j
) > 0, odnosno sve vrednosti moraju biti ≤0 da bi baza bila optimalna, u
suprotnom uzima se najveća pozitivna vrednost i taj vektor se uvodi u bazu).
