板取り問題

OR事典

板取り問題

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

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

「OR事典」の他の用語

組合せ最適化：

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

ウィキペディア

板取り問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/11/05 09:53 UTC 版)

オペレーションズ・リサーチにおける板取り問題（いたどりもんだい、英: cutting stock problem）、またはカッティングストック問題とは、定形の母材（ストック（stock）とも。例えばロール紙や板金）から廃材の量が最小になるように特定の大きさの製品群を切り出す問題である。産業上の応用から生じた数学的な最適化問題の1つであり、また計算複雑性理論においてはナップサック問題に還元されるNP困難問題の1つである。整数計画問題として定式化することができる。