Simpleks metoda

George Dantzig radio je na načinima planiranja zrakoplovstva američke vojske tijekom Drugog svjetskog rata koristeći stolni kalkulator. Tijekom 1946. kolega ga je izazvao da mehanizira postupak planiranja kako bi ga odvratio od zaposlenja. Dantzig je problem formulirao kao linearne nejednakosti nadahnute radom Wassilya Leontiefa , međutim, u to vrijeme nije uključio cilj kao dio svoje formulacije. Bez cilja, ogroman broj rješenja može biti izvediv, i stoga za pronalaženje „najboljeg“ izvedivog rješenja moraju se koristiti vojno određena „osnovna pravila“ koja opisuju kako se ciljevi mogu postići za razliku od samoga određivanja cilja. Dantzigov temeljni uvid bio je shvatiti da se većina takvih osnovnih pravila može prevesti u linearnu objektivnu funkciju koju je potrebno maksimalno iskoristiti. Razvoj simpleks metode bio je evolucijski i dogodio se u razdoblju od oko godinu dana.
Nakon što je Dantzig uključio objektivnu funkciju kao dio svoje formulacije sredinom 1947., Problem je bio matematički više uočljiv. Dantzig je shvatio da je jedan od neriješenih problema koji je pogriješio kao domaći zadatak u klasi svog profesora Jerzyja Neymana (i zapravo kasnije riješen) bio primjenjiv u pronalaženju algoritma za linearne programe. Ovaj problem uključivao je pronalaženje Lagrangeovih množitelja za opće linearne programe preko kontinuuma varijabli, svaka ograničena između nule i jedne, i zadovoljavanje linearnih ograničenja izraženih u obliku Lebesgueovih integrala. Dantzig je svoju domaću zadaću kasnije objavio kao tezu da bi stekao doktorat. Geometrija stupaca korištena u ovoj tezi dala je Dantzigu uvid koji ga je natjerao da vjeruje da će Simplex metoda biti vrlo učinkovita.
Danas, 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.

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 . 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 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 :
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;
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.