まず,強双対性定理を述べよう.

定理(強双対性定理)主問題の制約条件を満たす $x$ が存在し主問題の目的関数の値が上に有界であることと双対問題の制約条件を満たす $y$ が存在し双対問題の目的関数の値が下に有界であることは同値である.また,そのとき主問題と双対問題はいずれも最適解を持ち,しかも主問題の目的関数の最大値と双対問題の目的関数の最小値は一致する.

前半の証明.まず,前半を示す.主問題の制約条件を満たす $x$ の存在を仮定し,さらに主問題の目的関数の値が上に有界であるとする.このとき双対問題の制約条件 $y'\cdot A\ge c'$ を満たす非負解 $y\ge 0$ が存在しないなら,前回の命題2より,$A\cdot z\le 0$ かつ $c'\cdot z>0$ となるような非負ベクトル $z\ge 0$ が存在する.そこで,$\theta\ge 0$ として,$x_{\theta}=x+\theta\cdot z$ とする.すると,$A\cdot x_{\theta}\le b$ となる.すなわち,$x_{\theta}$ は主問題の制約条件を満たしている.また,$c'\cdot x_{\theta}=c'\cdot x+\theta(c'\cdot z)$ で $c'\cdot z>0$ であるから,$\theta\to+\infty$ とすれば,$c'\cdot x_{\theta}\to+\infty$ となる.これは主問題の目的関数の値が上に有界であることに矛盾する.したがって,双対問題の制約条件を満たすような非負ベクトル $y$ が存在しなければならない.また,主問題の制約条件を満たす $x$ が存在することから,弱双対性定理より,双対問題の目的関数の値は下に有界である.この逆も命題1を用いて同様に示すことができる.$\square$