第三回 - 山梨大学工学部 土木環境工学科

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