Processing math: 100%

線形計画法(生産計画)

提供: Internet Web School

(版間での差分)
1 行: 1 行:
'''生産計画'''
'''生産計画'''
 +
 +
 +
 +
 +
 +
ある製造会社があって, <math>x</math>と<math>y</math>という２種類の製品の製造販売をしている.
 +
これらを製造するには, 原材料<math>A</math>，<math>B</math>，<math>C</math>が必要で, <math>x</math>, <math>y</math>をそれぞれ1単位当
 +
たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている．
 +
<math>
 +
\begin{center}
 +
\begin{tabular}{cccc}
 +
  & x & y & (在庫量) \\
 +
A & 10 & 20 & 400 \\
 +
B & 20 & 10 & 600 \\
 +
C & 15 & 40 & 1300
 +
\end{tabular}
 +
\end{center}
 +
</math>
 +
<math>x</math>, <math>y</math>を販売するとそれぞれ1単位当たり２万円, 1万円の利益が得られる.
 +
問題は, 表の在庫量の範囲で, <math>x</math>と<math>y</math>をそれぞれ何単位ずつ造れば利益が最大に
 +
なるかである。
 +
 +
これを数式化すると, <math>x</math>, <math>y</math>の製造量を<math>x</math>, <math>y</math>で表すとして：
 +
 +
原材料<math>A<math>, <math>B<math>, <math>C<math>についての制約から
 +
<math>
 +
10x+10y\leq 400 qquad (1) \\
 +
20x+10y\leq 600 \\
 +
15x+40y\leq 1300
 +
</math>
 +
 +
無論, 負の生産量はないのであるから
 +
 +
<math>
 +
0\leq x \\
 +
0\leq y qquad (5) \\
 +
</math>
 +
 +
 +
利益は 
 +
<math>
 +
2x+y qquad (6)
 +
</math>
 +
 +
で結局, (6)を<math>(1)\sim (5)</math>の条件のもとで最大にすることになる。下の図は関数<math>F(x,y)=2x+y<math>の図である。
 +
 +
 +
\vspace{5cm}
 +
\par 
 +
(図1.0)\\
 +
 +
 +
制約条件
 +
<math>
 +
10x+10y\leq 400 qquad (7) \\
 +
20x+10y\leq 600 \\
 +
15x+40y\leq 1300 \\
 +
0\leq x \\
 +
0\leq y qquad (8) \\
 +
</math>
 +
 +
 +
のもとで,関数
 +
<math>
 +
f(x,y)=2x+y qquad (9)
 +
</math>
 +
を最大化する問題である.
 +
条件<math>(7)\sim (8)</math>を充たす点<math>P=(x,y)</math>は
 +
下のような,凸多角形の境界線も含めた内部にある。
 +
 +
(図1.1)\\
 +
 +
この凸多角形の頂点を
 +
<math>
 +
P_0=(x_0,y_0),P_1=(x_1,y_1),P_2=(x_2,y_2),P_3=(x_3,y_3),P_4=(x_4,y_4)
 +
</math>
 +
とすると,
 +
内部の点<math>P=(x,y)</math>はこれらの頂点<math>P_i=(x_i,y_i),i=0,1,2,3,4</math>によって
 +
 +
<math>
 +
(1) \qquad P=\lambda_0 P_0 + \lambda_1 P_1+\lambda_2 P_2+\lambda_3 P_3+\lambda_4 P_4 \\
 +
(2) \qquad \lambda_0  + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4 =1 \\
 +
(3) \qquad 0 \le \lambda_0 \le 1,~~0 \le \lambda_1 \le 1,~~2 \le \lambda_2 \le 1,~~
 +
0 \le \lambda_3 \le 1,~~0 \le \lambda_4 \le 1
 +
</math>
 +
で表される。これを<math>P_i=(x_i,y_i),i=0,1,2,3,4</math>の凸結合という．
 +
 +
<math>
 +
f(x,y)=2x+y qquad (9)
 +
</math>
 +
には「線形性」という性質がある。
 +
これは
 +
<math>
 +
P=(x,y),Q=(x',y') 
 +
</math>
 +
 +
と<math>\alpha,\beta</math>について,
 +
 +
<math>
 +
f(\alpha P+ \beta Q)=f(\alpha (x,y)+\beta (x',y')
 +
=\alpha f(x,y)+\beta f(x',y')=\alpha f(P)+\beta f(Q)
 +
</math>
 +
という性質である。この線形性を使うと,以下の議論ができる。
 +
 +
まず各頂点での関数<math>f</math>
 +
<math>
 +
f(P_i)=f(x_i,y_i),i=0,1,2,3,4
 +
</math>
 +
のうち最大値を<math>f(P_*)=f(x_*,y_*)</math>とす。すると凸多角形の内の任意の
 +
 +
点<math>P=(x,y)<math>に対する<math>f(P)=f(x,y)<math>は
 +
 +
<math>P</math>が<math>P_i=(x_i,y_i),i=0,1,2,3,4</math>の凸結合で表されることから
 +
 +
<math> f(P)=f(\lambda_0 P_0 + \lambda_1 P_1+\lambda_2 P_2+\lambda_3 P_3+\lambda_4 P_4)</math>
 +
 +
さらに<math>f</math>の線形性から
 +
 +
<math>
 +
右辺=\lambda_0 f(x_0,y_0) + \lambda_1 f(x_1,y_1)
 +
+\lambda_2 f(x_2,y_2)+\lambda_3 f(x_3,y_3)+\lambda_4f(x_4,y_4) （ｆの線形性）
 +
</math>
 +
 +
<math>f(P_*)=f(x_*,y_*)</math>が最大で,(3)のように各<math>\lambda_i</math>は正の数(<math>1 \ge
 +
\lambda_i \ge 0</math>)であるから,
 +
 +
<math>
 +
右辺\le (\lambda_0  + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4)f(x_*,y_*)\\
 +
</math>
 +
 +
 +
さらに,(2)から
 +
 +
<math>
 +
\lambda_0  + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4= 1
 +
</math>
 +
 +
で
 +
 +
<math>
 +
f(P)=f(x,y) \le  f(x_*,y_*)=f(P_*)
 +
</math>
 +
となる。結局,関数<math>f</math>の制約条件を表す凸多角形の内部(境界を含む)の点全てを調べる必要がなく、
 +
 +
頂点での関数<math>f</math>の値を調べれば良いことが判る．
 +
 +
 +
(図1.2)
 +
 +
線形化計画法の代表的な解法であるシンプレクス法は,制約条件を表す凸多角形の頂点での
 +
関数<math>f</math>の値を効率的に調べる方法である。
 +
適当な,頂点から始め,関数<math>f</math>の値が増大する頂点へ次々移動して,最大解を探す．
 +
 +
この他に,凸多角形の内部の点から,最大解を与える頂点を探索する内点法もある。
 +
 +
 +
 +
ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している.　製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする．
ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している.　製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする．

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

生産計画



ある製造会社があって, xとyという２種類の製品の製造販売をしている. これらを製造するには, 原材料A，B，Cが必要で, 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単位当たり２万円, 1万円の利益が得られる. 問題は, 表の在庫量の範囲で, xとyをそれぞれ何単位ずつ造れば利益が最大に なるかである。

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

原材料A<math>,<math>B<math>,<math>C<math>についての制約から<math>10x+10y≤400qquad(1)20x+10y≤60015x+40y≤1300 

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

0≤x0≤yqquad(5)


利益は 2x+yqquad(6)

で結局, (6)を(1)∼(5)の条件のもとで最大にすることになる。下の図は関数F(x,y)=2x+y<math>の図である。\vspace5cm\par(図1.0)制約条件<math>10x+10y≤400qquad(7)20x+10y≤60015x+40y≤13000≤x0≤yqquad(8)


のもとで,関数 f(x,y)=2x+yqquad(9) を最大化する問題である. 条件(7)∼(8)を充たす点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≤λ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+yqquad(9) には「線形性」という性質がある。 これは 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)<math>に対する<math>f(P)=f(x,y)<math>は<math>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(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)

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

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



ある企業では製品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+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を求めよ.


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


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

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

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

「http://ja.iwschool.org/wiki/%E7%B7%9A%E5%BD%A2%E8%A8%88%E7%94%BB%E6%B3%95(%E7%94%9F%E7%94%A3%E8%A8%88%E7%94%BB)」より作成
個人用ツール