第 七 回 双対問題とその解法 2003.5.8 山梨大学

内容と目標 内容： 目標： １．双対問題 ２．双対問題のシンプレックス方法 １．双対問題を復習する ２．自分で双対問題を作る ３．シンプレックス方法で双対問題を解析する 2003.5.8 山梨大学

LP問題のシンプレックス法 LP問題の解法 目的関数ｆ(x) 標準のシンプレックス法：Max. f(x) ＜ー＞ g(x)c 2) Min. f(x) ＜ー＞ g(x) c 3) Min. f(x) ＜ー＞ g(x) , =, c 目的関数ｆ(x) 標準：　　Max. f(x) 最小値問題：　Min. f(x) 　　　　 Min. f(x) ー＞Max. f0(x) Max. f’(x)=-i ただし、f0(x) = -f(x) 2003.5.8 山梨大学

制約条件の処理 最小不等式： g(x)c 等式： g(x)=c 最大不等式: g(x)c スラック変数： g(x)+λ=c スラック変数と人為変数を利用する g(x)ーλ＋ μ =c 2003.5.8 山梨大学

最小値問題ー原問題 目的関数： Min. f = 2x1 + 19x2 + 7x3 (1) 制約条件： 2003.5.8 山梨大学

二段階法 制約条件： x1+12x2+6x3 -λ1 +μ1 ＝ 4 2x1+18x2+4x3 -λ2 +μ2 ＝ 3 (4) 目的関数： 　　 　　 f0 = - 2x1 - 19x2 - 7x3　　 　　 (5) 　　　　　 f’ = -μ1 -μ2 　　　 　　　　　　 (6) 2003.5.8 山梨大学

二段階法のシンプレックス表 ステップ -2 -19 -7 0 0 基底 x１ x2 x3 λ１ λ2 定数 θ 1 -1 μ1 μ2   -2 -19 -7 0 0 基底 x１　 x2 x3 λ１ λ2 定数 θ 1 -1 μ1 μ2 1 12 6 2 18 4 -1 0 0 -1 4 3 1/3 1/6 f0 f’ 2 19 7 -3 -30 -10 0 0 1 1 -7 2 -19 x2 -1/3 0 10/3 1/9 1 2/9 -1 2/3 0 -1/18 3/5 3/4 -1/9 0 25/9 1/3 0 -10/3 0 1 1 -2/3 -19/6 -2 x3 -1/10 0 1 2/15 1 0 -3/10 1/5 1/15 -1/10 1/30 1/6 0 0 0 0 0 5/6 1/2 -29/6 c 2003.5.8 山梨大学

双対問題：最小化ー＞最大化 　以上の例の最小化問題の不等号制約式(2)、(3)に対し、非負のy1 , y2を対応させる。そして(2)×y1+(3)×y2を計算すると　(y1+2y2)x1+(12y1+18y2)x2+(6y1+4y2)x3 　　　　　≧ 4y1+3y2 　　　 (7) となる。 2003.5.8 山梨大学

制約条件の変化 ここで y1 + 2y2 ≦ 2 12y1+18y2 ≦ 19 (8) 6y1 + 4y2 ≦ 7 と仮定すると、式(7)は 2x1+19x2+7x3 ≧ 4y1+3y2 となる。 2003.5.8 山梨大学

新しい最大値問題？ 　　変数x1, x2, x3は、上述最小化問題の制約条件下2x1+19x2+7x3の最小化に関連したが、新しく導入された変数y1, y2も何かの最適化問題に関連しているようである。新しい変数に与えられた条件、つまり式(8)と非負条件下で4y1+3y2の最大化問題を考えてみる。 2003.5.8 山梨大学

標準LP問題 目的関数： Max. f = 4y1+3y2 (9) 制約条件： y1 + 2y2 ≦ 2 2003.5.8 山梨大学

標準LP問題のシンプレックス表 ステップ c 4 3 0 0 0 基底 y1 y2 λ1 λ2 λ3 定数 θ 1 λ1 λ2 λ3 1 2   4 3 0 0 0 基底 y1 y2 λ1 λ2 λ3 定数 θ 1 λ1 λ2 λ3 1 2 12 18 6 4 2 19 7 11/7 7/6 f -4 -3 4 y1 0 4/3 0 10 1 2/3 1 0 -1/6 0 1 -2 0 0 1/6 5/6 5 5/8 1/2 7/4 0 -1/3 0 0 2/3 14/3 3 y2 0 0 0 1 1 0 1 -1/7 0 0 1/10 -1/5 0 0 2/7 1/6 0 0 0 0 3/5 29/6 2003.5.8 山梨大学

結果の説明 (i) 基底変数はλ1、y1、y2で、非基底変数はλ2 、 λ3である。 (ii) 最適基底解は 　 　　y1 =5/6, y2 =1/2, λ1 =1/6, f=29/6 である。 この解は例(1)に示した原問題の最大値と全く同じになる。しかし、計算は簡単になった。 2003.5.8 山梨大学

課 題 目的関数： Min. f = 4x1 + 5x2 (1) 制約条件 x1+3x2 ≧ 4 2x1+ x2 ≧ 3 (2) 課　　　題 目的関数： 　　 　　　 Min. f = 4x1 + 5x2 　　　　　　　　　　(1) 制約条件 x1+3x2 ≧ 4 2x1+ x2 ≧ 3 　　 　　　　 (2) x1 , x2 ≧0 要求： 1).　シンプレックス法を用いて解け。 2).　上記の線形計画問題の双対問題を作れ。 3).　双対問題をシンプレックス法で解け。 4). 原問題のスラック変数・最適解と双対問題のスラック変数・最適解を比較せよ。 2003.5.8 山梨大学

課題の解答 1). 最適解はx1=1, x2=1, f=9. 3). 双対問題の最適解はy1=6/5, y2=7/5,f’=9. 2003.5.8 山梨大学