線形計画法(生産計画)
提供: Internet Web School
線形計画法は 線形計画法 (Wikipedia)に説明がある.
解法には
シンプレックス法(Wikipedia)や内点法(Wikipedia)がある. シンプレクス法は[菅沼]の解説が判りやすい.
ここでは2つの例を用いて説明する. Microsoft Excel のソルバーを用いた解法例も説明する.
生産計画
例題1
ある製造会社があって, xとyという2種類の製品の製造販売をしている. これらを製造するには, 原材料A,B,Cが必要で, x, yをそれぞれ1単位当 たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている.
Fx
x, yを販売するとそれぞれ1単位当たり2万円, 1万円の利益が得られる. 問題は, 表の在庫量の範囲で, xとyをそれぞれ何単位ずつ造れば利益が最大に なるかである。
線形計画法(1)
これを数式化すると, x, yの製造量をx, yで表すとして:
原材料A, B, Cについての制約から
10x+20y≤400(1)20x+10y≤600(2)15x+40y≤1300(3)
負の生産量はないのであるから
0≤x(4)0≤y(5)
利益は
f(x,y)=2x+y(6)
で結局, (6)を(1)∼(5)の条件のもとで最大にすることになる。
下の図は関数f(x,y)=2x+yの図である。
条件(1)∼(5)を充たす点P=(x,y)は 下のような,凸多角形の境界線も含めた内部にある。
この凸多角形の頂点を P0=(x0,y0),P1=(x1,y1),P2=(x2,y2),P3=(x3,y3),P4=(x4,y4) とすると,
内部の点P=(x,y)はこれらの頂点Pi=(xi,yi),i=0,1,2,3,4によって
(1)P=λ0P0+λ1P1+λ2P2+λ3P3+λ4P4(2)λ0+λ1+λ2+λ3+λ4=1(3)0≤λ0≤1, 0≤λ1≤1, 2≤λ2≤1,0≤λ3≤1, 0≤λ4≤1
で表される。これをPi=(xi,yi),i=0,1,2,3,4の凸結合という.
f(x,y)=2x+y(6)
には「線形性」が成り立っている.
これは P=(x,y),Q=(x′,y′)
とα,βについて,
f(αP+βQ)=f(α(x,y)+β(x′,y′))=αf(x,y)+βf(x′,y′)=αf(P)+βf(Q)
という性質である。この線形性を使うと,以下の議論ができる。
まず各頂点での関数fの値
f(Pi)=f(xi,yi),i=0,1,2,3,4
のうち最大値をf(P∗)=f(x∗,y∗)とする.
凸多角形の内の任意の点P=(x,y)に対するf(P)=f(x,y)は
PがPi=(xi,yi),i=0,1,2,3,4 の凸結合で表されることから
f(P)=f(λ0P0+λ1P1+λ2P2+λ3P3+λ4P4)
さらにfの線形性から
右辺=λ0f(x0,y0)+λ1f(x1,y1)+λ2f(x2,y2)+λ3f(x3,y3)+λ4f(x4,y4)(fの線形性)
f(P∗)=f(x∗,y∗)が最大で,(3)のように各λiは正の数(1≥λi≥0)であるから,
右辺≤(λ0+λ1+λ2+λ3+λ4)f(x∗,y∗)
さらに,(2)から
λ0+λ1+λ2+λ3+λ4=1
で
f(P)=f(x,y)≤f(x∗,y∗)=f(P∗)
となる。結局,関数fの制約条件を表す凸多角形の内部(境界を含む)の点全てを調べる必要がなく、
頂点での関数fの値を調べれば良いことが判る.
(図1.2)ファイル:Fig1.2.gi
(1)∼(5)式のように変数に関する制約条件式が1次式で与えられ, (6)式のように評価関数も1次式で与えられる問題は線形計画法と呼ばれる.
線形化計画法の代表的な解法であるシンプレクス法は,制約条件を表す凸多角形の頂点での 関数fの値を効率的に調べる方法である。 適当な,頂点から始め,関数fの値が増大する頂点へ次々移動して,最大解を探す.
この他に,凸多角形の内部の点から,最大解を与える頂点を探索する内点法もある。
例題2
ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している. 製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする. また, 製品A,B,Cを1単位生産するのに必要な原料Ⅰ,Ⅱ,Ⅲ,Ⅳのそれぞれ量と使用可能な上限が次の表で与えられる. これらの条件のもとに,利益を最大にするには製品A,B,Cをそれぞれ,どれだけ生産すれば良いか?.
この問題も例題1と同じように以下のように数学的に定式化される.
線形計画法(2)
製品A,B,Cをそれぞれx1,x2,x3 単位生産するときx1,x2,x3は以下の不等式を満たす.
4x1+0x2+7x3≤901x1+3x2+9x3≤606x1+0x2+14x3≤1104x1+10x2+1x3≤75 (1)
さらに各製品生産量は負ではないから
0≤x1,0≤x2,0≤x3(2)
この制約条件のもとに
L(x1,x2,x3)=80x1+110x2+95x3(3)
を最大にするx1,x2,x3を求めよ.
この問題の解法にはシンプレックス法や内点法がある.
シンプレクス法は[菅沼]の解説が判りやすい.
この問題を解くのにはMicrosoft Excelのソルバーや
フリーソフトのOpen Office で提供されるソルバーと同等の機能をもつソフトを用いることができる.
この問題のMicrosoft Excelのソルバーによる解法例を示す。 ファイル:生産計画.pdf