業界別最適化Example集: カッティングストック問題 (製材業)
nAG数値計算ライブラリ > 業界別最適化Example集 > カッティングストック問題 (製材業)

Keyword: 製材業, 最適化, 資源管理, 切断問題, カッティングストック問題, MILP

製材業分野の最適化問題:カッティングストック問題

木材

問題の概要

製材業においては、長い木材から必要なサイズの製品を切り出す際に材料の無駄をできるだけ減らすことが求められます。このような状況で取り組まれるのがカッティングストック問題です。この問題では、いかにして材料を効率的に切断し、製品の必要量を満たしつつ材料のロスを最小限に抑えるかを計算することが目的です。問題を解くためには、各製品が必要とする数を確実に切り出せるように計画を立て、その上で使用する材料の長さが最小限になるように切断方法を選びます。

木材のカッティングストック問題(具体例)

例として、製材会社が6メートルの木材から、異なる長さと数量で製品を作るケースを考えます。製品ごとの必要な長さと本数が指定され、いくつかの切断パターンが提案されています。例えば、「製品1を5本切り出す」というパターンや、「製品2を4本、製品1を2本切り出す」といった複合的なパターンも含まれます。これらのパターンを組み合わせて、全製品の需要を満たし、かつ使用する木材の本数を最小にする最適な切断計画を立てることが課題です。

製品 長さ(メートル) 本数
1 1.2 80
2 1.5 60
3 2.0 50
4 2.5 40
5 3.0 30
  1. パターン1: 製品1を5本
  2. パターン2: 製品2を4本
  3. パターン3: 製品3を3本
  4. パターン4: 製品4を2本
  5. パターン5: 製品5を2本
  6. パターン6: 製品1を2本、製品2を1本
  7. パターン7: 製品1を1本、製品3を1本
  8. パターン8: 製品2を1本、製品4を1本
  9. パターン9: 製品3を1本、製品5を1本
  10. パターン10: 製品1を1本、製品2を1本、製品3を1本

問題の定式化

パラメータ

パラメータ 説明
m 製品の種類数 5
n 考えられる切断パターンの数 10
L 原材料の長さ(メートル) 6.0
li 製品 i の長さ(メートル) 表参照
di 製品 i の需要量(本) 表参照
aij パターン j での製品 i の本数 表参照

決定変数

変数 説明 範囲
xj 切断パターン j の使用回数 非負整数

目的関数

目的
最小化 j=1nxj

目的関数は、使用する切断パターンの合計回数を最小化することです。これにより、原材料の無駄を最小限に抑えることができます。

制約条件

制約 説明
需要満足制約 j=1naijxjdi,i 各製品の需要量を満たすこと
材料利用制約 i=1maijliL,j 切断パターンで切り出される製品の合計長さが原材料の長さを超えないこと
非負整数制約 xj0,xjZ,j 切断パターンの使用回数は非負の整数であること

需要満足制約は、各製品の需要量を満たすために必要な本数が切り出されることを保証します。材料利用制約は、各切断パターンで切り出される製品の合計長さが原材料の長さを超えないようにします。非負整数制約は、切断パターンの使用回数が現実的な値となるようにします。

コード例

以下に、この混合整数計画問題を nAG Library for Python の 混合整数線形計画ソルバー関数 mip.handle_solve_milp を用いて解くコード例を示します。

今回の問題は、決定変数が整数条件を持つ問題であるため、汎用的な混合整数線形計画ソルバーである mip.handle_solve_milp を選択しました。

from naginterfaces.library import opt, mip

# 問題のサイズ
m = 5  # 製品の種類数
n = 10  # 考えられる切断パターンの数

# 原材料の長さ
L = 6.0

# 製品の長さ
l = [1.2, 1.5, 2.0, 2.5, 3.0]

# 製品の需要量
d = [80, 60, 50, 40, 30]

# 切断パターンごとの製品の切り出し本数
a = [
    [5, 0, 0, 0, 0],  # パターン1: 製品1を5本
    [0, 4, 0, 0, 0],  # パターン2: 製品2を4本
    [0, 0, 3, 0, 0],  # パターン3: 製品3を3本
    [0, 0, 0, 2, 0],  # パターン4: 製品4を2本
    [0, 0, 0, 0, 2],  # パターン5: 製品5を2本
    [2, 1, 0, 0, 0],  # パターン6: 製品1を2本、製品2を1本
    [1, 0, 1, 0, 0],  # パターン7: 製品1を1本、製品3を1本
    [0, 1, 0, 1, 0],  # パターン8: 製品2を1本、製品4を1本
    [0, 0, 1, 0, 1],  # パターン9: 製品3を1本、製品5を1本
    [1, 1, 1, 0, 0]   # パターン10: 製品1を1本、製品2を1本、製品3を1本
]

# 問題を定義するためのハンドルを作成
handle = opt.handle_init(nvar=n)

# 目的関数の設定
c = [1] * n  # 全ての切断パターンの係数を1に設定
opt.handle_set_linobj(handle, c)

# 需要満足制約の設定
for i in range(m):
    bl = [d[i]]  # 下限は需要量
    bu = [float('inf')]  # 上限は無限大
    irowb = [1] * n
    icolb = list(range(1, n+1))
    b = [a[j][i] for j in range(n)]  # 切断パターンごとの製品の切り出し本数
    opt.handle_set_linconstr(handle, bl=bl, bu=bu, irowb=irowb, icolb=icolb, b=b)

# 材料利用制約の設定
for j in range(n):
    bl = [-float('inf')]  # 下限は負の無限大
    bu = [L]  # 上限は原材料の長さ
    irowb = [1] * m
    icolb = list(range(1, m+1))
    b = [a[j][i] * l[i] for i in range(m)]  # 切断パターンで切り出される製品の合計長さ
    opt.handle_set_linconstr(handle, bl=bl, bu=bu, irowb=irowb, icolb=icolb, b=b)

# 変数の整数性の設定
lb = [0] * n  # 全ての変数の下限を0に設定
ub = [float('inf')] * n  # 全ての変数の上限を無限大に設定
opt.handle_set_simplebounds(handle, bl=lb, bu=ub)

# 整数制約の設定
for j in range(n):
    opt.handle_set_property(handle, 'INTEGER', idx=[j+1])  
    
# ソルバーのオプションを設定
opt.handle_opt_set(handle, 'Print Level = 0')

# 問題を解く
x = mip.handle_solve_milp(handle)[0]

# 結果を表示
print(f"最適な切断パターンの使用回数: {x}")
print(f"必要な木材の本数: {sum(x)}")

# 需要満足制約の検証
for i in range(m):
    demand = sum(a[j][i] * x[j] for j in range(n))
    print(f"製品{i+1}の需要量: {d[i]}, 実際の生産量: {demand}")

# ハンドルを解放
opt.handle_free(handle)

結果例

上記のコードを実行すると、以下のような結果が得られます。

最適な切断パターンの使用回数: [1. 0. 1. 1. 1. 28. 19. 38. 28. 0.]
必要な木材の本数: 117.0
製品1の需要量: 80, 実際の生産量: 80.0
製品2の需要量: 60, 実際の生産量: 66.0
製品3の需要量: 50, 実際の生産量: 50.0
製品4の需要量: 40, 実際の生産量: 40.0
製品5の需要量: 30, 実際の生産量: 30.0

この結果から、必要な木材の本数を最小化する最適な切断パターンが求められています。具体的には、パターン1を1回、パターン3を1回、パターン4を1回、パターン5を1回、パターン6を28回、パターン7を19回、パターン8を38回、パターン9を28回使用することで、全ての製品の需要量を満たしつつ、必要な木材の本数を117本に抑えることができます。

また、需要満足制約の検証結果から、全ての製品の需要量が満たされていることが確認できます。製品2については、必要な本数より多く生産されていますが、これは問題の制約条件を満たしているため許容されます。

まとめ

ここでは、カッティングストック問題を混合整数計画法により定式化し、最適な切断パターンを求めることで、原材料の無駄を最小限に抑える方法を示しました。 材料の品質や強度に関する制約を加えて製品の品質を考慮したり、原材料の調達コストを目的関数に含めて材料の選択を考慮したり、より現実的な応用も可能です。

またこの問題解決アプローチは、木材以外の材料を扱う鉄鋼業、ガラス産業、プラスチック製造業など他の産業にも幅広く適用可能です。


関連情報
© 日本ニューメリカルアルゴリズムズグループ株式会社 2024
Privacy Policy  /  Trademarks