ゲーム理論NEXT 線形計画問題第3回 -双対問題と双対定理-
はい、みなさんこんにちはこんばんは。S.Kと申します。
今回から双対問題と双対定理の話です。
動画としては、分離定理の話(第4回)、双対定理の証明（第5回）までアップロードできましたので、このシリーズの追加記事を書いていこうと思います。
双対定理とは、以下のようなものです。
双対定理（duality theorem）
主問題が最適解をもつならば双対問題も最適解をもち、その最適値が等しい
これを証明するために色々と準備してたのですが、その前に第3回では以下を証明しています。
まずは動画をどうぞ。
動画
ニコニコ動画
Youtube
スライドシェア
余談
いかがでしたでしょうか。
今回の定理は、
主問題と双対問題の実行可能解、それぞれにおいて目的関数の値が等しい最適値となるのであれば、その実行可能解はそれぞれの問題における最適解となる、ということです。
双対定理はこの逆で、主問題が最適解を持つならば、双対問題も最適解を持っていて、最適値が等しくなる、ということを主張しています。証明はこっちの方が複雑。第4回、第5回で説明。
そもそも双対問題を考える意義について、述べてないような気がします。一応補足しておくと、主問題・双対問題のどちらかの問題の方が解きやすかったりします。一方で最適解、最適値があれば、もう一方の問題の最適値が求まるわけですからね。
これ以外にもあるのですが、それはまたお話しします。
では、次回の記事でお会いしましょう。
参考文献
チャンネル
いいなと思ったら応援しよう！
