質問: 双対問題について教えてください。 変数がたくさんあるものがわからないです。 以下の問題の双対問題はどうなるか教えて下さい。 最大化:3x1+2x2+x3-x4+2x5 >条件:x1+3x2+2x3+x4+x5≦3 > xi≧0、i=1,2,3,4,5
回答: 双対問題は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 となります.