高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽D題

1、2011高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承 諾 書(shū)我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則。我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從a/b/c/d中選擇一項(xiàng)填寫）： d 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置

2、報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?成都航空職業(yè)技術(shù)學(xué)院 參賽隊(duì)員 (打印并簽名) ：1. 林 亮 2. 呂 迪 3. 崔丁飛 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期： 年 月 日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2011高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編 號(hào) 專 用 頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：天然腸衣搭配問(wèn)題摘要 本文針對(duì)天然腸衣搭配問(wèn)題的研究，根據(jù)公司對(duì)搭配方案的具體要求，建立起最佳搭配模型。首先，在理

3、想情況下建立最優(yōu)搭配方案，然而，此方案中變量太多，可操作性較低，所以不易實(shí)現(xiàn)。在此基礎(chǔ)上，我們先簡(jiǎn)化模型減少變量，用maple編程的方法來(lái)確定具體要求下最優(yōu)的搭配方案。先將三種不同規(guī)格的成品進(jìn)行最優(yōu)化求解，將規(guī)格2（7至13.5）的剩余原料與規(guī)格1（3至6.5）的剩余原料進(jìn)行合理搭配，兩種原料搭配后的剩余原料再與規(guī)格3（14至）的剩余原料進(jìn)行合理搭配。如果合理搭配之后規(guī)格3（14至）的原料還有剩余則降級(jí)成規(guī)格2（7至13.5）進(jìn)行捆扎，如果最終規(guī)格1（3至6.5）的原料還有剩余，則不能進(jìn)行捆扎，因此該剩余規(guī)格1（3至6.5）的原料不能進(jìn)行生產(chǎn)，從而使搭配出的成品捆數(shù)較多。按此解決方案代入表2中

4、的數(shù)據(jù)，得出該批原料搭配出的成品最優(yōu)捆數(shù)為187捆，并在對(duì)實(shí)際數(shù)據(jù)進(jìn)行求解的過(guò)程中得出相應(yīng)的搭配方案（maple編程得出的三種規(guī)格的搭配方案見(jiàn)附錄二），并模擬出了產(chǎn)生方案所需總時(shí)間大約為22分鐘。 按題中具體要求得到的模型搭配方式太多，不適宜工人的實(shí)際操作。因此，我們根據(jù)表一和表二的描述設(shè)計(jì)了一個(gè)原料搭配方案。關(guān)鍵詞：腸衣搭配、maple編程。一、問(wèn)題重述天然腸衣（以下簡(jiǎn)稱腸衣）制作加工是我國(guó)的一個(gè)傳統(tǒng)產(chǎn)業(yè)，出口量占世界首位。腸衣經(jīng)過(guò)清洗整理后被分割成長(zhǎng)度不等的小段（原料），進(jìn)入組裝工序。傳統(tǒng)的生產(chǎn)方式依靠人工，邊丈量原料長(zhǎng)度邊心算，將原材料按指定根數(shù)和總長(zhǎng)度組裝出成品（捆）。原料按長(zhǎng)度分檔，

5、通常以0.5米為一檔，如：3-3.4米按3米計(jì)算，3.5米-3.9米按3.5米計(jì)算，其余的依此類推。表1是幾種常見(jiàn)成品的規(guī)格，長(zhǎng)度單位為米，表示沒(méi)有上限，但實(shí)際長(zhǎng)度小于26米。表1 成品規(guī)格表最短長(zhǎng)度最大長(zhǎng)度根數(shù)總長(zhǎng)度36.52089713.588914589為了提高生產(chǎn)效率，公司計(jì)劃改變組裝工藝，先丈量所有原料，建立一個(gè)原料表。表2為某批次原料描述。表2 原料描述表長(zhǎng)度3-3.43.5-3.94-4.44.5-4.95-5.45.5-5.96-6.46.5-6.9根數(shù)4359394127283421長(zhǎng)度7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.410

6、.5-10.9根數(shù)2424202521232118長(zhǎng)度11-11.411.5-11.912-12.412.5-12.913-13.413.5-13.914-14.414.4-14.9根數(shù)3123225918253529長(zhǎng)度15-15.415.5-15.916-16.416.5-16.917-17.417.5-17.918-18.418.5-18.9根數(shù)3042284245495064長(zhǎng)度19-19.419.5-19.920-20.420.5-20.921-21.421.5-21.922-22.422.5-22.9根數(shù)526349352716122長(zhǎng)度23-23.423.5-23.924-24.

7、424.5-24.925-25.425.5-25.9根數(shù)060001根據(jù)以上成品和原料描述，設(shè)計(jì)一個(gè)原料搭配方案，工人根據(jù)這個(gè)方案“照方抓藥”進(jìn)行生產(chǎn)。公司對(duì)搭配方案有以下具體要求：(1) 對(duì)于給定的一批原料，裝出的成品捆數(shù)越多越好；(2) 對(duì)于成品捆數(shù)相同的方案，最短長(zhǎng)度最長(zhǎng)的成品越多，方案越好；(3) 為提高原料使用率，總長(zhǎng)度允許有± 0.5米的誤差，總根數(shù)允許比標(biāo)準(zhǔn)少1根；(4) 某種規(guī)格對(duì)應(yīng)原料如果出現(xiàn)剩余，可以降級(jí)使用。如長(zhǎng)度為14米的原料可以和長(zhǎng)度介于7-13.5米的進(jìn)行捆扎，成品屬于7-13.5米的規(guī)格；(5) 為了食品保鮮,要求在30分鐘內(nèi)產(chǎn)生方案。請(qǐng)建立上述問(wèn)題的數(shù)

8、學(xué)模型，給出求解方法，并對(duì)表1、表2給出的實(shí)際數(shù)據(jù)進(jìn)行求解，給出搭配方案。二、模型假設(shè)1不計(jì)丈量腸衣時(shí)的誤差。2按照表一中三種成品規(guī)格進(jìn)行生產(chǎn)，不考慮其它規(guī)格。3不考慮外界因素對(duì)產(chǎn)生方案時(shí)間的影響。4腸衣原料實(shí)際長(zhǎng)度小于26米。5優(yōu)化后的剩余量降級(jí)使用，不再考慮長(zhǎng)度，可以加到下一種規(guī)格的任何一檔。6原料按長(zhǎng)度分檔，以0.5米為一檔，3-3.4米按3米計(jì)算，3.5-3.9按3.5米計(jì)算，其余的以此類推。三、符號(hào)說(shuō)明：成品總捆數(shù)；：第種規(guī)格產(chǎn)品的捆數(shù)；：第種規(guī)格成品按第種搭配方式所需第檔原料數(shù)目；：第種規(guī)格分配好以后原料剩余總根數(shù)；：產(chǎn)生方案所需時(shí)間；：第檔原料數(shù)目；：第檔原料長(zhǎng)度；：第種規(guī)格按第

9、種方式搭配的捆數(shù)；：第規(guī)格成品所需根數(shù)；：第種規(guī)格的組合方式；（注釋：=1,2,3，46；=1,2,3；第1種規(guī)格為成品（3至6.5），第2種規(guī)格為成品（7至13.5），第3種規(guī)格為成品（14至）。四、模型的建立 天然腸衣要按照指定的根數(shù)和總長(zhǎng)度組裝出成品，對(duì)于給定的一批原料來(lái)說(shuō)，組裝出成品的捆數(shù)越多越好，我們將成品的捆數(shù)作為目標(biāo)，得出以下整數(shù)優(yōu)目標(biāo)函數(shù)。天然腸衣原料長(zhǎng)度不一，以0.5米為一檔共被分為46檔。為提高原料利用率，總長(zhǎng)度允許有0.5米的誤差，得到第一個(gè)約束條件；第種規(guī)格成品按第種搭配方式所需第檔原料數(shù)目為定值，則由此得到第二至第五個(gè)約束條件；第種規(guī)格成品按第種方式搭配的捆數(shù)不能超過(guò)

10、第檔原料數(shù)目，據(jù)此得到第七個(gè)約束條件。 目標(biāo)函數(shù)：約束條件：五、模型的求解由總模型可知，變量數(shù)目相當(dāng)龐大，如果用窮舉法求解模型，時(shí)間將會(huì)大大超過(guò)30分鐘，而且將所有規(guī)格的原材料放在一起捆扎勢(shì)必對(duì)工人的工作增大難度。所以為了避免計(jì)算困難及企業(yè)工人操作上的困難，將模型分為三個(gè)優(yōu)化模型，即針對(duì)三種規(guī)格的腸衣分別求出最優(yōu)捆扎方案，再將剩余的原料進(jìn)行優(yōu)化組合。由于長(zhǎng)度長(zhǎng)的原料可以降級(jí)處理，長(zhǎng)度短的卻不能升級(jí)，所以先將借用規(guī)格2的原料來(lái)補(bǔ)充規(guī)格1剩下的余料捆扎出最多的成品，如果不夠再向規(guī)格3借用。類似地，如果規(guī)格2借用后還有剩余就借用規(guī)格3的余料進(jìn)行優(yōu)化捆扎。如果最后只剩規(guī)格1的余料，那這些余料將無(wú)法再組

11、合，組裝結(jié)束；如果最后只剩規(guī)格2的余料，將其全部降級(jí)成規(guī)格1進(jìn)行捆扎；如果最后只剩規(guī)格3的余料，將其全部降級(jí)成規(guī)格2進(jìn)行捆扎。最后再結(jié)合前面得出的，得出成品的最多捆數(shù)。各規(guī)格優(yōu)化求解后的剩余量可降級(jí)使用，如下示意圖：規(guī)格1規(guī)格3規(guī)格2剩余量將規(guī)格1中余量補(bǔ)齊剩余量將規(guī)格2中余量補(bǔ)齊剩余量將規(guī)格1中余量補(bǔ)齊六、實(shí)例運(yùn)算用maple編程（對(duì)規(guī)格1編程見(jiàn)附錄一）對(duì)天然腸衣的三種規(guī)格分別進(jìn)行最優(yōu)化求解,在編程時(shí)，將最短長(zhǎng)度最長(zhǎng)的的成品首先進(jìn)行運(yùn)算，使得方案滿足最短長(zhǎng)度最長(zhǎng)的成品越多越好的條件。求得：第1種規(guī)格：最優(yōu)化捆數(shù)；剩余原料根數(shù)；maple運(yùn)行時(shí)間為439.5秒；第2種規(guī)格：最優(yōu)化捆數(shù)；剩余原料

12、根數(shù)；maple運(yùn)行時(shí)間為232.8秒；第3種規(guī)格：最優(yōu)化捆數(shù)；剩余原料根數(shù)；maple運(yùn)行時(shí)間為61.2秒；規(guī)格1剩余12根要補(bǔ)成一捆成品需在規(guī)格2剩余的145根里拿7根，規(guī)格3剩余49根，所以要從規(guī)格3里拿出49根補(bǔ)到規(guī)格2，現(xiàn)在規(guī)格2里的總根數(shù)為145-7=138根，余5，所以規(guī)格2里的剩余原料為5根不能進(jìn)行生產(chǎn)。綜上所述，得到的成品數(shù)捆，總的運(yùn)行時(shí)間分鐘。表一為按第三種規(guī)格生產(chǎn)的搭配方案，表二為第二種生產(chǎn)的搭配方案，表三為第三種生產(chǎn)的搭配方案。根據(jù)此原理搭配方案，工人可根據(jù)此方案“照方抓藥”進(jìn)行生產(chǎn)。（表格奇數(shù)行表示原料的根數(shù)，偶數(shù)行表示原料搭配方案）表一表二表三七、模型評(píng)價(jià)與改進(jìn)本論

13、文所建立的數(shù)學(xué)模型有成熟的理論基礎(chǔ)，操作較簡(jiǎn)單。針對(duì)條件約束中生產(chǎn)方案的時(shí)間不能超過(guò)30分鐘的問(wèn)題，我們?cè)趯?duì)表一、表二中實(shí)際數(shù)據(jù)進(jìn)行求解過(guò)程中，模擬了本次產(chǎn)生方案的時(shí)間。maple運(yùn)行時(shí)間為12.225分鐘，手工輸入數(shù)據(jù)花費(fèi)了5分鐘，分配搭配方案用了5分鐘，共計(jì)22.225分鐘，所以在30分鐘之內(nèi)該方案可行，符合保持天然腸衣新鮮的要求。該模型簡(jiǎn)單易行，運(yùn)行時(shí)間短，可推廣到其他需要短時(shí)間內(nèi)得到搭配方案的實(shí)例中。該模型中沒(méi)有考慮降級(jí)使用的腸衣是否能被切割的問(wèn)題，如果可以進(jìn)行合理切割，那么總捆數(shù)將會(huì)變大。八、參考文獻(xiàn) 1、羅榮桂，新編運(yùn)籌學(xué)題解，武漢，華中科技大學(xué)出版社，2002年。附錄一>

14、reatrat:k1:=43,59,39,41,27,28,34,21:k1:for nn from 7 to 20 do#nn:=8:num:=0:nn1:=nn:nn2:=nn:nn3:=nn:nn4:=nn:nn5:=nn:nn6:=nn:nn7:=nn:nn8:=nn:k1:=43,59,39,41,27,28,34,21:for i from 0 to nn1 do if(k11>nn) then nn1:=nn: elif(k11<nn) then nn1:=k11: elif(k11=0) then nn1:=0: end if: for j from 0 to nn

15、2 do if(k12>nn) then nn2:=nn: elif(k12<nn) then nn2:=k12: elif(k12=0) then nn2:=0: end if: for k from 0 to nn3 do if(k13>nn) then nn3:=nn: elif(k13<nn) then nn3:=k13: elif(k13=0) then nn3:=0: end if: for l from 0 to nn4 do if(k14>nn) then nn4:=nn: elif(k14<nn) then nn4:=k14: elif(k

16、14=0) then nn4:=0: end if: for m from 0 to nn5 do if(k15>nn) then nn5:=nn: elif(k15<nn) then nn5:=k15: elif(k15=0) then nn5:=0: end if: for n from 0 to nn6 do if(k16>nn) then nn6:=nn: elif(k16<nn) then nn6:=k16: elif(k16=0) then nn6:=0: end if: for o from 0 to nn7 do if(k17>nn) then n

17、n7:=nn: elif(k17<nn) then nn7:=k17: elif(k17=0) then nn7:=0: end if: for p from 0 to nn8 do if(k18>nn) then nn8:=nn: elif(k18<nn) then nn8:=k18: elif(k18=0) then nn8:=0: end if:if(i+j+k+l+m+n+o+p=20) and (3*i+3.5*j+4*k+4.5*l+5*m+5.5*n+6*o+6.5*p=89 or 3*i+3.5*j+4*k+4.5*l+5*m+5.5*n+6*o+6.5*p=88.5 or 3*i+3.5*j+4*k+4.5*l+5*m+5.5*n+6*o+6.5*p=89.5) and k11-i>=0 and k12-j>=0 and k13-k>=0 and k14-l>=0 and k15-m>=0 and k16-n>=0 and k17-o>=0 and k18-p>=0) then p