基于0—1規劃的天然腸衣搭配模型設計

摘要：設計天然腸衣搭配方案，將提供的原料描述表按規格要求劃分為三類區間，由計算機在Excel表中生成模擬數據進行分析處理，建立了0-1規劃模型，將每種規格的各區間數據在Excel表中分配，建立分配控件，利用Excel的VBA編程按各規格的每個區間的根數進行分配，給出最終材料搭配方案，得到三種規格的較優搭配方案。

關鍵詞：0-1規劃 搭配方案 捆數 長度

1 概述

天然腸衣（以下簡稱腸衣）制作加工是我國的一個傳統產業，出口量占世界首位。腸衣經過清洗整理后被分割成長度不等的小段（原料），進入組裝工序。傳統的生產方式依靠人工，邊丈量原料長度邊心算，將原材料按指定根數和總長度組裝出成品（捆）。本文對于給定的一批原料，為提高原料使用率，最短長度最長的成品越多裝出的成品捆數越多越好，設計一個原料搭配方案，工人根據這個方案“照方抓藥”進行生產。

2 數據分析及處理

我們把天然腸衣幾種常見成品規格分為三種規格，見表1（長度單位為米）：

表1 成品規格表

■

根據成品規格要求將原料分檔劃分為三類區間進行取料組裝出成品（捆），規格1對應8個取料樣本區間；規格2對應14個取料樣本區間；規格3對應24個取料樣本區間，將某批次原料描述分類進行數據處理。先由計算機生成一批原料長度模擬數據，對這批數據進行分析處理，為了每次抽取樣本個數都為1或0，我們采取一種分配原則：

2.1 計算理論最大捆數

根據每種規格的根數總和可以求出理論最大捆數（我們不考慮長度總和是否合格）。

即Ki=INT■（i=1，2，3，m，n∈Z），取上限①。

規格1中K1=■=14.6捆，最多15捆；規格2中K2=■=44.2捆，最多45捆；規格3中K3=■=135.4捆，最多136捆，這批原料理論上最多可以組裝K=15+45+136=196捆。

2.2 將每種規格的各區間原料在Excel表中初次分配

將每個區間原料根數在滿足理論最大捆數的原則下盡可能全部分配，也就是說各規格中有K捆就在excel表中設定為K行，將各區間的根數盡可能的均分到K行L列，L列的生成原則是l=INT[■]，取上限；反之再確定mr 能確切分配多少行，h=INT[■]，取下限。例如規格1最多有15捆，那么就在excel表中設定為15行，在a1區間（3-3.4）中有43根原料，則l=INT[■]=INT[2.9]，取上限l為3列，反過來求行數h，h=INT[■]=INT[14.3]，取下限為14行，也就是將43根分配到14行3列中，以此原則類推，將計算機生成的模擬數據在Excel表中設置開始分配控件，用VB程序編寫源程序，按各規格的每個區間的原料根數進行第一次K行L列的分配。

2.3 計算每行原料的總長度和根數，及與標準規格的長度差，進行二次調配

在Excel表中進行計算，得到三種規格的數據，二次的搭配原則是定位標記初始調配行，就是說已分配的根數與標準根數之差越小且長度差小于0的那個行數首先開始進行調配，原則上從根數最多的行中挑選樣本，使長度在（88.5，89.5）之間，可以有±0.5米的誤差，利用計算機編程進行調配，得出各規格組裝后的捆數K■■，K■■，K■■，及各規格的剩余根數m■■，m■■，m■■。

2.4 如果某種規格對應原料出現剩余，可以降級使用繼續組裝捆綁

把規格3的剩余根數m■■降級到規格2搭配，還能組裝的捆數K■■=INT[■]且總長度在（88.5，89.5）之間，搭配剩余的規格2根數繼續降級按此原則組裝捆綁得到捆數K■■。最后得到成品最終捆數K=K■■+K■■+K■■+K■■+K■■及搭配方案。

3 算法步驟

對系統隨機生成的原料分配方案，要計算出每一組方案中最佳的原料組合。具體算法為：假設g為每次由0-1模型分配產生的根數總和，c為長度差， bi（i=1，2，3）為標準根數/捆。為提高原料使用率，在總長：89+0.5米的范圍內，即c∈（-0.5，0.5）；總根數允許比標準少一根，b或ibi-1都是有效捆法。

Step1：對第i捆數據，計|g-bi+1（i=1，2，3）為N，N為最多篩選數量，統計C■■中的滿足條件的篩選元素記錄集合，當c最小時，對應區間數據置0，被篩選出數據元素，按各自對應列空間存放。

Step2：當C■■中記錄數為0時，N=N+1，N為達到標

準捆數的差值，統計C■■中的滿足條件的篩選元素記錄集合，當c最小時，對應區間數據置0，被篩選出數據元素，按各自對應列空間存放。

Step3：如果c最小值相同，當C■■中記錄數為多個時，根據題目要求2的原則，篩選最短長度較短的腸衣記錄。

Step4：重復執行步驟1，2，直至所有數據均被處理完成。

Step5：根據材料降級處理原則，降級處理剩余材料，給出最終材料搭配方案。

4 建立0-1規劃模型計算出成品捆數最大值

設置0-1變量aij=1 第i行第j列取走樣本原料0 第i行第j列沒取樣本原料，設mr為第r個區間根數，建立目標函數min=mr-■■aij，（n=8，14，24）。

根據公司對搭配方案的要求，裝出的成品捆數越多越好，并且最短長度最長的成品越多越好，總長度允許有± 0.5米的誤差，總根數允許比標準少1根，故約束條件如下：s.t88.5≤■aijxij≤89.519≤■aij≤20

我們利用計算機模擬所描述的原料數據，按照建立的模型及算法運行程序數次，運行時間小于30分鐘，按要求能快速選出一個較優的搭配方案及捆數。

規格1搭配方案得出K■■=15捆，m■■=2根；規格2搭配方案得出K■■=36捆，剩余根數m■■=66根；規格3搭配方案得出K■■=120捆，剩余根數m■■=80根；規格3的剩余根數m■■降級到規格2搭配，K■■=INT（■）=18捆，剩余2根。

最后得出總捆數：

K=K■■+K■■+K■■+K■■+K■■

=15+36+120+18=189捆。

注釋：

①天然腸衣原料規格要求及數據來源于2011全國大學生數學建模D題.

參考文獻：

[1]楊啟帆，數學建模[M].北京：高等教育出版社，2005.

[2]姜啟源，數學建模[M].北京：高等教育出版社，2003.

[3]李秀珍，龐常詞.數學實驗[M].北京：機械工業出版社，2008.

[4]姜啟源，謝金星，葉俊.數學模型.第三版[M].北京：高等級教育出版社，2003.

[5]姜啟源等.大學數學實驗[M].北京：清華大學出版社，2005.