ソースを表示

提供: Internet Web School

以下に示された理由により、このページの編集を行うことができません:

このページのソースを閲覧し、コピーすることができます:

[[メディア: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 ある製造会社があって, <math>x</math>と<math>y</math>という２種類の製品の製造販売をしている. これらを製造するには, 原材料<math>A</math>，<math>B</math>，<math>C</math>が必要で, <math>x</math>, <math>y</math>をそれぞれ1単位当 たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている． {| border="3" class="wikitable" |原材料＼製品 |x |y |在庫量 |- ||A |10 |20 |400 |- ||B |20 |10 |600 |- ||C |15 |40 |1300 |} <math>x</math>, <math>y</math>を販売するとそれぞれ1単位当たり２万円, 1万円の利益が得られる. 問題は, 表の在庫量の範囲で, <math>x</math>と<math>y</math>をそれぞれ何単位ずつ造れば利益が最大に なるかである。 ===線形計画法(1)=== これを数式化すると, <math>x</math>, <math>y</math>の製造量を<math>x</math>, <math>y</math>で表すとして： 原材料<math>A</math>, <math>B</math>, <math>C</math>についての制約から <math> 10x+20y\leq 400 \qquad (1) \\ 20x+10y\leq 600 \qquad (2) \\ 15x+40y\leq 1300 \qquad (3) </math> 負の生産量はないのであるから <math> 0\leq x \qquad (4) \\ 0\leq y \qquad (5) \\ </math> 利益は <math> f(x,y)=2x+y \qquad (6) </math> で結局, (6)を<math>(1)\sim (5)</math>の条件のもとで最大にすることになる。 下の図は関数<math>f(x,y)=2x+y</math>の図である。 (図1.0)[[ファイル:Fig1.0.gif|400px]] 条件<math>(1)\sim (5)</math>を充たす点<math>P=(x,y)</math>は 下のような,凸多角形の境界線も含めた内部にある。 (図1.1)[[ファイル:Fig1.1.gif|400px]] この凸多角形の頂点を <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 (6) </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)[[ファイル:Fig1.2.gif|400px]] <math>(1)\sim(5) </math>式のように変数に関する制約条件式が1次式で与えられ, <math>(6)</math>式のように評価関数も1次式で与えられる問題は[https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E8%A8%88%E7%94%BB%E6%B3%95 線形計画法]と呼ばれる. 線形化計画法の代表的な解法であるシンプレクス法は,制約条件を表す凸多角形の頂点での 関数<math>f</math>の値を効率的に調べる方法である。 適当な,頂点から始め,関数<math>f</math>の値が増大する頂点へ次々移動して,最大解を探す． この他に,凸多角形の内部の点から,最大解を与える頂点を探索する内点法もある。 ===線形計画法(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; color: green;" |原材＼製品名 |A |B |C |使用できる上限 |- |Ⅰ |4 |0 |7 |90 |- |Ⅱ |1 |3 |9 |60 |- |Ⅲ |6 |0 |14 |110 |- |Ⅳ |4 |10 |1 |75 |} この問題も例題1と同じように以下のように数学的に定式化される． 製品A,B,Cをそれぞれ<math>x_1,x_2,x_3</math> 単位生産するとき<math>x_1,x_2,x_3</math>は以下の不等式を満たす. <math> 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) </math> さらに各製品生産量は負ではないから <math> 0 \leq x_1,0 \leq x_2,0 \leq x_3 \qquad (2)　 </math> この制約条件のもとに <math> L\left(x_1,x_2, x_3 \right)=80x_1+110x_2+95x_3 \qquad (3)　　 </math> を最大にする<math>x_1,x_2, x_3</math>を求めよ. この問題の解法には[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　であり4\bulletx_1+\ \ 0\bulletx_2+\ \ {7\bulletx}_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をもつことを表す.制約条件は満たされている.

線形計画法(生産計画) に戻る。