SIMPLEKS METODA
a) Op
ć
enito o simpleks metodi
Do sada se nije našlo analiti
č
ko rješenje op
ć
eg problema linearnog programiranja. Ta
nealternativa nalaženja analiti
č
kog rješenja dovela je do usavršavanja velikog broja
numeri
č
kih metoda, od kojih niti jedna ne rješava problem u jednom koraku
1
. Sve su te
metode iterativne, tj. polaze od nekog mogu
ć
eg rješenja da bi ga u nizu koraka poboljšavale
dok se ne do
đ
e do optimalnog rješenja ili se utvrdi da takvo rješenje ne postoji. Utvr
đ
eno je
da je za po
č
etno rješenje najzgodnije uzeti ono, u kojem su bazi
č
ni vektori jedini
č
ni vektori,
tj. da je baza ortonormalna baza.
Najviše primjenjivana op
ć
a metoda rješavanja problema linearnog programiranja, a
koja ima i niz varijacija, sigurno je simpleks metoda. Ta metoda se primjenjuje (uz niz
modifikacija) u svim tipovima problema linearnog programiranja, s time da je prethodno
potrebno, ako to ve
ć
nije, problem svesti u kanonsku formu.
Simpleks metoda predstavlja neku vrst kompromisa izme
đ
u dviju krajnosti:
a)
potrebe da se optimalno rješenje na
đ
e u jednom koraku i
b)
potrebe da se ispitaju sva bazi
č
na rješenja (da bismo bili sigurni da je na
đ
eno optimalno
rješenje stvarno optimalno).
Broj bazi
č
nih rješenja, a time i broj potrebnih iza
č
unavanja kod primjene simpleks
metode, redovito je manji od ukupnog broja mogu
ć
ih bazi
č
nih rješenja
2
.
Ta metoda se mora primijeniti ako problem sadrži više od dvije varijable, a može se
primijeniti i ako problem ima dvije varijable.
3
Jedna od osnovnih zna
č
ajki simpleks metode je
iterativnost
. To zna
č
i da se proces
rješavanja sastoji od (kona
č
nog
4
) niza koraka. Pritom se u svakom koraku dobiva neko
bazi
č
no rješenje koje za problem maksimuma osigurava da je trenutna vrijednost funkcije
cilja najmanje jednaka ili ve
ć
a od vrijednosti u prethodnom koraku,
5
dok je za problem
minimuma obrnuto.
Ideja simpleks metode sadrži tri bitna elementa:
6
1.
alternativa odre
đ
ivanja bar jednog mogu
ć
eg rješenja,
2.
alternativa provjere je li odre
đ
eno mogu
ć
e rješenje optimalno ili nije,
1
To se zapravo podrazumijeva, jer bi ina
č
e bile analiti
č
ke.
2
Ukoliko sa N ozna
č
imo broj svih iteracija, a sa m broj jednadžbi, tada se broj svih iteracija kre
ć
e unutar sljede
ć
ih veli
č
ina
1 5
2
,
m N
m
≤
≤
, što zna
č
i da sa pove
ć
anjem broja jednadžbi kojih u realnim zadacima ima i nekoliko tisu
ć
a, zna
č
ajno
raste i broj iteracija. Ukoliko se uzme u obzir da se u svakoj iteraciji obavlja velik broj ra
č
unskih operacija, posebice ako
imamo i veliki broj nepoznanica, tada je smanjenje broja iteracija, bez obzira na primjenu informati
č
ke tehnologije, važan
zadatak.
3
U tom slu
č
aju se, kao što je prikazano, može primjeniti elementarna grafi
č
ka metoda za rješavanje tog tipa zadataka.
4
Ako postoji optimalno rješenje, tj. ako funkcija cilja nema infinitnu vrijednost.
5
Dok je u problemu minimuma naravno suprotno, tj. svaka sljede
ć
a vrijednost funkcije cilja je najviše jednaka ili manja od
prethodne.
6
Petri
ć
, J., op.cit., str. 28.
3.
alternativa da se u slu
č
aju izbora mogu
ć
eg rješenja koji nije optimalan odredi novi plan
koji je bliži optimalnom.
U slu
č
aju da postoje sve tri mogu
ć
nosti, može se u okviru kona
č
nog broja koraka
7
dobiti
optimalno rješenje koje predstavlja rješenje formuliranog zadatka. Prema tome, simpleks
metoda se zasniva na sukcesijskom poboljšanju mogu
ć
eg plana, sve dok se ne dobije
optimalno rješenje.
Ovakav prilaz u formuliranju algoritma simpleks metode tako
đ
er omogu
ć
ava da se u procesu
rješavanja bilo kojeg zadatka ustanovi, je li rješiv ili nije, što zna
č
i da postoji alternativa
ispitivanja postojanja proturije
č
nosti u ograni
č
enjima i ispitivanje je li funkcija cilja F(X)
neograni
č
ena u oblasti (D).
Druga
č
ije re
č
eno, ta metoda predvi
đ
a cijeli niz kontrola kojima se utvr
đ
uje, odgovara li
posljednje bazi
č
no rješenje optimalnom rješenju ili optimalna vrijednost ne postoji ukoliko
funkcija cilja u prostoru mogu
ć
ih rješenja može poprimiti proizvoljno velike vrijednosti.
Simpleks metoda omogu
ć
ava da se najkra
ć
im putem do
đ
e do ekstremne vrijednosti funkcije
cilja, prelaskom iz jednog vrha poliedra na drugi.
Startna to
č
ka simpleks procedure je neka ekstremna to
č
ka. Svaka iteracija tog procesa sastoji
se u translaciji (paralelnom pomaku) hiperravnine koja predstavlja funkciju cilja.
Hiperravnina se translatira od jedne to
č
ke do neke susjedne ekstremne to
č
ke tako, da je
njezina distanca od ishodišta sve manja (u problemu minimuma) odnosno sve ve
ć
a (u
problemu maksimuma). Proces se nastavlja dok hiperravnina ne dosegne optimalnu distancu
od ishodišne to
č
ke.
U tom smislu, simpleks metoda omogu
ć
ava:
1.
postupak nalaženja vrhova poliedra, tj. odre
đ
ivanje komponenti vektora koji odgovara
vrhu poliedra;
2.
formiranje kriterija za brzu ocjenu je li odgovaraju
ć
a vrijednosti funkcije cilja minimalna
(maksimalna) ili nije;
3.
ako nije, simpleks metoda omogu
ć
ava nalaženje drugog vrha, u kojem funkcija cilja ima
ve
ć
u vrijednost.
Naime, metoda se sastoji od slijeda bazi
č
nih rješenja od kojih je svako dobiveno na osnovi
prethodne izmjene baze samo za jedan vektor-stupac. S geometrijskog stajališta to je
ekvivalentno promatranju susjednih vrhova u prostoru mogu
ć
ih rješenja i kretanju duž tih
vrhova. Razlog što se promatraju samo bazi
č
na mogu
ć
a rješenja, proizlazi iz fundamentalnog
teorema linearnog programiranja.
No, kako simpleks metoda traži neko bazi
č
no rješenje bolje od ve
ć
postoje
ć
eg, pitanje je kako
se našlo prvo bazi
č
no mogu
ć
e rješenje. U stvarnosti to rješenje se ili može odmah o
č
itati ili se
izgra
đ
uje
ad hoc
tehnikama.
Prikaz ovog poglavlja zapo
č
et
ć
e se pokazuju
ć
i u prvom redu kako se dobiva po
č
etno
rješenje, i na jednostavnom primjeru kako se dolazi do optimalnog rješenja. Nakon toga
slijedi detaljan prikaz algoritma simpleks metode koji je primjenjiv na sve slu
č
ajeve, pri
č
emu
ć
e se od niza mogu
ć
ih prednost dati tzv. tabelarnom pristupu, prikladnom za ru
č
no
ra
č
unanje.
8
7
Misli se na ra
č
unski korak u iteracijskom procesu traženju rješenja.
8
Tabelarni prikaz je osnovica za razumijevanje ra
č
unarskih programa koji u sebi uklju
č
uju simpleks algoritam.
Nadalje, zbog istaknutih posebicesti koje proizlaze iz strukture pojedinih vrsta problema,
prikazat
ć
e se pravila i primjene za sljede
ć
e tipove problema:
1.
problem maksimuma u standardnom obliku,
2.
problem minimuma u standardnom obliku.
Treba naglasiti da su osnovna pravila sadržana u rješavanju standardnog problema
maksimuma i minimuma, dok
ć
e se pravila za rješavanje originalnog
9
mješovitog i op
ć
eg
problema kao i za kanonski problem, izre
ć
i samo u nužno potrebnom dijelu.
Nadalje
ć
e se unutar svakog od tih tipova problema, a zbog niza posebicesti, zasebno prikazati
na
č
in
č
itanja, odnosno dobivanja dualnih rješenja. Dobivanje, odnosno na
č
in
č
itanja dualnog
rješenja se u literaturi navodi za standardne probleme. Za mješovite probleme kao i za op
ć
i
problem u literaturi se ne susre
ć
u na
č
ini formiranja tabele iz kojih bi bilo mogu
ć
e neposredno
o
č
itati i dualno rješenje.
1. SIMPLEKS METODA I STANDARDNI PROBLEM MAKSIMUMA
Da bi se simpleks metoda mogla primijeniti prethodno treba problem svesti na
kanonsku formu. To se radi na na
č
in koji proizlazi iz teorije linearnog programiranja. Ukoliko
je originalni problem standardni problem maksimuma, tada se on mora transformirati u
kanonski problem dodavanjem dodatnih varijabli u ograni
č
enjima i funkciji cilja, s time da su
svi koeficijenti uz dodatne varijable u funkciji cilja jednaki nuli.
a)
po
č
etno rješenje simpleks metode kod standardnog problema maksimuma
Polaze
ć
i od re
č
enog cijeli se problem može prikazati tabelarno na sljede
ć
i na
č
in:
Tab 7. Po
č
etna simpleks tabela za standardni problem maksimuma
10
j
c
1
c
2
c
...
n
c
0 0 ...
0
i
c
Baza
A
1
A
2
...
A
n
U
1
U
2
...
U
m
B
B/a'
ij
0
U
1
a
11
a
12
...
a
n
1
1 0 ...
0
b
1
b
1
/a'
1j
0
U
2
a
21
a
22
...
a
n
2
0 1 ...
0
b
2
b
2
/a'
2j
...
... ... ... ...
... ... ... ...
... ...
...
0
U
m
a
m
1
a
m
2
...
a
mn
0 0 ...
1
b
m
b
m
/a'
mj
Z
z
j
z
1
z
2
...
z
n
z
n
+
1
z
n
+
2
...
z
n m
+
=
0
z
c
j
j
−
z
c
1
1
−
z
c
2
2
−
...
z
c
n
n
−
z
n
+
−
1
0
z
n
+
−
2
0
...
z
n m
+
−
0
9
Misli se na zadržavanje problema kakav je zadan, bez njegove transformacije na odgovaraju
ć
e standardne probleme.
10
Postoji više mogu
ć
ih na
č
ina da se tabelarno prikaže tijek rješavanja problema linearnog programiranja korištenjem
simpleks algoritma. Ovdje je prikazan jedan od mogu
ć
ih. Za ostale vidjeti npr. Vadnal, A.,(1980): Primjena matemati
č
kih
metoda u ekonomiji, Informator, Zagreb i Petri
ć
, J., op.cit., i dr.
