整数計画法

第１章では,線形計画法の説明で典型的な問題として以下のような問題を例示しました。制約条件

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

$$10x+5y\leq 600$$ (13)

$$300x+20y\leq 1300$$ (14)

$$0\leq x$$ (15)

$$0\leq y$$ (16)

のもとで,関数

$$f(x,y)=100x+10y$$

を最大化する問題でした。 ここで,特に変数$x,y$が整数値しか取り得ないという条件を付加します。

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

$$10x+5y\leq 600$$ (18)

$$300x+20y\leq 1300$$ (19)

$$0\leq x$$ (20)

$$0\leq y$$ (21)

$$x,y は整数$$ (22)

のもとで,関数

$$f(x,y)=100x+10y$$

を最大化する。このような問題を整数計画問題と言います。
一見すると, $(\ref{seisu1}) \sim (\ref{seisu3})$の問題を解き、解の$x,y$の値を四捨五入などすれば $(\ref{seisu4}) \sim (\ref{seisu6})$の解が得られるように思われるかもしれませんが,そう簡単にはいきません。
変数が整数という制約が加わると,難しくなります。 実際,整数値という制約のない問題 $(\ref{seisu1}) \sim (\ref{seisu3})$の解は, $x=1.79,y=38.21,f(x,y)=560.71$ ですが,問題 $(\ref{seisu4}) \sim (\ref{seisu6})$ では, $x=2,y=35,f(x,y)=550$です。

それぞれ重さが, $g_1,g_2,\cdots,g_m$で,値段が $p_1,p_2,\cdots,p_m$の$m$個の品物があり,それを,最大$G$まで入れることが出きる容器に詰めるとして,売上が最大になる ような詰め方は？　という問題を定式化すると

$$\begin{eqnarray*} && g_1 x_1 + g_2 x_2 + \cdots +g_m x_m \le G \\ && x_k \in \{0,1 \} ,k=1,2,\cdots,m \\ \end{eqnarray*}$$

のもとで,

$$p_1 x_1 + p_2 x_2 + \cdots +p_m x_m$$

を最大にする。
ただし,変数 $x_k \in \{0,1 \} ,k=1,2,\cdots,m$

$$x_k = \left \{ \begin{array}{l} 1~~(k番目の品物を詰める)\\ 0~~(k番目の品物を詰めない)\\ \end{array}\right.$$

を表す。という問題になります。これはナップサック問題と呼ばれています。