【双対問題と双対定理】

==================================================================
●【双対問題と双対定理】●
==================================================================
▼1.1【双対問題】【双対問題の定義】
線形計画問題には、それと対をなす双対問題が存在し、元の問題を主問題と呼ぶ。

 

▼1.2【双対問題】【一般形の線形計画問題の双対問題の例】
例がある

▼2.1【双対定理】【弱双対定理と双対定理】
弱双対定理：両問題が実行可能ならば、主問題の目的関数値は、常に、双対問題の目的関数値より大きい。

双対ギャップ：両問題が実行可能な場合のみ、
（主問題の目的関数） - （双対問題の目的関数） = 双対ギャップ
という

主問題と双対問題に対して成り立つこと：
①弱双対定理
②両問題が実行可能ならば、それぞれ最適解を持つ
③主問題が実行可能で非有界ならば、双対問題は実行不能である
④それぞれの実行可能解で、主問題と双対問題の目的関数値が一致した場合、それが最適解。

双対定理：主問題が最適解を持つならば、双対問題も最適解を持ち、その最適値が等しい。

相補性条件：両問題の実行可能解において、主問題の解と双対問題のスラック変数の積（双対ギャップ）が「0」だから、必ずどちらかが「0」


▼2.2【双対定理】【主問題と双対問題の例】
例がある


▼2.3【双対定理】【分離定理】
やってない