腸衣搭配問題之求解

童寧江

（臺州科技職業學院機電與模具工程學院，浙江 臺州318020）

0 問題重述

天然腸衣（以下簡稱腸衣）制作加工是我國的一個傳統產業，出口量占世界首位。腸衣經過清洗整理后被分割成長度不等的小段 （原料），進入組裝工序。傳統的生產方式依靠人工，邊丈量原料長度邊心算，將原材料按指定根數和總長度組裝出成品（捆）。

原料按長度分檔，通常以0.5米為一檔，如：3-3.4米按3米計算，3.5米-3.9米按3.5米計算，其余的依此類推。為了提高生產效率，公司計劃改變組裝工藝，先丈量所有原料，建立一個原料描述。根據成品規格和原料描述，現需要我們通過數學模型方法為公司設計一個原料搭配方案，工人根據這個方案“照方抓藥”進行生產。

公司對搭配方案有以下具體要求[1]：

（1）對于給定的一批原料，裝出的成品捆數越多越好；

（2）對于成品捆數相同的方案，最短長度最長的成品越多，方案越好；

（3）為提高原料使用率，總長度允許有±0.5米的誤差，總根數允許比標準少1根；

（4）某種規格對應原料如果出現剩余，可以降級使用。如長度為14米的原料可以和長度介于7-13.5米的進行捆扎，成品屬于7-13.5米的規格；

（5）為了食品保鮮,要求在30分鐘內產生方案。

1 符號說明

原料描述為長度檔位mj米有nj根。最大根數是G。第i類組合的次數是yi。第i類組合的第j長度檔位根數是aij。

2 解題思路

本問題的解題思路為：先求第一種規格的成品方案、第二種規格的成品方案、第三種規格的成品方案，再求這三種方案剩余腸衣的成品方案。

3 模型一的建立與求解

3.1 模型一的建立

模型一是單目標非線性規劃模型，用于優化原料搭配組合（及組合次數）。對于每種規格，模型一不僅可以求得最大成品捆數，而且可以求得原料搭配組合及其次數。

目標：求各種原料搭配組合次數之和的最大值。

約束：

（1）對于每種組合，長度下界≤該組合的各檔原料長度之和；

（2）對于每種組合，該組合的各檔原料長度之和≤長度上界；

（3）對于每種組合，根數下界≤該組合的各檔原料根數之和；

（4）對于每種組合，該組合的各檔原料根數之和≤根數上界；

（5）對于每檔原料，各種組合的該原料根數之和≤可用根數；

（6）對于每種組合每檔原料，使用根數是自然數；

（7）對于每種組合，組合次數是正整數。

下面是模型一的數學描述。

目標函數：max Σyi。

約束條件：每個 i有 88.5≤Σ(mj×aij)≤89.5,G-1≤Σaij≤G+1;每個j有 Σ(aij×yi)≤nj;aij是自然數,yi是正整數。

3.2 模型一的求解

實踐表明，在軟件LINGO[2]上，模型一的求解時間主要決定于原料檔位數。原料檔位數越大，求解時間也越長。當原料檔位不多時，在普通電腦上1個小時內產生方案是非常輕松。當原料檔位很多時，在普通電腦上1個小時內產生方案是有些勉強。

當原料檔位很多時，為了在普通電腦上1個小時內產生方案，比較有效的解決辦法是減少組合數和采用中斷技術。因為，減少組合數可以讓軟件LINGO縮短求解時間，采用中斷技術可以讓軟件LINGO立即返回局部最優解。特別，為了減少組合數，可以限制組合的使用原料檔位個數。

現在，利用模型一，通過軟件Lingo求得：第一種、第二種規格和第三種規格的最大成品捆數為分別為14、35和120。

4 模型二的建立與求解

4.1 模型二的建立

為了解決剩余問題，提出了模型二：先第三種規格的剩余合并到第二種規格的剩余，在第二種規格的剩余中求解成品的搭配與捆數；再第二種規格的剩余合并到第一種規格的剩余，在第一種規格的剩余中求解成品的搭配與捆數。

4.2 模型二的求解

首先，第三種的剩余合并到第二種的剩余，建立新的原料描述。利用模型一，通過軟件Lingo求得最大成品捆數為19。

然后，第二種的剩余合并到第一種的剩余，建立新的原料描述。利用模型一，通過軟件Lingo求得最大成品捆數為0。

綜上所述，剩余的原料最多可以搭配為成品19捆。

5 結論

通過模型一和模型二的求解，得出總捆數為188。

［1］2011高教社杯全國大學生數學建模競賽D題[Z].

［2］LINGO 12.0 用戶手冊[Z].