Dualität (Lineare Optimierung)

Gegeben sei ein lineares Optimierungsproblem in der Form

Maximiere unter den Nebenbedingungen

Das Problem

Minimiere unter den Nebenbedingungen

nennt man das zu duale Problem .

Aussagen

1. Einem primalen Maximierungsproblem entspricht ein duales Minimierungsproblem
2. Einer -Restriktion in primalen Problemen entspricht eine im Vorzeichen beschränkte () Dualvariable; zu einer Gleichheitsrestriktion gehört eine unbeschränkte ( Dualvariable.
3. (Gleiches gilt in die andere Richtung)
4. Seien eine zulässige Lösung des primalen Problems und eine zulässige Lösung des zugehörigen dualen Problems, dann gilt
5. Seien eine optimale Lösung des primalen Problems und eine optimale Lösung des zugehörigen dualen Problems, dann gilt Einschließungssatz:

Dualisierung - Beispiel

Primales Problem

Maximiere unter den Nebenbedingungen

Duales Problem

Minimiere unter den Nebenbedingungen