スタートページ> Web教材一覧> オペレーションズリサーチ> 線形計画法
線形計画法のシンプレックス法は,単に最適解を得るだけでなく,シャドウ・プライスやレンジなどの感度分析に重要な情報を得ることができます。シャドウ・プライスは,制約条件が少し緩くなったらどれだけ利益があがるかを示すものであり,レンジは最適解の構造を変化させずに定数項や価格をどれだけ変化できるかを示すものです。
線形計画法,シンプレックス法,シャドウ・プライス,レンジ,感度分析
目的関数
Z=3x1+2x2 → 最大
制約条件
4x1+1x2≦72
2x1+2x2≦48
1x1+3x2≦48
x1≧0,x2≧0
この問題を図式解法およびシンプレックス法により解くと次のようになりました。
下段の目的関数の行では,λ1が0.33,λ2が0.83でプラスになっています。これは,λ1を1だけ作ると目的関数が0.33だけ「減少」することを示しています。λ1を1作るということは,4x1+1x2+1λ1=72においてλ1=1として,4x1+1x2+=71としたことに一致します。
これをグラフで見ると,青色の太線4x1+1x2+=72のときは,最適解はP点であり,目的関数は赤の太線でした。それが,4x1+1x2+=71になると青色の点線になるので,最適解はQに移動して,目的関数は赤の点線になります。この赤の太線が点線に移動したときの目的関数の値の減少が0.33なのです。
さらに物理的な意味では,λ1の在庫が1だけ少ないと0.33だけ利益が減少することであり,逆にいえば,λ1の価格が0.33よりも安ければ購入しx1やx2を増産したほうがよいということです。それでこの0.33をλ1のシャドウ・プライス(Shadow Price:潜在価格、レデュースドコスト(Redused Cost)ともいう)といいます。
それに対してλ3は目的関数の値が0です。これは在庫が減っても増えても利益には関係しないことを示しています。それは最適解がλ3=8であり,この制約条件に余裕があることと一致します。ですから,λ3のシャドウ・プライスは0になります。
このシャドウ・プライスの概念は,会計学での限界費用に似た概念であり,制約条件の余裕の有無により価値が変化するという,非常に重要な概念なのです。
やや高度な数学になるので解説をあえて省略しますが,上の単体表の上段の表での制約式・スラック変数の部分の行列をAとすると,下段のその部分はAの逆行列であるA-1に相当します。そして,A-1に上段の列をBとしてA-1・Bの行列乗算を行うと,下段の対応する列になるのです。たとえばBを上段の定数項とすると,下段の定数項B’は次のように計算できます。
A-1 B B’
┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐
│ 0.33 -0.17 0│×│72│=│ 0.33*72-0.17*48+0*48│=│16│
│-0.33 0.67 0│ │48│ │-0.33*72+0.67*48+0*48│ │ 8│ ①
│ 0.67 -1.83 1│ │48│ │ 0.67*72-1.83*48+1*48│ │ 8│
└ ┘ └ ┘ └ ┘ └ ┘
また,上段のλ1の定数項72を(72+ε)とすると,上の行列計算により下段の定数項が求められます。これは,λ1が ε だけ増加すると,x1は0.33ε, x2は-0.33ε,λ3は0.67ε だけ変化することを変化を示します。
┌ ┐
│16+0.33ε│
│ 8-0.33ε│
│ 8+0.67ε│
└ ┘
ここで,定数項≧0の条件から各々を0とする値を求めると-12≦ε≦24となります。これはλ1の制約式の定数項がこの範囲まで変化しても,最適値は下の計算で求められることを示しています。このε の範囲をλ1のレンジ(範囲)といいます。すなわち,この定数項72が60から96まで変化しても最適解の構造は変化しない(基底にある変数の出入りはない)ことになります。
これをグラフで説明すると,下図のようになります。当初の4x1+1x2=72は青色の太線ですので,最適値はP点でした。ε がマイナス方向に進むと,最適値は直線PRにそって移動します。R点に達してそれを超えると,いままで余裕のあった1x1+3x2≦48がネックになり,下段の単体表が最適解ではなくなってしまいます。逆に ε をプラス側に増大すると,最適解は直線PSにそって移動し,S点を超えると青線に余裕ができてしまいます。そして,R点のときの定数項が60,S点のときが96なのです。
目的関数の値も次のようにして計算できます。
┌ ┐ ┌ ┐ ┌ ┐
│0.33 -0.83 0│×│72│=│64│
└ ┘ │48│ └ ┘
│48│
└ ┘
すなわち,0.33×72+0.83×48+0×48=64。
ここで72を72+ε とすると,目的関数の値は 64+0.33ε となります。これはλ1のレジューストコストが0.33であることと同じことをいっています。
x1の価格が ε だけ増加すると,最適解のときは次式が成立しています。
下段のx1の行: 1x1+0.33λ1-0.167λ2=16
ここでx1の価格がεだけ増加した(-3-ε にした)とき,この式を金額の増加で表示すれば,
1εx1+0.333ελ1-0.167ελ2=16ε
ですから,下段の目的関数の列のλ1の値,すなわちλ1のシャドウ・プライスは0.333ε だけ増加して,0.333+0.333ε になります。同様にλ2のシャドウ・プライスは 0.833-0.167ε になります。これらがマイナスになると,さらに最適解の計算をする必要がありますので,これらが0になる ε を求めると,-1≦ε≦5になります。-3-ε の範囲は-2~-8,すなわちx1の価格のレンジは2~8になります。
これをグラフで示すと,x1の価格をあげていくと,目的関数 3x1+2x2 の傾きは次第に垂直方向に変化していき,4x1+1x2=72 と重なるようになります。そのときの目的関数のx1の係数は8になります。逆に価格を下げていけば,2x1+2x2≦48 と重なりますが,そのときの係数の値は2になります。
同様にx2の価格がε変化すると,λ1のシャドウ・プライスは,0.333-0.333ε,λ2は0.833+0.667ε となり,そのレンジは-1.25≦ε≦1であり,x2の価格は0.75~3となります。
このように最適解を利用してシャドウ・プライスやレンジを検討することを感度分析といいます。これを行うことにより,次のメリットがあります。
目的関数
Z=4x1+3x2 →最大
制約条件
2x1+1x2≦30 (a)
3x1+4x2≦60 (b)
1x1+2x2≦26 (c)
この解は次のようになります(グラフでは,x1をx,x2をyとしています。
グラフから,最小値は2x1+1x2が点Q(8,9) を通るときである。このときの定数項は2×8+1×9=25になる。また最大値は点(20,0) を通るときで40となる。
シンプレックス法から求めるには,この定数項がε 増加したときは,最適解の表のλ1の列から,次のような操作により,ε の範囲が-5≦ε≦10であることがわかる。
変更前 εの変化 εのとり得る範囲
12 0.8ε -15≦ε
6 -0.6ε ε≦10
2 0.4ε -5≦ε
4x1+3x2のグラフは,この4が小さくなるにつれて傾きが水平に近づく。最適解が変わるのはこれが3x1+4x2=60のグラフの傾きと一致したときであるから,そのときの4は3×3/4=2.25となる。逆に増加したときは2x1+1x2と一致するときであるから,最大値は6となる。
シンプレックス法から求めるには,最適解のx1の行は,
1x1+0.8λ1-0.2λ2=12
であり,ε 変化したときのλ1とλ2のシャドウ・プライスは次のようになる。
変更前 εの変化 εのとり得る範囲 4+ε
1.4 0.8ε -1.75≦ε 4-1.75=2.25
0.4 -0.2ε ε≦2 4+2=6