Inhoudsopgave:
Definitie - Wat betekent Simplex-methode?
De simplex-methode, in wiskundige optimalisatie, is een bekend algoritme dat wordt gebruikt voor lineair programmeren. Volgens het tijdschrift Computing in Science & Engineering wordt deze methode beschouwd als een van de top 10 algoritmen die in de twintigste eeuw zijn ontstaan.
De simplex-methode presenteert een georganiseerde strategie voor het evalueren van de vertices van een haalbare regio. Dit helpt om de optimale waarde van de objectieve functie te achterhalen.
George Dantzig ontwikkelde de simplex-methode in 1946.
De methode is ook bekend als het simplex-algoritme.
Techopedia legt de Simplex-methode uit
De simplex-methode wordt gebruikt om de problemen in lineair programmeren op te lossen. Het onderzoekt achtereenvolgens de aangrenzende hoekpunten van de haalbare set om ervoor te zorgen dat bij elke nieuwe top de objectieve functie toeneemt of niet wordt beïnvloed. Over het algemeen is de simplex-methode extreem krachtig, die meestal maximaal 2m tot 3m iteraties nodig heeft (hier geeft m het bereik van gelijkheidsbeperkingen aan), en deze convergeert in verwachte polynoomtijd voor specifieke verdelingen van willekeurige invoer.
De simplex-methode maakt gebruik van een systematische strategie om kandidaat-hoekpuntoplossingen voor een lineair programma te genereren en te testen. Bij elke iteratie kiest het de variabele die de grootste wijziging in de richting van de minimale oplossing kan aanbrengen. Die variabele vervangt dan een van zijn covariabelen, die hem het meest drastisch beperkt, waardoor de simplex-methode naar een ander deel van de set oplossingen wordt verplaatst en in de richting van de uiteindelijke oplossing.
Bovendien kan de simplex-methode evalueren of er geen oplossing bestaat. Opgemerkt kan worden dat het algoritme hebzuchtig is omdat het bij elke iteratie voor de beste optie kiest, zonder vraag naar informatie uit eerdere of komende iteraties.
Soms wordt de belangrijkste datastructuur die wordt toegepast door de simplex-methode een woordenboek genoemd. Woordenboeken bevatten een illustratie van de set vergelijkingen die goed zijn afgestemd op de bestaande basis. Woordenboeken kunnen worden gebruikt om een intuïtief begrip te geven van waarom alle variabelen de basis binnenkomen en verlaten.
