第四回 線形計画法（２） 混合最大値問題 2003.4.24 山梨大学.

Presentation on theme: "第四回 線形計画法（２） 混合最大値問題 2003.4.24 山梨大学."— Presentation transcript:

1 第四回 線形計画法（２） 混合最大値問題 山梨大学

2 内容と目標 内容： ２．ＬＰ問題と人為変数：罰金法 ３．ＬＰ問題と人為変数：２段階法 目標： １．シンプレックス表を十分に理解する
　 　１．シンプレックス表に起こる諸問題 　 ２．ＬＰ問題と人為変数：罰金法 　 ３．ＬＰ問題と人為変数：２段階法 目標： 　１．シンプレックス表を十分に理解する 　２．混合型ＬＰ問題を理解する 　３．人為変数の概念を理解する 山梨大学

3 スラック変数の導入 a11x1 + a12x2 + … + a1nxn+λ1 = b1
………………………………… am1x1 +am2x2 + … + amnxn　　　　　　　+λm= bm f ー c1x1 ー c2 x2… ー cnxn　　　　 = (2) 山梨大学

4 シンプレックス表（ステップ１） 基底 x1 x2 … xn λ1 λ2 … λm 定数 λ1 λ2 。 λm
a a12 … a1n … 0 a a22 … a2n … 0 am1 am2 … amn … 0 b1 b2 . bm f -c c1 … -cn … 0 山梨大学

5 シンプレックス表における 計算手順 (1) f行の最小負数の列に縦ワクをつける。
　(2)  定数列の数を縦ワク列の数で割ってθ列を作り、θ列の最小値の行に横ワクをつける。 　(3)  横ワク行の数をピボットで割り、ピボットの値を１にする。 山梨大学

6 (4) 横ワク行に適当な数を掛けて他の行から引き、ピボット以外の縦ワク列の数を０にする。これで新しいステップの表が完成する。
　(4) 横ワク行に適当な数を掛けて他の行から引き、ピボット以外の縦ワク列の数を０にする。これで新しいステップの表が完成する。 　(5)  上記(1)〜(4)を繰り返し、f行の数がすべて非負になれば最適解が得られている。 山梨大学

7 混合型LP問題の例 例： Max. f = 2x1 + 3x2 (3) 制約条件： 2x1+5x2 ≦ 20
山梨大学

8 スラック変数の導入 スラック変数を導入すると、 2x1+5x2+λ1 ＝ 20 3x1+2x2 ーλ2 ＝ 14 (5)
　　でも、これは標準形ではない！ 山梨大学

9 人為変数の導入 非負の（人為）変数μ2、μ3を導入すると 2x1+5x2+λ1 ＝ 20 3x1+2x2 ―λ2 +μ2 ＝ 14 (6)
「非常に大きな正数」Mを導入すると、 　　　　　f = 2x1+3x2-Mμ2-Mμ (7) Mはその性質から罰金とよばれる。 山梨大学

10 罰金法ー＞二段階法 罰金法： 二段階法 理解しやすい 計算機による計算のときは不便 第１段階：人為変数がすべて０になるような基底解を求める
第２段階：人為変数を条件式から除き、目的関数の最大化を行う 山梨大学

11 二段階法の例 まず人為変数が、すべて０になるような基底解を求めることを考える。そのために f’ = ーμ2 –μ3 (8)
　　まず人為変数が、すべて０になるような基底解を求めることを考える。そのために 　　　　　　　　f’ = ーμ2 –μ3　 (8) という式を考え、これを目的関数として条件(6)のもとで最大化する。これが第１段階である。 μ2, μ3は非負であるからf’=0になればμ2＝μ3＝０で、第１段階は終わりである。ここで、μ2、μ3を条件式から除き、目的関数をfにして最大化を行う。これが第２段階である。 山梨大学

12 二段階法での計算例 　　最初はf’行に注目して計算し、基底に人為変数がなくなったときf’行とμ2列、μ3列を除き、その後はf行に注目して計算を行なえばよい。 下の表は(3), (6), (8)から作られたシンプレックス表で、２段階法の計算例である。 山梨大学

13 二段階法のシンプレックス表 2003.4.24 山梨大学 ステップ 2 3 0 0 -1 -1 基底 x１ x2 λ１ λ2 μ2 μ3
基底 x１　 x λ１ λ2 μ μ3 定数 1 -1 1 2 μ3 20 14 6 f f’ -20 2 λ１ x1 3 / /3 / –1/3 / /3 32/3 14/3 4/3 / /3 / /3 28/3 -4/3 3 x2 /4 /2 /4 7 4 /4 11 8 12 山梨大学 μ3

14 fとf’行の計算 　　c行、c列にはfの係数とf’の係数を一緒に書いたので、ステップ１のf行、f’行を作るときに注意しなければならない。ｆの式(3)ではμ2、μ3の係数は０であるから、ｆ行を作るときはμ2、μ3に対するｃの値は０と考えて作らねばならないし、f’の式(8)ではμ2、μ3以外の変数の係数は０であるから、f’行を作るときはμ2、μ3以外のｃの値はすべて０と考えて作らねばならない。以下の表を参考して、例えば、 山梨大学

15 ｆ’行計算例 cj 定数 c1 c2 c3 a1 a2 a3 f’ c’j c’j = c1 a1 + c2 a2 + c3 a3 - cj
 定数 c1 c2 c3 a1 a2 a3 f’ c’j C 基底 c c’j = c1 a1 + c2 a2 + c3 a3 - cj 山梨大学

16 例3-1の説明 (1)ｆ行のx1列なら 0✕2 + 0✕3 + 0✕1 – 2 = -2 f’行のx1列なら
　　　0✕ ✕ ✕1 – 2 = -2 　　f’行のx1列なら　 　　　0✕2 +(-1)✕3 + (-1)✕1 - 0 = -4 (2) θの最小値が、どの行になるかは容易に見当がつくので、θ列は省略しても構いません。 山梨大学

17 (3)ステップ１のf’行には最小負数の-4が2つある。ここではx１列に縦ワクをつけたが、x2列につけてもよい。
(4)ステップ２でμ2が基底から追い出されたので、ここからはμ2は不要になり、μ2列の計算はやめることにした。 山梨大学

18 (5) ステップ３ではμ3が基底から追い出されたので、μ3列の計算もやめることにした。ここで、基底からすべての人為変数が追い出され、当然f’=0になり、第一段階の終わりである。この表では念のためにf’行が書いてあるが、基底に人為変数がなくなると同時にf’行も必要がなくなるから、本来ならここでf’行を表から省いてよい。 山梨大学

19 (6) ステップ３の表す条件式と目的関数の式は以下のとおりである。これ以降は条件(12)のもとで(13)のfを最大にする計算で、それが第２段階である。したがって、縦ワクはf行の最小負数につけてある。
山梨大学

20 (7) ステップ３以降は人為変数の列がすべて空白になり、定数列だけがはなれすぎるので、定数列を左に移動して、μ2列の下におくことを考えてもよい。
(8) この表はステップ４で最適解が得られ λ１=8, x１=6, λ2=4, x2=μ2=μ3=0, f=12 　 である。すなわち 　　　　　x１= 6, x2 = 0, f = 12 　 は最初の問題の最適解である。 山梨大学

21 課 題 目的関数 Max. f = 3x1+4x2 制約条件 x1＋ x2 ≦15 2x1 - x2 ≧7 - x1 +3x2≧9
課　　題 目的関数 　　　　　　Max. f = 3x1+4x2 　制約条件 　　　　　x1＋ x2 ≦15 　2x1 - x2 ≧7 　- x1 +3x2≧9 　 x1, x2≧0 解答：　x1=22/3, x2=23/3, f=158/3 山梨大学