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

線形計画法(生産計画)

提供: Internet Web School

(版間での差分)
(ページの作成: (生産計画) ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している.　製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする． 　…)
 
(間の140版分が非表示)
1 行: 1 行:
-
  (生産計画)
+
[[メディア:Example.ogg]]線形計画法は
 +
[https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E8%A8%88%E7%94%BB%E6%B3%95 線形計画法]
 +
（Wikipedia）に説明がある.
 +
 
 +
解法には
 +
 
 +
[https://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%B3%E3%83%97%E3%83%AC%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95 シンプレックス法]（Wikipedia）や[https://ja.wikipedia.org/wiki/%E5%86%85%E7%82%B9%E6%B3%95 内点法]（Wikipedia）がある.
 +
シンプレクス法は[https://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/linear/linear.htm#1.2 [菅沼]]の解説が判りやすい．
 +
 
 +
ここでは2つの例を用いて説明する.　Microsoft　Excel　のソルバーを用いた解法例も説明する.
 +
 
 +
==生産計画==
 +
 
 +
例題1
 +
 
 +
ある製造会社があって, x と y という２種類の製品の製造販売をしている.
 +
これらを製造するには, 原材料A，B，Cが必要で, x, yをそれぞれ1単位当
 +
たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている．
 +
 
 +
 
 +
 
 +
{| 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単位当たり２万円, 1万円の利益が得られる.
 +
問題は, 表の在庫量の範囲で, xとyをそれぞれ何単位ずつ造れば利益が最大に
 +
なるかである。
 +
 
 +
 
 +
===線形計画法(1)===
 +
 
 +
これを数式化すると, x, yの製造量をx, yで表すとして：
 +
 
 +
原材料A, B, Cについての制約から
 +
 
 +
$
 +
  10x+20y\leq 400  \qquad (1) \\
 +
20x+10y\leq 600  \qquad (2) \\
 +
15x+40y\leq 1300 \qquad (3)
 +
$
 +
 
 +
負の生産量はないのであるから
 +
 
 +
$
 +
0\leq x \qquad (4) \\
 +
0\leq y \qquad (5) \\
 +
$
 +
 
 +
利益は 
 +
 
 +
$
 +
f(x,y)=2x+y \qquad (6)
 +
$
 +
 
 +
で結局, (6)を(1)∼(5)の条件のもとで最大にすることになる。
 +
 
 +
 
 +
下の図は関数f(x,y)=2x+yの図である。
 +
 
 +
(図1.0)[[ファイル:Fig1.0.gif|400px]]
 +
 
 +
条件(1)∼(5)を充たす点P=(x,y)は
 +
下のような,凸多角形の境界線も含めた内部にある。
 +
 
 +
(図1.1)[[ファイル:Fig1.1.gif|400px]]
 +
 
 +
この凸多角形の頂点を
 +
$
 +
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)はこれらの頂点Pi=(xi,yi),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 \\
 +
(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
 +
$
 +
 
 +
 
 +
で表される。これをPi=(xi,yi),i=0,1,2,3,4の凸結合という．
 +
 
 +
$
 +
f(x,y)=2x+y \qquad (6)
 +
$
 +
 
 +
には「線形性」が成り立っている.
 +
 
 +
これは
 +
$
 +
P=(x,y),Q=(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)
 +
$
 +
 
 +
という性質である。この線形性を使うと,以下の議論ができる。
 +
 
 +
 
 +
まず各頂点での関数fの値
 +
 
 +
$
 +
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がPi=(xi,yi),i=0,1,2,3,4
 +
の凸結合で表されることから
 +
 
 +
f(P)=f(λ0P0+λ1P1+λ2P2+λ3P3+λ4P4)
 +
 
 +
さらにfの線形性から
 +
 
 +
$
 +
右辺=\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(P∗)=f(x∗,y∗)が最大で,(3)のように各λiは正の数($1 \ge
 +
\lambda_i \ge 0$)であるから,
 +
 
 +
$
 +
右辺\le (\lambda_0  + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4)f(x_*,y_*)\\
 +
$
 +
 
 +
 
 +
さらに,(2)から
 +
 
 +
$
 +
\lambda_0  + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4= 1
 +
$
 +
 
 +
で
 +
 
 +
$
 +
f(P)=f(x,y) \le  f(x_*,y_*)=f(P_*)
 +
$
 +
 
 +
となる。結局,関数fの制約条件を表す凸多角形の内部(境界を含む)の点全てを調べる必要がなく、
 +
 
 +
頂点での関数fの値を調べれば良いことが判る．
 +
 
 +
 
 +
(図1.2)[[ファイル:Fig1.2.gif|400px]]
 +
 
 +
(1)∼(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の値が増大する頂点へ次々移動して,最大解を探す．
 +
 
 +
この他に,凸多角形の内部の点から,最大解を与える頂点を探索する内点法もある。
 +
 
 +
===線形計画法(2)===
 +
 
 +
例題2
 +
 
ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している.　製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする．
ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している.　製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする．
　また, 製品A,B,Cを1単位生産するのに必要な原料Ⅰ,Ⅱ,Ⅲ,Ⅳのそれぞれ量と使用可能な上限が次の表で与えられる.
　また, 製品A,B,Cを1単位生産するのに必要な原料Ⅰ,Ⅱ,Ⅲ,Ⅳのそれぞれ量と使用可能な上限が次の表で与えられる.
 +
これらの条件のもとに,利益を最大にするには製品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と同じように以下のように数学的に定式化される．
 +
製品A,B,Cをそれぞれx1,x2,x3 単位生産するときx1,x2,x3は以下の不等式を満たす.
 +
 +
$
 +
4x_1+0x_2+7x_3 \leq  90 \\
 +
1x_1+3x_2+9x_3 \leq  60 \\
 +
6x_1+0x_2+14x_3 \leq 110 \\
 +
4x_1+10x_2+1x_3 \leq    75　\qquad (1)
 +
$
 +
 +
さらに各製品生産量は負ではないから
 +
 +
$
 +
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)　　
 +
$
 +
 +
を最大にするx1,x2,x3を求めよ.
 +
 +
 +
この問題の解法には[https://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%B3%E3%83%97%E3%83%AC%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95 シンプレックス法]や[https://ja.wikipedia.org/wiki/%E5%86%85%E7%82%B9%E6%B3%95 内点法]がある.
 +
シンプレクス法は[https://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/linear/linear.htm#1.2 [菅沼]]の解説が判りやすい．
 +
 +
 +
この問題を解くのにはMicrosoft Excelのソルバーや
 +
フリーソフトのOpen Office で提供されるソルバーと同等の機能をもつソフトを用いることができる.
 +
この問題のMicrosoft Excelのソルバーによる解法例を示す。
 +
 +
 +
Microsoft Excelのソルバー　を用いる.
 +
*ソルバーの導入
 +
*Excel　の　メニュー「データ」に「分析」「ソルバー」がある場合は以下の手続きは不要である．　
 +
そのままソルバーによる解法の例を実行する．　
 +
*Excelのメニュー「データ」に「分析」「ソルバー」がない場合
 +
**ファイル　>　オプション　>　アドイン　の順に選択
 +
**アドインの表示窓　アクティブでないアプリケーションにExcelソルバー　があることを確認
 +
**画面下の管理(A)と表示される小さい窓のドロップダウンリスト▼でExcelアドインを選択後，設定(G)をクリック
 +
**有効なアドインが小窓で表示される.　その中のソルバーアドインを選択しチェックを入れ[OK]をクリックする.
 +
 +
*ソルバーによる解法の例　
 +
**Excelに下記の作成例のように表１のデータを作成する.
 +
[[ファイル:LP-Fig.2.jpg|500px]]
 +
 +
[[ファイル:LP-Fig3.jpg|500px]]
 +
 +
 +
この作成例では
 +
セル　B2,C2,D2　が　製品A,B,Cのそれぞれの生産量
 +
x1,x2,x3を表す.
 +
 +
** 線形の一次式
 +
$
 +
4x_1+0x_2+7x_3\\
 +
1x_1+3x_2+9x_3 \\
 +
6x_1+0x_2+14x_3 \\
 +
4x_1+10x_2+1x_3
 +
$
 +
 +
を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\left(x_1,x_2, x_3 \right)=80x_1+110x_2+95x_3 　　
 +
$
 +
 +
を表す式を入力している．
 +
** 表のデータを入力後,
 +
*** メニュー　「データ」，「分析」，「ソルバー」の順にクリックしてソルバーのパラメータ入力用の窓を開く．
 +
[[ファイル:LP-Fig.4.jpg|500px]]
 +
*** 目的の設定という欄にセルE7を指定する　
 +
*** 目標値には「最大値」を選択し，チェックを入れる．
 +
*** 変数セルの変更欄にはx_1,x_2,x_3を表すセルB2からD2をドラックして指定する．
 +
 +
***制約条件の対象の欄には
 +
この例題の制約条件式
 +
 +
$
 +
4x_1+0x_2+7x_3 \leq  90 \\
 +
1x_1+3x_2+9x_3 \leq  60 \\
 +
6x_1+0x_2+14x_3 \leq 110 \\
 +
4x_1+10x_2+1x_3 \leq    75　
 +
$
 +
 +
を表す式を入力する．　
 +
　このためには,入力窓の「追加」をクリックし制約条件の追加入力用の窓を表示させ,
 +
例えば
 +
 +
4x1+0x2+7x3≤90
 +
 +
を表す式を入力するのであればセルの参照欄に4x1+0x2+7x3を表すセルE3を指定
 +
≦,=,≧などのドロップダウンリストで≦を選択し,制約条件の欄には上限値の90を入力する．入力後さらに「追加」をクリックし他の３つの制約条件式も同様に入力する．
 +
 +
***さらに, 制約条件式　
 +
 +
$
 +
0 \leq x_1,0 \leq x_2,0 \leq x_3　
 +
$
 +
を入力するため
 +
 +
「制約のない変数を非負数にする」　にチェックを入れる．
 +
 +
 +
**最後に「解決」をクリックすると以下の結果が出力される.
 +
 +
[[ファイル:LP-Fig.5.jpg|500px]]
 +
 +
 +
x1=7.8,x2=3.9,x3=4.5
 +
のときに
 +
 +
L(x1,x2, x3)=80x1+110x2+95x3　
 +
 +
が最大値1485をもつことを表す.制約条件は満たされている.

2020年12月22日 (火) 04:28 時点における最新版

メディア:Example.ogg線形計画法は 線形計画法 （Wikipedia）に説明がある.

解法には

シンプレックス法（Wikipedia）や内点法（Wikipedia）がある. シンプレクス法は[菅沼]の解説が判りやすい．

ここでは2つの例を用いて説明する.　Microsoft　Excel　のソルバーを用いた解法例も説明する.

生産計画

例題1

ある製造会社があって, x と y という２種類の製品の製造販売をしている. これらを製造するには, 原材料A，B，Cが必要で, x, yをそれぞれ1単位当 たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている．


原材料＼製品 x y 在庫量
A 10 20 400
B 20 10 600
C 15 40 1300


x, yを販売するとそれぞれ1単位当たり２万円, 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.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≤λ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(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)

(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に下記の作成例のように表１のデータを作成する.


この作成例では セル　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を入力する．入力後さらに「追加」をクリックし他の３つの制約条件式も同様に入力する．

      • さらに, 制約条件式　

0≤x1,0≤x2,0≤x3 を入力するため

「制約のない変数を非負数にする」　にチェックを入れる．


    • 最後に「解決」をクリックすると以下の結果が出力される.


x1=7.8,x2=3.9,x3=4.5 のときに

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

が最大値1485をもつことを表す.制約条件は満たされている.

「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)」より作成
個人用ツール