Loading [MathJax]/jax/output/HTML-CSS/jax.js

線形計画法(生産計画)

提供: Internet Web School

(版間での差分)
1 行: 1 行:
'''生産計画'''
'''生産計画'''
 +
 +
例題1
ある製造会社があって, <math>x</math>と<math>y</math>という2種類の製品の製造販売をしている.
ある製造会社があって, <math>x</math>と<math>y</math>という2種類の製品の製造販売をしている.
17 行: 19 行:
問題は, 表の在庫量の範囲で, <math>x</math>と<math>y</math>をそれぞれ何単位ずつ造れば利益が最大に
問題は, 表の在庫量の範囲で, <math>x</math>と<math>y</math>をそれぞれ何単位ずつ造れば利益が最大に
なるかである。
なるかである。
 +
 +
 +
'''線形計画法'''
 +
 +
 +
これを数式化すると, <math>x</math>, <math>y</math>の製造量を<math>x</math>, <math>y</math>で表すとして:
これを数式化すると, <math>x</math>, <math>y</math>の製造量を<math>x</math>, <math>y</math>で表すとして:
94 行: 102 行:
という性質である。この線形性を使うと,以下の議論ができる。
という性質である。この線形性を使うと,以下の議論ができる。
 +
まず各頂点での関数<math>f</math>の値
まず各頂点での関数<math>f</math>の値
153 行: 162 行:
-
 
+
例題2
ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している. 製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする.
ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している. 製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする.
161 行: 170 行:
-
この問題は以下のように数学的に定式化される.
+
この問題も以下のように数学的に定式化される.
'''線形計画法'''
'''線形計画法'''

2020年11月25日 (水) 16:00時点における版

生産計画

例題1

ある製造会社があって, xyという2種類の製品の製造販売をしている. これらを製造するには, 原材料ABCが必要で, x, yをそれぞれ1単位当 たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている. \begin{center} \begin{tabular}{cccc}   & x & y & (在庫量) \\ A & 10 & 20 & 400 \\ B & 20 & 10 & 600 \\ C & 15 & 40 & 1300  \end{tabular} \end{center} x, yを販売するとそれぞれ1単位当たり2万円, 1万円の利益が得られる. 問題は, 表の在庫量の範囲で, xyをそれぞれ何単位ずつ造れば利益が最大に なるかである。


線形計画法



これを数式化すると, x, yの製造量をx, yで表すとして:

原材料A, B, Cについての制約から

10x+10y400(1)20x+10y600(2)15x+40y1300(3)

負の生産量はないのであるから

0x(4)0y(5)

利益は

f(x,y)=2x+y(6)

で結局, (6)を(1)(5)の条件のもとで最大にすることになる。


下の図は関数f(x,y)=2x+yの図である。


\vspace{5cm} \par (図1.0)\\

条件(1)(5)を充たす点P=(x,y)は 下のような,凸多角形の境界線も含めた内部にある。

(図1.1)\\

この凸多角形の頂点を 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λ01,  0λ11,  2λ21,0λ31,  0λ41


で表される。これを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)

PPi=(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(P)=f(x,y)が最大で,(3)のように各λiは正の数(1λi0)であるから,

(λ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)

線形化計画法の代表的な解法であるシンプレクス法は,制約条件を表す凸多角形の頂点での 関数fの値を効率的に調べる方法である。 適当な,頂点から始め,関数fの値が増大する頂点へ次々移動して,最大解を探す.

この他に,凸多角形の内部の点から,最大解を与える頂点を探索する内点法もある。


例題2

ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している. 製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする.  また, 製品A,B,Cを1単位生産するのに必要な原料Ⅰ,Ⅱ,Ⅲ,Ⅳのそれぞれ量と使用可能な上限が次の表で与えられる. これらの条件のもとに,利益を最大にするには製品A,B,Cをそれぞれ,どれだけ生産すれば良いか?.


この問題も以下のように数学的に定式化される.

線形計画法

製品A,B,Cをそれぞれx1,x2,x3 単位生産するときx1,x2,x3は以下の不等式を満たす.

4x1+0x2+7x3901x1+3x2+9x3606x1+0x2+14x31104x1+10x2+1x375 (1)

さらに各製品生産量は負ではないから

0x1,0x2,0x3(2)

この制約条件のもとに

L(x1,x2,x3)=80x1+110x2+95x3(3)

を最大にするx1,x2,x3を求めよ.


(1)式のように変数に関する制約条件式が1次式で与えられ, (3)式のように評価関数も1次式で与えられる問題は線形計画法と呼ばれる. この問題の解法にはシンプレックス法内点法がある. シンプレクス法は[菅沼]の解説が判りやすい.


この問題を解くのにはMicrosoft Excelのソルバーや フリーソフトのOpen Office で提供されるソルバーと同等の機能をもつソフトを用いることができる.

この問題のMicrosoft Excelのソルバーによる解法例を示す。 ファイル:生産計画.pdf

ファイル:LP-Fig.1.jpg

個人用ツール