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

Presentation on theme: "第 七 回 双対問題とその解法 2003.5.8 山梨大学."— Presentation transcript:

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

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

3 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) 山梨大学

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

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

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

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

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

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

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

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

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

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

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

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