Innholdsfortegnelse:
Definisjon - Hva betyr Simplex Method?
Simplex-metoden, i matematisk optimalisering, er en kjent algoritme som brukes til lineær programmering. I tidsskriftet Computing in Science & Engineering regnes denne metoden som en av de 10 beste algoritmene som oppsto i løpet av det tjuende århundre.
Simplex-metoden presenterer en organisert strategi for å evaluere en mulig regionens toppunkt. Dette er med på å finne ut den optimale verdien av objektivfunksjonen.
George Dantzig utviklet simplex-metoden i 1946.
Metoden er også kjent som simplex-algoritmen.
Techopedia forklarer Simplex Method
Simplex-metoden brukes til å utrydde problemene i lineær programmering. Den undersøker det gjennomførbare settets tilstøtende vertikaler i rekkefølge for å sikre at objektivfunksjonen øker eller ikke påvirkes ved hvert nytt toppunkt. Generelt er simplex-metoden ekstremt kraftig, som vanligvis tar 2 til 3 m iterasjoner på det meste (her betegner m rekkevidden av likhetsbegrensninger), og den konvergerer i forventet polynomisk tid for spesifikke fordelinger av tilfeldige input.
Simplex-metoden bruker en systematisk strategi for å generere og teste kandidatens toppunktløsninger til et lineært program. Ved hver iterasjon velger den variabelen som kan gjøre den største modifiseringen mot minimumsløsningen. Den variabelen erstatter deretter en av dens samvariabler, som mest drastisk begrenser den, og forskyver dermed simplex-metoden til en annen del av løsningssettet og mot den endelige løsningen.
Videre er simplex-metoden i stand til å vurdere om ingen løsning faktisk eksisterer. Det kan observeres at algoritmen er grådig da den velger det beste alternativet ved hver iterasjon, uten behov for informasjon fra tidligere eller kommende iterasjoner.
Noen ganger blir den viktigste datastrukturen anvendt med simplex-metoden referert til som en ordbok. Ordbøker inkluderer en illustrasjon av ligningssettet som er riktig finjustert til det eksisterende grunnlaget. Ordbøker kan brukes til å gi en intuitiv forståelse av hvorfor alle variabler kommer inn og går fra grunnlaget.
