線形計画法とは、与えられた条件から最大の効果を求めるた
めに用いられる技法である。
グラフによる解法の手順は次のとおり。
STEP1.問題の制約条件をテーブル(表)にまとめる。
STEP2.テーブル(表)から制約条件式(一次不等式)作成し目的関
数(最大利益を得るための条件式)を記述する。
STEP3.制約条件式を等式にしたグラフ(一次関数)を作成し、不
等式の領域を図示する。
STEP4.グラフから連立方程式を解いて基底解(多角形の頂点の
座標)を求める。
STEP5.基底解を目的関数に代入し、結果が最大になる基底解
(最適解)を決定する。
例題1 ある工場で製品A、Bを生産している。
製品Aを1個製造するのに、原料P、Qをそれ
ぞれ8トン、6トン必要とし、製品Bについても
それぞれ2トン、3トン必要とする。また、製品
A、Bは、それぞれ1個あたり3万円、1万円
の利益を生む。しかし、原料Pは18トン、原料
Qは15トンしかない。
利益を最大にする生産量を求めなさい。
STEP1
問題の制約条件を表にまとめる。
製品A
製品B
使用可能量
原料Q
8
6
2
3
18
15
製品1個当た
りの利益
3
1
原料P
STEP2
制約条件式と目的関数を式化する。
製品A、Bの生産量をx、yで表すと、
・制約条件式
原料P: 8x+2y≦ 18 → 4x+2y≦ 9
原料Q:6x+3y≦15 → 2x+1y≦5
・非負条件:x≧0、y≧0
・目的関数:
利益:f(x,y)=3x+1y →max
STEP3
制約条件式を等式に直し、グラフを作成する。
4x+y=9 → y=-4x+9・・・①
2x+y=5 → y=-2x+5・・・②
Y
グラフを右の座標軸に描きなさい。
制約条件式の領域は編みかけ部分
連立方程式
4x+y=9 ・・・①
2x+y=5 ・・・②
を解くと、x= 2
, y=1
O
x
STEP4
2つの制約条件式グラフの共通する編みかけ
の部分に解が存在することになる。
編みかけ部分の四角形の頂点を基底解という。
基底解は、
(0,0)、(0、5)、(2、1)、(2.25、0)
STEP5
上記の基底解をそれぞれ目的関数 f(x,y)=3x+y に
代入する。
利益f(0,0)
=
利益f(0,5)
=
利益f(2,1)
=
利益f(2.25,0)=
となる。
したがって、目的関数を最大にする基底解(2,1)
が最適解となり製品Aを2個と製品Bを1 個生産す
れば、最大利益7 万円を得ることができる
ダウンロード

線形計画法とは、与えられた条件から最大の効果を求めるために用い