ソースを表示

[[メディア: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)\sim (5)$の条件のもとで最大にすることになる。


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

(図1.0)[[ファイル:Fig1.0.gif|400px]]

条件$(1)\sim (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)$はこれらの頂点$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 \\
(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
$


で表される。これを$P_i=(x_i,y_i),i=0,1,2,3,4$の凸結合という．

$
 f(x,y)=2x+y \qquad (6)
$

には「線形性」が成り立っている.

これは
$
P=(x,y),Q=(x',y')  
$

と$\alpha,\beta$について,

$
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$が$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_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)のように各$\lambda_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)\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$の値が増大する頂点へ次々移動して,最大解を探す．

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

===線形計画法(2)===

例題2

ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している.　製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする．
　また, 製品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をそれぞれ$x_1,x_2,x_3$ 単位生産するとき$x_1,x_2,x_3$は以下の不等式を満たす.

$
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)　　
$

を最大にする$x_1,x_2, x_3$を求めよ.


この問題の解法には[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のそれぞれの生産量
$x_1,x_2,x_3$を表す.

** 線形の一次式
$
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,B$2:D$2)はベクトル(B4,C4,D4) と(B2,C2,D2)の内積　B4*B2+C4*C2+D4*D2　
であり$4x_1+0x_2+7x_3$　を表す．

**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　
$

を表す式を入力する．　
　このためには,入力窓の「追加」をクリックし制約条件の追加入力用の窓を表示させ,
例えば

$4x_1+0x_2+7x_3 \leq  90$

を表す式を入力するのであればセルの参照欄に$4x_1+0x_2+7x_3$を表すセルE3を指定
≦,=,≧などのドロップダウンリストで≦を選択し,制約条件の欄には上限値の90を入力する．入力後さらに「追加」をクリックし他の３つの制約条件式も同様に入力する．

***さらに, 制約条件式　

$
0 \leq x_1,0 \leq x_2,0 \leq x_3　
$
を入力するため

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

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

[[ファイル:LP-Fig.5.jpg|500px]]


$x_1=7.8,x_2=3.9,x_3=4.5$
のときに

$L\left(x_1,x_2,\ x_3 \right)=80x_1+110x_2+95x_3$　

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



フリーソフトOpenOfficeの表計算(Calc)　でも同様に解くことができる.