数理最適化（線形計画問題②）

線形計画問題の定式化をいくつか見ていきたいと思います。

生産計画問題

・○○製造会社は、複数の製品を生産している
製造会社の清算効率を最大化し、コストを最小化したいという問題です。

問題

・M：製品の数
・T：製造会社の生産可能な総時間
・R：利用可能な総資源量
・ci：製品 i の単位時間当たりのコスト
・di：製品 i の需要量
・pi：製品 i 1個当たりの販売価格
・ti：製品 i 1個当たりの生産時間
・ri：製品 i 1個当たりの資源量
・xi：製品 i の生産量
利益が最大となるよう、各製品の生産量を求めます。

$$
\begin{array}{|c|c|c|c|c|c|}
\hline
 & コスト & 価格 & 需要量 & 生産時間 & 資源量 \\
\hline
製品_1 & c_1 & p_1 & d_1& t_1 & r_1 \\
製品_2 & c_2 & p_2 & d_2 & t_2 & r_2\\
… & … & … & … & … & … \\
製品_M & c_M & p_M & d_M & t_M & r_M \\
\hline
\end{array}
$$

定式化

製品ごとの収入総額は、
　　生産量　×　1個当たりの販売価格
で表せます。
支出の総額は、
　　生産量　×　1個当たりの生産コスト
で表せます。
利益は、
　　利益　＝　収入総額　－　支出総額
　　　　　＝　( 生産量　×　販売価格 )　－　( 生産量　×　生産コスト )
　　　　　＝　生産量　×　( 販売価格　－　生産コスト )
となります。
そのため、利益の合計は、
　　利益合計　＝　　製品1の生産量　×　( 製品1価格 － 製品1コスト )
　　　　　　　　＋　製品2の生産量　×　( 製品2価格 － 製品2コスト )
　　　　　　　　＋　　　・・・
　　　　　　　　＋　製品Mの生産量　×　( 製品M価格 － 製品Mコスト )
　　　　　　　＝　　x1　×　( p1 - c1 )
　　　　　　　　＋　x2　×　( p2 - c2 )
　　　　　　　　＋　　　・・・
　　　　　　　　＋　xM　×　( pM - cM )
となります。
これは、以下の定式で表すことができます。
（業者番号を j とする）

$$
\displaystyle\sum _{i=1}^{M} {x_i ( p_i - c_i )} \\
$$

目的関数

$$
最大化　\displaystyle\sum _{i=1}^{M} {x_i ( p_i - c_i )} \\
$$

制約条件
・需要量以上生産しないといけない
・総生産時間は、生産可能な時間を超えてはいけない
・資源量の総使用量は、利用可能な総資源量を超えてはいけない
・生産量は 0 以上

$$
{x_{i}} \ge d_i,    \forall i\\
\displaystyle\sum _{i=1}^{M} {t_i x_i} \le T,    \forall j\\
\displaystyle\sum _{i=1}^{M} {r_i x_i} \le R,    \forall j\\
xi \ge 0,    \forall i
$$

定式化できました。

輸送問題

次に、輸送問題を定式化してみます。
・○○企業は、日本全国に工場を持っている
・全工場で同じ商品を作っている
・この商品を取り扱っている複数の取引業者がある
各工場から各取引業者への出荷量を最適化したいという問題です。

問題

・M：工場の数
・N：取引業者の数
・ai：工場 i の生産量の上限
・bj：取引業者 j の納品量
・ci：工場 i から取引業者へ商品を輸送する際の単位量あたりの輸送費
・xi：工場 i からの輸送量
輸送費合計が最小となるよう、各工場から各業者への輸送量を求めます。

$$
\begin{array}{|c|c|c|}
\hline
 & 生産量上限 & 業者への輸送費 \\
 &  & \begin{array}{c|c|c|c} c_{1} & c_{2} & … & c_{n} \end{array} \\
\hline
工場_1 & a_1 & \begin{array}{c|c|c|c} c_{11} & c_{12} & … & c_{1n} \end{array} \\
工場_2 & a_2 & \begin{array}{c|c|c|c} c_{21} & c_{22} & … & c_{2n} \end{array} \\
… & … & … \\
工場_M & a_M & \begin{array}{c|c|c|c} c_{M1} & c_{M2} & … & c_{MN} \end{array} \\
\hline
\end{array}
$$

$$
\begin{array}{|c|c|}
\hline
 & 納品量 \\
\hline
業者_1 & b_1\\
業者_2 & b_2 \\
… & … \\
業者_N & b_N \\
\hline
\end{array}
$$

定式化

工場から各取引業者への輸送量は、
　　単位量あたりの輸送費　×　輸送量
で表せます。
そのため、工場１(a1) の輸送費合計は、
　　a1の輸送費合計　＝　　a1→b1輸送費　×　a1 の b1 への輸送量
　　　　　　　　　　　＋　a1→b2輸送費　×　a1 の b2 への輸送量
　　　　　　　　　　　＋　　　・・・
　　　　　　　　　　　＋　a1→bN 輸送費　×　a1 の bN への輸送量
　　　　　　　　　　＝　　c11　×　x11
　　　　　　　　　　　＋　c12　×　x12
　　　　　　　　　　　＋　　　・・・
　　　　　　　　　　　＋　c1N　×　x1N
となります。
これは、以下の定式で表すことができます。
（業者番号を j とする）

$$
\displaystyle\sum _{j=1}^{N} {c_{1j} x_{1j}} \\
$$

同様に、工場２(a2) の輸送費合計は、以下のように表せます。

$$
\displaystyle\sum _{j=1}^{N} {c_{2j} x_{2j}} \\
$$

全ての工場の輸送費合計を求めるには、
　全工場の輸送費合計　＝　　工場１の輸送費合計
　　　　　　　　　　　　＋　工場２の輸送費合計
　　　　　　　　　　　　＋　　・・・
　　　　　　　　　　　　＋　工場ｎの輸送費合計
とすればよいので、目的関数は以下のように表すことができます。

$$
\displaystyle\sum _{i=1}^{M} \sum _{j=1}^{N} {c_{ij} x_{ij}}  \\
$$

目的関数

$$
最小化　\displaystyle\sum _{j=1}^{N} {c_{2j} x_{2j}} \\
$$

制約条件
・工場の生産量上限 a を超えてはならない
・「工場からの輸送量合計」と「業者の納品量」は一致
・輸送量は 0 以上

$$
\displaystyle\sum _{j=1}^{N} {x_{ij}} \le a_i,    \forall i\\
\displaystyle\sum _{i=1}^{M} {x_{ij}} = b_j,    \forall j\\
xij \ge 0,    \forall i,   \forall j
$$

定式化できました。

なんとなく、コツをつかんできました。
次回は、非線形関数の近似に取り組んでみたいと思います。