次の表 8 は、ある工場における製品 A と製品 B の製造に係る諸条件をまとめたものである。
制限量 | 製品 A | 製品 B | |
利益 | 50 | 60 | |
原料 1 | 50 | 0.15 | 0.05 |
原料 2 | 40 | 0.05 | 0.10 |
生産能力 | 500 | 1 | 1 |
ある工場では製品 A と製品 B をそれぞれ同じ原料 1 と原料 2 を使って生産している。表 8 の制限量の列は各原料の在庫量および工場の生産能力の上限を表しており、各製品の列はそれぞれの生産時における消費量を表している。また、利益の行は各製品の生産1単位(販売1単位)当たりの利益を表している。このとき、利益を最大にするための各製品の最適生産量を求めよ。
さまざまな条件の下で最も大きな成果を上げたいといったことはあらゆる場面で見られることである。ここでは、使用できる原料や生産能力の範囲内で利益が最も大きくなるような2つの製品の生産量の組み合わせを求めることが目標であるが、このように複数の組み合わせの中から最も良い組み合わせを求める問題を組み合わせ最適化問題という。
組み合わせ最適化問題を解く方法には、その制約条件や目的の性質(数や複雑さなど)に応じた様々な方法が提案されているが、ここでは、問題を数式によりモデル化(定式化)した場合に、すべての式が1次式(線形式)で表される場合に適用できる線形計画法を用いる。
どのような問題であっても、数理的な処理を行うためには問題を単純化し、数式で表現するモデル化が必要となる。
今、製品 A の生産量を $x$、製品 B の生産量を $y$ とおくと、その利益 $z$ は表 8 より
$$ z=50x+60y $$
で表すことができる。この式を目的関数という。同様に原材料と生産能力による制約条件を式で表すと
\begin{gather*} 0.15x+0.05y\leqq 50 \\ 0.05x+0.10y\leqq 40 \\ x+y\leqq 500 \\ x,y\geqq 0 \end{gather*}
となる。これらを制約式という。
このように、この問題は上の 4 つの制約式を満たし、目的関数 $z$ を最大化する $x$ と $y$ の組み合わせ最適化問題としてモデル化(定式化)でき、目的関数および制約式がすべて1次式で表されていることから、線形計画法を適用することができる。ここでは グラフ利用による方法と Excel に付属のアドインからソルバーを用いた方法により線形計画法による解を求める。
制約式と目的関数をグラフ化すると図 10 のようになる。これは求める $x$ と $y$ の組み合わせが、制約式1~3を表す直線と $x$ 軸および $y$ 軸によって囲まれた多角形内にあることを意味している。また、目的関数を表す直線の式において、利益 $z$ は $y$ 切片 $\displaystyle\frac{z}{60}$ 内にあることから、$z$ の値を大きくすることにより直線は傾き一定のまま平行移動することになる。このことから、求める解は、目的関数の直線が制約式で表される多角形の一部を通り(制約条件を満たすこと)、かつ、目的関数の直線の切片が最も大きくなる(利益最大)目的関数の直線上にあることが分かる。
ソルバーを利用するには、まず、表8 をもとにした計算表を作成しておく必要がある。
制限量 | 製品 A | 製品 B | 利益/消費量 | |
変数 | ||||
利益 | 50 | 60 | =C3*\$C\$2+D3*\$D\$2 | |
原料 1 | 50 | 0.15 | 0.05 | =C4*\$C\$2+D4*\$D\$2 |
原料 2 | 40 | 0.05 | 0.10 | =C5*\$C\$2+D5*\$D\$2 |
生産能力 | 500 | 1 | 1 | =C6*\$C\$2+D6*\$D\$2 |
表 9 の左上をセル A1 としたとき、C2,D2 に生産量を入力したときの総利益(E3)、原料および生産能力の消費量(E4:E6)を求める数式を入力しておく。この状態で C2,D2 に入力する数量を試行錯誤することにより総利益(E3)を求めることができるが、これにより最適な組み合わせを求めることは難しい。そこでここではソルバーを利用することにする。