Indholdsfortegnelse:
Definition - Hvad betyder Simplex Method?
Simplex-metoden i matematisk optimering er en velkendt algoritme, der bruges til lineær programmering. Pr. Tidsskrift Computing in Science & Engineering betragtes denne metode som en af de top 10 algoritmer, der stammer fra i det tyvende århundrede.
Simplex-metoden præsenterer en organiseret strategi til evaluering af en gennemførlig regions vertikater. Dette hjælper med at finde ud af den optimale værdi af objektfunktionen.
George Dantzig udviklede simplex-metoden i 1946.
Metoden er også kendt som simplex-algoritmen.
Techopedia forklarer Simplex Method
Simplex-metoden bruges til at udrydde problemerne i lineær programmering. Det undersøger det gennemførlige sættets tilstødende hjørner i rækkefølge for at sikre, at objektivfunktionen for hver ny toppunkt øges eller ikke påvirkes. Generelt er simplex-metoden ekstremt kraftig, som normalt tager 2 til 3 m iterationer højst (her betegner m området for ligestillingsbegrænsninger), og den konvergerer i forventet polynomisk tid for specifikke fordelinger af tilfældige input.
Simplex-metoden bruger en systematisk strategi til at generere og teste kandidatens toppunktløsninger til et lineært program. Ved hver iteration vælger den den variabel, der kan foretage den største ændring mod minimumsløsningen. Denne variabel erstatter derefter en af dens covariables, som mest drastisk begrænser den, hvorved simplex-metoden flyttes til en anden del af løsningsættet og mod den endelige løsning.
Desuden er simplex-metoden i stand til at evaluere, om der faktisk ikke findes nogen løsning. Det kan observeres, at algoritmen er grådig, da den vælger den bedste mulighed ved hver iteration uden behov for information fra tidligere eller kommende iterationer.
Undertiden omtales den vigtigste datastruktur, der anvendes ved simplex-metoden, som en ordbog. Ordbøger inkluderer en illustration af de ligninger, der er korrekt afstemt til det eksisterende grundlag. Ordbøger kan bruges til at give en intuitiv forståelse af, hvorfor alle variabler går ind og forlader grundlaget.
