線形計画

質問

線形計画の双対問題についてわからないところがあるので教えてください。

http://home.hiroshima-u.ac.jp/~kato/b_mp1/MP1_12_20061219_an...双対問題'

の（２）の問題の解答のところなんですけど

最初に標準形に変換するときなんでわざわざＸ2＝Ｘ2+　－　Ｘ2-　としているのでしょう？
普通にＸ3を追加して＝にしＭＡＸの符号を変えてＭＩＮにすればいいのではないでしょうか？
またここではＸ2を1行目のようにしてますがこれはＸ1ではいけないのでしょうか？

わかりにくい質問かと思いますが教えてください。

回答No.1

kts2371148 · ベストアンサー

リンクがきちんと貼れていないようです。
正しいリンク先は、
http://home.hiroshima-u.ac.jp/~kato/b_mp1/MP1_12_20061219_answers.pdf
です。

問題に、「x1≧0 , x2 は自由変数」とあります。
これは、x1 は非負条件がついていますが、
x2 には非負条件がついていない（負でもよい）ことを意味します。
しかし、標準形では、すべての変数に非負条件がつき、
x1≧0 , x2≧0 , … , xn≧0 になります。
ですから、何も工夫をしないと、

subject to
　a11x1 + a12x2 ≧ b1
　a21x1 + a22x2 ＝ b2
　x1≧0 , x2 は自由変数

を解きたいのに、

subject to
　a11x1 + a12x2 ≧ b1
　a21x1 + a22x2 ＝ b2
　x1≧0 , x2≧0

を解くことになってしまいます。

それで、x2 = x2[+] - x2[-] とおきます。
x2[+]≧0 , x2[-]≧0 の条件をつけても、
x2 はどんな値も（正でも負でも）とり得ることになります。
それで、

subject to
　a11x1 + a12x2 ≧ b1
　a21x1 + a22x2 ＝ b2
　x1≧0 , x2 は自由変数

を解くことは

subject to
　a11x1 + a12x2[+] - a12x2[-] ≧ b1
　a21x1 + a22x2[+] - a12x2[-] ＝ b2
　x1≧0 , x2[+]≧0 , x2[-]≧0

を解くことと同じことです。
あとは、x3 を追加して max を min に変えればＯＫです。