線形計画法(生産計画)

提供: Internet Web School

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

解法には

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

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

生産計画

例題1

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

Food complements

オレンジ	りんご
パン	パイ
バター	アイスクリーム

\(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)

条件\((1)\sim (5)\)を充たす点\(P=(x,y)\)は 下のような,凸多角形の境界線も含めた内部にある。

(図1.1)

この凸多角形の頂点を \( 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)

\((1)\sim(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をそれぞれ,どれだけ生産すれば良いか?.

この問題も例題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\)を求めよ.

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

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

Microsoft Excelのソルバー　を用いる.

• ソルバーの導入
• Excel　の　メニュー「データ」に「分析」「ソルバー」がある場合は以下の手続きは不要である．　

そのままソルバーによる解法の例を実行する．　

• Excelのメニュー「データ」に「分析」「ソルバー」がない場合
  • ファイル　>　オプション　>　アドイン　の順に選択
  • アドインの表示窓　アクティブでないアプリケーションにExcelソルバー　があることを確認
  • 画面下の管理(A)と表示される小さい窓のドロップダウンリスト▼でExcelアドインを選択後，設定(G)をクリック
  • 有効なアドインが小窓で表示される.　その中のソルバーアドインを選択しチェックを入れ[OK]をクリックする.

• ソルバーによる解法の例　
  • Excelに下記の作成例のように表１のデータを作成する.

この作成例では セル　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 　　 $

を表す式を入力している．

• • 表のデータを入力後,
    • メニュー　「データ」，「分析」，「ソルバー」の順にクリックしてソルバーのパラメータ入力用の窓を開く．

• • • 目的の設定という欄にセル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　 $ を入力するため

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

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

$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をもつことを表す.制約条件は満たされている.