基于0―1規(guī)劃的天然腸衣搭配模型設(shè)計

1、<p>　　基于0―1規(guī)劃的天然腸衣搭配模型設(shè)計</p><p>　　摘要：設(shè)計天然腸衣搭配方案，將提供的原料描述表按規(guī)格要求劃分為三類區(qū)間，由計算機在Excel表中生成模擬數(shù)據(jù)進(jìn)行分析處理，建立了0-1規(guī)劃模型，將每種規(guī)格的各區(qū)間數(shù)據(jù)在Excel表中分配，建立分配控件，利用Excel的VBA編程按各規(guī)格的每個區(qū)間的根數(shù)進(jìn)行分配，給出最終材料搭配方案，得到三種規(guī)格的較優(yōu)搭配方案。 </p>

2、<p>　　關(guān)鍵詞：0-1規(guī)劃 搭配方案 捆數(shù) 長度 </p><p><b>　　1 概述 </b></p><p>　　天然腸衣（以下簡稱腸衣）制作加工是我國的一個傳統(tǒng)產(chǎn)業(yè)，出口量占世界首位。腸衣經(jīng)過清洗整理后被分割成長度不等的小段（原料），進(jìn)入組裝工序。傳統(tǒng)的生產(chǎn)方式依靠人工，邊丈量原料長度邊心算，將原材料按指定根數(shù)和總長度組裝出成品（捆）。本文對于

3、給定的一批原料，為提高原料使用率，最短長度最長的成品越多裝出的成品捆數(shù)越多越好，設(shè)計一個原料搭配方案，工人根據(jù)這個方案“照方抓藥”進(jìn)行生產(chǎn)。 </p><p>　　2 數(shù)據(jù)分析及處理 </p><p>　　我們把天然腸衣幾種常見成品規(guī)格分為三種規(guī)格，見表1（長度單位為米）： </p><p><b>　　表1 成品規(guī)格表 </b></p&

4、gt;<p><b>　　■ </b></p><p>　　根據(jù)成品規(guī)格要求將原料分檔劃分為三類區(qū)間進(jìn)行取料組裝出成品（捆），規(guī)格1對應(yīng)8個取料樣本區(qū)間；規(guī)格2對應(yīng)14個取料樣本區(qū)間；規(guī)格3對應(yīng)24個取料樣本區(qū)間，將某批次原料描述分類進(jìn)行數(shù)據(jù)處理。先由計算機生成一批原料長度模擬數(shù)據(jù)，對這批數(shù)據(jù)進(jìn)行分析處理，為了每次抽取樣本個數(shù)都為1或0，我們采取一種分配原則： </p&g

5、t;<p>　　2.1 計算理論最大捆數(shù) </p><p>　　根據(jù)每種規(guī)格的根數(shù)總和可以求出理論最大捆數(shù)（我們不考慮長度總和是否合格）。 </p><p>　　即Ki=INT■（i=1，2，3，m，n∈Z），取上限①。 </p><p>　　規(guī)格1中K1=■=14.6捆，最多15捆；規(guī)格2中K2=■=44.2捆，最多45捆；規(guī)格3中K3=■=135.

6、4捆，最多136捆，這批原料理論上最多可以組裝K=15+45+136=196捆。 </p><p>　　2.2 將每種規(guī)格的各區(qū)間原料在Excel表中初次分配 </p><p>　　將每個區(qū)間原料根數(shù)在滿足理論最大捆數(shù)的原則下盡可能全部分配，也就是說各規(guī)格中有K捆就在excel表中設(shè)定為K行，將各區(qū)間的根數(shù)盡可能的均分到K行L列，L列的生成原則是l=INT[■]，取上限；反之再確定mr 能

7、確切分配多少行，h=INT[■]，取下限。例如規(guī)格1最多有15捆，那么就在excel表中設(shè)定為15行，在a1區(qū)間（3-3.4）中有43根原料，則l=INT[■]=INT[2.9]，取上限l為3列，反過來求行數(shù)h，h=INT[■]=INT[14.3]，取下限為14行，也就是將43根分配到14行3列中，以此原則類推，將計算機生成的模擬數(shù)據(jù)在Excel表中設(shè)置開始分配控件，用VB程序編寫源程序，按各規(guī)格的每個區(qū)間的原料根數(shù)進(jìn)行第一次K行L列的

8、分配。 </p><p>　　2.3 計算每行原料的總長度和根數(shù)，及與標(biāo)準(zhǔn)規(guī)格的長度差，進(jìn)行二次調(diào)配 </p><p>　　在Excel表中進(jìn)行計算，得到三種規(guī)格的數(shù)據(jù)，二次的搭配原則是定位標(biāo)記初始調(diào)配行，就是說已分配的根數(shù)與標(biāo)準(zhǔn)根數(shù)之差越小且長度差小于0的那個行數(shù)首先開始進(jìn)行調(diào)配，原則上從根數(shù)最多的行中挑選樣本，使長度在（88.5，89.5）之間，可以有±0.5米的誤差，利用計

9、算機編程進(jìn)行調(diào)配，得出各規(guī)格組裝后的捆數(shù)K■■，K■■，K■■，及各規(guī)格的剩余根數(shù)m■■，m■■，m■■。 </p><p>　　2.4 如果某種規(guī)格對應(yīng)原料出現(xiàn)剩余，可以降級使用繼續(xù)組裝捆綁 </p><p>　　把規(guī)格3的剩余根數(shù)m■■降級到規(guī)格2搭配，還能組裝的捆數(shù)K■■=INT[■]且總長度在（88.5，89.5）之間，搭配剩余的規(guī)格2根數(shù)繼續(xù)降級按此原則組裝捆綁得到捆數(shù)K■■。最

10、后得到成品最終捆數(shù)K=K■■+K■■+K■■+K■■+K■■及搭配方案。 </p><p><b>　　3 算法步驟 </b></p><p>　　對系統(tǒng)隨機生成的原料分配方案，要計算出每一組方案中最佳的原料組合。具體算法為：假設(shè)g為每次由0-1模型分配產(chǎn)生的根數(shù)總和，c為長度差， bi（i=1，2，3）為標(biāo)準(zhǔn)根數(shù)/捆。為提高原料使用率，在總長：89+0.5米的范圍內(nèi)

11、，即c∈（-0.5，0.5）；總根數(shù)允許比標(biāo)準(zhǔn)少一根，b或ibi-1都是有效捆法。 </p><p>　　Step1：對第i捆數(shù)據(jù)，計|g-bi+1（i=1，2，3）為N，N為最多篩選數(shù)量，統(tǒng)計C■■中的滿足條件的篩選元素記錄集合，當(dāng)c最小時，對應(yīng)區(qū)間數(shù)據(jù)置0，被篩選出數(shù)據(jù)元素，按各自對應(yīng)列空間存放。 </p><p>　　Step2：當(dāng)C■■中記錄數(shù)為0時，N=N+1，N為達(dá)到標(biāo) <

12、;/p><p>　　準(zhǔn)捆數(shù)的差值，統(tǒng)計C■■中的滿足條件的篩選元素記錄集合，當(dāng)c最小時，對應(yīng)區(qū)間數(shù)據(jù)置0，被篩選出數(shù)據(jù)元素，按各自對應(yīng)列空間存放。 </p><p>　　Step3：如果c最小值相同，當(dāng)C■■中記錄數(shù)為多個時，根據(jù)題目要求2的原則，篩選最短長度較短的腸衣記錄。 </p><p>　　Step4：重復(fù)執(zhí)行步驟1，2，直至所有數(shù)據(jù)均被處理完成。 </p

13、><p>　　Step5：根據(jù)材料降級處理原則，降級處理剩余材料，給出最終材料搭配方案。 </p><p>　　4 建立0-1規(guī)劃模型計算出成品捆數(shù)最大值 </p><p>　　設(shè)置0-1變量aij=1 第i行第j列取走樣本原料0 第i行第j列沒取樣本原料，設(shè)mr為第r個區(qū)間根數(shù)，建立目標(biāo)函數(shù)min=mr-■■aij，（n=8，14，24）。 </p>&

14、lt;p>　　根據(jù)公司對搭配方案的要求，裝出的成品捆數(shù)越多越好，并且最短長度最長的成品越多越好，總長度允許有± 0.5米的誤差，總根數(shù)允許比標(biāo)準(zhǔn)少1根，故約束條件如下：s.t88.5≤■aijxij≤89.519≤■aij≤20 </p><p>　　我們利用計算機模擬所描述的原料數(shù)據(jù)，按照建立的模型及算法運行程序數(shù)次，運行時間小于30分鐘，按要求能快速選出一個較優(yōu)的搭配方案及捆數(shù)。 </p

15、><p>　　規(guī)格1搭配方案得出K■■=15捆，m■■=2根；規(guī)格2搭配方案得出K■■=36捆，剩余根數(shù)m■■=66根；規(guī)格3搭配方案得出K■■=120捆，剩余根數(shù)m■■=80根；規(guī)格3的剩余根數(shù)m■■降級到規(guī)格2搭配，K■■=INT（■）=18捆，剩余2根。 </p><p><b>　　最后得出總捆數(shù)： </b></p><p>　　K=K■■

16、+K■■+K■■+K■■+K■■ </p><p>　　=15+36+120+18=189捆。 </p><p><b>　　注釋： </b></p><p>　?、偬烊荒c衣原料規(guī)格要求及數(shù)據(jù)來源于2011全國大學(xué)生數(shù)學(xué)建模D題. </p><p><b>　　參考文獻(xiàn)： </b></p>

17、;<p>　　[1]楊啟帆，數(shù)學(xué)建模[M].北京：高等教育出版社，2005. </p><p>　　[2]姜啟源，數(shù)學(xué)建模[M].北京：高等教育出版社，2003. </p><p>　　[3]李秀珍，龐常詞.數(shù)學(xué)實驗[M].北京：機械工業(yè)出版社，2008. </p><p>　　[4]姜啟源，謝金星，葉俊.數(shù)學(xué)模型.第三版[M].北京：高等級教育出版社