スタートページWeb教材一覧オペレーションズリサーチ線形計画法

シンプレックス法

学習のポイント

線形計画法(LP:リニアプログラミング)の代表的な解法にシンプレックス法があります。シンプレックス法とは,簡単な数学的知識により線形計画法を解くアルゴリズム(答を求めるための計算手段)です。現実にはシンプレックス法により手計算で解くことはないでしょうが,シンプレックス法を理解することは,線形計画法をよりよく理解することにつながります。

キーワード

線形計画法(LP:リニアプログラミング),シンプレックス法,掃出計算


シンプレックス・タブローの作成

  目的関数
    Z=3x1 +2x2  → 最大
  制約条件
      4x1 +1x2 ≦72
      2x1 +2x2 ≦48
      1x1 +3x2 ≦48

(注)この元の問題は「線形計画法の定式化と図式解法」にあります。そこではx,y,a,b,cという変数名を用いていましたが,ここからは,数学的な表現をするために,このような変数名を用います。

上の不等式は,次のように等式に表現することができます。
    4x+1x+1λ=72
    2x+2x+1λ=48
    1x+3x+1λ=48
 また,一般に線形計画法では最小化問題を基準としていますので,目的関数のxとxの係数をマイナスにして最小化問題にします。すると,
    Z=-3x1 -2x2+1λ+1λ+1λ  → 最小
になります。

このようなλ,λ,λのことをスラック変数といいます。λとは,制約条件 4x1 +1x2 ≦72 の余裕であり,原料Aの在庫が使われずに残った数量であると解釈されます。

これを「表0」のよう表にしたものを単体表(シンプレックス・タブロー)といいます。シンプレックスとは「単体」という意味で,シンプレックス法とはこの単体表を操作することにより,線形計画法を解く方法です。

表0
列 →


2次元表を一般に行列といいます。そして縦を,横をといい,個々のセルを要素といいます。例えば「目的関数の行のxの列の要素の値は-3である」というような表現をします。

なお,表0に「基底」という列があります。これは,変数に値を入れた(生産をした)変数の名称です。ここにλ,λ,λがあるのは,これらの変数を定数項だけ作る(すなわちxもxも生産しない)ことを意味しています。このときの目的関数の値(定数項)は0になりますので定数項を0にしておきます。

シンプレックス法の手順

手順1
目的関数の行の各要素のうち,最小の要素を持つ列をL列とします。
その要素が0か正であれば,最適解に達したことになり終了します。
手順2
L列の制約条件の要素が正のものについて,定数項をその要素で割った値が最小になる行をK行とします。
手順3
K行L列の要素をピボットとして掃出計算(後述)をします。
手順1に戻ります。

掃出計算

上の表で,i行j列の要素をA(i,j) ということにします。ピボットの要素はA(K,L) になりますが,その値をPとします。

手順3a
K行以外の行(目的関数も含む)の全要素について,
    A(i,j) = A(i,j) - A(K,j)×A(i,L)/P
の操作をします。
手順3b
K行の全要素(定数項も含む)をピボットPで割ります。

数値例

実際に表0に対してこの手順を行ってみましょう。

第1回

手順1
目的関数の行では,x1 での-3が最小ですからL=1列になります。-3<0ですからまだ最適解にはなっていないので,手順2へ進みます。
目的関数の各要素の値は,それぞれの変数を1作るときの利益(マイナス表示になってはいますが)を示します。そのうちの最小のもの(ここではx1)をピボット列に選ぶということは,目的関数の値を増加させるのに最も効率のよいものを選ぶということです。
手順2
72/4=18,48/2=24,48/1=48ですからλ1 の行がKになります。ピボットの値Pは4になります。
x1をできるだけ生産しようとするのですが,図式解法のグラフからわかるように,18が限度であるとわかります。これが「定数項/係数が最小の列を選ぶ」ことなのです。
手順3a
目的関数の行については,次のようになります。
  x1 の要素:A(i,j)=-3,A(K,j)=4,A(i,L)=-3,P=4ですから,(-3)- 4×(-3)/4=0
  x2 の要素:(-2) - 1×(-3)/4=-1.25
  λ1 の要素:0 - 1×(-3)/4=0.75
  λ2 の要素:0 - 0×(-3)/4=0
  λ3 の要素:0 - 0×(-3)/4=0
となり,表にすれば次のようになります。
          x1    x2    λ1   λ2   λ3  定数項
  目的関数  0 -1.25 0.75  0   0  54
λ2 の行,λ3 の行についても同様な操作により,次の結果になります。
        x1   x2    λ1    λ2  λ3  定数項
   λ2    0  1.5  -0.5   1  0   12
   λ3    0  2.75 -0.25  0  1   12

連立方程式の解法での表現をすればわかりよいでしょう。
λ行を例にすると,
   元のλの列: 2x+2x+1λ=48   ①
   元のλの列: 4x+1x+1λ=72   ②
において,xの係数に着眼して ①-(2/4)×② をすることにより,
   新λの列: 0x+1.5x-0.5+1λ=12  ③
を求めたことになります。あるいは,手順3bでの④を①に代入して,xを消去して③を得たともいえます。
手順3b
λ1 の行の全要素を4で割ります。その結果は次のようになります。
       x1   x2     λ1    λ2   λ3  定数項
   λ1    1  0.25  0.25   0  0   18
このとき,x1 の列λ1 の行で掃出計算をしたということで,基底のλ1 をx1 に変えておきます。

このピボット列(λの列)を数式で表現すると,
   4x+1x+1λ=72
ですから,それをピボットで割るということは,
   1x+0.25x+0.25λ=18     ④
としたことなのです。

ここまでの計算でわかるように,掃出計算とは連立方程式からある変数を消去する操作なのです。この操作により,表0は次の表1に書き換えられました。ピボットになったL列について,K行は1,それ以外は0になっているはずです。

表1

表1は,x=18,λ=12,λ=30としたとき,目的関数の値が54になることを示しています。表0→表1の操作を図式解法で図示すると,下図のAを行ったことになります。

表1の目的関数の行には,未だマイナスの要素がありますので最適解ではありません。それで第2回の操作をするのですが,その操作は上図でのBを行うことです。

第2回

手順1と手順2
目的関数の行での最小値はx2 の列の-1.25です。L=2。
 x1 :18/0.25=72,λ2 :12/1.5=8,λ3 :30/2.75=11ですから,その最小のものはλ2 の行であり,ピボットはλ2 行x2 列のP=1.5になります。
 言い換えれば次のようになります。表1ではxを最大限作りxは作らないことを意味していました。ところが目的関数の列を見るとxを1作れば目的関数の値が1.25増加することを示しています。そこで,点(18,0)からどこまでxを増加できるかを調べると,定数項/係数が最小になるのは,λの12/1.5=8ですから,(λ,x)がピボットにするのです。

手順3
ここでの掃出計算は,xの消去計算になります。目的関数,x1 ,λ3 の行について手順3a
    A(i,j) = A(i,j) - A(K,j)×A(i,L)/P
を行い,λ2 の行については,
    A(K,j) = A(K,j)/P
を行います。その結果は表2になります。

表2

この結果,目的関数の行がすべて0以上になるので,どれを作成しても目的関数は増加しないので,これが最適解であることがわかります。

「基底」と「定数項」を見てください。これより,「x1 =16,x2 =8,λ3 =8のとき,目的関数は最大値64になる」と読み取ります。ここでλ3 =8とは,制約式 1x1 +3x2 ≦48 において8の余裕があるという意味です。

以下に表0~表2の全体を示します。


理解度チェック

第1問

  1. 次の問題をシンプレックス法で解きなさい。

     目的関数
      Z=4x1 +3x2  →最大
     制約条件
      2x1 +1x2 ≦30  (a)
      3x1 +4x2 ≦60  (b)
      1x1 +2x2 ≦26  (c)
      (x1 ≧0,x2 ≧0)・・・暗黙の条件

    シンプレックス表は次のようになります。これより,
       x1 =12
       x2 = 6
    のとき,最大値=66になります。