數(shù)學(xué)建模下料問題ppt課件

.,下料問題,生產(chǎn)中常會(huì)遇到通過切割、剪裁、沖壓等手段，將原材料加工成所需大小這種工藝過程，稱為原料下料（cuttingstock）問題。按照進(jìn)一步的工藝要求，確定下料方案，使用料最省，或利潤(rùn)最大,.,鋼管下料問題,某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出。從鋼管廠進(jìn)貨時(shí)得到的原料鋼管都是19米長(zhǎng)。1)現(xiàn)有一客戶需要50根4米長(zhǎng)、20根6米長(zhǎng)和15根8米長(zhǎng)的鋼管。應(yīng)如何下料最節(jié)?。?)零售商如果采用的不同切割模式太多，將會(huì)導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要1）中的三種鋼管外，還需要10根5米長(zhǎng)的鋼管。應(yīng)如何下料最節(jié)??？,.,問題1）的求解,問題分析首先，應(yīng)當(dāng)確定哪些切割模式是可行的。所謂一個(gè)切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。例如，我們可以將19米長(zhǎng)的鋼管切割成3根4米長(zhǎng)的鋼管，余料為7米顯然，可行的切割模式是很多的。,其次，應(yīng)當(dāng)確定哪些切割模式是合理的。通常假設(shè)一個(gè)合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。在這種合理性假設(shè)下，切割模式一共有7種，如表5-3所示。,.,表5-3鋼管下料的合理切割模式,.,問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少根原料鋼管，最為節(jié)省。而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)，一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最少。下面將對(duì)這兩個(gè)目標(biāo)分別討論。,.,模型建立決策變量用xi表示按照第i種模式（i=1,2,7）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。決策目標(biāo)以切割后剩余的總余料量最小為目標(biāo)，則由表1可得,(32),以切割原料鋼管的總根數(shù)最少為目標(biāo)，則有,(33),下面分別在這兩種目標(biāo)下求解。,.,約束條件為滿足客戶的需求，按照表1應(yīng)有,.,模型求解,1.將（32），（34）（36）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO如下：,Title鋼管下料-最小化余量,Min3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5=50 x2+2x4+x5+3x6=20 x3+x5+2x7=15endgin7,.,Min=3*x1+x2+3*x3+3*x4+x5+x6+3*x7;4*x1+3*x2+2*x3+x4+x5=50;x2+2*x4+x5+3*x6=20;x3+x5+2*x7=15;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);,.,求解可以得到最優(yōu)解如下：,OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000,.,即按照模式2切割12根原料鋼管，按照模式5切割15根原料鋼管，共27根，總余料量為27米。顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式2和5的余料為1米），這會(huì)導(dǎo)致切割原料鋼管的總根數(shù)較多。,.,2.將（33）（36）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO：,Title鋼管下料-最小化鋼管根數(shù)Minx1+x2+x3+x4+x5+x6+x7s.t.4x1+3x2+2x3+x4+x5=50 x2+2x4+x5+3x6=20 x3+x5+2x7=15endgin7,.,求解，可以得到最優(yōu)解如下：,OBJECTIVEFUNCTIONVALUE1)25.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.000000,.,即按照模式2切割15根原料鋼管，按模式5切割5根，按模式7切割5根，共27根，可算出總余料量為35米。與上面得到的結(jié)果相比，總余料量增加了8米，但是所用的原料鋼管的總根數(shù)減少了2根。在余料沒有什么用途的情況下，通常選擇總根數(shù)最少為目標(biāo)。,.,問題2）的求解,問題分析按照解問題1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格增加到4種，所以枚舉法的工作量較大。下面介紹的整數(shù)非線性規(guī)劃模型，可以同時(shí)確定切割模式和切割計(jì)劃，是帶有普遍性的方法。,同1）類似，一個(gè)合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸（本題中為4米），切割計(jì)劃中只使用合理的切割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于3米。此外，這里我們僅選擇總根數(shù)最少為目標(biāo)進(jìn)行求解。,.,模型建立,決策變量由于不同切割模式不能超過3種，可以用xi表示按照第i種模式（i=1,2,3）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。設(shè)所使用的第i種切割模式下每根原料鋼管生產(chǎn)4米長(zhǎng)、5米長(zhǎng)、6米長(zhǎng)和8米長(zhǎng)的鋼管數(shù)量分別為r1i,r2i,r3i,r4i（非負(fù)整數(shù)）。,決策目標(biāo)以切割原料鋼管的總根數(shù)最少為目標(biāo)，即目標(biāo)為,（37）,.,約束條件為滿足客戶的需求，應(yīng)有,(38),(39),(40),(41),.,每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過19米，也不能少于16米（余量不能大于3米），于是,(42),(43),(44),.,模型求解,（37）（44）構(gòu)成這個(gè)問題的優(yōu)化模型。由于在（38）（41）式中出現(xiàn)了決策變量的乘積，所以這是一個(gè)整數(shù)非線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但我們發(fā)現(xiàn)在較低版本的LINGO軟件中需要運(yùn)行很長(zhǎng)時(shí)間也難以得到最優(yōu)解。為了減少運(yùn)行時(shí)間，可以增加一些顯然的約束條件，從而縮小可行解的搜索范圍。,例如，由于3種切割模式的排列順序是無關(guān)緊要的，所以不妨增加以下約束：,（45）,.,又例如，我們注意到所需原料鋼管的總根數(shù)有著明顯的上界和下界。首先，無論如何，原料鋼管的總根數(shù)不可能少于,（根）,其次，考慮一種非常特殊的生產(chǎn)計(jì)劃：第一種切割模式下只生產(chǎn)4米鋼管，一根原料鋼管切割成4根4米鋼管，為滿足50根4米鋼管的需求，需要13根原料鋼管；第二種切割模式下只生產(chǎn)5米、6米鋼管，一根原料鋼管切割成1根5米鋼管和2根6米鋼管，為滿足10根5米和20根6米鋼管的需求，需要10根原料鋼管；,.,第三種切割模式下只生產(chǎn)8米鋼管，一根原料鋼管切割成2根8米鋼管，為滿足15根8米鋼管的需求，需要8根原料鋼管。于是滿足要求的這種生產(chǎn)計(jì)劃共需13+10+8=31根原料鋼管，這就得到了最優(yōu)解的一個(gè)上界。所以可增加以下約束：,(46),將（37）（46）構(gòu)成的模型輸入LINGO如下：,.,將（37）（46）構(gòu)成的模型輸入LINGO如下：,model:Title鋼管下料-最小化鋼管根數(shù)的LINGO模型;min=x1+x2+x3;x1*r11+x2*r12+x3*r13=50;x1*r21+x2*r22+x3*r23=10;x1*r31+x2*r32+x3*r33=20;x1*r41+x2*r42+x3*r43=15;4*r11+5*r21+6*r31+8*r41=16;4*r12+5*r22+6*r32+8*r42=16;4*r13+5*r23+6*r33+8*r43=16;,x1+x2+x3=26;x1+x2+x3=x2;x2=x3;gin(x1);gin(x2);gin(x3);gin(r11);gin(r12);gin(r13);gin(r21);gin(r22);gin(r23);gin(r31);gin(r32);gin(r33);gin(r41);gin(r42);gin(r43);end,.,經(jīng)過LINGO求解，得到輸出如下：Localoptimalsolutionfound.Objectivevalue:28.00000Extendedsolversteps:72Totalsolveriterations:3404ModelTitle:鋼管下料-最小化鋼管根數(shù)的LINGO模型,.,VariableValueReducedCostX110.000000.000000X210.000000.000000X38.0000000.000000R112.0000000.000000R123.0000000.000000R130.0000000.000000R211.0000000.000000R220.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000,.,即按照模式1、2、3分別切割10、10、8根原料鋼管，使用原料鋼管總根數(shù)為28根。第一種切割模式下一根原料鋼管切割成3根4米鋼管和1根6米鋼管；第二種切割模式下一根原料鋼管切割成2根4米鋼管、1根5米鋼管和1根6米鋼管；第三種切割模式下一根原料鋼管切割成2根8米鋼管。,如果充分利用LINGO建模語言的能力，使用集合和屬性的概念，可以編寫以下LINGO程序，這種方法更具有一般的通用性，并有利于輸入更大規(guī)模的下料問題的優(yōu)化模型：,.,model:Title鋼管下料-最小化鋼管根數(shù)的LINGO模型;SETS:NEEDS/1.4/:LENGTH,NUM;!定義基本集合NEEDS及其屬性LENGTH,NUM;CUTS/1.3/:X;!定義基本集合CUTS及其屬性X;PATTERNS(NEEDS,CUTS):R;!定義派生集合PATTERNS（這是一個(gè)稠密集合）及其屬性R;ENDSETSDATA:LENGTH=4568;NUM=50102015;CAPACITY=19;ENDDATAmin=SUM(CUTS(I):X(I);,.,!目標(biāo)函數(shù);FOR(NEEDS(I):SUM(CUTS(J):X(J)*R(I,J