線形計画法(生産計画)
提供: Internet Web School
(→生産計画) |
|||
(間の29版分が非表示) | |||
14 行: | 14 行: | ||
例題1 | 例題1 | ||
- | ある製造会社があって, | + | ある製造会社があって, $x$ と $y$ という2種類の製品の製造販売をしている. |
- | これらを製造するには, 原材料 | + | これらを製造するには, 原材料$A$,$B$,$C$が必要で, $x$, $y$をそれぞれ1単位当 |
たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている. | たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている. | ||
- | {| border=" | + | {| border="3" class="wikitable" style="text-align: center; " |
- | | | + | |原材料\製品 |
+ | |x | ||
+ | |y | ||
+ | |在庫量 | ||
|- | |- | ||
- | | | + | ||A |
- | | | + | |10 |
+ | |20 | ||
+ | |400 | ||
|- | |- | ||
- | | | + | ||B |
- | | | + | |20 |
+ | |10 | ||
+ | |600 | ||
|- | |- | ||
- | | | + | ||C |
- | | | + | |15 |
+ | |40 | ||
+ | |1300 | ||
|} | |} | ||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | + | $x$, $y$を販売するとそれぞれ1単位当たり2万円, 1万円の利益が得られる. | |
- | + | 問題は, 表の在庫量の範囲で, $x$と$y$をそれぞれ何単位ずつ造れば利益が最大に | |
- | + | ||
- | 問題は, 表の在庫量の範囲で, | + | |
なるかである。 | なるかである。 | ||
55 行: | 51 行: | ||
===線形計画法(1)=== | ===線形計画法(1)=== | ||
- | これを数式化すると, | + | これを数式化すると, $x$, $y$の製造量を$x$, $y$で表すとして: |
- | 原材料 | + | 原材料$A$, $B$, $C$についての制約から |
- | + | $ | |
10x+20y\leq 400 \qquad (1) \\ | 10x+20y\leq 400 \qquad (1) \\ | ||
20x+10y\leq 600 \qquad (2) \\ | 20x+10y\leq 600 \qquad (2) \\ | ||
15x+40y\leq 1300 \qquad (3) | 15x+40y\leq 1300 \qquad (3) | ||
- | + | $ | |
負の生産量はないのであるから | 負の生産量はないのであるから | ||
- | + | $ | |
0\leq x \qquad (4) \\ | 0\leq x \qquad (4) \\ | ||
0\leq y \qquad (5) \\ | 0\leq y \qquad (5) \\ | ||
- | + | $ | |
利益は | 利益は | ||
- | + | $ | |
f(x,y)=2x+y \qquad (6) | f(x,y)=2x+y \qquad (6) | ||
- | + | $ | |
- | で結局, (6)を | + | で結局, (6)を$(1)\sim (5)$の条件のもとで最大にすることになる。 |
- | 下の図は関数 | + | 下の図は関数$f(x,y)=2x+y$の図である。 |
(図1.0)[[ファイル:Fig1.0.gif|400px]] | (図1.0)[[ファイル:Fig1.0.gif|400px]] | ||
- | 条件 | + | 条件$(1)\sim (5)$を充たす点$P=(x,y)$は |
下のような,凸多角形の境界線も含めた内部にある。 | 下のような,凸多角形の境界線も含めた内部にある。 | ||
91 行: | 87 行: | ||
この凸多角形の頂点を | この凸多角形の頂点を | ||
- | + | $ | |
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) | 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) | ||
- | + | $ | |
とすると, | とすると, | ||
- | 内部の点 | + | 内部の点$P=(x,y)$はこれらの頂点$P_i=(x_i,y_i),i=0,1,2,3,4$によって |
- | + | $ | |
(1) \qquad P=\lambda_0 P_0 + \lambda_1 P_1+\lambda_2 P_2+\lambda_3 P_3+\lambda_4 P_4 \\ | (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 \\ | (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, | (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 | 0 \le \lambda_3 \le 1,~~0 \le \lambda_4 \le 1 | ||
- | + | $ | |
- | で表される。これを | + | で表される。これを$P_i=(x_i,y_i),i=0,1,2,3,4$の凸結合という. |
- | + | $ | |
f(x,y)=2x+y \qquad (6) | f(x,y)=2x+y \qquad (6) | ||
- | + | $ | |
には「線形性」が成り立っている. | には「線形性」が成り立っている. | ||
これは | これは | ||
- | + | $ | |
P=(x,y),Q=(x',y') | P=(x,y),Q=(x',y') | ||
- | + | $ | |
- | と | + | と$\alpha,\beta$について, |
- | + | $ | |
f(\alpha P+ \beta Q)=f(\alpha (x,y)+\beta (x',y')) | 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) | =\alpha f(x,y)+\beta f(x',y')=\alpha f(P)+\beta f(Q) | ||
- | + | $ | |
という性質である。この線形性を使うと,以下の議論ができる。 | という性質である。この線形性を使うと,以下の議論ができる。 | ||
- | まず各頂点での関数 | + | まず各頂点での関数$f$の値 |
- | + | $ | |
f(P_i)=f(x_i,y_i),i=0,1,2,3,4 | f(P_i)=f(x_i,y_i),i=0,1,2,3,4 | ||
- | + | $ | |
- | のうち最大値を | + | のうち最大値を$f(P_*)=f(x_*,y_*)$とする. |
- | 凸多角形の内の任意の点 | + | 凸多角形の内の任意の点$P=(x,y)$に対する$f(P)=f(x,y)$は |
- | + | $P$が$P_i=(x_i,y_i),i=0,1,2,3,4$ | |
の凸結合で表されることから | の凸結合で表されることから | ||
- | + | $ f(P)=f(\lambda_0 P_0 + \lambda_1 P_1+\lambda_2 P_2+\lambda_3 P_3+\lambda_4 P_4)$ | |
- | さらに | + | さらに$f$の線形性から |
- | + | $ | |
右辺=\lambda_0 f(x_0,y_0) + \lambda_1 f(x_1,y_1) | 右辺=\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) (fの線形性) | +\lambda_2 f(x_2,y_2)+\lambda_3 f(x_3,y_3)+\lambda_4f(x_4,y_4) (fの線形性) | ||
- | + | $ | |
- | + | $f(P_*)=f(x_*,y_*)$が最大で,(3)のように各$\lambda_i$は正の数($1 \ge | |
- | \lambda_i \ge 0 | + | \lambda_i \ge 0$)であるから, |
- | + | $ | |
右辺\le (\lambda_0 + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4)f(x_*,y_*)\\ | 右辺\le (\lambda_0 + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4)f(x_*,y_*)\\ | ||
- | + | $ | |
さらに,(2)から | さらに,(2)から | ||
- | + | $ | |
\lambda_0 + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4= 1 | \lambda_0 + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4= 1 | ||
- | + | $ | |
で | で | ||
- | + | $ | |
f(P)=f(x,y) \le f(x_*,y_*)=f(P_*) | f(P)=f(x,y) \le f(x_*,y_*)=f(P_*) | ||
- | + | $ | |
- | となる。結局,関数 | + | となる。結局,関数$f$の制約条件を表す凸多角形の内部(境界を含む)の点全てを調べる必要がなく、 |
- | 頂点での関数 | + | 頂点での関数$f$の値を調べれば良いことが判る. |
(図1.2)[[ファイル:Fig1.2.gif|400px]] | (図1.2)[[ファイル:Fig1.2.gif|400px]] | ||
- | + | $(1)\sim(5) $式のように変数に関する制約条件式が1次式で与えられ, | |
- | + | $(6)$式のように評価関数も1次式で与えられる問題は[https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E8%A8%88%E7%94%BB%E6%B3%95 線形計画法]と呼ばれる. | |
線形化計画法の代表的な解法であるシンプレクス法は,制約条件を表す凸多角形の頂点での | 線形化計画法の代表的な解法であるシンプレクス法は,制約条件を表す凸多角形の頂点での | ||
- | 関数 | + | 関数$f$の値を効率的に調べる方法である。 |
- | 適当な,頂点から始め,関数 | + | 適当な,頂点から始め,関数$f$の値が増大する頂点へ次々移動して,最大解を探す. |
この他に,凸多角形の内部の点から,最大解を与える頂点を探索する内点法もある。 | この他に,凸多角形の内部の点から,最大解を与える頂点を探索する内点法もある。 | ||
196 行: | 192 行: | ||
また, 製品A,B,Cを1単位生産するのに必要な原料Ⅰ,Ⅱ,Ⅲ,Ⅳのそれぞれ量と使用可能な上限が次の表で与えられる. | また, 製品A,B,Cを1単位生産するのに必要な原料Ⅰ,Ⅱ,Ⅲ,Ⅳのそれぞれ量と使用可能な上限が次の表で与えられる. | ||
これらの条件のもとに,利益を最大にするには製品A,B,Cをそれぞれ,どれだけ生産すれば良いか?. | これらの条件のもとに,利益を最大にするには製品A,B,Cをそれぞれ,どれだけ生産すれば良いか?. | ||
- | + | ||
+ | {| border="3" class="wikitable" style="text-align: center; " | ||
+ | |原材\製品名 | ||
+ | |A | ||
+ | |B | ||
+ | |C | ||
+ | |使用できる上限 | ||
+ | |- | ||
+ | |Ⅰ | ||
+ | |4 | ||
+ | |0 | ||
+ | |7 | ||
+ | |90 | ||
+ | |- | ||
+ | |Ⅱ | ||
+ | |1 | ||
+ | |3 | ||
+ | |9 | ||
+ | |60 | ||
+ | |- | ||
+ | |Ⅲ | ||
+ | |6 | ||
+ | |0 | ||
+ | |14 | ||
+ | |110 | ||
+ | |- | ||
+ | |||
+ | |Ⅳ | ||
+ | |4 | ||
+ | |10 | ||
+ | |1 | ||
+ | |75 | ||
+ | |} | ||
+ | |||
この問題も例題1と同じように以下のように数学的に定式化される. | この問題も例題1と同じように以下のように数学的に定式化される. | ||
- | 製品A,B,Cをそれぞれ | + | 製品A,B,Cをそれぞれ$x_1,x_2,x_3$ 単位生産するとき$x_1,x_2,x_3$は以下の不等式を満たす. |
- | + | $ | |
4x_1+0x_2+7x_3 \leq 90 \\ | 4x_1+0x_2+7x_3 \leq 90 \\ | ||
1x_1+3x_2+9x_3 \leq 60 \\ | 1x_1+3x_2+9x_3 \leq 60 \\ | ||
6x_1+0x_2+14x_3 \leq 110 \\ | 6x_1+0x_2+14x_3 \leq 110 \\ | ||
4x_1+10x_2+1x_3 \leq 75 \qquad (1) | 4x_1+10x_2+1x_3 \leq 75 \qquad (1) | ||
- | + | $ | |
さらに各製品生産量は負ではないから | さらに各製品生産量は負ではないから | ||
- | + | $ | |
0 \leq x_1,0 \leq x_2,0 \leq x_3 \qquad (2) | 0 \leq x_1,0 \leq x_2,0 \leq x_3 \qquad (2) | ||
- | + | $ | |
この制約条件のもとに | この制約条件のもとに | ||
- | + | $ | |
L\left(x_1,x_2, x_3 \right)=80x_1+110x_2+95x_3 \qquad (3) | L\left(x_1,x_2, x_3 \right)=80x_1+110x_2+95x_3 \qquad (3) | ||
- | + | $ | |
- | を最大にする | + | を最大にする$x_1,x_2, x_3$を求めよ. |
263 行: | 292 行: | ||
をE3, E4, E5, E6に入力している. | をE3, E4, E5, E6に入力している. | ||
- | ここで,sumproduct(B4:D4,B2:D2)はベクトル(B4,C4,D4) と(B2,C2,D2)の内積 B4*B2+C4*C2+D4* | + | ここで,sumproduct(B4:D4,B2:D2)はベクトル(B4,C4,D4) と(B2,C2,D2)の内積 B4*B2+C4*C2+D4*D2 |
+ | であり$4x_1+0x_2+7x_3$ を表す. | ||
**F3,F4, F5, F6には,原材料Ⅰ,Ⅱ,Ⅲ,Ⅳの使用できる量の上限を入力している. | **F3,F4, F5, F6には,原材料Ⅰ,Ⅱ,Ⅲ,Ⅳの使用できる量の上限を入力している. |
2020年12月22日 (火) 04:28 時点における最新版
メディア:Example.ogg線形計画法は 線形計画法 (Wikipedia)に説明がある.
解法には
シンプレックス法(Wikipedia)や内点法(Wikipedia)がある. シンプレクス法は[菅沼]の解説が判りやすい.
ここでは2つの例を用いて説明する. Microsoft Excel のソルバーを用いた解法例も説明する.
生産計画
例題1
ある製造会社があって, x と y という2種類の製品の製造販売をしている. これらを製造するには, 原材料A,B,Cが必要で, x, yをそれぞれ1単位当 たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている.
原材料\製品 | x | y | 在庫量 |
A | 10 | 20 | 400 |
B | 20 | 10 | 600 |
C | 15 | 40 | 1300 |
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)∼(5)式のように変数に関する制約条件式が1次式で与えられ, (6)式のように評価関数も1次式で与えられる問題は線形計画法と呼ばれる.
線形化計画法の代表的な解法であるシンプレクス法は,制約条件を表す凸多角形の頂点での 関数fの値を効率的に調べる方法である。 適当な,頂点から始め,関数fの値が増大する頂点へ次々移動して,最大解を探す.
この他に,凸多角形の内部の点から,最大解を与える頂点を探索する内点法もある。
線形計画法(2)
例題2
ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している. 製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする. また, 製品A,B,Cを1単位生産するのに必要な原料Ⅰ,Ⅱ,Ⅲ,Ⅳのそれぞれ量と使用可能な上限が次の表で与えられる. これらの条件のもとに,利益を最大にするには製品A,B,Cをそれぞれ,どれだけ生産すれば良いか?.
原材\製品名 | A | B | C | 使用できる上限 |
Ⅰ | 4 | 0 | 7 | 90 |
Ⅱ | 1 | 3 | 9 | 60 |
Ⅲ | 6 | 0 | 14 | 110 |
Ⅳ | 4 | 10 | 1 | 75 |
この問題も例題1と同じように以下のように数学的に定式化される.
製品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のソルバーによる解法例を示す。
Microsoft Excelのソルバー を用いる.
- ソルバーの導入
- Excel の メニュー「データ」に「分析」「ソルバー」がある場合は以下の手続きは不要である.
そのままソルバーによる解法の例を実行する.
- Excelのメニュー「データ」に「分析」「ソルバー」がない場合
- ファイル > オプション > アドイン の順に選択
- アドインの表示窓 アクティブでないアプリケーションにExcelソルバー があることを確認
- 画面下の管理(A)と表示される小さい窓のドロップダウンリスト▼でExcelアドインを選択後,設定(G)をクリック
- 有効なアドインが小窓で表示される. その中のソルバーアドインを選択しチェックを入れ[OK]をクリックする.
- ソルバーによる解法の例
- Excelに下記の作成例のように表1のデータを作成する.
この作成例では
セル B2,C2,D2 が 製品A,B,Cのそれぞれの生産量
x1,x2,x3を表す.
- 線形の一次式
4x1+0x2+7x31x1+3x2+9x36x1+0x2+14x34x1+10x2+1x3
をE3, E4, E5, E6に入力している.
ここで,sumproduct(B4:D4,B2:D2)はベクトル(B4,C4,D4) と(B2,C2,D2)の内積 B4*B2+C4*C2+D4*D2 であり4x1+0x2+7x3 を表す.
- F3,F4, F5, F6には,原材料Ⅰ,Ⅱ,Ⅲ,Ⅳの使用できる量の上限を入力している.
- E7には
L(x1,x2,x3)=80x1+110x2+95x3
を表す式を入力している.
- 表のデータを入力後,
- メニュー 「データ」,「分析」,「ソルバー」の順にクリックしてソルバーのパラメータ入力用の窓を開く.
- 表のデータを入力後,
- 目的の設定という欄にセルE7を指定する
- 目標値には「最大値」を選択し,チェックを入れる.
- 変数セルの変更欄にはx_1,x_2,x_3を表すセルB2からD2をドラックして指定する.
- 制約条件の対象の欄には
この例題の制約条件式
4x1+0x2+7x3≤901x1+3x2+9x3≤606x1+0x2+14x3≤1104x1+10x2+1x3≤75
を表す式を入力する. このためには,入力窓の「追加」をクリックし制約条件の追加入力用の窓を表示させ, 例えば
4x1+0x2+7x3≤90
を表す式を入力するのであればセルの参照欄に4x1+0x2+7x3を表すセルE3を指定 ≦,=,≧などのドロップダウンリストで≦を選択し,制約条件の欄には上限値の90を入力する.入力後さらに「追加」をクリックし他の3つの制約条件式も同様に入力する.
- さらに, 制約条件式
0≤x1,0≤x2,0≤x3 を入力するため
「制約のない変数を非負数にする」 にチェックを入れる.
- 最後に「解決」をクリックすると以下の結果が出力される.
x1=7.8,x2=3.9,x3=4.5
のときに
L(x1,x2, x3)=80x1+110x2+95x3
が最大値1485をもつことを表す.制約条件は満たされている.