Satz vom komplementären Schlupf

Für lineare Optimierungsprobleme in Gleichungsform (Normalform oder kanonische Form) besagt der Satz vom komplementären Schlupf, dass die beiden zulässigen Punkte (x,u) (des primalen Problems) und (y,w) (des dualen Problems) genau dann optimal sind, wenn die Komplementaritätsbedingungen Xi * Wi = 0 für alle i bzw. Yj * Uj = 0 für alle j erfüllt ist.

 

D.h. wenn das Skalarprodukt der primalen Entscheidungsvariablen und dualen Schlupfvariablen gleich 0 ist – und umgekehrt!