cumcm2011D-陸立強(qiáng)-天然腸衣搭配優(yōu)化問題的模型-數(shù)模講座27

天然腸衣搭配優(yōu)化問題的模型和計算陸立強(qiáng)復(fù)旦大學(xué)數(shù)學(xué)科學(xué)學(xué)院問題的背景天然腸衣（以下簡稱：腸衣）指的是家畜的大、小腸經(jīng)刮制而成的畜產(chǎn)品，主要用于香腸、灌腸等食品的外衣。中國加工腸衣歷史悠久，產(chǎn)量占世界總產(chǎn)量的三分之一，其中約80%出口，年出口量達(dá)30多萬桶我國現(xiàn)有腸衣出口注冊企業(yè)200家左右，其中對歐盟注冊的就有119家左右。近幾年，國內(nèi)市場對腸衣的需求也呈遞增趨勢，機(jī)會越來越多，競爭也更加激烈。問題的背景傳統(tǒng)腸衣加工工藝清洗整理捆扎丈量搭配腸衣加工主要依靠人工，其中捆扎環(huán)節(jié)要求工人眼明手快，人力成本高原料長短不一成品中腸衣的總長度和總根數(shù)固定問題的背景作為一種食品，不允許將剩余的原材料留作以后使用，因此對于原料的使用率有比較高的要求。人工搭配一般不作整體考慮，只是憑經(jīng)驗和簡單的計算判斷是否可以搭配成一捆成品，無法保證原材料的充分利用。問題的提出腸衣加工企業(yè)希望開發(fā)一套計算機(jī)軟件，只需一線工人將測量所得原料數(shù)據(jù)輸入電腦，就能自動生成經(jīng)過優(yōu)化后的滿足成品規(guī)格要求的搭配方案，這樣既可以減少勞動強(qiáng)度、又能提高原料使用率。問題的提出原料信息：企業(yè)的測量以0.5米為一檔，如：3.1-3.5米按3米計算，3.6米-4米按3.5米計算，其余的依此類推；成品描述：一般分成三種規(guī)格每種規(guī)格用（最短原料長度，最長原料長度，原料根數(shù)，總長度）加以描述問題的提出目標(biāo)對于給定的一批原料，裝出的成品捆數(shù)越多，方案越好。對于成品捆數(shù)相同的方案，最短長度最長的成品越多，方案越好。要在30分鐘內(nèi)產(chǎn)生方案。問題的提出條件總長度允許誤差范圍為[-0.5，0.5]，總根數(shù)允許誤差范圍為[-1，0]。剩余原料可以降級使用。問題的分析目標(biāo)2是難點最小最大問題解決難度高和目標(biāo)1可能是相互矛盾的辦法把成品規(guī)格分成大、中、小三擋，其實質(zhì)是將“最短長度最長的成品最多”的要求轉(zhuǎn)化為“最短長度在某個值以上的成品最多”將一個從理論上完美但難以實現(xiàn)的最優(yōu)目標(biāo)轉(zhuǎn)化為可行的優(yōu)化目標(biāo)。問題的分析受目標(biāo)2的限制，無法依據(jù)目標(biāo)1建立關(guān)于全部原料的優(yōu)化裝配模型辦法結(jié)合條件1按照三種不同規(guī)格分步進(jìn)行優(yōu)化。結(jié)合條件2，擴(kuò)大每種規(guī)格最大長度的上限，提高原料使用率。問題的分析總體方案根據(jù)大規(guī)格要求，求最優(yōu)解；將第1步優(yōu)化后多余的原料納入中規(guī)格，求最優(yōu)解；將第2步優(yōu)化后多余的原料納入小規(guī)格求最優(yōu)解。如果多余的原料總長小于88.5米或者接近于理論最優(yōu)值，則優(yōu)化成功。模型一搭配方式模型記號：

：材料的最短長度

：材料的最大長度

：材料根數(shù)

：成品總長度。

種不同長度的材料：各種材料的長度

：材料根數(shù)

：某種搭配方式中各檔材料的根數(shù)模型一搭配方式模型模型上述不等式組的解表示所有可能的搭配方式

模型一最優(yōu)搭配模型記號：不等式組解的個數(shù)為M，第j個解(第j種搭配方式)為(a1j,x2j,…,xNj)T(j=1,…,M)搭配方案表示為(x1,x2,…,xM)xj表示第j種搭配方式對應(yīng)的捆數(shù)(j=1,…,M，模型一最優(yōu)搭配模型模型：約束條件目標(biāo)

模型一求解：搭配方式模型自編程序多重循環(huán)簡單循環(huán)層次不變遞推方式循環(huán)層次可變

復(fù)雜模型一求解：最優(yōu)搭配模型LINGO求解model:sets:rows/1..2862/:x;cols/1..23/:y;table(rows,cols):A;endsetsmax=@sum(rows(i):x(i));@for(cols(j):@sum(rows(i):A(i,j)*x(i))<=y(j));@for(rows(i):@gin(x(i)));end模型一求解：最優(yōu)搭配模型結(jié)果分析大規(guī)格：捆扎方式=2862種，最多捆數(shù)=137，

原料長度捆數(shù)1414.51515.51616.51717.51818.51919.52020.52121.52222.52323.52424.52525.5搭配方式110000000001110000000000410001000101000010000000011000011000000200000000002100001000020100000000000710000001011100000000000080100000110110000000000001501000000040000000000000010剩余18米一根模型一求解：最優(yōu)搭配模型結(jié)果分析中規(guī)格：M=19635種，最優(yōu)捆數(shù)=37捆

原料長度捆數(shù)77.588.599.51010.51111.51212.51313.518捆扎方式0011000030003002001100000303000200103000000013030010004000000301001000012040000400021000002201020001100202000205000102001004000110000400003000011000010040003000100000040110020040001001020220001長度77.589.51313.5根數(shù)24248111模型一求解：最優(yōu)搭配模型結(jié)果分析小規(guī)格：只考慮等式約束，M接近500萬思路：減少搜索空間的維數(shù)代價：近似最優(yōu)解方法一：M個搭配方式中選取LINGGO所允許的最大個數(shù)結(jié)果：M=24564種，最優(yōu)捆數(shù)=16。模型一求解：最優(yōu)搭配模型結(jié)果分析

原料長度捆數(shù)33.544.555.566.577.589.51313.5搭配方式401144101300101344102040011001243040041110001232420043000001231023403110002137013201010011072330310100003043811110010003040008016100001014100420800001001100705600001長度33.55.57根數(shù)27121模型二思路：模仿人工搭配方式，將最優(yōu)捆數(shù)和搭配方式一起作為優(yōu)化變量進(jìn)行求解方法：先估計出成品捆數(shù)上限，再求出可能的搭配方式；直接求出最優(yōu)捆數(shù)和搭配方式。模型一搭配方式模型記號：

：材料的最短長度

：材料的最大長度

：材料根數(shù)

：成品總長度。

種不同長度的材料：各種材料的長度

：材料根數(shù)

：成品中各檔材料的使用總數(shù)模型二捆數(shù)上限模型模型：模型二搭配方式模型2設(shè)：根據(jù)上限模型求得成品捆數(shù)的上限為M0

設(shè)：第i捆成品中第j種材料的根數(shù)為xij

(i=1,…,M0,j=1,…,N)模型二聯(lián)合優(yōu)化模型設(shè)：成品捆數(shù)為M

設(shè)：第i捆成品中第j種材料的根數(shù)為xij (i=1,…,M,j=1,…,N)maxM模型二分析搭配方式模型2的變量個數(shù)為M0*N，比搭配方案優(yōu)化模型的變量個數(shù)M一般要小得多，不會發(fā)生因為太大而無法優(yōu)化的情況。但模型沒有目標(biāo)函數(shù)，所以每次只能得到局部最優(yōu)，而非整體最優(yōu)。聯(lián)合優(yōu)化模型可以直接通過LINGO求解，但因為第一和第三兩個約束條件的求和項數(shù)也是一個優(yōu)化變量，因此它是一個非標(biāo)準(zhǔn)的整數(shù)規(guī)劃問題。使用LINGO每次只能得到一個局部最優(yōu)。模型二分析以上兩種模型求搭配方案，一次優(yōu)化只能得到一種搭配方式的最多捆數(shù)。為了得到全部材料的搭配，需要修改剩余原料數(shù)據(jù)，再次優(yōu)化，如此逐步進(jìn)行，直到剩余材料無法成捆為止。人工干預(yù)較多，一般不能保證在30分鐘內(nèi)得到搭配方案。模型一對問題的理解比較徹底，是一個標(biāo)準(zhǔn)的整數(shù)規(guī)劃模型，理論上可以得到真正的最優(yōu)解只要編程得當(dāng)，基本不需要人工干預(yù)，符合企業(yè)的最終要求?？偨Y(jié)問題可以表達(dá)為數(shù)學(xué)規(guī)劃問題，對于接受過數(shù)學(xué)建模訓(xùn)練的大學(xué)生而言應(yīng)該不是一個難題。但是，實際情況沒有想象的那樣樂觀?！澳c衣搭配優(yōu)化問題”是一個源于中國的“土”問題，幾乎得不到任何有用的資料，許多參賽同學(xué)因此心存怯意，不敢嘗試。也有一些同學(xué)感覺它和經(jīng)典的“鋼材切割問題”非常相像，后者是化整為零，前者是集零成整，但