双対問題について教えてください。

質問

変数がたくさんあるものがわからないです。
以下の問題の双対問題はどうなるか教えて下さい。
最大化：3X1+2X2+X3-X4+2X5
>条件：X1+3X2+2X3+X4+X5≦3
> 　　　Xi≧0、i=1,2,3,4,5

回答No.2

killer_7 · ベストアンサー

双対問題は1変数になりますよ．
s-125-_-さんがどういう知識をお持ちなのか書かれていないので答えにくいのですが，一般の線形計画問題について記します．

まず表記について書きます．
・ベクトル・行列の転置を^Tであらわします．
・ベクトル間の不等号をつぎのように導入します．
　n次元のベクトルx, yについて，
　x ≧ y <=> x_i ≧ y_i (i=1, ..., n)．
　（対応する要素間に不等号の関係が成り立つということ．
　例：(x y z)^T ≧ (1 2 3)^T <=> x≧1かつy≧2かつz≧3）

このとき，n次元ベクトルx,c，m×n行列A，m次元ベクトルbについての線形計画問題
最小化：　c^T x
制約条件：Ax ≦ b
　　　　　x ≧ 0
を主問題とすると，
双対問題は，m次元ベクトルyと，主問題とおなじA, b, cについての線形計画問題
最大化：　y^T b
制約条件：y^T A ≧ c^T
　　　　　y ≧ 0
となります．
ご質問の問題は，c = (3 2 1 -1 2)^T, x = (x_1 x_2 x_3 x_4 x_5)^T,
A = (1 3 2 1 1), b = (3)
で，双対問題は
最大化：3y
制約条件：y(1 3 2 1 1) ≧ (3 2 1 -1 2)
　　　　　y ≧ 0
となります．

回答No.3

killer_7

失礼．最小と最大を逆に書いてしまいました．
すべて逆に読み替えてください．

お礼

基本から丁寧に教えてくださってありがとうございました。
確認してみて理解することができました。
本当に感謝です。

回答No.1

Mr_Holland

自信はないけど、次のようになるのでは？

ｃT＝（-3 -2 -1 1 -2）
Ａ＝（-1 -3 -2 -1 -1）
ｂ＝-3

／　 -y1　＼　　　／　-3　＼
｜　-3y2　｜　　　｜　-2　｜
｜　-2y3　｜　≦　｜　-1　｜
｜ 　-y4　｜　　　｜　 1　｜
＼ 　-y5　／　　　＼　-2　／

行列をはずすと、y1≧3, 3y2≧2, 2y3≧1, y4≧-1, y5≧2
ここで、yi≧0, i=1,2,3,4,5だから、
制約条件：　y1≧3, y2≧2/3, y3≧1/2, y4≧0, y5≧2

また、最大化はyT bだから、
最小化：　3y1+3y2+3y3+3y4+3y5

行列が見にくいかもしれないけど、等角フォントにすればなんとか見られるかも。

参考URL：

http://next1.cc.it-hiroshima.ac.jp/MULTIMEDIA/linearProg/node5.html

お礼

丁寧に教えてくださってありがとうございました。
とてもわかりやすかったです。
参考URLまで載せてくださって本当にありがとうございました。