UNIVERZITET U TRAVNIKU
FAKULTET ZA MENADŽMENT I POSLOVNU EKONOMIJU
SIMPLEKS METODA
-
SEMINARSKI RAD
-
Kandidati: Mentor:
Sanela Palavra 2940/17 Doc.dr. Lejla Dacić
Samela Jusić 2891/17
Kiseljak, april 2020.
4
2. SIMPLEKS METODA – definicija, osnovne značajke i
mogućnosti
Linearno programiranje je najstarija i jedna od metoda operacijskih istraživanja koja se
najčešće primjenjuje u praksi. To je model kojom se matematički može opisati lingvistički
problem traženja optimalne vrijednosti (minimum ili maksimum) funkcije cilja s određenim
brojem strukturnih varijabli x1, x2,…,xn međusobno povezanih linearnim vezama, tj.
ograničenjima u obliku linearnih jednadžbi ili nejednadžbi. Da bi se problem linearnog
programiranja mogao riješiti, potrebno je postaviti matematički model koji se sastoji od funkcije
cilja ili kriterija i ograničenja u obliku jednadžbi ili nejednadžbi i uvjeta nenegativnosti.
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. 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.
Kao što je navedeno u uvodu danas, najviše primjenjivana opća metoda rješavanja problema
linearnog programiranja, a koja ima i niz varijacija, sigurno je simpleks metoda.
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
4
. 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. Jedna od osnovnih značajki simpleks metode je iterativnost. To znači da se proces
rješavanja sastoji od niza koraka. Pritom se u svakom koraku dobiva neko bazično rješenje koje
4
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 15 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.
5
za problem maksimuma osigurava da je trenutna vrijednost funkcije cilja najmanje jednaka ili
veća od vrijednosti u prethodnom koraku, dok je za problem minimuma obrnuto.
Ideja simpleks metode sadrži tri bitna elementa
5
:
1. alternativa određivanja bar jednog mogućeg rješenja,
2. alternativa provjere je li određeno moguće rješenje optimalno ili nije,
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 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;
5
Petrić, J, nosioc podjele.
7
rješenje se podvrgava ispitivanju je li ono i optimalno. Ukoliko nije, tada se to rješenje također
poboljšava. Svaki takav korak se naziva iteracija.
Kada se utvrdi da je dobiveno rješenje optimalno ili da optimalno rješenje ne postoji, tada je
primjena metode završena. Ukoliko je dobiveno rješenje optimalno, tada slijedi očitavanje
optimalnih vrijednosti, kako varijabli tako i funkcije cilja, kako originalnog problema tako i
njegovog duala. Konačno dobiveno optimalno rješenje treba i tumačiti. S interpretacijom cijeli
postupak ne treba biti gotov jer se nakon toga može izvesti cijeli niz daljnjih analiza, od traženja
cjelobrojnog rješenja, ukoliko je to cilj postavljenog problema, traženja vrijednosti duala, pa do
analize osjetljivosti.
Postupak kojim se dobiva novo moguće rješenje, uz testiranje je li ono optimalno ili nije, naziva
se simpleks algoritam. Taj algoritam treba omogućiti sljedeće:
odabrati varijablu koja će zamijeniti neku od varijabli iz baze, tj. iz skupa bazičnih
rješenja,
odabrati varijablu koja će izaći iz baze,
transformirati sustav ograničenja na način da nova varijabla stvarno zamijeni staru,
uključujući i promjene u funkciji cilja;
utvrditi (testirati) je li novo rješenje (rješenje u bazi) optimalno ili nije, tj. je li dobivena
ili nije optimalna vrijednost funkcije cilja.
Detaljan opis i primjena simpleks metode, a time i simpleks algoritma je moguć:
a) u tabelarnom obliku,
b) bez tabelarnog prikaza.
Kao praktičniji, odnosno prihvatljiviji, prikazat će se prvi način u tabelarnoj formi. 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 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
