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

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

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

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

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

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

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

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

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

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

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

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

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

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

ｆ’行計算例 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 2003.4.24 山梨大学

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

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

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

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

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

課 題 目的関数 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 2003.4.24 山梨大学