第三回 線形計画法の解法（１） 標準最大値問題 2003.4.17 山梨大学
内容と目標 内容 目標 LP問題のシンプレックス解法 Excelを用いてLP問題の解析をする スラック変数について復習 2003.4.17 山梨大学
LP問題のシンプレックス解法 第一回の演習問題（４）：生産計画問題 f = x1 +2 x2 ――＞ max (1) Subject to: 2003.4.17 山梨大学
スラック変数 式の左辺は原料a, b, cの使用量を表していたが、各原料の残りをλ1, λ2, λ3とする。原料の残りは1kgについて０万円の利益を生むと考えると、このLP問題は次のようになった： 2003.4.17 山梨大学
f = x1 +2 x2+ 0λ1+ 0λ2+ 0λ3 (3) 0.8x1+0.6 x2+λ1 ＝8.8 ➀ 2003.4.17 山梨大学
普通の連立１次方程式と異なる点は、変数の値に負数が許されないことである。 結局、最初の問題は表現を変えて、x1 , x2,λ1,λ2,λ3を変数とする連立１次方程式(4)の解で、(3)のｆの値を最大にするものを求めるということになる。 普通の連立１次方程式と異なる点は、変数の値に負数が許されないことである。 2003.4.17 山梨大学
シンプレックス表 連立１次方程式の計算と同じように、係数と定数のみを並べた表によって行うのがよい。この表はシンプレックス表とよばれている。 連立１次方程式の計算と同じように、係数と定数のみを並べた表によって行うのがよい。この表はシンプレックス表とよばれている。 ステップ１において基底列の変数と定数列の数を等号で結び、基底列にない変数を０とおくと x1=0, x2=0,λ1=8.8,λ2=6.4,λ3=4.0 で、これは基底解である。 2003.4.17 山梨大学
ステップ１のf行はfの増減判定に役立つ。すなわち、f行の最小負数-2に対応している変数x2が、最も有効にfを増加させる変数であるから、次のステップではx2を基底に取り入れる。θ列の最小値８に対する行の基底変数λ2が基底から追い出される変数である。 2003.4.17 山梨大学
λ2を基底から追い出して、代わりにｘ2を取り入れる計算、ステップ１からステップ２に移る計算は、次のようになる。 λ2を基底から追い出して、代わりにｘ2を取り入れる計算、ステップ１からステップ２に移る計算は、次のようになる。 １．基底列のλ2をｘ2に変えたものをステップ２の基底列にする。 2. 横ワク行の数をピボットの0.8で割ったものを、ステップ２のｘ2行にする。 2003.4.17 山梨大学
3. (2)でできたｘ2行に0.6を掛けたものを、ステップ１のλ１行から引いて、ステップ２のλ１行にする。 3. (2)でできたｘ2行に0.6を掛けたものを、ステップ１のλ１行から引いて、ステップ２のλ１行にする。 4. (2)でできたｘ2行に0.4を掛けたものを、ステップ１のλ3行から引いて、ステップ２のλ3行にする。 2003.4.17 山梨大学
5. (2)でできたｘ2行に２を掛けたものを、ステップ１のｆ行と「ｆの値」に加えて、ステップ２のｆ行と「ｆの値」にする。 5. (2)でできたｘ2行に２を掛けたものを、ステップ１のｆ行と「ｆの値」に加えて、ステップ２のｆ行と「ｆの値」にする。 基底列と定数列から、基底解は λ1=4, x2=8, λ3=0.8, x1=λ2=0 となり、それに対するｆの値がf=16であることも直に分かる。 2003.4.17 山梨大学
ステップ２のｆ行には負数が１つあり、変数x1が対応しているから、x1の値が増加するとｆの値も増加する。ゆえに、x1列に縦ワクをつけ、定数列の数を縦ワク列の数で割ってθ列を作り、その最小値２が対応しているλ3行に横ワクをつける。 2003.4.17 山梨大学
次はλ3を基底から追い出し、代わりにｘ１を基底に取り入れる計算である。その計算結果がステップ３である。 ここで、基底変数はλ1, x2, x1で、基底解は λ1=1.4, x2=7, x1=4, λ2=λ3=0 であり、ｆ＝18である。 2003.4.17 山梨大学
ステップ３のｆ行には負数がないから、どの変数を増加してもｆが増加することはない。したがって、この解がｆの最大値を与える唯一の解である。 このようにｆ行がすべて非負になると最適解が得られたことになるので、ｆ行がすべで非負になることを最適条件ということにする。 2003.4.17 山梨大学
課 題 目的関数： 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 2003.4.17 山梨大学