第三回 線形計画法の解法（１） 標準最大値問題 2003.4.17 山梨大学.

Presentation on theme: "第三回 線形計画法の解法（１） 標準最大値問題 2003.4.17 山梨大学."— Presentation transcript:

1 第三回 線形計画法の解法（１） 標準最大値問題 山梨大学

2 内容と目標 内容 目標 LP問題のシンプレックス解法 Excelを用いてLP問題の解析をする スラック変数について復習
山梨大学

3 LP問題のシンプレックス解法 第一回の演習問題（４）：生産計画問題 f = x1 +2 x2 ――＞ max (1) Subject to:
山梨大学

4 スラック変数 式の左辺は原料a, b, cの使用量を表していたが、各原料の残りをλ1, λ2, λ3とする。原料の残りは1kgについて０万円の利益を生むと考えると、このLP問題は次のようになった： 山梨大学

5 f = x1 +2 x2+ 0λ1+ 0λ2+ 0λ3 (3) 0.8x1+0.6 x2+λ1 ＝8.8 ➀
山梨大学

6 普通の連立１次方程式と異なる点は、変数の値に負数が許されないことである。
　　結局、最初の問題は表現を変えて、x1 , x2,λ1,λ2,λ3を変数とする連立１次方程式(4)の解で、(3)のｆの値を最大にするものを求めるということになる。 　　普通の連立１次方程式と異なる点は、変数の値に負数が許されないことである。 山梨大学

7 シンプレックス表 連立１次方程式の計算と同じように、係数と定数のみを並べた表によって行うのがよい。この表はシンプレックス表とよばれている。
　　連立１次方程式の計算と同じように、係数と定数のみを並べた表によって行うのがよい。この表はシンプレックス表とよばれている。 　　ステップ１において基底列の変数と定数列の数を等号で結び、基底列にない変数を０とおくと 　　x1=0, x2=0,λ1=8.8,λ2=6.4,λ3=4.0 で、これは基底解である。 山梨大学

8 　ステップ１のf行はfの増減判定に役立つ。すなわち、f行の最小負数-2に対応している変数x2が、最も有効にfを増加させる変数であるから、次のステップではx2を基底に取り入れる。θ列の最小値８に対する行の基底変数λ2が基底から追い出される変数である。 山梨大学

9 λ2を基底から追い出して、代わりにｘ2を取り入れる計算、ステップ１からステップ２に移る計算は、次のようになる。
　　λ2を基底から追い出して、代わりにｘ2を取り入れる計算、ステップ１からステップ２に移る計算は、次のようになる。 　１．基底列のλ2をｘ2に変えたものをステップ２の基底列にする。 　2. 　横ワク行の数をピボットの0.8で割ったものを、ステップ２のｘ2行にする。 山梨大学

10 3. (2)でできたｘ2行に0.6を掛けたものを、ステップ１のλ１行から引いて、ステップ２のλ１行にする。
　3.  (2)でできたｘ2行に0.6を掛けたものを、ステップ１のλ１行から引いて、ステップ２のλ１行にする。 　4.  (2)でできたｘ2行に0.4を掛けたものを、ステップ１のλ3行から引いて、ステップ２のλ3行にする。 山梨大学

11 5. (2)でできたｘ2行に２を掛けたものを、ステップ１のｆ行と「ｆの値」に加えて、ステップ２のｆ行と「ｆの値」にする。
　 5.  　(2)でできたｘ2行に２を掛けたものを、ステップ１のｆ行と「ｆの値」に加えて、ステップ２のｆ行と「ｆの値」にする。 基底列と定数列から、基底解は 　　　λ1=4, x2=8, λ3=0.8, x1=λ2=0 となり、それに対するｆの値がf=16であることも直に分かる。 山梨大学

12 ステップ２のｆ行には負数が１つあり、変数x1が対応しているから、x1の値が増加するとｆの値も増加する。ゆえに、x1列に縦ワクをつけ、定数列の数を縦ワク列の数で割ってθ列を作り、その最小値２が対応しているλ3行に横ワクをつける。 山梨大学

13 次はλ3を基底から追い出し、代わりにｘ１を基底に取り入れる計算である。その計算結果がステップ３である。
ここで、基底変数はλ1, x2, x1で、基底解は 　　　　　λ1=1.4, x2=7, x1=4, λ2=λ3=0 であり、ｆ＝18である。 山梨大学

14 ステップ３のｆ行には負数がないから、どの変数を増加してもｆが増加することはない。したがって、この解がｆの最大値を与える唯一の解である。
　このようにｆ行がすべて非負になると最適解が得られたことになるので、ｆ行がすべで非負になることを最適条件ということにする。 山梨大学

15 課 題 目的関数： Max. f=10x1+12x2 制約条件 8x1＋5x2≦3800 4x1+9x2≦4500 3x1+4x2≦3800
課 　題 目的関数： 　　　　　　Max.　f=10x1+12x2 制約条件 　　　　　8x1＋5x2≦3800 　4x1+9x2≦4500 　3x1+4x2≦3800 　　x1, x2 ≧0 　解答： x1=225, x2=400, f=7050　　　 山梨大学