1、下料問題,中常會遇到通過切割、剪裁、沖壓等手段，將原材料加工成所需大小這種工藝過程，稱為原料下料（cutting stock）問題。按照進(jìn)一步的工藝要求，確定下料方案，使用料最省，或利潤最大,鋼管下料問題,某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出。從鋼管廠進(jìn)貨時(shí)得到的原料鋼管都是19米長。 1) 現(xiàn)有一客戶需要50根4米長、20根6米長和15根8米長的鋼管。應(yīng)如何下料最節(jié)?。?2) 零售商如果采用的不同切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要1）中的三種鋼管外，還需要10根5米長的鋼管。應(yīng)

2、如何下料最節(jié)??？,問題1）的求解,問題分析 首先，應(yīng)當(dāng)確定哪些切割模式是可行的。所謂一個切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。例如，我們可以將19米長的鋼管切割成3根4米長的鋼管，余料為7米顯然，可行的切割模式是很多的。,其次，應(yīng)當(dāng)確定哪些切割模式是合理的。通常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。在這種合理性假設(shè)下，切割模式一共有7種，如表5-3所示。,表5-3 鋼管下料的合理切割模式,問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少根原料鋼管，最為節(jié)省。而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)，一是切割后剩余的總余料量最小，二是切割原料鋼

3、管的總根數(shù)最少。下面將對這兩個目標(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 鋼管下料 - 最小化余量,Min 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7 s.t. 4x1 +

4、 3x2 + 2x3 + x4 + x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15 end gin 7,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)解如下：,OBJECTIVE FUN

5、CTION VALUE 1) 27.00000 VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000,即按照模式2切割12根原料鋼管，按照模式5切割15根原料鋼管，共27根，總余料量為27米。顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式2和5的余料為1米），這會導(dǎo)致切割原

6、料鋼管的總根數(shù)較多。,2. 將（33）（36）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO：,Title 鋼管下料 - 最小化鋼管根數(shù) Min x1 + x2 + x3 + x4 + x5 + x6 + x7 s.t. 4x1 + 3x2 + 2x3 + x4 + x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15 end gin 7,求解，可以得到最優(yōu)解如下：,OBJECTIVE FUNCTION VALUE 1) 25.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X

7、2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000,即按照模式2切割15根原料鋼管，按模式5切割5根，按模式7切割5根，共27根，可算出總余料量為35米。與上面得到的結(jié)果相比，總余料量增加了8米，但是所用的原料鋼管的總根數(shù)減少了2根。在余料沒有什么用途的情況下，通常選擇總根數(shù)最少為目標(biāo)。,問題2）的求解,問題分析 按照解問題1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)

8、格增加到4種，所以枚舉法的工作量較大。下面介紹的整數(shù)非線性規(guī)劃模型，可以同時(shí)確定切割模式和切割計(jì)劃，是帶有普遍性的方法。,同1）類似，一個合理的切割模式的余料不應(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米長、5米長、6米長和8米長的鋼管數(shù)量分別為r1

9、i, 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)成這個問題的優(yōu)化模型。由于在（38）（41）式中出現(xiàn)了決策變量的乘積，所以這是一個整數(shù)非線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但我們發(fā)現(xiàn)在較低版本的LINGO軟件中需要運(yùn)行很長時(shí)間也難以得到最優(yōu)解。為了減少運(yùn)行時(shí)間，可以增加一些顯然

10、的約束條件，從而縮小可行解的搜索范圍。,例如，由于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根

11、8米鋼管的需求，需要8根原料鋼管。于是滿足要求的這種生產(chǎn)計(jì)劃共需13+10+8=31根原料鋼管，這就得到了最優(yōu)解的一個上界。所以可增加以下約束：,(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

12、+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求解，得到輸出如下： Local optimal solution found. Obj

13、ective value: 28.00000 Extended solver steps: 72 Total solver iterations: 3404 Model Title: 鋼管下料-最小化鋼管根數(shù)的LINGO模型,Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 0.000000 X3 8.000000 0.000000 R11 2.000000 0.000000 R12 3.000000 0.000000 R13 0.000000 0.000000 R21 1.000000 0.000000 R22 0.00

14、0000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000,即按照模式1、2、3分別切割10、10、8根原料鋼管，使用原料鋼管總根數(shù)為28根。第一種切割模式下一根原料鋼管切割成3根4米鋼管和1根6米鋼管；第二種切割模式下一根原料鋼管切割成2根4米鋼管、1根5米鋼管和1根6米鋼管；第三種切割模式下一根原料鋼管切割成2根8米鋼

15、管。,如果充分利用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（這是一個稠密集合）及其屬性R; ENDSETS DATA: LENGTH=4 5 6 8; NUM=50 10 20 15; CAPACITY=19; ENDDATA min=SUM(CUTS(I): X(I) );,!目標(biāo)函數(shù); FOR(NEEDS(I): SUM(CUTS(J): X(J)*R(I,J) ) NUM(I) ); !滿足需求約束;