Lineare Optimierung[Bearbeiten]
Auf dieser Seite wird die lineare Optimierung behandelt. Eine lineare Optimierungsaufgabe ist: Maximiere eine lineare Funktion in mehreren Variablen
.
Die lineare Nebenbedingung sind gegeben als lineare Gleichungen:
...
Dies entspricht dem Gleichungssystem:
Doch ist das ausdrucksstark genug für unsere Probleme?
Umformung von Gleichungssystemen[Bearbeiten]
Beliebige Systeme lassen sich in die Standardform übertragen.
- Minimieren ist wie maximieren:

Bedingungen statt
Bedingungen: 
- Gleichung zu Ungleichung:

- Ungleichung zu Gleichung (Schlupfvariablen einführen):

kann negativ sein: 
Beispiel Gewinnmaximierung[Bearbeiten]
Eine Firma produziert zwei verschiedene Waren. Ware
erbringt einen Gewinn von einem Euro. Ware
erbringt einen Gewinn von 6 Euro. Die Frage hierzu lautet, welches Verhältnis von
und
führt zum größten Gewinn? Dazu gibt es zwei Nebenbedingungen:
- Die Firma kann täglich maximal 200 Einheiten der Ware
produzieren und maximal 300 Einheiten der Ware 
- Insgesamt kann die Firma maximal 400 Einheiten pro Tag produzieren
Die Firma beschließt eine weitere Ware zu produzieren.
- Die Ware
bringt einen Gewinn von 13 Euro.
- Die maximale Tagesproduktion liegt weiterhin bei 400 Einheiten.
- Für die Produktion von Ware
und Ware
wird dieselbe Maschine verwendet, allerdings ist der Produktionsaufwand für
dreimal höher. Insgesamt kann die Maschine 600 Arbeitsschritte leisten.
Formuliere, die Zielfunktion:
.
Anschließend formuliere die Nebenbedingungen:
Die Nebenbedingungen definieren ein drei-dimensionales Polyeder, in dem die optimale Lösung liegt.
Nun formen wir in die Normalform um:
Die Nebenbedingungen definieren nun ein Polyeder, in dem die optimale Lösung liegt.
Die Zielfunktion
ist eine Gerade. Nun wird die Gerade verschoben, bis das Maximum erreicht ist.
Die Linearen Optimierungsprobleme der Form
besitzen genau dann eine endliche Optimallösung, wenn sie eine optimale Ecklösung (= „Ecke“ des zugehörigen Polyeders) besitzen. D.h. man muss zur Lösungsfindung nur die Ecken des Polyeders betrachten.