天然腸衣搭配問題

1、承 諾 書我們仔細閱讀了中國大學生數(shù)學建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）：我們的參賽報名號為（如果賽區(qū)設置報名號的話）：所屬學校（請?zhí)顚懲暾娜?/p>

2、參賽隊員 (打印并簽名) ：1. 2. 3.指導教師或指導教師組負責人 (打印并簽名)： 日期：年月日天然腸衣搭配問題摘 要本文主要是對天然腸衣搭配問題進行探討與研究，建立線性規(guī)劃數(shù)學模型，利用編程，得到符合實際的最優(yōu)方案。文章以成品規(guī)格表和原料描述表為參考依據(jù)，采用整數(shù)規(guī)劃，分別從“最大捆數(shù)、最優(yōu)方案和時間限制”三個方面建立優(yōu)化模型，利用編程最優(yōu)求解，最終制作出了一套科學、合理和實用的搭配方案。本文分三步解決問題，具體如下：首先，通過分析題設，按照要求（1）、（3）和（4），建立“最大捆數(shù)”的優(yōu)化模型。根據(jù)文中給出的三種成品規(guī)格，我們建立了三個求最大捆數(shù)的整數(shù)規(guī)劃模型?？紤]到剩余原料可以降級

3、規(guī)格使用，我們采用“倒序”原則，利用編程，先算出第三種規(guī)格的最大捆數(shù)，接著把剩余原料23.5-23.9米的6根和25.5-25.9米的1根降級到第二種規(guī)格搭配使用，以此類推，運行得到三種規(guī)格的最大捆數(shù)，分別為134捆,41捆和16捆。其次，根據(jù)最大捆數(shù)，本文得到兩個具體的搭配方案。方案一是根據(jù)材料使用情況建立最大損失函數(shù)模型，通過編程得到搭配方案（表）。方案二是按照原料的最大利用原則建立優(yōu)化模型，利用編程得到搭配方案（表），按照要求（2），比較兩個方案的剩余原料（表），檔次低的原料越多，搭配方案越好。我們最終選擇方案二。對剩余原料再次替代，得到優(yōu)化方案（表）。最后，考慮到食品保鮮，要求30分鐘

4、內產生方案，而第三規(guī)格原料數(shù)據(jù)太多，給程序運行帶來困難，我們對模型改進。把第三規(guī)格原料分成5個批次（表、），對每個批次分別建模，求出的最大捆數(shù)分別32,32,32,18,19。然后通過編程分別求出各個批次的搭配方案（表、）。最后剩余的5根，利用替代原則，再優(yōu)化1捆，得到最終的搭配方案（表）。關鍵詞： 整數(shù)規(guī)劃 搭配方案 最優(yōu)求解 天然腸衣1 問題重述天然腸衣的制作加工首先要經過清洗整理后被分割成長度不等的小段（原料），然后進入組裝工序。傳統(tǒng)的生產方式就是人工邊丈量原料長度邊心算，將原材料按指定根數(shù)和總長度組裝出成品（捆）。原料按長度分檔，以0.5米為一檔，附表是幾種常見成品的規(guī)格，長度單位為米

5、，表示沒有上限，但實際長度小于米。為了提高生產效率，公司計劃改變組裝工藝，先丈量所有原料，建立一個原料表。附表為某批次原料描述。根據(jù)以上成品和原料描述，設計一個原料搭配方案，工人根據(jù)這個方案“照方抓藥”進行生產。公司對搭配方案有以下具體要求：（1）對于給定的一批原料，裝出的成品捆數(shù)越多越好；（2）對于成品捆數(shù)相同的方案，最短長度最長的成品越多，方案越好；（3）為提高原料使用率，總長度允許有米的誤差，總根數(shù)允許比標準少根；（4）某種規(guī)格對應原料如果出現(xiàn)剩余，可以降級規(guī)格使用。如長度為米的原料可以和長度介于米的進行捆扎，成品屬于米的規(guī)格；（5）為了食品保鮮,要求在分鐘內產生方案。根據(jù)上述問題建立數(shù)

6、學模型，給出求解方法，并對附表、附表給出的實際數(shù)據(jù)進行求解，給出搭配方案。2 問題分析問題中要求根據(jù)成品規(guī)格和原料描述，以及公司對搭配方案的具體要求，設計一個原料的最優(yōu)搭配方案。制作原料的搭配方案，首先要確定最大捆數(shù)。考慮到文中要求（1）裝出的成品捆數(shù)越多越好，因此把三個規(guī)格的最大捆數(shù)作為目標函數(shù)。文中的要求（3）指出總長度可以允許米的誤差，鑒于最大捆數(shù)的要求，把要求（3）作為約束條件對目標函數(shù)進行優(yōu)化。文中（4）要求，如果原料有剩余，可以考慮降級規(guī)格使用。所以，先求第三種規(guī)格的最大捆數(shù)。此規(guī)格中剩余的原料，降級使用，安排到第二種規(guī)格里面，作為新的長度檔，參與第二種規(guī)格的分配。同理，第二種規(guī)格

7、中剩余的原料降級到第一種規(guī)格使用。對建立的目標函數(shù)，根據(jù)題目的約束條件，進行編程，運行得到最大捆數(shù)為191捆。在求出最大捆數(shù)的前提下，通過建立不同的目標函數(shù)得到兩種優(yōu)化模型：一種是按照原料的最大損失函數(shù)建立的優(yōu)化模型，另一種是根據(jù)原料的最大利用原則建立優(yōu)化模型，通過分別編程，得出兩種搭配方案。鑒于文中要求（2）提出：最短長度最長的成品越多，方案越好，我們選擇第二種方案作為最終搭配方案。要求（3）中提出：總長度允許有米誤差、總根數(shù)允許比標準根少一根。在滿足要求（3）的前提下，又把剩余的原料中檔次較高的去替代檔次較低的，使得搭配方案更加合理優(yōu)化，達到了最優(yōu)的搭配效果。根據(jù)第二種方案，利用編程，可以

8、很快的求出原料第一、二規(guī)格的具體搭配方案。但是在求第三種規(guī)格搭配方案時，由于數(shù)據(jù)較多，程序運行會占用很多時間，從而不滿足要求（5）中的食品保鮮，即要求30分鐘內產生方案。本文對搭配方案模型進行改進，采用“化整為零”的思想優(yōu)化模型：把第三規(guī)格原料分成5個批次，對每個批次分別建模，再用進行編程，求出最大捆數(shù)分別32,32,32,18,19。然后通過對每個批次建立最優(yōu)搭配模型，編程分別求出各個批次的搭配方案。最后剩余的5根，利用替代原則，再優(yōu)化1捆，得到最終的搭配方案（表）。3 模型假設（1）假設分割后的腸衣沒有損壞；（2）假設原料的丈量誤差忽略不計；（3）假設原料的分檔無誤；（4）假設腸衣在捆裝的

9、過程中不出現(xiàn)斷裂；（5）假設電腦運行正常；（6）假設在測量長度時不出現(xiàn)重疊；（7）假設工人可以看懂搭配方案；（8）假設腸衣在制作過程中不收縮變形；（9）假設不考慮溫度、濕度等外界因素對腸衣質量的影響；4 符號說明：第一種規(guī)格中的總捆數(shù)：第二種規(guī)格中的總捆數(shù)：第三種規(guī)格中的總捆數(shù)：第一種規(guī)格中的第檔次 ：第二種規(guī)格中的第檔次 ：第二種規(guī)格中的第檔次 ：第三種規(guī)格中得第檔次 ：第三種規(guī)格中的第檔次 ：第一種規(guī)格的第捆中第檔的根數(shù) ：第二種規(guī)格的第捆中第檔的根數(shù) ：第三種規(guī)格的第捆中第檔的根數(shù) 5 模型建立與求解最大捆數(shù)的模型建立與求解根據(jù)附表1,2和公司要求（1），首先建立求最大捆數(shù)的優(yōu)化模型?？?/p>

10、慮原材料分為米、米、米三個規(guī)格，根據(jù)每個規(guī)格求最大捆數(shù)，求和得到原料的總的最大捆數(shù)。要求（4）中提到，剩余原料可以降級使用。因此先求第三規(guī)格的最大捆數(shù)，建立目標函數(shù)：要求（3）為提高原料的使用率，總長度允許有米的誤差，以此約束條件： （5.1.1）第三種規(guī)格中每捆5根，得到另一約束條件： （5.1.2） 每檔的根數(shù)不能超過現(xiàn)有根數(shù)，約束為： （5.1.3）利用軟件進行編程（附錄一）計算，得出第三種規(guī)格中各檔使用根數(shù)（表5-1）和總的最大捆數(shù)捆。檔次使用根數(shù)檔次使用根數(shù)表由表知，第三種規(guī)格中和有剩余。根據(jù)要求中降級使用，把剩余的根數(shù)和降級到第二種規(guī)格進行計算（根據(jù)內置算法編號不能有斷層，所以將和

11、重新編號為和），作為兩個新檔。求第二種規(guī)格最大捆數(shù)，建立目標函數(shù)：約束條件：（5.1.4） （5.1.5） （5.1.6）利用軟件進行編程（附錄二）計算得出第二種規(guī)格各檔使用根數(shù)（表5-2）和總的最大捆數(shù)捆。檔次使用根數(shù)檔次使用根數(shù)表由表得出第二種規(guī)格中、和有剩余，根據(jù)要求可降級使用，把剩余的根數(shù)、和降級到第一種規(guī)格中進行計算。得第一種規(guī)格最大捆數(shù)的目標函數(shù)：約束條件： （5.1.7） （5.1.8） （5.1.9） （5.1.10）利用軟件進行計算（附錄三）得出第一種規(guī)格中各檔使用根數(shù)（表5-3）和總的最大捆數(shù)為捆。檔 次使用根數(shù)表由表得出第一種規(guī)格中、和有剩余,剩余的根數(shù)為、和。選擇最優(yōu)搭

12、配方案在滿足成品捆數(shù)越多越好的情況下，本文得到了兩個具體的搭配方案。方案一是根據(jù)材料使用情況建立最大損失函數(shù)模型，通過編程得到搭配方案。方案二是按照原料的最大利用原則建立優(yōu)化模型，利用編程得到搭配方案。按照要求（2）對于成品捆數(shù)相同的方案，最短長度最長的成品越多，方案越好；就是說兩個方案剩余的原料，檔次低的原料越多，搭配方案越好，所以只需要比較第一種規(guī)格即可。比較方案一和方案二剩余原料的根數(shù)，本文最終選擇方案二。具體建模如下：方案一：通過構建損失函數(shù)，并使得損失函數(shù)值最大（損失的最大也就是賣出的最少但獲得的利潤不變）。根據(jù)提高使用率的要求和給定原料的根數(shù)，采用線性規(guī)劃的方法，建立模型如下：（5

13、.2.1）約束條件為： （5.2.2） （5.2.3）我們用軟件計算，得到結果（附錄四）。經過處理得出表：表方案二：從原料的最大利用的角度來考慮。根據(jù)提高原料使用率的要求和給定的原料根數(shù)，采用線性規(guī)劃的方法，進行模型的建立與求解。具體模型如下： （5.2.4）約束條件為： （5.2.5） （5.2.6）用軟件進行計算，得出結果（附錄五）。然后經過處理得出下表：表根據(jù)要求（2）對于成品捆數(shù)相同的方案，最短長度最長的成品越多，也就是在剩余的根數(shù)里，最短的根數(shù)越多方案就相對越好。由此，比較方案一與方案二相剩余的根數(shù)（表）。檔次3-一剩000000140600二剩03090000072表根據(jù)題目要求對

14、于成品捆數(shù)相同的方案，最短長度最長的成品越多方案越好，所以采用方案二。對方案二剩余原料根據(jù)要求（4）進行替代，得到更好的搭配方案（表）。表應用方案二，可以得到第二中規(guī)格的搭配方案，即以總長度最大為目標函數(shù)，建立模型： （5.2.7）約束條件： （5.2.8） （5.2.9）用軟件進行計算，得出結果（附錄六），然后經過處理得出下表：表根據(jù)第一、二兩種規(guī)格的建模求解過程，可以類推出第三種規(guī)格的優(yōu)化模型。但是由于第三種規(guī)格的數(shù)據(jù)太多，一般計算機運算時間的花費遠遠超過三十分鐘，不滿足文中的要求（5）。為了解決這個問題，提出了改進的最優(yōu)搭配方案。在改進的最優(yōu)模型中，采取分批計算原則，將第三種規(guī)格中所有根

15、數(shù)按檔次不同分成4份，前三份均勻分配，將剩余的放在第四份里（表）。第一份根數(shù)第二份根數(shù)第三份根數(shù)第四份根數(shù)999877787779101010127777101010121111111212121213121212141616161613131325151515181212121399987776444433330002表將第一份的根數(shù)按照中求捆數(shù)的模型進行計算，用軟件將最大捆數(shù)和所用根數(shù)求出。對第四份進行求解時，又因為運行時間過長，我們又將其分成兩組計算（表5-10）。表經過計算分別得出第一批捆，第二批捆，第三批捆，第四批18捆，第五批19捆，最后剩余5根。將上述得到的捆數(shù)，按照中方案二的模

16、型進行計算（附錄七），從而得出方案（表5-11,5-12，5-13）。結果是32捆的搭配方案的運行程序和結果（附錄十）。結果是32捆的搭配方案為：表結果是18捆的搭配方案的運行程序和結果（附錄十一）。結果是18捆的搭配方案為：表結果是19捆的搭配方案的運行程序和結果（附錄十二）。結果是19捆的搭配方案為：表由于捆，與中計算的134捆差一捆，但剩余5根，符合根數(shù)的要求，但不符合長度的要求，考慮總長度有米的誤差允許范圍，所以我們將上述方案進一步優(yōu)化。 剩余的根，用檔次高一級的替代檔次低一級的捆成最后的那一捆，最后得到第三種規(guī)格的捆數(shù)為捆，具體搭配方案見表5-14。表6 模型評價及推廣 本文求解結果使用了大量的圖表，使得結論更為直觀，易于理解。在問題中應用了編程處理數(shù)據(jù)，并對結果進行優(yōu)化。同時考慮原料的利用率，在每捆總長度和