Schwacher Dualitätssatz

Ist $x$ zulässig für das primale Problem und $(\lambda ,\mu )$ zulässig für das duale Problem, dann gilt: $p(\bar{x})=f(\bar{x})\ge d(\bar{\lambda },\bar{\mu })$ Also das duale Problem ist eine untere Schranke für den optimalen ZFW des primalen Problems.

Für ein typisches LP: $b^{\top }y\le c^{\top }x\text{ fu¨r alle }x\in \mathcal{F}\text{. }$

Beweis: Da alle Gleichungsnebenbedingungen gleich 0 sind und alle Ungleichungsnebenbedingungen kleiner gleich 0 sind und alle $\mu \ge 0$ sind, gilt: $d(\bar{\lambda },\bar{\mu })={\inf }_{x\in {\mathbb{R}}^n}\mathcal{L}(x,\bar{\lambda },\bar{\mu })\le \mathcal{L}(\bar{x},\bar{\lambda },\bar{\mu })=f(\bar{x})+\underset{=0}{\underbrace{{\bar{\lambda }}^{\top }h(\bar{x})}}+\underset{\le 0}{\underbrace{{\bar{\mu }}^{\top }g(\bar{x})}}\le f(\bar{x})=p(\bar{x}).$