腸衣搭配問(wèn)題之求解

童寧江

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

0 問(wèn)題重述

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

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

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

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

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

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

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

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

1 符號(hào)說(shuō)明

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

2 解題思路

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

3 模型一的建立與求解

3.1 模型一的建立

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

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

約束：

（1）對(duì)于每種組合，長(zhǎng)度下界≤該組合的各檔原料長(zhǎng)度之和；

（2）對(duì)于每種組合，該組合的各檔原料長(zhǎng)度之和≤長(zhǎng)度上界；

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

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

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

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

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

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

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

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

3.2 模型一的求解

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

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

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

4 模型二的建立與求解

4.1 模型二的建立

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

4.2 模型二的求解

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

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

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

5 結(jié)論

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

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

［2］LINGO 12.0 用戶(hù)手冊(cè)[Z].