'Anura' obrt za poduke
Strossmayerova 1a, Osijek
www.anura.hr
e-mail: [email protected], [email protected]
mob. 098-184-3163, 091-733-1635, 095-528-7269
Skripta iz
kvantitativnih
metoda za
poslovno
upravljanje
Kristina Perdić
'Anura' obrt za poduke
www.anura.hr – [email protected]
098-184-3163, 091-733-1635, 095-528-7269
Lin
ea
rno
p
ro
gr
am
ir
anj
e (s
im
pl
ek
s m
eto
da
)
4
Linearno programiranje (simpleks metoda)
Metode linearnog programiranja su trenutno najvažniji instrument operacijskih istraživanja. Postoji više
metoda za rješavanje problema linearnog programiranja. Jedan od najuspješnijih razvio je Dantzig 1947.
godine. Ta metoda zove se
simpleks metoda
.
Linearna optimizacija
se bavi minimiziranjem ili maksimiranjem linearne
funkcije cilja
ovisne o
konačno mnogo varijabli koje zadovoljavaju konačno mnogo dodatnih uvjeta (
restrikcija
ili
ograničenja
)
zadanih u obliku linearnih jednadžbi ili nejednadžbi, tj. pronalaženje optimalnog rješenja pomoću
linearnog programiranja.
Linearna optimizacija važna je jer se mnogi praktični problemi mogu formulirati kao problemi linearne
optimizacije, a zatim na jednostavan način riješiti jer su teorija i metode rješavanja linearnih
optimizacijskih problema su jednostavne i pregledne.
Simpleks metoda
je iterativna metoda. Ona polazi od nekog dopuštenog rješenja te ga u nizu koraka
poboljšava dok se ne postigne optimalno rješenje.
Problem maksimuma
Opća
matematička formulacija
linearnog programiranja (
problem maksimuma
):
max
z = c
1
x
1
+ c
2
x
2
+ ... + c
n
x
n
a
11
x
1
+ a
12
x
2
+ a
1j
x
j
+ ... + a
1n
x
n
≤ b
1
a
21
x
1
+ a
22
x
2
+ a
2j
x
j
+ ... + a
2n
x
n
≤ b
2
...
a
m1
x
1
+ a
m2
x
2
+ a
mj
x
j
+ ... + a
mn
x
n
≤ b
m
x
1
,
2
,
...
n
≥ 0
m
– broj restrikcija
n
– obujam pojedinih aktivnosti
a
ij
– koeficijent koji govori koliko je potrebno jedinica proizvodnog faktora
i
za jedinicu aktivnosti x
j
b
i
– ograničavajući faktor
c
j
– dobit po jedinici j – koeficijent funkcije cilja
x
j
– nepoznata aktivnost
j
, nepoznata akcija usmjerena na izradu jedinice nekog proizvoda, strukturna
varijabla
Cilj
linearnog programiranja je maksimalizacija profita, prihoda, dobiti... (problem maksimuma) ili
minimalizacija troškova, vremena... (problem minimuma).
Zadatak
linearnog programiranja je utvrditi vrijednosti za varijable odlučivanja, koje će maksimalizirati ili
minimalizirati funkciju cilja.
Ograničenja
ili
restrikcije
su zadani u obliku jednadžbi ili nejednadžbi. Sastoji se od 4 elementa:
1.
Količina (desna strana) = konstanta
2.
Algebarski znak (≥, ≤, =)
3.
Varijabla odlučivanja (x
1
, x
2
, x
3
... )
4.
Parametri (vrijednosti uz varijable odlučivanja)
Postoje
tri tipa ograničenja
:
1.
sustavno – sadrži dvije ili više varijabli odlučivanja
2.
individualno – sadrži samo jednu varijablu odlučivanja
3.
uvjet nenegativnosti – odnosi se na potencijalne vrijednosti koje mogu poprimiti varijable
odlučivanja ('uvjet za x')
Dopušteno rješenje
je ono rješenje koje zadovoljava zadani skup ograničenja. Ako dopušteno rješenje
ujedno i optimalizira vrijednost funkcije cilja tada ga nazivamo i
optimalno rješenje
(najbolja moguća
kombinacija varijabli odlučivanja).
Formuliranje modela linearnog programiranja
:
1.
identifikacija varijabli odlučivanja
2.
formuliranje funkcije cilja
3.
identifikacija ograničenja
4.
određivanje vrijednosti za parametre
5.
formuliranje modela
6.
rješavanje modela linearnog programiranja
'Anura' obrt za poduke
www.anura.hr – [email protected]
098-184-3163, 091-733-1635, 095-528-7269
Lin
ea
rno
p
ro
gr
am
ir
anj
e (s
im
pl
ek
s m
eto
da
)
5
Opći oblik simpleks tablice:
x
1
x
2
...
x
n
y
1
y
2
...
y
m
z
1
a
11
a
12
...
a
1n
1
0
...
0
b
1
a
21
a
22
...
a
2n
0
1
...
0
b
2
...
...
...
...
...
...
...
...
...
a
m1
a
m2
...
a
mn
0
0
...
1
b
m
c
1
c
2
...
c
n
0
0
0
0
1
0
U simpleks tablicu unose se restrikcije i funkcija cilja. U tablicu unosimo strukturne i dopunske varijable.
One mogu biti bazične i nebazične.
Strukturne varijable
su x
1
, x
2
, ... x
n ,
a njihove vrijednosti koje unosimo u tablicu nalaze se u restrikcijama.
Te vrijednosti koje unosimo u tablicu, koje se nalaze uz varijable odlučivanja u restrikcijama, nazivamo
tehnički
koeficijenti
(a
11
, a
12
, ... a
mn
).
Tehnički koeficijenti
nam govore koliko je potrebno jedinica n-tog
resursa za izradu jedne jedinice m-tog proizvoda.
Dopunske varijable
su y
1
, y
2
, ... y
m.
One nam nisu zadane u zadatku već njih dodajemo kako bismo mogli
primijeniti simpleks metodu, tj. kako bismo nejednadžbe pretvorili u jednadžbe. Njihov broj jednak je
broju restrikcija, a one govore o (ne)iskorištenosti kapaciteta.
Bazične varijable
su varijable koje imaju u stupcu jednu vrijednost 1 i sve ostale vrijednosti 0. Njihovu
vrijednost očitavamo u krajnjem desnom stupcu (obično su to varijable y).
Nebazične varijable
su sve ostale varijable i njihova vrijednost jednaka je 0.
Slobodni člano
vi
s desne strane u restrikcijama predstavljaju ograničenja ili kapacitete i upisuju se u
krajnji desni stupac(b1, b2, ... bm).
U zadnji red,
red funkcije cilja
, upisujemo koeficijente uz varijable odlučivanja u funkciji cilja (c1, c2, ... cn).
Računanje simpleks tablicom
1.
Prvi korak je izabrati
pivot stupac
, tj. stupac nebazične varijable koji mora dospjeti u bazu – označimo
ga sa
s
. To je onaj stupac koji ima najnegativniji kvocijent u redu funkcije cilja. Pivot stupac
određujemo izrazom:
Ako ne postoji niti jedan negativan element
, računski postupak je završen jer je pronađen
optimum.
2.
Sada treba pronaći koja će bazična varijabla izaći iz baze, red te varijable zove se
pivot red
– označimo
ga s
r
. To nam je red u kojem se nalazi najmanji pozitivan kvocijent elemenata desne strane i
elemenata pivot stupca.
3.
Na sjecištu pronađenog pivot stupca i pivot reda nalazi se
pivot element
. Pivot element moramo svesti
na jedinicu, a sve ostale elemente u pivot stupcu računamo pomoću izraza:
Tim postupkom doveli smo pivot stupac u bazu.
4.
Ostale koeficijente u tablici računamo prema pravilu:
Nakon ova četiri koraka završena je prva iteracija. Postupak ponavljamo dok više ne možemo naći
pivot stupac niti pivot red.
'Anura' obrt za poduke
www.anura.hr – [email protected]
098-184-3163, 091-733-1635, 095-528-7269
Lin
ea
rno
p
ro
gr
am
ir
anj
e (s
im
pl
ek
s m
eto
da
)
7
Pravila za računanje
simpleks metodom
1)
Slobodna varijabla
-
Cilj nam je dovesti ju
u bazu
(jedinica i nule)
-
Pivot stupac nam je po volji odabran stupac u kojem se nalazi slobodna, ali nebazična varijabla
-
Pivot red je neki po volji odabran red u kojem neka druga slobodna varijabla nije bazična
2)
Artificijelna varijabla
-
Cilj nam je izbaciti ju
iz baze
-
Pivot red je po volji odabran red u kojem je artificijelna varijabla bazična, tj. red u kojem
artificijelna varijabla ima vrijednost 1
-
Pivot stupac je po volji odabran stupac s neartificijelnom varijablom koja je nabazična
3)
Nedopušteno rješenje
-
Negativan broj na desnoj strani, tj. u zadnjem desnom stupcu (stupcu slobodnih članova)
-
Pivot red je po volji odabran red u kojem slobodna varijabla nije bazična
-
Pivot stupac je po volji odabran stupac s neartificijelnom varijablom koja nije bazična te uz uvjet
da pivot element mora biti
negativan
. Ako takav element ne postoji to je znak da zadatak
nema
rješenja
4)
Negativan stupac
-
Negativan element u redu funkcije cilja (zadnji red)
-
Pivot stupac je stupac s neartificijelnom i nebazičnom varijablom, koji ima najnegativniji
koeficijent u redu funkcije cilja
-
Pivot red je red u kojem slobodna varijabla nije bazična te red u kojem se nalazi najmanji
pozitivni kvocijent elemenata desne strane i koeficijenata pivot stupca. U slučaju da takav,
pozitivni kvocijent ne postoji, zadatak ima
neograničeno rješenje
Grafič
ko prikazivanje
Uvjet
za grafičko prikazivanje problema linearnog programiranja je postojanje
samo dvije strukturne
varijable.
Grafičko rješenje prikazujemo u koordinatnom sustavu. Da bismo nacrtali graf prvo moramo restrikcije
svesti na
kanonski oblik
. Ako su restrikcije jednadžbe one su predstavljene pravce, ako su nejednadžbe
tada one dijele područje na područje dopuštenog rješenja i područje nedopuštenog rješenja. Nedopušteno
područje je
šrafirano
. Osim restrikcija šrafiramo i ovisno o uvjetima nenegativnosti za strukturne
varijable.
