最大化問題

先ず線形計画法の典型的な問題から：

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

	x	y	(在庫量)
A	10	10	400
B	20	10	600
C	15	40	1300

$x$, $y$を販売するとそれぞれ1単位当たり２万円, 1万円の利益が得られます。 問題は, 表の在庫量の範囲で, $x$と$y$をそれぞれ何単位ずつ造れば利益が最大に なるかです。

これを数式化すると, $x$, $y$の製造量を$x$, $y$で表すとして：

原材料$A$, $B$, $C$についての制約から

$$10x+10y\leq 400$$ (1)

$$20x+10y\leq 600$$ (2)

$$15x+40y\leq 1300$$ (3)

$$無論, 負の生産量はないのですから$$

$$0\leq x$$ (4)

$$0\leq y$$ (5)

$$利益は 2x+y$$ (6)

で結局, (6)を $(\ref{senkei1})\sim (\ref{senkei5})$の条件のもとで最大にすることになります。下の図は関数$F(x,y)=2x+y$の図です。

(図1.0)

この 程度の簡単な問題なら, 手計算でできますが, 変数が$x$, $y$の２個ではなく, 実際の 問題では, 数百個というものがあります。そのため, 計算機を使うことになりますが このような問題を効率良く解くために開発されたものにシンプレクス法があります。 それについての説明は, 後で, 述べることとして, まず上の問題にチャレンジしてください。

例えば, Microsoft Excelでは次のようにワークシートを作成します。

	A	B	C	D
1			=A1*2+B1
2	10	10	=A1*A2+B1*B2	400
3	20	10	=A1*A3+B1*B3	600
4	15	40	=A1*A4+B1*B4	1300

ツールメニューのソルバーを選択
目的セル $C1$
目標値 最大値
変化させるセル $A1:B1$
制約条件

$A1=>0$

$B1=>0$

$C2<=D2$

$C3<=D3$

$C4<=D4$

セルの$A1$が$x$, $B1$が$y$を表しています。 制約条件を入力するには, 制約条件の「追加」を選択して 入力します。 各セルの指定はマウスでそのセルをクリックします。$<=$, $=$, $=>$, 範囲指定などの選択も出来ます。