腸衣搭配問題之求解

童寧江

（臺州科技職業(yè)學(xué)院機電與模具工程學(xué)院，浙江 臺州318020）

0 問題重述

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

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

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

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

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

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

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

（5）為了食品保鮮,要求在30分鐘內(nèi)產(chǎn)生方案。

1 符號說明

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

2 解題思路

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

3 模型一的建立與求解

3.1 模型一的建立

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

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

約束：

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

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

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

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

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

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

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

下面是模型一的數(shù)學(xué)描述。

目標函數(shù)：max Σyi。

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

3.2 模型一的求解

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

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

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

4 模型二的建立與求解

4.1 模型二的建立

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

4.2 模型二的求解

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

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

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

5 結(jié)論

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

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

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