天然腸衣搭配問題的通用優化模型

【摘要】對于天然腸衣搭配問題，通過建立最大捆數和搭配方案的兩個通用模型，得出了三種規格的原料的最大捆數，以及在保證捆數最多的情況下的原料搭配的最優方案，根據這個方案可以“照方抓藥”進行生產，提高了勞動效率和原料的使用率.

【關鍵詞】天然腸衣；搭配方案；捆數；模型

2011年高教社杯全國大學生數學建模競賽D題：天然腸衣搭配問題.要求解決的問題是根據題目提供的成品規格表和原料描述表，設計一個原料搭配方案，工人根據這個方案“照方抓藥”進行生產.公司對搭配方案有以下具體要求：

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

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

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

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

(5)為了食品保鮮，要求在30分鐘內產生方案.

請建立上述問題的數學模型，給出求解方法，并對成品規格表、原料描述表給出的實際數據進行求解，給出搭配方案.

一、問題分析

假設某種規格對應原料如果出現剩余，可以平移降級使用.如長度為7米、7.5米、8米的原料出現剩余，可以向下一級平移降級為5.5米、6米、6.5米使用.

因為原料若有剩余可以降級使用，所以按照從長到短的順序進行，對三種規格的原料來說：

1.每一捆的根數=該規格使用的總根數/該規格的總捆數.

2.每一捆的長度=該規格使用根數的總長度/該規格的總捆數.

以每一規格的最大捆數為目標，每一捆的根數和長度進行約束，首先建立最大捆數的通用模型，分別就三種規格的具體數據，利用LINGO軟件編程，求出最大捆數和每一規格在最大捆數下使用的具體根數（若有剩余考慮降級）.

在最大捆數使用的具體根數確定的情況下，就每一捆的具體搭配建立通用的搭配模型，分別就三種規格的具體數據，利用LINGO軟件編程，求出三種規格成品的搭配方案.

二、模型建立與求解

1最大捆數的優化模型

用i=1，2，3表示規格數，j=1，2，…，ni表示三種規格原料的分段個數（ni=8，14，24）.

設ki表示第i規格成品的最大捆數，pi表示第i規格成品的標準根數，xijaij，bij分別表示第i規格第j段原料使用的根數、原料的長度、原料提供的根數.

目標函數為：maxki(i=1，2，3)

約束條件為：

s.t.pi-1≤∑nij=1xijki≤pi，對每捆根數的約束，

885≤∑nj=1aijxijki≤895，對每捆長度的約束，

xij≤bij，使用的根數不超過提供的原料根數，

ki，xij均為整數（i=1，2，3；j=1，2，…，ni).(Ⅰ)

利用模型(Ⅰ)編制LINGO程序一，從第三規格開始，分別對三種規格求解.

（1）在第三規格中，a3j=14，145，15，…，25，255；b3j=35，29，30，…，0，1，取n3=24，p3=5；利用程序一解得：第三規格最大捆數k3=137，使用根數x3j=b3j；第三規格原料全部用完無剩余.

（2）將程序中的數據改為第二規格的數據，利用程序一解得：第二規格最大捆數k2=37，使用根數為：x2j=0，0，10，25，21，23，21，18，31，23，22，59，18，25；第二規格原料剩余數為：b2j-x2j=24，24，10，0，0，…，0；剩余總數58根，根據假設可平移降級使用.

（3）同理，利用程序一解得：第一規格最大捆數k1=18，使用根數為：x1j=43，59，39，41，26，52，54，30；第一規格原料剩余數為：b1j-x1j=0，0，0，0，1，0，4，1；剩余總數6根.

2搭配方案的優化模型

設wsj表示第s捆成品中使用的第j段原料的根數（s=1，2，…，ki；j=1，2，…，ni）.將上述模型中求出的三種規格成品使用的根數xij進行搭配扎捆（i=1，2，3）.建立通用模型：

∑kis=1wsj=xij，扎捆中第j段總根數等于選定的根數(i=1，2，3)，

pi-1≤∑nij=1wsj≤pi，對每捆根數的約束，

885≤∑nij=1aijwsj≤895，對每捆長度的約束(i=1，2，3)，

wsj均為整數，（s=1，2，…，ki；j=1，2，…，ni）.（Ⅱ）

利用模型（Ⅱ）編制LINGO程序二，分別對三種規格求解.

（1）在第一規格中，取k1=18，n1=8，p1=20，a1j=3，35，4，…，6，65，x1j=43，59，39，41，26，52，54，30；利用程序二解出第一規格成品的搭配扎捆方案（略），由方案可以看出，18捆成品全是19根的.

（2）將程序中的數據改為第二規格的數據，利用程序二解得：第二規格成品的搭配扎捆方案（略），由方案可以看出，37捆成品全是8根的.

（3）同理，利用LINGO程序解出第三規格成品的搭配扎捆方案（略），由方案可以看出，137捆成品中129捆是5根的，8捆是4根的.

三、結束語

兩個通用模型簡單方便，根據不同情況，只要將數據改變代入兩個模型中，運用LINGO程序即可求出多種結果.篩選出最短長度最長的搭配方案，工人根據這個方案“照方抓藥”進行生產，提高了工作效率.將剩余原料平移降級使用，可以減少原料的剩余，最后僅剩余6根，大大提高了原料的使用率.該模型可推廣到不同材料的切割模式搭配、材料下料等問題中.

【參考文獻】

［1］姜啟源，謝金星，葉俊.數學模型（第三版）.北京：高等教育出版社，2003.

［2］肖華勇.實用數學建模大賽與軟件應用.西北工業大學出版社，2008.