典型的な(簡単な)線形計画法を掲げます。
「製品Xを1kg生産するには,原料Aを4kg,原料Bを2kg,原料Cを1kg必要とし,製品Yを1kg生産するには,原料A1kg,原料Bを2kg,原料Cを3kg必要とします。原料の在庫量は,Aは72kg,Bは48kg,Cは48kgあります。製品Xの売価は3万円/kg,製品Bの売価を2万円とするとき,利益(=売上高。原料や生産の費用は考えないことにします)を最大にするには,製品Xと製品Yをどれだけ生産すればよいでしょうか。」
この問題文を整理すると次表になります(製品を横,原料を縦にとるのがコツです)。
製品X 製品Y 原料在庫量
原料A 4 1 72
制約条件 原料B 2 2 48
原料C 1 3 48
目的関数 Z: 3 2 → 最大
製品Xをxkg,製品Yをykg生産するには原料Aを 4x+1y kg必要とします。ところが原料Aの在庫量は72kgですので,
4x+1y≦72
の式が成立します。
以下同様にして,上の問題は次のように定式化することができます。
制約条件
4x+1y≦72
2x+2y≦48
1x+3y≦48
(x≧0,y≧0)・・・暗黙の条件
のなかで,
目的関数
Z=3x+2y
を最大にする,xとyの値を求める。
この問題を抽象的に表現すれば,「一次不等式の制約条件の下で一次式を最大(最小)にする技法」だといえます。一次式はグラフに描くと直線,すなわち線形(リニア)になります。一次式を取り扱う数学の分野を線形数学といいます。線形数学を利用した計画法(プログラミング)という意味で線形計画法(リニア・プログラミング-LP)というのです。
一次式以外の制約条件や目的関数があるときは,非線形計画法といいます。また,制約条件の下で目的関数を最大化する技法を総称して数理計画法といいます。線形計画法は数学的計画法のなかで最もポピュラな技法で,実務的にも広く活用されています。さらに線形計画法には,特殊な条件を加えた整数計画法とか輸送問題・割当問題の解法など,多様な技法があります。
変数がXとYの2つであれば,右図のように図式解法で簡単に解くことができます。
変数が3以上のときのポピュラな解法にシンプレックス法があります。大規模なモデルを効率的に解くために,さまざまな工夫がなされており,専用のコンピュータプログラムが市販されています。
過去問題: 「線形計画法」
発展: 「線形計画法」