Lineare Ungleichungen und Optimierung

Entscheidungsproblem:

• Eingabe: Constraintsystem,
• gesucht: eine erfüllende Belegung

Optimierungsproblem:

• Eingabe: Constraintsystem und Zielfunktion (linearer Ausdruck in Unbekannten)
• gesucht: eine optimale erfüllende Belegung (d. h. mit größtmöglichem Wert der Zielfunktion)

Standard-Form des Opt.-Problems:
A⋅x^T = b, x^T≥ 0, minimiere c⋅x^T.

Ü: reduziere OP auf Standard-OP, reduziere EP auf OP