板取り問題
板取り問題を数学的に定式化するには(これが唯一の方法ではないが)、まず製品種類の数 m と、各製品が要求されている単位数 q j {\displaystyle q_{j}} ( j = 1 , ... , m {\displaystyle j=1,\ldots ,m} )の整理から始める。次に、母材1単位から製品を切り出す方法(これを「パターン」と呼ぶことが多い)を全て挙げてリストを構成する。パターンの総数を n {\displaystyle n} とする。各パターン i {\displaystyle i} に、それが何度用いられるかを表す変数 x i {\displaystyle x_{i}} (0含む自然数)を対応させる( i = 1 , ... , n {\displaystyle i=1,\ldots ,n} )。このとき線形計画問題は次のように定式化できる:
min ∑ i = 1 n c i x i {\displaystyle \min \sum _{i=1}^{n}c_{i}x_{i}}
s.t. ∑ i = 1 n a i j x i ≥ q j , ∀ j = 1 , ... , m {\displaystyle {\text{s.t.}}\sum _{i=1}^{n}a_{ij}x_{i}\geq q_{j},\quad \quad \forall j=1,\dots ,m}
x i ≥ 0 {\displaystyle x_{i}\geq 0} , 整数
ペーパーロール製造機が、幅5600mmのマスターロールを無限に生産できるとする。ここから下表に示したような13種類の製品ロールを切り出さなければならない。
重要なのは、同一のマスターロールから様々な方法で製品ロールを切り出せること(この切り出し方のそれぞれを「パターン」と呼ぶことにする)である。パターンの総数は一般に膨大な数に上り、列挙することは容易ではない。
この状況で、廃棄部分が最小限となるような製品ロールの最適な切り出し方を求めるのが板取り問題である。