天然腸衣搭配分析(2011D)

1、20112011年高教社杯全國大學生數(shù)學建模競賽賽題解析年高教社杯全國大學生數(shù)學建模競賽賽題解析20112011年年D D題題天然腸衣搭配問題分析天然腸衣搭配問題分析吉耀武吉耀武西安鐵路職業(yè)技術學院西安鐵路職業(yè)技術學院. . 流流 程程 圖圖一一. . 問問 題題 提出提出 二二. . 賽賽 題題 簡簡 述述 三三. . 問問 題題 分分 析析 四四. . 模模 型型 假假 設設 五五. .模型建立與求解模型建立與求解 六六. . 小小 結結 數(shù)學教研室 吉耀武 天然腸衣指的是家畜的大小腸經(jīng)刮制而成的畜天然腸衣指的是家畜的大小腸經(jīng)刮制而成的畜產(chǎn)品，主要用于香腸、灌腸等食品的外衣。我國加產(chǎn)品，主

2、要用于香腸、灌腸等食品的外衣。我國加工腸衣歷史悠久，產(chǎn)量占世界總產(chǎn)量的工腸衣歷史悠久，產(chǎn)量占世界總產(chǎn)量的1/3,1/3,其中約其中約80%80%出口出口. . 傳統(tǒng)的腸衣加工主要依靠人工來完成，一方面?zhèn)鹘y(tǒng)的腸衣加工主要依靠人工來完成，一方面，人工成本高；另一方面，作為食品，不允許將剩，人工成本高；另一方面，作為食品，不允許將剩余材料留作以后使用，而人工搭配一般不作整體考余材料留作以后使用，而人工搭配一般不作整體考慮，只是憑經(jīng)驗判斷是否可搭配成捆，無法保證原慮，只是憑經(jīng)驗判斷是否可搭配成捆，無法保證原材料的充分利用。材料的充分利用。一、問題提出一、問題提出數(shù)學教研室 吉耀武 2011年高教社杯全

3、國大學生數(shù)學建模競賽年高教社杯全國大學生數(shù)學建模競賽D題題天然天然腸衣搭配問題。要求解決的問題是根據(jù)題目提供的成品規(guī)格腸衣搭配問題。要求解決的問題是根據(jù)題目提供的成品規(guī)格表和原料描述表，設計一個原料搭配方案，工人根據(jù)這個方表和原料描述表，設計一個原料搭配方案，工人根據(jù)這個方案案“照方抓藥照方抓藥”進行生產(chǎn)。進行生產(chǎn)。 公司對搭配方案有以下具體要求：公司對搭配方案有以下具體要求： (1) 對于給定的一批原料，裝出的成品捆數(shù)越多越好；對于給定的一批原料，裝出的成品捆數(shù)越多越好； (2) 對于成品捆數(shù)相同的方案，最短長度最長的成品越對于成品捆數(shù)相同的方案，最短長度最長的成品越多，方案越好；多，方案越

4、好； (3) 為提高原料使用率，總長度允許有為提高原料使用率，總長度允許有 0.5米的誤差，米的誤差，總根數(shù)允許比標準少總根數(shù)允許比標準少1根；根； (4) 某種規(guī)格對應原料如果出現(xiàn)剩余，可以降級使用。某種規(guī)格對應原料如果出現(xiàn)剩余，可以降級使用。如長度為如長度為14米的原料可以和長度介于米的原料可以和長度介于7-13.5米的進行捆扎，米的進行捆扎，成品屬于成品屬于7-13.5米的規(guī)格；米的規(guī)格； (5) 為了食品保鮮為了食品保鮮,要求在要求在30分鐘內(nèi)產(chǎn)生方案。分鐘內(nèi)產(chǎn)生方案。二、賽題簡述二、賽題簡述數(shù)學教研室 吉耀武 成品規(guī)格表數(shù)學教研室 吉耀武 原料描述表數(shù)學教研室 吉耀武目標：目標： (

5、1) 對于給定的原料，裝出的成品捆數(shù)越多越好；對于給定的原料，裝出的成品捆數(shù)越多越好； (2) 對于成品捆數(shù)相同的方案，最短長度最長的成對于成品捆數(shù)相同的方案，最短長度最長的成品品 越多，方案越好；越多，方案越好； (3) 為了食品保鮮為了食品保鮮,要求在要求在30分鐘內(nèi)產(chǎn)生方案。分鐘內(nèi)產(chǎn)生方案。 三、問三、問 題題 分分 析析條條 件：件： (1)總長度允許有總長度允許有 0.5米的誤差；米的誤差； (2)總根數(shù)允許比標準少總根數(shù)允許比標準少1根；根； (3)剩余原料可以降級使用。剩余原料可以降級使用。 數(shù)學教研室 吉耀武三、問三、問 題題 分分 析析解決方案：解決方案： 將產(chǎn)品規(guī)格分成長、

6、中、短三檔。其實質是將將產(chǎn)品規(guī)格分成長、中、短三檔。其實質是將“最短長最短長度最長的成品最多度最長的成品最多” 轉化為轉化為 “最短長度在某個值以上的成最短長度在某個值以上的成品最多品最多”。 1）按照可降級的要求，先從長規(guī)格開始，進行求解優(yōu)）按照可降級的要求，先從長規(guī)格開始，進行求解優(yōu)化搭配；化搭配； 2）將第）將第1步優(yōu)化后剩余的原料放入中規(guī)格，進行求解優(yōu)步優(yōu)化后剩余的原料放入中規(guī)格，進行求解優(yōu)化搭配；化搭配； 3）將第）將第2步優(yōu)化后剩余的原料放入短規(guī)格，進行求解優(yōu)步優(yōu)化后剩余的原料放入短規(guī)格，進行求解優(yōu)化搭配；化搭配； 4）如果剩余的原料總長小于）如果剩余的原料總長小于88.5米或接近

7、于理論最優(yōu)米或接近于理論最優(yōu)值，則認為優(yōu)化成功。值，則認為優(yōu)化成功。數(shù)學教研室 吉耀武四、四、模模 型型 假假 設設模型假設：模型假設： 1、原料描述表中提供的原料不能剪裁使用；、原料描述表中提供的原料不能剪裁使用； 2、為提高原料使用率，總長度允許有、為提高原料使用率，總長度允許有 0.5米的米的誤差，總根數(shù)允許比標準少誤差，總根數(shù)允許比標準少1根；根； 3、某種規(guī)格對應的原料如果出現(xiàn)、某種規(guī)格對應的原料如果出現(xiàn)剩余較多剩余較多時，時，可以平移降級使用。如長度為可以平移降級使用。如長度為7米、米、7.5米、米、8米的米的原料出現(xiàn)剩余，可以向下一規(guī)格原料出現(xiàn)剩余，可以向下一規(guī)格平移降級平移降級

8、為為5.5米、米、6米、米、6.5米使用，這樣可以提高原料的使用率。米使用，這樣可以提高原料的使用率。什么是平什么是平移降級移降級?數(shù)學教研室 吉耀武五、模型建立與求解五、模型建立與求解方法一方法一 ： 1、將捆數(shù)和搭配分開優(yōu)化、將捆數(shù)和搭配分開優(yōu)化 （1）最大捆數(shù)的優(yōu)化模型）最大捆數(shù)的優(yōu)化模型數(shù)學教研室 吉耀武數(shù)學教研室 吉耀武五、模型建立與求解五、模型建立與求解模型建立模型建立: :數(shù)學教研室 吉耀武 捆數(shù)優(yōu)化程序： model: N=; L=89; sets: yuanliao/1.k/: x,c,a,b; endsets data: a=; b=; enddata max=M; sum

9、(yuanliao(i): x)=M*(N-1); sum(yuanliao(i): x)=M*(L-0.5); sum(yuanliao(i): a*x)=M*(L+0.5); for(yuanliao(i): x=N-1; sum(yuanliao(i): y(i,j)=L-0.5; sum(yuanliao(i): a(j)*y(i,j)=L+0.5);for(link(i,j): gin(y);end 數(shù)學教研室 吉耀武五、模型建立與求解五、模型建立與求解2. 將捆數(shù)和搭配聯(lián)合優(yōu)化模型將捆數(shù)和搭配聯(lián)合優(yōu)化模型數(shù)學教研室 吉耀武建立聯(lián)合優(yōu)化模型：取整數(shù)ijM1ijijk1jijjk1jijyby0.5Lya0.5LNy1NM.s.tmax數(shù)學教研室 吉耀武方法二：方法二： 五、模型建立與求解五、模型建立與求解數(shù)學教研室 吉耀武五、模型建立與求解五、模型建立與求解數(shù)學教研室 吉耀武 目標函數(shù)： 約束條件： 扎捆模式可用MATLAB編程得到 優(yōu)化程序類似于前面捆數(shù)的優(yōu)化程序M1iixmax取整數(shù)ijM1iijixbrxk kM M)(ijr數(shù)學教研室 吉耀武 六、小 結 1、模型分析要全面、模型分析要全面; 2、按長、中、短規(guī)格順序建立模型、按長、中、短規(guī)格順序建立模型; 3、模型的建