スタートページ> Web教材一覧> オペレーションズリサーチ> 線形計画法
線形計画法(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には余裕があることは上のグラフから読み取ることができます。
次のように定式化できます。
制約条件
2x+1y≦30
3x+4y≦60
1x+2y≦26
(x≧0,y≧0)・・・暗黙の条件
目的関数
Z=4x+3y →最大
グラフは右図のようになるので,
x=12kg,y=6kgのときZ=66万円
が解になります。