Utgangspunktet for Simplex

Simplex er en metode som brukes i lineære programmeringsproblemer for å få løsninger på lineære programmeringsproblemer. Som en oppsummering innebærer et lineært programmeringsproblem å bestemme maksimums- eller minimumsverdien til en objektivfunksjon gitt et sett med begrensninger. Begrensningene ville danne grensen til et polyeder. Under forutsetningene om at begrensningssettet er konveks, vil ethvert toppunkt i polyederet gi en ekstrem verdi av objektivfunksjonen enten maksimum eller minimum.

På grunn av at den mulige grensen er konveks, vil et toppunkt gi et lokalt minimum som også er det globale minimumet. På samme måte i en konkav funksjon vil det lokale maksimumet også være det globale maksimumet på grunn av at funksjonen er konkav. Å gjengi en konveks funksjon er en der et punkt på funksjonen alltid faller innenfor linjen som er koblet mellom to punkter på funksjonens grense.

Simplex-metoden starter med å sette verdien av de ikke-grunnleggende variablene til 0 og fortsetter deretter med å finne ut den optimale verdien av objektfunksjonen ved å identifisere retninger for bratteste forsterkning eller reduksjon av verdien til objektfunksjonen. Men simplex antar et utgangspunkt der de ikke-grunnleggende variablene er satt til 0 hver. Den optimale verdien av objektivfunksjonen blir funnet etter flere iterasjoner der algoritmen velger et toppunkt med maksimal forsterkning av objektivfunksjonens absolutte verdi. Simplex -metoden er effektiv da den ikke oppregner alle mulige løsninger, men konvergerer til den faktiske verdien i et færre antall søk.

Her hvis det er 4 eller 5 hjørner av polyederet og den optimale løsningen blir funnet etter 5 iterasjoner (for eksempel), bør man forstå at det er en iboende antagelse om at den første mulige løsningen bestemmes ved å sette de ikke-grunnleggende variablene til 0 som er (0,0) koordinaten til polyederet.

Her bemerkes det at man ved å fikse de ikke-grunnleggende variablene til 0 som utgangspunktet for simplexen kan anta et utgangspunkt som er langt borte fra det optimale. Så Simplex kan revideres for å gi et intelligent gjettestimat om hvor iterasjonene må begynne. Antall kjøringer av Simplex er omtrent proporsjonal med kraften i antall begrensninger. Man kan bruke noen sannsynlighetsmetoder og utlede heuristiske regler for å få Simplex til å begynne på et tidspunkt nær det optimale.