生産計画問題

生産計画問題をテスト勉強も兼ねてブログにまとめてみます。

問題

原料$\textrm{A}, \textrm{B}, \textrm{C}, \textrm{D}$を用いて、3種類の製品$\textrm{I, II, III}$を生産する時最大の利益をあげるにはどのようにすればよいか。

目的関数

製品$\textrm{I}$を$c_1$円、製品$\textrm{II}$を$c_2$円、製品$\textrm{III}$を$c_3$円とする。

ベクトルで表すと以下のようになる。

\begin{eqnarray} \textbf{c} &=& \left(\begin{array}{c} c_1\\c_2\\c_3 \end{array}\right) \end{eqnarray}

各製品を生産する個数を$\textbf{x}$とする。

\begin{eqnarray} \textbf{x} &=& \left(\begin{array}{c} x_1\\x_2\\x_3 \end{array}\right) \end{eqnarray}

利益は次のように計算される。

\begin{eqnarray} 利益 &=& \textbf{c}^{\mathrm{T}} \textbf{x} \end{eqnarray}

利益が最大になればいいので、

\begin{eqnarray} \textbf{c}^{\mathrm{T}} \textbf{x} \to 最大 \end{eqnarray}

これを目的関数という。

\begin{eqnarray} 目的関数: \textbf{c}^{\mathrm{T}} \textbf{x} \to 最大 \end{eqnarray}

制約条件

製品を作るために必要な原料を$a$とする。たとえば、製品$\textrm{I}$の必要な原料$A$ の個数が$n$であるとすると、$a_{\textrm{A}\textrm{I}} = n$とする。

これを行列で書くと、

\begin{eqnarray} A &=& \left(\begin{array}{ccc} a_{\textrm{A}\textrm{I}} && a_{\textrm{A}\textrm{II}} && a_{\textrm{A}\textrm{III}} \\ a_{\textrm{B}\textrm{I}} && a_{\textrm{B}\textrm{II}} && a_{\textrm{B}\textrm{III}} \\ a_{\textrm{C}\textrm{I}} && a_{\textrm{C}\textrm{II}} && a_{\textrm{C}\textrm{III}}\\ a_{\textrm{D}\textrm{I}} && a_{\textrm{D}\textrm{II}} && a_{\textrm{D}\textrm{III}} \end{array}\right) \end{eqnarray}

つぎに、原料の上限が次のようであった場合。(原料$X$の上限を$b_\textrm{X}$とするとき)

\begin{eqnarray} \textbf{b} &=& \left(\begin{array}{c} b_\textrm{A}\\b_\textrm{B}\\b_\textrm{C}\\b_\textrm{D} \end{array}\right) \end{eqnarray}

\begin{eqnarray} A\textbf{x} \leqq \textbf{b} \end{eqnarray}

が成り立つ。

そして、製品の数は0以上である(非負条件)から、

\begin{eqnarray} \textbf{x} \geqq \textbf{0} \end{eqnarray}

である。

この2つの条件を制約条件という。

\begin{eqnarray} 制約条件: A\textbf{x} \leqq \textbf{b}, \textbf{x} \geqq \textbf{0} \end{eqnarray}

まとめ

\begin{eqnarray} 目的関数:& \textbf{c}^{\mathrm{T}} \textbf{x} \to 最大\\ 制約条件:& A\textbf{x} \leqq \textbf{b}, \textbf{x} \geqq \textbf{0} \end{eqnarray}