トップ > 数理計画用語集 > カッティングストック問題

数理計画用語集

カッティングストック問題

読み:かってぃんぐすとっくもんだい
英名:Cutting Stock Problem

長さequationの木材をそれぞれequation本用意する必要があるとする.しかし用意できる木材は長さがequationのものだけである.(equationとする.)そこで長さがequationの木材から長さequationを切り出して用意することを考える.このとき長さequationの木材を最低何本用意すれば,それぞれequation本用意することができるか,というのがカッティングストック問題である.

古典的解法としてまず一本の長さequationの木材から長さequationの木材をそれぞれ何本ずつ切りだせるかのパターンをすべて列挙する.そのあとにすべての切り出しパターンのデータを使って線形計画問題を解くことに問題を帰着させる,という方法がある.しかし大規模になると,この「すべての切り出しパターンを列挙する」というところで途方もなく計算時間を使ってしまう.そのため現在では解決手法としてパターンを一つとりだしては線形計画問題を解いていくという「列生成法」が考えられている.また現在では現実的な視点として切り出しのパターンをできるだけ少なくするという目的を考慮した問題の定式化がおこなわれている[1].

資材切り出しソリューションについてはこちら

[参考]
[1] 梅谷俊治,今堀慎治,切り出し・詰め込み問題とその応用オペレーションズ・リサーチ : 経営の科学 Operations research as a management science research Vol.50, No.4(20050401) pp. 270-276