双対問題の概念
次のような問題が与えられていたとします。
目的関数
ｖ１ｘ１＋ｖ２ｘ２＋・・・＋ｖｎｘｎ → 最大
制約条件
ａ１１ｘ１＋ａ１２ｘ２＋・・・＋ａ１ｎｘｎ ≦ ｂ１
ａ２１ｘ１＋ａ２２ｘ２＋・・・＋ａ２ｎｘｎ ≦ ｂ２
・・・・・・・・・・・
ａｍ１ｘ１＋ａｍ２ｘ２＋・・・＋ａｍｎｘｎ ≦ ｂｍ
ｘ１，ｘ１，・・・，ｘｎ ≧ ０
この問題を、ｍ個の変数ｕ１，ｕ１，・・・，ｕｍ を考えることにりり、次のように変形します。
・制約式の右辺 ｂ を、目的関数の係数にする。
・目的関数の係数 ｖ を、制約式の右辺にする。
・制約式の不等号の向きを反対にする。
・制約式の係数 ａｉｊ の行と列をとりかえて、 ａｊｉ を係数とする。
・最大値問題を最小問題にする。
すなわち、次の式になります。
目的関数
ｂ１ｕ１＋ｂ２ｕ２＋・・・＋ｂｍｕｍ → 最小
制約条件
ａ１１ｕ１＋ａ２１ｕ２＋・・・＋ａｍ１ｕｍ ≧ ｖ１
ａ１２ｕ１＋ａ２２ｕ２＋・・・＋ａｍ２ｕｎ ≧ ｖ２
・・・・・・・・・・・
ａ１ｎｕ１＋ａ２ｎｕ２＋・・・＋ａｎｍｕｎ ≧ ｖｍ
ｕ１，ｕ１，・・・，ｕｎ ≧ ０
このように変形した問題を双対問題（双対－そうつい－Dual）といいます。これは元の問題を裏返しにした表現であり、元の問題は新しい問題の双対問題であるともいえます。
元の問題と双対問題の解には、次の対応があります。
・最適値はどちらも同じになる。
・双対問題の最適解 ｕoptｉ は、元の問題の制約式 ｂｉ のシャドウ・プライスになる。
（ｕoptｉ が０ならば、ｂｉ には余裕がある。）
・双対問題の ｖｊ のシャドウ・プライスは、元の問題の制約式 ｘｉ の最適解になる。
元の問題でのシャドウ・プライスとは、「その制約が少し変化したら、最適値がどれだけ変化するか」を示しています。そのため、最大化を図るということは、改善の余地を最小にすること、すなわちシャドウ・プライスを最小にするだといえます。
数値例
非常に簡単な数値例により、具体的に説明します。
●元の問題
目的関数
６ｘ１＋５ｘ２ → 最大
制約条件
２ｘ１＋１ｘ２ ≦ ５
３ｘ１＋４ｘ２ ≦ １０
●双対問題
目的関数
５ｕ１＋１０ｕ２ → 最小
制約条件
２ｕ１＋３ｕ２ ≧ ６
１ｕ１＋４ｕ２ ≧ ５
双対問題の定式化では、次の表を用いると便利です。
元の問題 双対問題
変数１ 変数２ 制約値 制約式１ 制約式２ 制約値
目的関数 ６ ５ → 最小 制約値 ６ ５ 最大
∧ ∧ ↑
制約式１ ２ １ ≦ ５ 変数１ ２ １ ５
制約式２ ３ ４ ≦ １０ 変数２ ３ ４ １０
元の問題の制約式を等号にしたときの点、ｘ１＝２，ｘ２＝１ が最適値であることは簡単にわかります。ここで、制約式を等号にするために、非負の変数λを導入します。
２ｘ１＋１ｘ２ ＋ λ１ ＝ ５
３ｘ１＋４ｘ２ ＋ λ２ ＝ １０
これを解くと、
ｘ１ ＝ ２－０.８λ１＋０.２λ２
ｘ２ ＝ １＋０.６λ１－０.４λ２
となり、目的関数は
６ｘ１＋５ｘ２ ＝ １７－１.８λ１－０.８λ２
となります。
すなわち、制約式１のシャドウ・プライスは－１.８、制約式２のシャドウ・プライスは－０.８になります。
同様に双対問題で、変数εを導入すれば、
２ｕ１＋３ｕ２ － ε１ ＝ ６
１ｕ１＋４ｕ２ － ε２ ＝ ５
ｕ１ ＝ １.８＋０.８ε１－０.６ε２
ｕ２ ＝ ０.８－０.２ε１＋０.４ε２
５ｕ１＋１０ｕ２ ＝ １７＋２ε１＋１ε２
になります。
これらから、前述した元の問題と双対問題での変数の最適値と制約式のシャドウ・プライスの関係が成立していることがわかります。
ここで、λとεについて考えてみましょう。
元の問題での制約式１を、
２ｘ１＋１ｘ２ ≦ ５ － λ１
とすれば、双対問題での目的関数は、
(５－λ１)ｕ１＋１０ｕ２ → 最小
となります。
ここで、λ１ を１単位変化させることは、制約式１の制約を１だけ変化させることです。そのときに目的関数の値が ｕ１ だけ変化するということは、ｕ１ が制約式１のシャドウ・プライスであることを示しています。
また、双対問題の制約式１を
２ｕ１＋３ｕ２ ≧ ６＋ε１
とすると、元の問題の目的関数は、
(６＋ε１)ｘ１＋５２ｘ２ → 最大
となります。
すなわち、ε１は、ｘ１の価値の増大分だと解釈できます。そして、制約式１の左辺は「ｘ１は、少なくとも６以上の
価値をもたなければならない」という意味だと解釈できます。双対問題の制約式は、変数ｘを使うことの価値、変数ｘをいくつにすればよいかに関する条件なのですから、そのシャドウ・プライスが変数ｘの最適値を示すことになるのです。