Schwacher Dualitätssatz

Ist xx zulässig für das primale Problem und (λ,μ)(\lambda, \mu) zulässig für das duale Problem, dann gilt:

p(xˉ)=f(xˉ)≥d(λˉ,μˉ)p(\bar{x})=f(\bar{x}) \geq 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⊤y≤c⊤x fu¨r alle x∈F. b^{\top} y \leq c^{\top} x \quad \text { für alle } x \in \mathcal{F} \text {. }

Beweis: Da alle Gleichungsnebenbedingungen gleich 0 sind und alle Ungleichungsnebenbedingungen kleiner gleich 0 sind und alle μ≥0\mu \ge 0 sind, gilt:

d(λˉ,μˉ)=inf⁡x∈RnL(x,λˉ,μˉ)≤L(xˉ,λˉ,μˉ)=f(xˉ)+λˉ⊤h(xˉ)⏟=0+μˉ⊤g(xˉ)⏟≤0≤f(xˉ)=p(xˉ).d(\bar{\lambda}, \bar{\mu})=\inf _{x \in \mathbb{R}^{n}} \mathcal{L}(x, \bar{\lambda}, \bar{\mu}) \leq \mathcal{L}(\bar{x}, \bar{\lambda}, \bar{\mu})=f(\bar{x})+\underbrace{\bar{\lambda}^{\top} h(\bar{x})}_{=0}+\underbrace{\bar{\mu}^{\top} g(\bar{x})}_{\leq 0} \leq f(\bar{x})=p(\bar{x}) .