靜態和動態規劃求解下料方法的比較研究

劉海金 賈春玉

（廣東培正學院管理學院，廣東 廣州 510830）

下料問題是木材、玻璃、紡織品、鋼材以及建筑業等眾多行業的常見問題。這類問題涉及生產下料、裝箱（即下料的反向問題）配送等。下料方式和方法對降低企業運營成本、高效并快速求得較少的下料方案和提高材料利用率至關重要。目前，已有的研究成果主要涵蓋啟發式算法、整數規劃法以及智能搜索法[1]等。然而，整數規劃法在求解規模較大的下料問題過程中經常受限制，耗時較長，甚至無法找出可行解。為應對這類挑戰，學界相繼提出了初始一大一小法[2]、平均數法和再平均法等改進后的一大一小法[3]。盡管這3 種方法在某種程度上解決了相關問題，但它們只考慮了初始原材料尺寸、各產品尺寸及產量要求，而沒有充分考慮已選定下料方案的影響。因此，這些方法仍有改進空間。該文提出了以動態規劃為基礎的求解方法，以改進現有解法并提高優化程度。該方法不僅停留在對原材料尺寸、產品尺寸和產量要求的考慮，還進一步考慮了已選定下料方案的影響，實現了下料問題的全面優化。期待這種新的求解方法能為實際生產帶來更高效的解決方案，進一步推動相關行業的發展。

1 有關符號、名詞和參數的界定

設原材料長度為H，生產產品品種數為n，產品尺寸為hj，下料方案種數為m，各種產品的產量為Qj，下料上限為UNj（不考慮產量大小時，一根原材料最多可下料第j種產品的個數），實際下料上限RNj（考慮產量大小時，一根原材料最多應該下料第j種產品的個數），需要個數（每種產品生產時所需原材料個數）為XNj，下料個數（在某個下料方案中各產品下料個數）Cij，代表第i個下料方案中第j個產品的下料個數。方案中，下料個數上限（為了選擇代表性良好的方案，在某個下料方案中對下料個數的限制）為CNj。其中i=1，2，…，m，j=1，2，…，n。

大比例和小比例方案的確定根據3 個參數進行，大比例參數KDj是確定某產品大比例方案的參數。為了滿足各種產品的產量要求，確保一個方案的某個產品下料個數大于等于該產品實際下料上限乘以大比例參數，使該產品下料個數足夠大。KDj取值范圍為0 ＜KDj≤1，通常取0.75左右。

小比例參數KXj是指為了保證各種產品的可下料總數與產量要求盡可能一致，便于優化組合并提高優化程度而設置的該產品下料上限的一定比例。KXj可保證在某個方案中該產品下料個數足夠小，并且下料個數小于等于該系數乘下料上限。KXj取值范圍通常為0.01 ＜KXj≤0.3，一般取0.1 左右。

下料個數上限比例參數為KSj。KSj是指為了便于優化組合，確保代表性良好，在小比例方案中盡可能出現較多產品而設置的各產品下料上限的一定比例。KSj可保證各產品下料個數大小適中，使下料個數小于等于該系數乘下料上限（注意這里取下料上限，而不是實際下料上限RNj，否則數據過小，影響優化程度）。KSj取值范圍一般為0.2＜KSj≤0.7，一般取0.5 左右。

綜上所述，可得如下文所示的重要計算公式。

下料上限UNj如公式（1）所示。

式中：符號“[]1”代表向下取整。

下文中（在大比例和小比例方案中）的符號“[]1”代表向上取整。

實際下料上限RNj如公式（2）所示。

需要個數XNj如公式（3）所示。

小比例方案中的下料個數上限CNj如公式（4）所示。

最優解下限LN如公式（5）所示。

式中：符號“[]1”代表向上取整。

優化程度Yp計算公式如（6）所示。

式中：Np為優化結果，原材料需要個數。

2 靜態和動態解法介紹

2.1 靜態解法介紹

靜態解法具體如下。

方法1，根據大比例參數KDj、小比例參數KXj和上限參數KSj統一設置，每種產品確保具有一個大比例方案。方案中下料個數Nj≥KDj·RNj，其余產品下料個數不限。每種產品確保具有一個小比例方案，方案中下料個數滿足1 ≤Nj≤KXj·RNj約束條件。其余產品下料個數滿足N≤KS·RN的約束條件。

方法2，可稱為平均數法，即根據各產品需要個數與該數的平均數進行比較，把產品分為2 種類型，一是各產品需要個數大于等于該數的平均數，界定為短缺。該類產品第一個參數不變，后2 個參數分別加k2和k3。其余產品為不短缺，將不短缺的產品的第一個參數減k1，其余2 個參數不變。其余與方法1 相同。

方法3，可稱為再平均數法，即在方法2 平均數基礎上再求平均數，根據各產品需要個數與再平均數進行比較，把產品分為2 種類型，一是各產品需要個數大于等于再平均數，界定為緊缺，其余為不緊缺。在平均法的基礎上，將緊缺的產品KDj調整為KDj+k2，不緊缺KDj調整為KXj，其余不變。KXj系數與方法2 參數相同。緊缺的產品KSj調整為KSj+k1，不緊缺產品KSj調整為KXj，其余不變。其余與方法2 相同。

2.2 動態解法介紹

該文提出了2 種動態解法，一是根據方法2 進行動態調整，選擇入選小比例方案，稱為方法4；二是根據方法3 進行動態調整，選擇入選小方案，稱為方法5。2 種動態解法方法如下。

方法4：在方法2 求解、確定各產品大比例方案后，計算各產品各方案累計下料個數及其平均數，將小于平均數為一類，稱為短缺，其余為不短缺。只進一步限制不短缺一類的取值上限，該文采用上限為1（也可用小比例上限代替1），其余與方法2 相同。

方法5：在方法3 求解、確定各產品大比例方案后，計算各產品各方案累計下料個數、累計下料個數平均數和再平均數，小于再平均數為一類，稱為緊缺，其余為不緊缺。進一步限制不緊缺一類的取值上限，該文采用上限為1。如果緊缺累計尺寸小于等于原材料尺寸，確保緊缺產品在小方案中出現，即下限為1，否則為0。避免都出現，否則會出現矛盾，其余與方法3 相同。

3 靜態和動態解法優勢與劣勢分析

3.1 靜態解法的優勢與劣勢分析

3.1.1 靜態解法的優勢

靜態解法沒有考慮求解過程中已入選下料方案的代表性、各產品數量和優化保證程度，即各產品在已有入選下料方案中的出現次數及累計數量。靜態解法優勢相對簡單，計算工作量相對較少，便于編寫求解程序，優化程度較高，便于掌握和運用。該方法只需要事先確定好相關比例和入選規則，進行規劃求解，確定入選方案。規劃求解如果優化程度不夠理想，可微調選相關比例參數，再求解2～3 組，通常可獲得滿意近似最優解。

3.1.2 靜態解法的劣勢

靜態解法沒有考慮求解過程中已入選下料方案、各產品數量和優化保證程度，有時會導致有些產品出現次數相對多或累計數量大，有些卻很少出現或累計數量不大，嚴重影響入選方案代表性程度，導致最終優化程度不夠理想。靜態解法的現有方法主要包括一大一小法、平均數法和再平均法等改進后的一大一小法。盡管這3 種方法在某種程度上解決了相關問題，但它們只考慮了初始原材料尺寸、各產品尺寸及產量要求，沒有充分考慮已選定下料方案的影響，因此有時代表性不夠理想。

3.2 動態解法的優勢與劣勢分析

3.2.1 動態解法的優勢

動態解法考慮求解過程中已入選的下料方案、各產品數量和優化保證程度，即各產品在已有入選下料方案中的產品出現次數及累計數量。根據已入選的下料方案，決定后續入選方案，在多數情況下可有效克服靜態解法劣勢，最大限度地避免有些產品出現次數相對多或累計數量大，有些卻很少出現或累計數量不大，進而影響入選方案代表性程度，導致最終優化程度可能不夠理想。

3.2.2 動態解法的劣勢

動態解法的劣勢主要是計算工作量相對多，方法比靜態略復雜，因組合方案多樣性和產品尺寸、數量以及原材料尺寸組合特殊性，有時動態解法優化程度比靜態提高幅度不大。

4 求解原理與步驟

求解步驟可分為2 個階段。第一階段，優化確定入選下料方案。第二階段，最終求解，即在入選優化組合方案中規劃求解出近似最優解。以方法1 為例，求解步驟如下。

第一階段，設計3 個參數數值，然后確定每種產品的2 種下料方案，一是根據大比例參數（KDj）規劃求解出一個大比例方案；二是根據小比例參數（KXj）和上限參數（KSj）規劃求解出一個小比例方案。設變量xij為第i個下料方案第j個產品的下料個數，則第一階段下料方案數學模型如下：1）第一階段第w（1 ≤w≤n）個產品第w個下料大比例方案數學模型為目標函數。其中，xiw≥RNw·KDj，xij為非負整數（i≠w，j≠w），RNw代表第w個產品實際下料上限。2）第一階段第y（y=w+n）個下料方案第w個產品小比例方案數學模型為目標函數。其中，，xiw≤RNw×KXj，xij≤CNj（j≠w），xiw≥1，xij為非負整數。

第二階段，最終求解。為了提高求解速度，在入選的若干個優化組合方案中判斷是否有相同的方案，如果有，就將對應下料個數賦值為0；否則保持原樣，剔出相同方案，在剩余最終入選的方案中規劃求解出近似最優解。該方法在多數情況下可獲得滿意近似最優解，但有時也會不理想。為了提高優化程度，獲得更理想的近似最優解，一方面可反復求解若干次（原因是有時有多個解），通常會提高優化程度。另一方面，可微調參數，再求解若干次，可獲得滿意的近似最優解。多數情況下只需求解一次就可獲得非常理想的近似最優解。設變量xi為第i個最終入選下料方案采用個數，則第二階段數學模型為目標函數，xi為非負整數。

5 求解實例

使用原材料200cm 棒料，生產產品（也可稱為毛坯，以下統稱為產品）長度分別為77cm、53cm、42cm、27cm和20cm，5 種產品產量分別為32、156、56、119 和80個，如果忽略切割寬度工藝損耗，求解最省原材料的下料方法，解法如下。

計算相關數據見表1。3 個參數（KDj、KXj、KSj）分別取0.95、0.07 和0.6，微調系數（k1、k2、k3）分別取0.08、0.03 和0.15，微調后的3 個參數見表2，采用方法4 進行求解。

表1 實例1 相關數據計算

表2 方法4 微調后的3 個參數（KDj、KXj、KSj）

第一步，確定第一個產品大比例方案。設5 種產品在第一個產品大比例方案中的下料個數分別為x1，1、x1，2、x1，3、x1，4和x1，5，因為要確保下料方案中第一個產品下料個數足夠大，因此應滿足x1，1≥[2×0.87]1=2，則可確定第一種產品大比例下料方案數學模型為目標函數maxZ=77x1，1+53x1，2+42x1，3+27x1，4+20x1，5，其中77x1，1+53x1，2+42x1，3+27x1，4+20x1，5≤200，x1，1≥2，變量為非負整數。

運用Excel 規劃求解軟件解得x1，1=2，x1，3=1，其余均為0。此時目標函數為maxZ=77×2+42×1=196cm。第一個方案為2、0、1、0、0。余下產品求解過程與第一個方案類似，其余4 個大比例方案分別如下：第二個方案為0、3、0、0、2；第三個方案為0、0、4、1、0；第四個方案為0、0、0、7、0；第五個方案為0、0、0、0、10。然后確定各產品小比例方案，根據表2 中的KXj、KSj數值確定約束條件。

第二步，確定第一個產品小比例方案。計算前5 個大方案各產品累計下料個數，各產品累計下料個數分貝為2、3、5、8 和12，平均數為6，其中第4 和第5 個產品累計下料個數分別是8 和12，大于平均數6，因此這2 個產品是不短缺產品，需要限制其出現個數，增加約束x1，4≤1 和x1，5≤1。設5 種產品在第一個產品小比例方案中的下料個數分別為x6，1、x6，2、x6，3、x6，4和x6，5。因為要確保下料方案中第一個產品所在比例足夠小且必須有，所以第一個產品在小比例方案中應滿足x6，1≥1，x6，1≤[2×0.07]1=1，其余產品下料個數分別滿足小于等于（CNj）3、3、5、6，則第一種產品小比例方案數學模型為目標函數maxZ=77x1，1+53x1，2+42x1，3+27x1，4+20x1，5。其中77x1，1+53x1，2+42x1，3+27x1，4+20x1，5≤200，x6，1≤1，x6，2≤3，x6，3≤3，x6，4≤5，x6，5≤6，x6，4≤1，x6，5 ≤1，x6，1≥1，變量為非負整數。解得x6，1=1，x6，2=1，x6，3=1，x6，4=1，x6，5=0，目標函數為maxZ=77×1+53×1+42×1+27×1=199cm。

第六個方案為1、1、1、1、0。余下產品求解過程與第六個方案類似，先計算上述各產品累計下料個數，再計算該數的平均數，其余4 個小比例方案分別如下：第七個方案為1、1、1、1、0；第八個方案為1、1、1、1、0；第九個方案為1、1、1、1、0；第十個方案為0、2、1、1、1。

第三步，規劃求解。經比較，第六～第九方案相同，去掉第七、第八和第九方案（即去掉方案對應下料個數分別賦值為0），再規劃求解。設實際7 個最終入選方案所采用的數量分別為x1、x2、x3、x4、x5、x6和x10，此時最終規劃求解數學模型為目標函數minNp=x1+x2+x3+x4+x5+x6+x10。其中2x1+x6≥32，3x2+x6+2x10≥156，x1+4x3+x6+x10≥56，x3+7x4+x6+x10≥119，2x2+10x5+x10≥80，xi為非負整數（i=1，2，...，10）。解得x1=0、x2=38、x3=5、x4=11、x5=0、x6=32、x10=5，目標函數Np=38+5+11+32+5=91 根。5 種產品可下料總數分別為32、156、57、119 和81 個，其中第3 個和第5 個產品比要求的產量各多1 個，其余與產量相等，能滿足各產品產量要求。因優化結果Np=91，最優解下限LN=[（77×32+53×156+42×56+27×119+20×80）/200]1=90，優化程度至少為[1-（91-90）/90]×100%≈98.9%。

5 種方法求解的Np分別為93、93、94、91 和94，優化程度至少分別為96.7%、96.7%、95.6%、98.9%和95.6%。因此該例題方法4 最好，比方法2 優化程度提高了3.3%。

6 試驗數據分析

該文隨機選取100 個樣本，其中需求個數差異大的（最大與最小相差5 倍及以上）和不大的樣本各50 個。產品種數為4～5 個，產品尺寸為12cm～187cm，產品產量為20～300個，原材料尺寸為200cm～600cm，大比例參數為0.65～0.95，小比例參數為0.01～0.3，上限參數為0.3～0.7。

在差異大的樣本中，5 種方法優化程度相對最好的出現次數分別為15、18、26、33 和24 次，分別占30%、36%、52%、66%和48%，平均優化程度至少分別為91.2%、91.8%、95.92%、95.99%和96%。方法4 單獨出現最好次數為10 次，占比20%，其余均為0 次。5 種方法差異較明顯，方法1 最差，方法4 最好。動態規劃解法方法4 比靜態解法方法2 的優化程度平均提高4.1%，動態解法6 與靜態解法方法3 幾乎無差異。

在差異不大的樣本中，5 種方法優化程度相對最好出現次數分別為39、39、32、39 和39 次，分別占78%、78%、64%、78%和78%。平均優化程度至少分別為98.32%、98.28%、97.65%、98.1%，97.39%和98.2%，方法2 和方法5 單獨出現最好次數分別為2 和4，占比4%和8%，只有方法3 略差，其余均相等。動態與靜態解法幾乎無差異，5 種方法也無明顯差異，5 種方法都應采用，取最好的方案作為最終優化方案。

在100 個樣本中，5 種方法優化程度相對最好出現次數分別為54、57、58、72 和63 次，分別占54%、57%、58%、72%和63%。5 種方法平均優化程度只少分別為94.76%、95.03%、96.78%、97.04%和97.03%，具有一定差異，優化程度級差為2.3%。方法2 的單獨最好出現次數為2 次，方法4 為10 次，方法5 為4 次，占比分別為2%、4%和10%。說明這3 種方法不能被替代，最好結合使用，并擇優作為最終優化結果。動態解法4 比靜態解法2 的優化程度平均提高了2%。動態解法6 與靜態解法3 相比幾乎無差異，優化程度平均提高了0.23%。

7 結論

雖然靜態規劃求解方法在多數情況下能得到可接受的近似最優解，但其僅考慮初始狀態，并未充分考慮已選取方案對后續方案選擇的影響，因此其優化能力仍有提升空間。特別是在產品需求差異顯著的情況下（例如最大需求與最小需求相差5 倍以上），這種局限性更突出。動態規劃解法在平均數法中的優化程度可比靜態解法平均提高4.1%，但在再平均法中，兩者的差異幾乎可以忽略不計。因此，該文建議將上述策略并行使用，并根據實際結果進行優選，以獲得最終的優化結果。然而，動態解法由于僅考慮絕對入選方案累計下料個數，而忽視了相對數，因此仍有改進余地。

綜上所述，該文提供的下料優化策略為解決實際生產中的問題提供了可行的解決方案，但仍有改進空間。未來的研究將針對該問題進行深入探索，以使生產更高效。