OR事典

板取り問題

読み方：いたどりもんだい
【英】：cutting-stock problem

長さが35, 60, 100, 150の板には, それぞれ500, 700, 450, 200枚以上の需要があり, これらを長さ1000の板から取り出したい. このとき, 使用する長さ1000の板の総枚数が最小になるように, どのような取り出しパターンで, 各何枚必要かを求めるような問題. 取り出す板の種類が増えると, 取り出しパターンも爆発的に増加するため, 数理計画法的定式化の陽な記述は難しいが, 改訂単体法の応用である列生成法を用いることによって, 効率よく解かれている.

「OR事典」の他の用語

組合せ最適化：

最短路問題  最適性の原理  木  板取り問題  混合整数計画  確率アルゴリズム  組合せ最適化問題