1、池州學院天然腸衣搭配問題 組員：陳強 趙晉彪 趙海龍 1 / 31目錄一、問題重述41.1問題背景41.2.問題條件41.3.問題要求51.4需要解決的問題5二、問題分析5三、模型假設6四、符號說明6五 模型的建立65.1、模型建立65.2、根據要求模型建立9六、模型求解106.1、問題要求（1）模型求解106.2、問題要求（2）模型求解126.3、問題要求（3）模型求解15七、模型的評價與推廣177.1.模型的評價177.1.1模型的優點177.1.2模型的缺點177.2模型的推廣17八、參考文獻17附錄18附錄A18附錄B20附錄C23附錄D25天然腸衣搭配問題摘要天然腸衣制作加工是我國的

2、一個傳統產業，出口量占世界首位，而天然腸衣傳統的人工生產方式已不能滿足出口量日益增長的需要。因此，我們從節約生產成本、提高企業生產效率的角度出發，我們結合原料的供給量、長度及成品規格等約束條件進行了模型設計。根據題目中的表1中的成品的規格和表2中的原料，我們所需要解決的問題有：如何搭配才能使得成品的捆數最多？對于針對這一個問題我們采用線性規劃建立模型并利用MATLAB以捆數相同，最短長度越長越好的原則，求得模型的最優解。另外，由于所有的原料按長度分檔，通常以0.5米為一檔，如：3-3.4米按3米計算，3.5米-3.9米按3.5米計算，其余的依此類推。表1是幾種常見成品的規格，長度單位為米，表示

3、沒有上限，但實際長度小于26米。再把不同檔次的原料按照不同的規格進行搭配，分別搭配成三種規格的成品，依次是成品一(36.5米,20根，總長度89米)，成品二(713.5米，8根，總長度89米)，成品三（14米，5根，總長度89米）。運用線性規劃分別對成品一、成品二、成品三建立模型，利用LINGO編程進行1步，2步，3步優化篩選，得出方案。并且，對各步篩選所剩余原料再進行優化得出方案，另外，為了提高原材料的使用率，每成品的總長度允許有0.5米的誤差，總根數允許比標準少1根，某種成品對應得原材料有剩余，可以降一級使用，這樣就會出現每捆總長度88.5米和89.5米，有19根一捆，7根一捆，4根一捆，

4、在滿足條件時，計算出最大捆數。關鍵詞：天然腸衣 ； 線性規劃 ；MATLAB ;LINGO一、問題重述1.1問題背景天然腸衣制作加工是我國的一個傳統產業，出口量占世界首位，而天然腸衣傳統的生產依靠工人，邊丈量長度，邊心算，將原材料按指定根數和總長度組裝成捆方式已不能滿足出口量日益增長的需要。因此，我們從節約生產成本、提高企業生產效率的角度出發，結合原料的供給量、長度及成品規格等約束條件進行生產模型設計。1.2.問題條件已知某天然腸衣組裝的規格表( 見表1) 和某批次原料的描述表( 見表2) 表1 成品規格表成品最短長度/m最長長度/m根數總長度/m成品一成品二 成品三37146.513.520

5、85898989表2 原料描述表長度3-3.43.5-3.94-4.44.5-4.95-5.45.5-5.96-6.46.5-6.9根數4359394127283421長度7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.410.5-10.9根數2424202521232118長度11-11.411.5-11.912-12.412.5-12.913-13.413.5-13.914-14.414.5-14.9根數3123225918253529長度15-15.415.5-15.916-16.416.5-16.917-17.417.5-17.918-18.418.

6、5-18.9根數3042284245495064長度19-19.419.5-19.920-20.420.5-20.921-21.421.5-21.922-22.422.5-22.9根數526349352716122長度23-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9根數0600011.3.問題要求根據生產規格和原料描述表，設計滿足以下要求及允許條件下的組裝方案( 即對原料進行打捆的搭配方案) 。1) 對于給定的一批原料，裝出的成品時，捆數越多越好；2) 對于成品捆數相同的方案，最短長度最長的成品越多，方案越好；3) 允許成品總長度有±

7、0.5 m 的誤差，即總長度88.5米，,89.5米；4) 每捆總根數允許比標準少1 根即每捆可以為19根，7根，4根；5) 某種成品對應原料如果出現剩余，可以降級使；。6）為了食品安全要求在30分鐘內完成。1.4需要解決的問題首先我們要考慮原料應該怎樣處理，然后考慮各類成品原料的搭配問題以及剩余材料的得搭配問題。二、問題分析 天然腸衣經過人工清理和截取成不等長度，在進行搭配成成品，傳統工藝里，工人們邊勞作用心丈量，其操作不僅效率差，有時會造成嚴重資源浪費，為了解決這一問題即做到同等材料中，加工成成品后，剩余材料最少，捆數最多，我們依據表一，表二的生產規格和所擁有的原料進行生產搭配成成品，作出

8、最有模型。 對于問題要求一，我們運用lingo軟件編程求出優化方案，并作出逐步優化，得出最大捆數；對于問題二，利用matlab編程，按照最短長度最長的原則選出最優方案，將選出的方案與lingo結合編程，得出最大捆數，然后在剩余中再按照最短長度最長的原則選擇最后所能組成的捆數；對于問題要求三、四、五，對于成品一規格，要求長度滿足，或根數滿足根； 對于成品二規格，要求長度滿足，或+0.5,根數滿足根；對于成品三規格，要求長度 滿足14m26m，或=+0.5,第三類原料最大長度為，但原料的實際長度小于26米,根數滿足5根。在每個檔次的原料滿足這些約束條件的前提下，建立不定方程組，用lingo軟件求解

9、出每種規格產品的最大捆數；為提高原料使用率，總長度允許有±0.5米的誤差，總根數允許比標準少1根。因此生產條件將變為每捆天然腸衣成品的總長度為89±0.5m，同時可能會出現成品一每捆十九根，成品二每捆七根，成品三每捆四根，建立不定方程組，用lingo軟件求解出每種規格產品的最大捆數。三、模型假設1、 假設題目所給的數據真實可靠；2、 所有原料都是新鮮的，沒有腐爛；3、 所有原料都是同種原料，不需要對原料進行分類；4、 廠房的環境、車間和工作人員的衛生等不會對原料產生影響；5、 廠房中的溫度，光照等不會對原料的保鮮產生影響。四、符號說明 每個檔次在組裝中所使用的根數 不同規格

10、成品按某種方案所組裝出來的捆數 每種規格所能夠組合出來的最大捆數 各規格的最大捆數的總和 各個檔次在經過縮小取值范圍后的取值 規格的成品第次按照某個方案組裝所的捆數 各個檔次經過組裝的剩余量 檔次的原料開始時的數量 每種規格所能取得的最大理想捆數 規格的原料在經過要求（2）的篩選后剩余的總根數五 模型的建立5.1、模型建立成品一成品一要求是選出20根不同腸衣組裝成1捆，原料長度按0.5米為一檔，如：33.4按3米計算，所選出得腸衣總長度之和為89米，可以得出 其中的限制條件為：按照某個方案組裝捆之后，的根數會減少一部分，減少后限制條件變化為 經過次組裝之后，規格1的成品的捆數要求最大，可以得出

11、成品二規格2的要求是選出8根不同腸衣組裝成1捆，所選出得腸衣總長度之和為89米，可以得出的根數限制條件為 按照某個方案組裝捆之后，的根數會減少一部分，減少后限制條件變化為 經過次組裝之后，規格2成品的捆數要求最大，可以得出成品三成品3要求是選出5根不同腸衣組裝成1捆，所選出得腸衣總長度之和為89米，可以得出的根數限制條件為 按照某個方案組裝捆之后，的根數會減少一部分，減少后限制條件變化為 經過次組裝之后，成品三成品的產品的捆數要求最大，可以得出最后得出成品的最大捆數為5.2、根據要求模型建立成品一在第一輪篩選后的余量總根數（即滿足問題要求2）由于題目要求是20跟一捆，即便充分利用問題要求（3）

12、和（4），也達不到題中的要求，所以成品一不能再搭配出多余的捆數。成品二同樣經過要求(2)的篩選后剩下的總根數根數可以達到8根一捆，再考慮一捆的總長度為米和每捆為8根，8根不行，再考慮每捆7根。成品三也是經過要求(2)篩選后剩下的總根數為 按題中5根一捆，根數能夠滿足要求，再加上每捆總長度在89米，每捆按5或求其次4根計算。目標函數：約束條件： 六、模型求解6.1、問題要求（1）模型求解對于不同規格的成品，會存在一個理想的最大捆數，但是由于實際條件的約束，總捆數不可能超過，其中理想的最大捆數等于此種規格的總根數之和除于此種規格每捆的根數要求成品一的最大理想捆數余下12根成品二的最大理想捆數余下2

13、根成品三的最大理想捆數余下2根成品一利用編程（程序見附錄A），對成品一進行最優化篩選，可得方案表3 成品一的原料第1輪篩選的方案選取根數25332131 方案所得捆數：11經過1輪的優化之后，并未達到最優，再進行優化，有方案表4 篩成品一的原料第2篩選的方案選取根數71211503 方案所得捆數：3成品一的實際的總捆數之和， 實際的總捆數之和與最大理想總捆數相等，成品一的優化結束。各個檔次剩余根數分別為表5 成品一的原料經過篩選所剩余的原料剩余根數01050211成品二 利用同樣的方法對成品二進行優化分配處理表6 成品二的原料第1輪篩選的方案選取根數0101000選取根數0111201 方案所

14、得捆數為：22表7 成品二的原料第2輪篩選的方案 選取根數0000021選取根數1100120 方案所得捆數為：9表8 成品二的原料第3輪篩選的方案選取根數0000012選取根數2000201 方案所得捆數為：3經3輪的篩選之后，各個檔次的根數剩余量為表9成品二的原料3輪篩選的剩余量 剩余根數2422032126剩余根數3010000剩余的原料不能再組裝出符合要求的成品，優化結束。最后得出成品二的原料所能夠組裝的最大實際捆數為成品三 成品三的原料采用同樣方法，經過九輪篩選之后剩余原料跟數為：表10成品三的原料9輪篩選的剩余量剩余根數000010100001剩余根數2001122060001經過

15、9輪的優化篩選之后，剩余的原料無法再組裝出符合要求的成品，最后求得成品三的實際最大捆數為所以，利用對題目中給定的原料求解出最大能夠組裝出的捆數6.2、問題要求（2）模型求解成品一利用編程（程序見附錄B），按照最短長度最長的原則選出如下方案，將選出的方案結合編程（程序見附錄C），得出捆數為11表11 成品一的原料按照最短長度最長優化的方案選取根數25332131在剩余中再按照最短長度最長的方案選擇3捆，方案如下表12 成品一的原料按照最短長度最長優化的方案選取根數71211503成品二在符合成品二的材料中按照最短長度最長的方案選擇22捆，方案如下表13 成品二的原料按照最短長度最長優化的方案選取

16、根數0101000選取根數0111201在剩余中再按照最短長度最長的方案選擇9捆，方案如下表14 成品二的原料按照最短長度最長優化的方案選取根數0000021選取根數1100120再在剩余中再按照最短長度最長的方案選擇3捆，方案如下表15成品二的原料按照最短長度最長優化的方案選取根數0000012選取根數2000201成品三在符合成品三的材料中按照最短長度最長的方案進行選擇42捆，方案如下表16 成品三的原料按照最短長度最長優化的方案選取根數000001101110選取根數000001000000在剩余中再按照最短長度最長的方案選擇31捆，方案如下表17 成品三的原料按照最短長度最長優化的方案

17、選取根數100100000002選取根數010000000000在剩余中再按照最短長度最長的方案選擇27捆，方案如下表18 成品三的原料按照最短長度最長優化的方案選取根數010010010000選取根數101000000000在剩余中再按照最短長度最長的方案選擇15捆，方案如下表19 成品三的原料按照最短長度最長優化的方案選取根數002000010000選取根數100100000000在剩余中再按照最短長度最長的方案選擇7捆，方案如下表20 成品三的原料按照最短長度最長優化的方案選取根數000100001300選取根數000000000000在剩余中再按照最短長度最長的方案選擇4捆，方案如下表

18、21 成品三的原料按照最短長度最長優化的方案選取根數100100000010選取根數110000000000在剩余中再按照最短長度最長的方案選擇2捆，方案如下表22 成品三的原料按照最短長度最長優化的方案選取根數010000010030選取根數000000000000在剩余中再按照最短長度最長的方案選擇1捆，方案如下表23 成品三的原料按照最短長度最長優化的方案選取根數000000031100選取根數000000000000在剩余中再按照最短長度最長的方案選擇1捆，方案如下表24 成品三的原料按照最短長度最長優化的方案選取根數000000220000選取根數100000000000按照上述成品

19、三選擇原材料進行組裝，即可使得這批原材料的所組裝出來的成品最短長度最長，此時各個規格的捆數之和為178，相比要求1所得的捆數多出了1捆，這是因為成品三在選擇最短長度最長的方案組裝的時候使得材料能夠更加充分利用6.3、問題要求（3）模型求解通過編程求解（程序見附錄D），有成品一沒有符合要求(3)的方案。成品二8根一捆，選出剩余的最長的8根總長度為米，沒有達到最低要求88.5米，每捆減少1根就更不能滿足要求，所以沒有搭配方案。成品三用lingo軟件運行每捆總長度為米，5根一捆的搭配，沒有符合的方案，再用4根一捆，結果可以搭配出6捆。在選擇4捆時，具體的方案為表25 成品三的原料按照要求(3)的優化

20、方案選取根數000000000000選取根數000030010000在剩余材料按要求(3)選擇1捆時，方案為表26 成品三的原料按照要求(3)的優化方案選取根數000000000000選取根數100000020000在剩余材料按要求(3)選擇1捆時，方案為表27 成品三的原料按照要求(3)的優化方案選取根數000000000000選取根數010010100001七、模型的評價與推廣7.1.模型的評價7.1.1模型的優點 （1）本模型的建立在相應的理論指導下，理論基礎較為成熟，并且有相應的專用軟件支持，因此可信度較高。（2）利用數學工具，通過，編程的方法，嚴格地對模型進行求解，具有較高的科學性。

21、（3）模型的建立與實際緊密聯系，充分考慮實際情況的多樣性，從而使得模型更貼進實際，通用性、推廣性較強。7.1.2模型的缺點（1）選取的數據難免在現實生活中存在諸多不協調，帶來不可避免誤差；（2）在對各檔的數據進行處理時，都采用各檔的標準值，這樣會存在系統誤差。（3）在建模的過程中，雖然考慮了很多因素，但仍然忽略了其他不確定因素等次要因素的影響，比如關于原料切割損壞問題等等，在模型假設里都忽略了7.2模型的推廣 該模型是一個典型的整數線性規劃模型，在實際生活中有著廣泛的使用空間。該模型不僅可以對天然腸衣搭配，還可以對類似的問題進行求解。以本模型為基礎可以進一步對復雜問題，用類似的方法對模型進行改

22、進，因此模型具有較強的普遍適用性。八、參考文獻1萬福永 戴浩暉 潘建瑜 數學實驗教程（matlab版）北京 科學出版社 20032謝金星、薛毅.優化建模與LINDO軟件M.北京：清華大學出版社，2005 3傅遠德.線性規劃和整數規劃M.成都：成都科技大學出版社，1989.12 4盧開澄、盧華明.線性規劃M.北京：清華大學出版社，2009 附錄附錄A、B、C、D每種程序均附上一個模板，后面的采用遞減重復運行即可附錄A成品一max=y;3*x1+3.5*x2+4*x3+4.5*x4+5*x5+5.5*x6+6*x7+6.5*x8=89;x1+x2+x3+x4+x5+x6+x7+x8=20;y*x1

23、<=43;y*x2<=59;y*x3<=39;y*x4<=41;y*x5<=27;y*x6<=28;y*x7<=34;y*x8<=21;gin(x1);bnd(0,x1,43);gin(x2);bnd(0,x2,59);gin(x3);bnd(0,x3,39);gin(x4);bnd(0,x4,41);gin(x5);bnd(0,x5,27);gin(x6);bnd(0,x6,28);gin(x7);bnd(0,x7,34);gin(x8);bnd(0,x8,21);gin(y);bnd(0,y,14);成品二max=y;7*x9+7.5*x10

24、+8*x11+8.5*x12+9*x13+9.5*x14+10*x15+10.5*x16+11*x17+11.5*x18+12*x19+12.5*x20+13*x21+13.5*x22=89;x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22=8;y*x9<=24;y*x10<=24;y*x11<=20;y*x12<=25;y*x13<=21;y*x14<=23;y*x15<=21; y*x16<=18; y*x17<=31; y*x18<=23; y*x19<=22;

25、y*x20<=59; y*x21<=18; y*x22<=25;gin(x9);bnd(0,x9,24);gin(x10);bnd(0,x10,24);gin(x11);bnd(0,x11,20);gin(x12);bnd(0,x12,25);gin(x13);bnd(0,x13,21); gin(x14);bnd(0,x14,23);gin(x15);bnd(0,x15,21); gin(x16);bnd(0,x16,18); gin(x17);bnd(0,x17,31); gin(x18);bnd(0,x18,23); gin(x19);bnd(0,x19,22); gi

26、n(x20);bnd(0,x20,59); gin(x21);bnd(0,x21,18); gin(x22);bnd(0,x22,25);gin(y);bnd(0,y,44);成品三max=y;14*x23+14.5*x24+15*x25+15.5*x26+16*x27+16.5*x28+17*x29+17.5*x30+18*x31+18.5*x32+19*x33+19.5*x34+20*x35+20.5*x36+21*x37+21.5*x38+22*x39+22.5*x40+23*x41+23.5*x42+24*x43+24.5*x44+25*x45+25.5*x46=89;x1+x2+x3

27、+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24=5;y*x23<=35; y*x24<=29; y*x25<=30; y*x26<=42; y*x27<=28; y*x28<=42; y*x29<=45; y*x30<=49; y*x31<=50; y*x32<=64; y*x33<=52;y*x34<=63; y*x35<=49; y*x36<=35; y*x37<=27; y*x38<=

28、16; y*x39<=12; y*x40<=2; y*x41<=0; y*x42<=6; y*x43<=0; y*x44<=0; y*x45<=0; y*x46<=1;gin(x23);bnd(0,x23,35);gin(x24);bnd(0,x24,29);gin(x25);bnd(0,x25,30);gin(x26);bnd(0,x26,42);gin(x27);bnd(0,x27,28); gin(x28);bnd(0,x28,42);gin(x29);bnd(0,x29,45); gin(x30);bnd(0,x30,49);gin(x3

29、1);bnd(0,x31,50);gin(x32);bnd(0,x32,64);gin(x33);bnd(0,x33,52);gin(x34);bnd(0,x34,63);gin(x35);bnd(0,x35,49);gin(x36);bnd(0,x36,35);gin(x37);bnd(0,x37,27);gin(x38);bnd(0,x38,16);gin(x39);bnd(0,x39,12);gin(x40);bnd(0,x40,2);gin(x41);bnd(0,x41,0);gin(x42);bnd(0,x42,6);gin(x43);bnd(0,x43,0);gin(x44);bn

30、d(0,x44,0);gin(x45);bnd(0,x45,0);gin(x46);bnd(0,x46,1);gin(y);bnd(0,y,136);附錄B成品一function yy1c=1;for x1=0:43/11 for x2=0:59/11 for x3=0:39/11 for x4=0:41/11 for x5=0:27/11 for x6=0:28/11 for x7=0:34/11 for x8=0:21/11 k1=x1*3+x2*3.5+x3*4+x4*4.5+x5*5+x6*5.5+x7*6+x8*6.5; k2=x1+x2+x3+x4+x5+x6+x7+x8; if

31、(k1=89)&(k2=20) fprintf('第%d種 n %d,%d,%d,%d,%d,%d,%d,%d n',c,x1,x2,x3,x4,x5,x6,x7,x8) c=c+1; end end end end end end end endend成品二function yy2 c=1;for x9=0:24/22 for x10=0:24/22 for x11=0:20/22 for x12=0:25/22 for x13=0:21/22 for x14=0:23/22 for x15=0:21/22 for x16=0:18/22 for x17=0:31/2

32、2 for x18=0:23/22 for x19=0:22/22 for x20=0:59/22 for x21=0:18/22 for x22=0:25/22 k1=7*x9+7.5*x10+8*x11+8.5*x12+9*x13+9.5*x14+10*x15+10.5*x16+11*x17+11.5*x18+12*x19+12.5*x20+13*x21+13.5*x22; k2=x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22; if (k1=89)&(k2=8) fprintf('第%d種 n %d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d n',c,x9,x10,x1