Simplexmetoden
TillbakaMETOD
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
- Maximera z = 2x + 5y under x ≥ 0, y ≥ 0, 3x + 4y ≤ 12(hörn)
- Hörnen (0; 0), (4; 0), (0; 3) ger z = 0, 8, 15(jämför)
- Max z = 15 i (0; 3)
Kontroll: 3 · 0 + 4 · 3 = 12 på randen; 2 · 0 + 5 · 3 = 15 ✓