在實際生產中，有效管理庫存並減少浪費至關重要。切割庫存問題旨在將大型原料切割成滿足客戶需求的尺寸，同時最小化材料浪費。本文將探討兩種主要方法：精確解法和預分配切割模式法，並深入研究進階技術，如非凸目標函式的處理和變數選擇技巧。精確解法透過建立數學模型，以最小化卷材使用量為目標，並加入對稱破缺約束來簡化計算。預分配切割模式法則預先定義一組切割模式，然後最佳化這些模式的使用次數，並迭代地生成新的模式，以逐步逼近最佳解。兩種方法各有優劣，適用於不同規模和複雜度的問題。
切割庫存問題的最佳化技術
簡介
切割庫存問題是一個典型的最佳化問題，涉及如何在滿足客戶需求的同時，最小化材料的浪費。本章節將探討兩種不同的最佳化技術：精確解法和預分配切割模式法。
精確解法
精確解法旨在找到滿足客戶需求的最優切割方案，同時最小化所使用的卷材數量。該方法透過建立一個數學模型來實作這一目標。
數學模型
模型的目標函式是最小化所使用的卷材數量，同時確保滿足客戶對不同寬度材料的訂單需求。模型中的主要決策變數包括：
- $x_{ij}$：表示從第 $j$ 個卷材中切割出第 $i$ 種寬度的材料數量。
- $y_j$：表示第 $j$ 個卷材是否被使用。
約束條件
需求滿足約束：確保每種寬度的材料需求都被滿足。 $$\sum_{j} x_{ij} = D_i$$
卷材容量約束：確保從每個卷材中切割出的材料總寬度不超過卷材的寬度（100%）。 $$\sum_{i} x_{ij} \cdot w_i \leq 100$$
對稱破缺約束：透過強制規定卷材的使用順序，減少多個等效解帶來的計算複雜度。 $$y_j \geq y_{j+1}$$
程式碼實作
def cutting_stock_model(D):
# 初始化模型引數
n = len(D)
# ... 省略其他初始化程式碼
# 建立模型並新增約束條件
# ... 省略模型建立程式碼
# 新增對稱破缺約束
for j in range(K-1):
model.add_constraint(y[j] >= y[j+1])
# 求解模型
# ... 省略求解程式碼
return solution
內容解密：
cutting_stock_model(D)函式負責建立切割庫存問題的數學模型，其中D代表客戶對不同寬度材料的需求。- 初始化模型引數，包括需求種類別數量
n等。 - 對稱破缺約束的新增是為了減少因多個等效解而帶來的計算複雜度，透過強制規定後續卷材的使用依賴於前一個卷材的使用情況。
預分配切割模式法
預分配切割模式法是一種啟發式方法，透過預先定義一組切割模式，然後最佳化這些模式的使用數量，以滿足客戶需求。
數學模型
該方法的目標函式是最小化使用預分配切割模式的卷材數量。決策變數是每個切割模式的使用次數。
演算法步驟
- 初始化一組切割模式。
- 最佳化這些模式的使用數量，以滿足客戶需求。
- 根據最佳化結果，生成新的切割模式並新增到模型中，重複最佳化過程，直到無法找到更好的模式或達到時間限制。
程式碼實作
def pre_allocate_cutting_patterns(D):
# 初始化切割模式
patterns = initial_patterns(D)
while True:
# 最佳化切割模式的使用數量
y = optimize_pattern_usage(patterns, D)
# 生成新的切割模式
new_pattern = generate_new_pattern(D, y)
if new_pattern is None:
break
patterns.append(new_pattern)
return y
內容解密：
pre_allocate_cutting_patterns(D)函式實作了預分配切割模式法，其中D代表客戶需求。- 初始化一組初始切割模式
patterns。 - 在迴圈中，不斷最佳化當前切割模式的使用數量
y，並嘗試生成新的切割模式new_pattern以改善解的品質。 - 如果無法生成新的有效切割模式，則停止迭代，傳回最佳化的結果
y。
進階技術：切割庫存問題的最佳化
在生產製造過程中，庫存管理是一項重要的任務。其中，切割庫存問題是指如何將大型原料切割成所需的尺寸，以滿足客戶需求，同時最小化浪費和成本。本章將介紹如何使用進階技術來解決切割庫存問題。
切割庫存問題的數學模型
切割庫存問題可以建模為一個線性規劃問題。給定一組客戶需求，我們需要找到最優的切割方案，以滿足這些需求，同時最小化浪費和成本。
程式碼實作：切割庫存模型
def solve_large_model(D):
n, iter = len(D), 0
A = get_initial_patterns(D)
while iter < 20:
rc, y, l = solve_master(A, [D[i][0] for i in range(n)])
iter = iter + 1
a, v = get_new_pattern(l, [D[i][1] for i in range(n)])
for i in range(n):
A[i].append(a[i])
rc, y, l = solve_master(A, [D[i][0] for i in range(n)], True)
return rc, A, y, rolls_patterns(A, y, D)
內容解密：
solve_large_model函式是切割庫存問題的主要求解函式。- 它首先初始化一個模式矩陣
A，然後進入一個迴圈，最多迭代 20 次。 - 在每次迭代中，它呼叫
solve_master函式來求解主問題，得到最優解y和對偶變數l。 - 然後，它呼叫
get_new_pattern函式來生成新的切割模式，並將其新增到模式矩陣A中。 - 最後，它傳回求解結果，包括最優解
y和對應的切割模式。
主問題的求解
主問題是指給定一組切割模式，如何最小化浪費和成本。我們可以使用線性規劃來求解這個問題。
程式碼實作：主問題求解
def solve_master(C, b, integer=False):
t = 'Cutting stock master problem'
m, n, u = len(C), len(C[0]), []
s = newSolver(t, integer)
y = [s.IntVar(0, 1000, "") for j in range(n)]
Cost = sum(y[j] for j in range(n))
s.Minimize(Cost)
for i in range(m):
u.append(s.Add(sum(C[i][j]*y[j] for j in range(n)) >= b[i]))
rc = s.Solve()
y = [int(ceil(e.SolutionValue())) for e in y]
return rc, y, [0 if integer else u[i].DualValue() for i in range(m)]
內容解密：
solve_master函式是主問題的求解函式。- 它首先建立一個新的求解器
s，然後定義變數y和目標函式Cost。 - 它新增約束條件，確保滿足客戶需求。
- 然後，它呼叫求解器的
Solve方法來求解主問題。 - 最後，它傳回求解結果，包括最優解
y和對偶變數l。
生成新的切割模式
生成新的切割模式是指根據對偶變數，找到新的切割方案，以進一步最佳化目標函式。
程式碼實作：生成新的切割模式
def get_new_pattern(l, w):
s = newSolver('Cutting stock slave', True)
n = len(l)
a = [s.IntVar(0, 100, "") for i in range(n)]
Cost = sum(l[i]*a[i] for i in range(n))
s.Maximize(Cost)
s.Add(sum(w[i]*a[i] for i in range(n)) <= 100)
rc = s.Solve()
return SolVal(a), ObjVal(s)
內容解密：
get_new_pattern函式是生成新的切割模式的函式。- 它首先建立一個新的求解器
s，然後定義變數a和目標函式Cost。 - 它新增約束條件，確保新的切割模式滿足寬度限制。
- 然後，它呼叫求解器的
Solve方法來求解子問題。 - 最後，它傳回新的切割模式和對應的目標函式值。
結果分析
透過上述程式碼實作，我們可以得到切割庫存問題的最優解。結果表明，使用進階技術可以有效地解決切割庫存問題，同時最小化浪費和成本。
非凸目標函式的處理
當目標函式非凸時，我們需要使用特殊的技巧來處理。本章介紹瞭如何使用 piecewise 線性函式來近似非凸目標函式。
表格：規模經濟下的成本函式
| 數量 | 單價 |
|---|---|
| 1-10 | 10 |
| 11-20 | 9 |
| 21-30 | 8 |
本章介紹瞭如何使用進階技術來解決切割庫存問題，包括主問題的求解、生成新的切割模式和非凸目標函式的處理。透過這些技術，可以有效地最小化浪費和成本，提高生產效率。
進階技術：非凸目標函式的最佳化與變數選擇
在最佳化問題中，非凸目標函式的處理是一項挑戰。尤其是在處理分段函式時，傳統的最佳化方法可能會失效。本文將探討如何使用特殊的變數選擇技術來解決這類別問題。
非凸分段函式的最佳化問題
考慮一個簡單的分段函式： [ f(x) = \begin{cases} 18x & \text{if } 0 \leq x \leq 194 \ 16(x-194) + 3492 & \text{if } 194 < x \leq 376 \ \vdots & \vdots \ \end{cases} ]
如果我們嘗試最小化這個函式，條件是 $x \geq 250$，使用傳統的模式可能會得到錯誤的結果，如表 7-5 所示。
引入二元變數解決非凸問題
為瞭解決這個問題，我們引入了二元變數 $\delta_i$ 和 $\lambda_i$。其中，$\lambda_i$ 用於表示哪一段包含最佳點，而 $\delta_i$ 用於確保只有相鄰的 $\lambda_i$ 非零。這樣，我們可以正確地確定函式的哪一段被使用。
def k_out_of_n(solver, k, x, rel='=='):
n = len(x)
binary = sum(x[i].Lb()==0 for i in range(n)) == n and \
sum(x[i].Ub()==1 for i in range(n)) == n
if binary:
l = x
else:
l = [solver.IntVar(0,1,'') for i in range(n)]
for i in range(n):
if x[i].Ub() > 0:
solver.Add(x[i] <= x[i].Ub()*l[i])
else:
solver.Add(x[i] >= x[i].Lb()*l[i])
S = sum(l[i] for i in range(n))
if rel == '==' or rel == '=':
solver.Add(S == k)
elif rel == '>=':
solver.Add(S >= k)
else:
solver.Add(S <= k)
return l
內容解密：
k_out_of_n函式用於選擇 $k$ 個變數使其非零。binary變數檢查輸入變數是否為二元變數。如果是，則不需要額外的二元變數層。- 使用
solver.IntVar(0,1,'')建立二元變數 $\lambda_i$。 - 使用條件約束確保 $x_i$ 和 $\lambda_i$ 之間的關係：如果 $x_i$ 的上限大於 0，則 $x_i \leq x_i.Ub() * \lambda_i$；否則，$x_i \geq x_i.Lb() * \lambda_i$。
S = sum(l[i] for i in range(n))計算所有 $\lambda_i$ 的總和，並根據rel引數新增相應的約束。
選擇 $k$ 個相鄰變數
對於非凸目標函式，我們需要選擇 $k$ 個相鄰變數。這需要多層二元變數。我們將透過考慮一組變數 $x_i \in [0, u_i]$ 來說明這一點。
技術深度與差異化觀點
本文介紹了使用特殊的變數選擇技術來解決非凸目標函式的最佳化問題。這些技術包括引入二元變數和使用 SOS2（Special Ordered Set of type 2）變數。這些方法可以有效地處理非凸分段函式的最佳化問題，並且可以擴充套件到更一般的情況。
進階技術：選擇性限制與分段函式最佳化
在最佳化問題中，經常需要處理一些特殊的限制條件或目標函式，例如選擇某些變數或限制式使其滿足特定條件。本章節將介紹如何使用進階技術來實作這些功能，包括選擇 k 個相鄰變數、分段線性函式的最佳化以及選擇 k 個限制式等。
7.2.1 選擇 k 個相鄰變數
在某些問題中，我們需要選擇 k 個相鄰的變數使其非零。這可以透過引入二元變數並建立遞迴的限制式來實作。
實作方法
首先，我們定義一個函式 sosn，它接受求解器 solver、選擇的變數數量 k、變數列表 x 以及關係運算元 rel。該函式內部使用遞迴函式 sosnrecur 來建立多層二元變數，以實作選擇 k 個相鄰變數的功能。
def sosn(solver, k, x, rel='<='):
def sosnrecur(solver, k, l):
n = len(l)
d = [solver.IntVar(0, 1, "") for _ in range(n-1)]
for i in range(n):
solver.Add(l[i] <= sum(d[j] for j in range(max(0, i-1), min(n-2, i+1))))
solver.Add(k == sum(d[i] for i in range(n-1)))
return d if k <= 1 else [d, sosnrecur(solver, k-1, d)]
n = len(x)
if 0 < k < n:
l = k_out_of_n(solver, k, x, rel)
return l if k <= 1 else [l, sosnrecur(solver, k-1, l)]
程式碼解析
sosn函式：接受求解器、選擇數量、變數列表和關係運算元，內部呼叫sosnrecur進行遞迴處理。sosnrecur函式：建立二元變數d，並新增限制式確保l[i]小於等於其鄰近的d[j]之和。- 遞迴處理：對於
k > 1的情況，遞迴呼叫sosnrecur以建立多層二元變數。
內容解密：
d變數的作用：表示相鄰變數是否被選中。- 限制式的意義：確保選中的變數是相鄰的，並且數量符合
k的要求。
7.2.2 分段線性函式的最佳化
對於非凸的分段線性函式，我們需要正確地選擇相關的分段區間，以確保最佳化結果的正確性。
實作方法
我們定義一個函式 minimize_piecewise_linear，它接受點集 Points、下界 B 以及是否為凸函式的標誌 convex。該函式建立最佳化模型，並使用前面介紹的 sosn 函式來處理非凸情況下的相鄰變數選擇。
def minimize_piecewise_linear(Points, B, convex=True):
s, n = newSolver('Piecewise', True), len(Points)
x = s.NumVar(Points[0][0], Points[n-1][0], 'x')
l = [s.NumVar(0, 1, 'l[%i]' % (i,)) for i in range(n)]
s.Add(1 == sum(l[i] for i in range(n)))
d = sosn(s, 2, l)
s.Add(x == sum(l[i]*Points[i][0] for i in range(n)))
s.Add(x >= B)
Cost = s.Sum(l[i]*Points[i][1] for i in range(n))
s.Minimize(Cost)
rc = s.Solve()
return rc, SolVal(l), SolVal(d[1])
程式碼解析
- 定義變數：
x為決策變數，l為權重變數，用於插值計算。 - 新增限制式：確保
x的值由l和Points中的點決定，並且x >= B。 - 目標函式：最小化由
l和Points中的值計算出的成本。
內容解密：
l變數的作用：用於權重插值計算，以確定x和目標函式的值。d變數的作用：確保選擇的分段區間是相鄰的。
7.2.3 選擇 k 個限制式
在某些問題中，我們需要選擇 k 個限制式使其被滿足。這可以透過引入二元變數並將其與原限制式結合來實作。
理論基礎
對於限制式 $a_i x \leq b_i$，我們可以引入二元變數 $\delta$，並新增如下限制式： [a_i x \leq b_i + u_i (1 - \delta)] 當 $\delta = 1$ 時，限制式必須被滿足；當 $\delta = 0$ 時，限制式可被違反。
程式碼實作與解析
這部分的實作涉及將二元變數與連續變數結合，以控制限制式的滿足情況。
內容解密：
- 二元變數 $\delta$ 的作用：控制限制式是否被滿足。
- 限制式的轉換：透過引入 $u_i$，確保當 $\delta = 1$ 時，限制式有效；當 $\delta = 0$ 時，限制式無效。