なぜ、双対問題（双対性）を考えるのですか？

現在、線形計画法を勉強中で、よくわからないことがあります。


例えばこのような問題があるとしまして、

主問題
max Z = 6X1 + 4X2（例えば収益を最大にしたい…）
s.t.　2X1 + X2 =< 70
　　　3X1 + 4X2 =< 180
　　　X1,X2 => 0

双対問題
min W = 70Y1 + 180Y2（例えば費用を最小にしたい…）
s.t.　2Y1 + 3Y2 => 6
　　　Y1 + 4Y2 => 4
　　　Y1,Y2 => 0

主問題の最適な目的関数値 Z と、
双対問題の最適な目的関数値 W は、必ず一致することは、
シンプレックス法で実際に解いて確認できます。できました。
（参考書として読んでいる本の、標準形での証明・説明はいまいちわかりませんでした…。）

ですが、

なんらかの収益を最大にしたい…という問題を定式化して解けば、
その収益を最大にしたいときの最適解・最適値を求められるなら
主問題の方だけ充分ではないのでしょうか？

上記の式の例ですと式の規模(？)に大した違いはないですが、
問題によって、双対問題に作り直した方が計算しやすい？
といったようなメリットがあるのですか？


なぜ、双対問題を考えるのか、どなたか分かりやすく教えて頂けませんでしょうか。

No.3 ベストアンサー 回答者： ur2c 回答日時： 2009/12/15 22:30

私も線形計画法で双対性を教わったとき、「だから何なんだ」でした。

しかしラグランジュ乗数法でわかって、線形計画法はその特殊な場合として納得できました。つまり少なくとも私の場合、ラグランジュ乗数法を経由しなければ双対性にどんな意味があるか、わかりませんでした。

f(x) を目的関数、g(x) = 0 を制約条件とすると、最適化問題 min_x {f(x) | g(x)=0} の解は、ラグランジュ関数 L(x,m) := f(x) + m g(x) の鞍点 dL/dx = dL/dm = 0 です。x が主変数、m が双対変数とかラグランジュ乗数と呼ばれるものです。

このとき　L を見てわかるのは、最適点においては g を目的関数と思って f を制約条件と思っても x は同じだ、ということです。つまり目的関数と制約条件との役割を入れ替えても解は同じです。

これを制約条件がたくさんある場合に一般化して言うと、最適点において目的関数は制約条件の 1 つと思ってかまわない、ということです。私はこの互換性が双対性の意味だと思ってます。

じゃあ、双対問題を考えると、どんな良いことがあるか？

No.1 で指摘されたように、ラグランジュ乗数、すなわち shadow price の経済的な意味がはっきりします。

主変数がたくさんあって制約条件が少なければ、双対問題の方が変数が少なくできます。すると、主問題より楽に解ける可能性が高いです。

L の鞍点を求めるのに、x に関する最小化と m に関する最大化を交互に行う解法が取れます。（主双対解法と言うのだと思います。）そうすると計算の途中でも「目的関数の最適値における値は、この値とあの値の間 (duality gap) にある」ということが言えます。つまり、とりあえず得られている解が最適解からどれくらい離れているかの評価ができます。

とは言え、最大の利点は先に述べた、目的関数と制約条件とを分けて考える必要がなくなるという、概念の単純化だと思います。「効用の最大化は費用の最小化」だけでも感動的ではないですか？

No.2 回答者： Duke_Mike 回答日時： 2009/12/15 02:33

(´・ω・｀)ノこんばんわ

数学者ではありませんが、双対性の問題は電気回路でも出てくるし
どこの分野でもあると思う。
まず双対性の議論をする前に双対性の定義を簡単に

Ａという集合があってＢという集合がある
Ａの中のある性質a,bをa→b　ｂ→aに入れ替えたときに
Ａで成り立つことがらがＢという場所でも成立する場合

ＡとＢに関して　a,bに関して双対性があるという風に言うのは
数学の群論だったかな？ではいいます。

人生論なんかでいくとあなたがある場所である経験をしたとします。
別の場所にいったら、今までの経験と対応したものがありそれが成立
していたとしたら、結構いいですよね？また今までの経験で有用だったものが別の場所でも有用であるということになります。

双対問題は今までの経験を新しい状況に対応させるまさに人生そのもの
の理論ではないかと思います。

何か趣旨をはずれていたらすいません。

この回答へのお礼

回答ありがとうございます。

いろいろ考えてみましたが、欲しい答えではない感じです…。

＞今までの経験で有用だったものが別の場所でも有用であるということになります。
今までの経験で有用だったもの…主問題の最適値？
別の場所でも有用である…双対問題の最適値？
つまり、主問題の最適値＝双対問題の最適値ということでしょうか。
そういうことは一応わかっているつもりです…。

＞双対問題は今までの経験を新しい状況に対応させるまさに人生そのものの理論
うーん。。。新しい状況に対応・・・。
最適な目的関数値は一致しますが、
主問題の変数 X と双対問題の変数 Y は表すものが違うんですよね。。。

やはり、抽象的な回答でよくわかりません。ごめんなさい。

お礼日時：2009/12/15 11:31

No.1 回答者： Tacosan 回答日時： 2009/12/14 23:30

双対の最適解から潜在価格 (shadow price) がわかるので, 感度分析に使えますね.

この回答への補足

回答ありがとうございます。

潜在価格…。これもよくわからないので質問しようかと思っていました。

＞双対の最適解から潜在価格 (shadow price) がわかるので, 感度分析に使えますね.
この潜在価格とは主問題の潜在価格でしょうか？
感度分析についてちょっと調べてみましたが、
感度分析に使えるとどんなメリット等あるのでしょうか？

潜在価格と感度分析についても教えて頂けませんでしょうか。

補足日時：2009/12/15 16:27