Hoppa till innehållet

Simplexmetoden

Tillbaka

METOD

Simplexmetoden

När och varför

I linjär optimering ligger optimum i ett hörn. I två variabler räcker hörnjämförelse; simplex gör samma sak systematiskt i högre dimension.

Härledning

Linjär målfunktion på en polyeder antar max/min i ett hörn. Simplex vandrar systematiskt mellan tills z inte kan förbättras.

Motivering

Simplex finner max/min för linjär z under linjära genom att vandra mellan — exakt när målfunktionen är linjär.

Exempel

  1. Maximera z = 2x + 5y under x ≥ 0, y ≥ 0, 3x + 4y ≤ 12(hörn)
  2. Hörnen (0; 0), (4; 0), (0; 3) ger z = 0, 8, 15(jämför)
  3. Max z = 15 i (0; 3)

Kontroll: 3 · 0 + 4 · 3 = 12 på randen; 2 · 0 + 5 · 3 = 15 ✓

Läs mer på Grokipedia (öppnas i ny flik)