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

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

：材料的最短長(zhǎng)度

：材料的最大長(zhǎng)度

：材料根數(shù)

：成品總長(zhǎng)度。

種不同長(zhǎng)度的材料：各種材料的長(zhǎng)度

：材料根數(shù)

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

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

模型一求解：搭配方式模型自編程序多重循環(huán)簡(jiǎ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，

原料長(zhǎng)度捆數(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捆

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

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

：材料的最短長(zhǎng)度

：材料的最大長(zhǎng)度

：材料根數(shù)

：成品總長(zhǎng)度。

種不同長(zhǎng)度的材料：各種材料的長(zhǎng)度

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