←【アプリケーション総論】シラバスへ
←講義のツボメニューへ

線形計画法２

【2001.05.31 ２限　第７回】
１．シンプレックス法の実際
発表者：鈴木（雄）
シンプレックス法：前回のような考え方に基づく計算を系統的に行う方法。
では、この例題に基づいて、シンプレックス法の計算プロセスを提示する。

前回のおさらい
非負変数x,y(x>=0,y>=0)において、
　　2x+ y<=100
　　3x+6y<=240
の制約条件式の元で、
　　z=2x+3y
で表される目的関数の値をできるだけ大きく（最大に）するような、xおよびyの値を求めること。

  1. 制約条件式を等式にする
    シンプレックス法では、まず、不等式で表された制約条件式を、等式条件にすることから始まる。
    そのために、前回の最後と同様に陳列スペースの余りをu、予算の余りをvとして、以下のように表す。
    2x+y+u=100
    3x+6y+v=240
    ちなみに、uやvのような変数のことを余裕変数と呼ぶ。
    次に目的関数も以下のように置き換える。
    z=2x+3y+0u+0v
    このようにして、初めの線形計画問題は以下のように置き換えられる。
    非負変数x,y,u,v(x>=0,y>=0,u>=0,v>=0)について、
    　　2x+ y+u=100
    　　3x+6y+v=240
    の制約条件式のもとで、
    　　z=2x+3y+0u+0v
    の値を最大にするx,y,u,vの値を求める

  2. シンプレックス表を作る
    シンプレックス法による計算は、表に基づいて行われる。
    そのための表を作成しよう。
    まず、各制約条件式の係数を、変数の見出しに合わせて表にしていく。
    なお、陳列スペースの限度や予算の限度を表す値を、表の左側に書くことにし、その列を表す見出しとしてbを用いる。
    b x y u v
    100 2 1 1 0
    240 3 6 0 1
    なお、見出しbの列の値（色が付いている部分）の事を、右辺の定数項という。
    次に、目的関数の係数を表内の各変数の見出しの上に書く。
    2 3 0 0
    b x y u v
    100 2 1 1 0
    240 3 6 0 1
    なお、これらの係数（色が付いている部分）の事を利益係数という。
    最後に、表の左側に規定変数という見出しを付けた列を作り、そこに余裕変数u,vを記入、その左側に余裕変数の利益係数を記入し、この列に見出しcをつける。
    2 3 0 0
    c 基底変数 b x y u v
    0 u 100 2 1 1 0
    0 v 240 3 6 0 1
    これでシンプレックス表の最初の表が出来たことになる。
    この表は、１つの仕入れ案（x=0,y=0,u=100,v=240）を示している。
    このように、表のなかで基底変数の列に入っている変数は正の値を取るのに対し、それ以外の変数はゼロとなる。正の値を取る変数のことを基底変数、ゼロとおかれる変数のことを非基底変数と呼ぶ。

  3. 式を評価する
    では、この表が表す仕入れ案において、利益はどうなるか計算してみよう。
    Z=2x+3y+0u+0v
    =2*0+3*0+0*100+0*240
    =0
    上の結果から見てもわかるとおり、非基底変数の値は０なので計算する必要がない。従って計算式は利益変数と基底変数との値をそれぞれ掛け合わせた物の合計となる。
    ここで求めた利益の値を新しい行に書き加えておき、この行の見出しをzとする。 さて、今の仕入れ案よりも利益が大きくなるかどうかを調べるために、シンプレックス基準と呼ばれる値を計算する。
    これは、c列とその各編数の下の列の係数とそれぞれ掛け合わせて、その合計から各変数の利益係数を引くことによって求める。
    例えばxの場合は
    （c列*x列）+（c列*x列）-（xの利益係数）=
    0*2+0*3-2=-2
    で、-2となる。同様にしてy,u,vも求める。
    そして求めた値を新しく追加した行に記入する。
    2 3 0 0
    c 基底変数 b x y u v
    0 u 100 2 1 1 0
    0 v 240 3 6 0 1
    　 z 0 -2 -3 0 0
    シンプレックス基準は、その中にマイナスの値があれば、それに対応する変数を基底変数に入れることによって、利益の値が増えることを示す。
    では次に、非基底変数を基底変数にして計算してみよう。
    この場合は、１度に１つの変数についておこなう。そしてシンプレックス基準の絶対値の大きい方を基底変数として選ぶ。

  4. 基底変数を入れ替え、新しい解を求める
    シンプレックス基準の絶対値の大きいyを新しい基底変数にするために、uかvのどちらかを非基底変数にしなければならない。
    どちらを入れ替えるか決める場合、bの列を新しく基底変数にする列の値で割、その結果の中で最も小さな値に対応する基底変数を基底からはずす変数とする。
    この計算の結果をθの見出しを付けて表の右側に記入する。
    2 3 0 0 　
    c 基底変数 b x y↑ u v θ
    0 u 100 2 1 1 0 100
    0 ←v 240 3 6 0 1 40*
    　 z 0 -2 -3 0 0 　
    なお、表内に記入されている記号*は最小値、↑、←はそれぞれ基底変数に入ること、基底変数からはずれることを示す。
    さて、yとvの基底変数の入れ替えは、yの列とvの行との交差する欄を１にする事から計算を始める。
    また、新たに基底に入れる変数の列と、基底からはずそうとしている変数の行とが交差する欄の数値（水色の部分）を軸要素と呼ぶ。
    さて、軸要素を１にするためには、v行を軸要素で割ればよい。
    その結果を表の下に追加する。
    2 3 0 0 　
    c 基底変数 b x y u v θ
    0 u 100 2 1 1 0 100
    0 ←v 240 3 6 0 1 40*
    　 z 0 -2 -3 0 0 　
    0 u 　 　 　 　 　 　
    3 y 40 1/2 1 0 1/6 　
    次に、y列のその他の要素（u）を０にする事を考える。
    これを０にするには、一番上のuの行からyの行を引けば良い。
    この結果を表に追加する。
    2 3 0 0 　
    c 基底変数 b x y u v θ
    0 u 100 2 1 1 0 100
    0 ←v 240 3 6 0 1 40*
    　 z 0 -2 -3 0 0 　
    0 u 60 3/2 0 1 -1/6 　
    3 y 40 1/2 1 0 1/6 　
    これで新しい計画が出来た。それはx=0,y=40,u=60,v=0である。
    なお、今のような基底変数を入れ替えるための計算をはき出し計算とよばれる。

  5. 新しい解を評価する
    新しい解が求められたので、３と同じ手順によって評価する。
    この場合は１２０となり、この値はb列のz行に記入される。
    同様にシンプレックス基準を求めて、４、５と繰り返してゆけばよい。
    最終的には以下のような表になる。
    2 3 0 0 　
    c 基底変数 b x y u v θ
    0 u 100 2 1 1 0 100
    0 ←v 240 3 6 0 1 40*
    　 z 0 -2 -3 0 0 　
    0 ←u 60 3/2 0 1 -1/6 40*
    3 y 40 1/2 1 0 1/6 80
    　 z 120 -1/2 0 0 1/2 　
    2 x 40 1 0 2/3 -1/9 　
    3 y 20 0 1 -1/3 2/9 　
    　 z 140 0 0 1/3 4/9 　
    さて、u,vのシンプレックス基準だが、uやvの値を増やすとそれだけ利益が減ってしまうことを表している。従って、現在の状態が最適の解であると言うことがわかる。


演習課題
発表者：畠山

（１）次の線形計画問題の最適解を求めよ
（２）上記（１）をシンプレックス法で解き、その過程のシンプレックス表を示しなさい。
非負変数,y(x>=0,y>=0)について
　　　3x+4y<=15
　　　7x+5y<=20
のもとで、z=8x+7yの値を最大にする

←【アプリケーション総論】シラバスへ
←講義のツボメニューへ
←鈴木研究室ホームへ