Simpleks metoda za rješavanje modela linearnog
programiranja
p g
j
(14.03.2012., 21.03.2012.)
Dr. sc. Tunjo Peri
ć
SADRŽAJ
ƒ
Osnovni principi simpleks metode
ƒ
Rješavanje op
ć
eg problema LP za maksimum pomo
ć
u
j
j
p g p
p
simpleks tablice
ƒ
Rješavanje op
ć
eg problema LP za minimum pomo
ć
u simpleks
t bli
tablice
ƒ
Da bismo odredili po
č
etno bazi
č
no dopustivo rješenje
ƒ
Da bismo odredili po
č
etno bazi
č
no dopustivo rješenje
potrebno je najprije op
ć
i model LP svesti na kanonski oblik
(sva ograni
č
enja moraju biti oblika jednakosti (=)).
ƒ
Svo
đ
enje
op
ć
eg/standardnog oblika
linearnog modela na
kanonski oblik
ovisi o obliku ograni
č
enja i vrsti linearnog
problema
problema.
ƒ
Lijevoj strani ograni
č
enja oblika manje ili jednako ( )
dodaju se tzv.
dopunske varijable
s koeficijentom 0 uz tu
≤
varijablu u funkciji cilja, kako za problem maksimuma tako i
za problem minimuma.
ƒ
Lijevoj strani ograni
č
enja oblika jednakosti (=) dodaje se tzv
Lijevoj strani ograni
č
enja oblika jednakosti ( ) dodaje se tzv.
artificijelna (umjetna) varijabla s koeficijentom
–M uz tu
varijablu u funkciji cilja za problem maksimuma, odnosno M
bl
i i
“M” j i
it
liki b j
za problem minimuma. “M” je izrazito veliki broj.
ƒ
Lijevoj strani ograni
č
enja oblika ve
ć
e ili jednako ( ) dodaje se
≥
dopunska varijabla s predznakom minus
(-), s koeficijentom 0 u
funkciji kriterija te artificijelna varijabla s koeficijentom –M za
problem maksimuma odnosno M za problem minimuma.
ƒ
Tabli
č
no prikazano svo
đ
enje op
ć
eg na kanonski oblik problema LP
izgleda ovako:
Oblik
Dopunske
i
Koeficijenti
u
funkciji
cilja
ogran
i
č
enja
umjetne
varijable
max
min
DOP
ART
DOP
ART
<=
+ DOP
0
0
<
+
DOP
0
0
=
+
ART
‐
M
M
>=
‐
DOP+ART
0
‐
M
0
M
ƒ
Artificijelne (umjetne) varijable (ART) uvode se samo kao ra
č
unsko
sredstvo u simpleks algoritmu s ciljem osiguranja dopustivog
b i
č
j š j
bazi
č
nog rješenja.
ƒ
Nebazi
č
ne su varijable
one koje u programu imaju vrijednost
ƒ
Nebazi
č
ne su varijable
one koje u programu imaju vrijednost
nula.
ƒ
Bazi
č
ne varijable
predstavljaju tzv. bazu, imaju vrijednosti
ve
ć
e od nule i ima ih onoliko koliko ima ograni
č
enja.
ƒ
Dopustivo bazi
č
no rješenje ima sljede
ć
e osobine
:
ƒ
Sadrži s e po iti ne rijednosti arijabli
i k d d
ij
ƒ
Sadrži sve pozitivne vrijednosti varijabli
osim kod degeneracije,
ƒ
Svaka varijabla iz baze može se pojaviti samo u jednom ograni
č
enju sa
strukturnim koeficijentom 1, tj.
strukturni koeficijenti u
ograni
č
enjima uz bazi
č
ne varijable
č
ine jedini
č
nu matricu
ograni
č
enjima uz bazi
č
ne varijable
č
ine jedini
č
nu matricu,
ƒ
Vrijednosti varijabli koje
č
ine dopustivo po
č
etno bazi
č
no rješenje
jednake su slobodnim koeficijentima u ograni
č
enjima,
a to su: (1)
dopunske varijable uvedene u ograni
č
enja oblika nejednadžbi
i (2)
≤
dopunske varijable uvedene u ograni
č
enja oblika nejednadžbi i (2)
artificijelne varijable uvedene u ograni
č
enja oblika jednadžbi i
nejednadžbi .
≤
≥
