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

シャドウ・プライスとレンジ

学習のポイント

線形計画法のシンプレックス法は,単に最適解を得るだけでなく,シャドウ・プライスやレンジなどの感度分析に重要な情報を得ることができます。シャドウ・プライスは,制約条件が少し緩くなったらどれだけ利益があがるかを示すものであり,レンジは最適解の構造を変化させずに定数項や価格をどれだけ変化できるかを示すものです。

キーワード

線形計画法,シンプレックス法,シャドウ・プライス,レンジ,感度分析


    目的関数
     Z=3x+2x → 最大
    制約条件
       4x+1x≦72
       2x+2x≦48
       1x+3x≦48
       x≧0,x≧0

この問題を図式解法およびシンプレックス法により解くと次のようになりました。

シャドウ・プライス

下段の目的関数の行では,λが0.33,λが0.83でプラスになっています。これは,λを1だけ作ると目的関数が0.33だけ「減少」することを示しています。λを1作るということは,4x+1x+1λ=72においてλ=1として,4x+1x+=71としたことに一致します。

これをグラフで見ると,青色の太線4x+1x+=72のときは,最適解はP点であり,目的関数は赤の太線でした。それが,4x+1x+=71になると青色の点線になるので,最適解はQに移動して,目的関数は赤の点線になります。この赤の太線が点線に移動したときの目的関数の値の減少が0.33なのです。

さらに物理的な意味では,λの在庫が1だけ少ないと0.33だけ利益が減少することであり,逆にいえば,λの価格が0.33よりも安ければ購入しxやxを増産したほうがよいということです。それでこの0.33をλシャドウ・プライス(Shadow Price:潜在価格、レデュースドコスト(Redused Cost)ともいう)といいます。

それに対してλは目的関数の値が0です。これは在庫が減っても増えても利益には関係しないことを示しています。それは最適解がλ=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│
   └             ┘ └  ┘ └           ┘ └  ┘

また,上段のλの定数項72を(72+ε)とすると,上の行列計算により下段の定数項が求められます。これは,λが ε だけ増加すると,xは0.33ε, xは-0.33ε,λは0.67ε だけ変化することを変化を示します。

   ┌        ┐
   │16+0.33ε│
   │ 8-0.33ε│
   │ 8+0.67ε│
   └        ┘

ここで,定数項≧0の条件から各々を0とする値を求めると-12≦ε≦24となります。これはλの制約式の定数項がこの範囲まで変化しても,最適値は下の計算で求められることを示しています。このε の範囲をλレンジ(範囲)といいます。すなわち,この定数項72が60から96まで変化しても最適解の構造は変化しない(基底にある変数の出入りはない)ことになります。

これをグラフで説明すると,下図のようになります。当初の4x+1x=72は青色の太線ですので,最適値はP点でした。ε がマイナス方向に進むと,最適値は直線PRにそって移動します。R点に達してそれを超えると,いままで余裕のあった1x+3x≦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ε となります。これはλのレジューストコストが0.33であることと同じことをいっています。

価格(目的関数の係数)の変化とレンジ

の価格が ε だけ増加すると,最適解のときは次式が成立しています。
  下段のxの行: 1x+0.33λ-0.167λ=16
ここでxの価格がεだけ増加した(-3-ε にした)とき,この式を金額の増加で表示すれば,
  1εx+0.333ελ-0.167ελ=16ε
ですから,下段の目的関数の列のλの値,すなわちλのシャドウ・プライスは0.333ε だけ増加して,0.333+0.333ε になります。同様にλのシャドウ・プライスは 0.833-0.167ε になります。これらがマイナスになると,さらに最適解の計算をする必要がありますので,これらが0になる ε を求めると,-1≦ε≦5になります。-3-ε の範囲は-2~-8,すなわちxの価格のレンジは2~8になります。

これをグラフで示すと,xの価格をあげていくと,目的関数 3x+2x の傾きは次第に垂直方向に変化していき,4x+1x=72 と重なるようになります。そのときの目的関数のxの係数は8になります。逆に価格を下げていけば,2x+2x≦48 と重なりますが,そのときの係数の値は2になります。

同様にxの価格がε変化すると,λのシャドウ・プライスは,0.333-0.333ε,λは0.833+0.667ε となり,そのレンジは-1.25≦ε≦1であり,xの価格は0.75~3となります。

感度分析

このように最適解を利用してシャドウ・プライスやレンジを検討することを感度分析といいます。これを行うことにより,次のメリットがあります。


理解度チェック

第1問

 目的関数
  Z=4x+3x →最大
 制約条件
  2x+1x≦30  (a)
  3x+4x≦60  (b)
  1x+2x≦26  (c)

 

この解は次のようになります(グラフでは,xをx,xをyとしています。

  1. この3つの制約条件で余裕のある条件はどれか。
    「グラフが最適値Pを通らない」,「基底にλがある」ことから,1x+2x≦26(c)に余裕があることがわかる。
  2. 制約条件:2x+1x≦30での30が30+ε(ε は微小量)に増加すると,目的関数の値はどうなるか。
    最適解の表におけるλのシャドウ・プライスが1.4ε であるから66+1.4ε になる。
  3. 制約条件:2x+1x≦30+εとしたとき、εを変化させても、すべての制約条件の結果(余裕がある、余裕がないの状態)が変化しない範囲を示せ。

    グラフから,最小値は2x+1xが点Q(8,9) を通るときである。このときの定数項は2×8+1×9=25になる。また最大値は点(20,0) を通るときで40となる。
    シンプレックス法から求めるには,この定数項がε 増加したときは,最適解の表のλの列から,次のような操作により,ε の範囲が-5≦ε≦10であることがわかる。

       変更前   εの変化    εのとり得る範囲
       12    0.8ε     -15≦ε
        6   -0.6ε         ε≦10
        2    0.4ε      -5≦ε

  4. ここでは、xの価格は4としたが,最適値が変化しない範囲でどの値までとることができるか。

    4x+3xのグラフは,この4が小さくなるにつれて傾きが水平に近づく。最適解が変わるのはこれが3x+4x=60のグラフの傾きと一致したときであるから,そのときの4は3×3/4=2.25となる。逆に増加したときは2x+1xと一致するときであるから,最大値は6となる。
    シンプレックス法から求めるには,最適解のxの行は,
       1x1+0.8λ-0.2λ=12
    であり,ε 変化したときのλ1とλ2のシャドウ・プライスは次のようになる。

       変更前   εの変化    εのとり得る範囲    4+ε
       1.4    0.8ε    -1.75≦ε     4-1.75=2.25
       0.4   -0.2ε          ε≦2   4+2=6