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

線形計画法の定式化と図式解法

学習のポイント

線形計画法(LP:リニアプログラミング)の概念を理解するために,簡単な例題を定式化して図式解法により解を求める方法を学習します。

キーワード

線形計画法(LP:リニアプログラミング),定式化,制約条件,目的関数,図式解法,最適値 


この例では,変数がxとyの2つですから,グラフを描いて解くことができます。それを図式解法といいます。

1x+3y≦48をグラフで示すには,1x+3y=48のグラフにより二分されたどちらか一方です。そのグラフを描くのには,y=-(1/3)x+16と変形してもよいのですが,次のようにするほうが簡単です。

同様にして,4x+1y≦72,2x+2y≦48,1x+3y≦48およびx≧0,y≧0がすべて成立する範囲は,下図のメッシュの部分になります。これが制約条件です。すなわちメッシュされら内部(線も含む)の点は,制約条件をすべて満足しており,それ以外の点は制約条件の少なくとも1つは満足していないことになります。

例をあげて確認しましょう。メッシュの内部の点として(5,8),外部の点として(4,16)を用います。

    制約条件      (5,8)のとき     (4,16)のとき
   4x+1y≦72  4×5+1×8=28 ○  4・4×1・16=32 ○
   2x+2y≦48  2×5+2×8=26 ○  2・4×2・16=40 ○
   1x+3y≦48  1×5+3×8=29 ○  1・4×3・16=52 ×
                                  (制約条件が不成立)

目的関数Z=3x+2yにおいて,Zを24,48,64,96としたときのグラフを描くと下図のようになります。すなわち傾きが-(2/3)の平行線で,右上になるほどZの値(目的関数の値)が大きくなることがわかります。

制約条件を満足するのはメッシュの内部であり,目的関数のグラフが右上にいくほど目的関数の値が大きくなるのですから,最大になるのは図の点P(16,8)を通るときです。すなわち,x=16,y=8が最適値であり,最大値はZ=64となります。これを元の問題で表現するのであれば,「製品Xを16kg,製品Yを8kg生産するのが最適であり,そのときの利益は64万円になる」となります。

なお,x=16,y=8のときは,4x+1y=72,2x+2y=48ですから原料Aと原料Bは全量使用したことになりますが,1x+3y=40≦48なので原料Cは8kg在庫が残っています。原料Aと原料Bには余裕がないが原料Cには余裕があることは上のグラフから読み取ることができます。


理解度チェック

第1問

  1. 製品Xを1kg生産するには,原料Aを2kg,原料Bを3kg,原料Cを1kg必要とし,製品Yを1kg生産するには,原料A1kg,原料Bを4kg,原料Cを2kg必要とします。原料の在庫量は,Aは30kg,Bは60kg,Cは26kgあります。製品Xの売価は4万円/kg,製品Bの売価を3万円とするとき,利益(=売上高。原料や生産の費用は考えないことにします)を最大にするには,製品Xと製品Yをどれだけ生産すればよいでしょうか。

    次のように定式化できます。
        制約条件
           2x+1y≦30
           3x+4y≦60
           1x+2y≦26
          (x≧0,y≧0)・・・暗黙の条件
        目的関数
           Z=4x+3y →最大
    グラフは右図のようになるので,
        x=12kg,y=6kgのときZ=66万円
    が解になります。