【文章內(nèi)容簡介】 Inv。 ENDSETS 優(yōu)化建模 ! 目標(biāo)函數(shù) 。 [OBJ] Min = sum(PXT(i,t): setup(i)*Y(i,t) + hold(i)*Inv(i,t) )。 ! 物流平衡方程 。 FOR( PXT(i, t) | t NE 1 : [Bal] Inv(i,t1)+X(i,t)Inv(i,t) = Demand(i, t) + SUM( USES(i,j): Req(i,j)*X(j,t)) )。 FOR( PXT(i, t) | t eq 1 : [Ba0] X(i,t)Inv(i,t) = Demand(i, t) + SUM( USES(i,j): Req(i,j)*X(j,t)) )。 ! 能力約束 。 FOR( TIME(t): [Cap] SUM( PART(i): A(i)*X(i,t) ) Capacity(t) )。 優(yōu)化建模 ! 其他約束 。 M = 25000。 FOR( PXT(i,t): X(i,t) = M*Y(i,t))。 FOR( PXT: BIN(Y) )。 DATA: Demand = FILE( 39。39。)。 Capacity = FILE( 39。39。)。 Setup = FILE( 39。39。)。 Hold = FILE( 39。39。)。 A = FILE( 39。39。)。 Req = FILE( 39。39。)。 ENDDATA END 注意：由于本例有 42個 01變量，LINGO演示版是無法求解的 優(yōu)化建模 表 52 生產(chǎn)計劃的最后結(jié)果 周次 1 2 3 4 5 6 A的產(chǎn)量 40 100 100 B的產(chǎn)量 200 1000 C的產(chǎn)量 1055 625 D的產(chǎn)量 1800 9000 E的產(chǎn)量 2200 11000 F的產(chǎn)量 13715 8125 G的產(chǎn)量 15825 9375 LINDO求解 : 得到最優(yōu)目標(biāo)函數(shù)值為 9245, 結(jié)果如下： 優(yōu)化建模 167。 下料問題 優(yōu)化建模 167。 下料問題 生產(chǎn)中常會遇到通過切割、剪裁、沖壓等手段，將原材料加工成所需大小這種工藝過程，稱為原料下料（ cutting stock）問題。按照進(jìn)一步的工藝要求，確定下料方案，使用料最省，或利潤最大，是典型的優(yōu)化問題。本節(jié)通過兩個實例討論用數(shù)學(xué)規(guī)劃模型解決這類問題的方法。 優(yōu)化建模 167。 例 某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出。從鋼管廠進(jìn)貨時得到的原料鋼管都是 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)如何下料最節(jié)省？ 優(yōu)化建模 問題 1）的求解 問題分析 首先，應(yīng)當(dāng)確定哪些切割模式是可行的。所謂一個切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。例如，我們可以將 19米長的鋼管切割成 3根 4米長的鋼管，余料為 7米。顯然，可行的切割模式是很多的。 其次，應(yīng)當(dāng)確定哪些切割模式是合理的。通常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。在這種合理性假設(shè)下，切割模式一共有 7種，如表 53所示。 優(yōu)化建模 表 53 鋼管下料的合理切割模式 4米鋼管根數(shù) 6米鋼管根數(shù) 8米鋼管根數(shù) 余料（米） 模式 1 4 0 0 3 模式 2 3 1 0 1 模式 3 2 0 1 3 模式 4 1 2 0 3 模式 5 1 1 1 1 模式 6 0 3 0 1 模式 7 0 0 2 3 優(yōu)化建模 問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少根原料鋼管，最為節(jié)省。而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)，一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最少。下面將對這兩個目標(biāo)分別討論。 優(yōu)化建模 模型建立 決策變量 用 xi 表示按照第 i種模式（ i=1, 2, …, 7 ）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。 決策目標(biāo) 以切割后剩余的總余料量最小為目標(biāo)，則由表 1可得 76543211 3333 xxxxxxxZMin ??????? (32) 以切割原料鋼管的總根數(shù)最少為目標(biāo)，則有 76543212 xxxxxxxZMin ??????? (33) 下面分別在這兩種目標(biāo)下求解。 優(yōu)化建模 約束條件 為滿足客戶的需求，按照表 1應(yīng)有 50234 54321 ????? xxxxx 2032 6542 ???? xxxx 152 753 ??? xxx 優(yōu)化建模 模型求解 1. 將（ 32），（ 34） ~（ 36）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入 LINDO如下： Title 鋼管下料 最小化余量 Min 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7 . 4x1 + 3x2 + 2x3 + x4 + x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15 end gin 7 優(yōu)化建模 求解可以得到最優(yōu)解如下： OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X1 X2 X3 X4 X5 X6 X7 優(yōu)化建模 即按照模式 2切割 12根原料鋼管，按照模式 5切割 15根原料鋼管，共 27根，總余料量為 27米。顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式 2和 5的余料為 1米），這會導(dǎo)致切割原料鋼管的總根數(shù)較多。 優(yōu)化建模 2. 將（ 33） ~（ 36）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入 LINDO： Title 鋼管下料 最小化鋼管根數(shù) Min x1 + x2 + x3 + x4 + x5 + x6 + x7 . 4x1 + 3x2 + 2x3 + x4 + x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15 end gin 7 優(yōu)化建模 求解，可以得到最優(yōu)解如下： OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X1 X2 X3 X4 X5 X6 X7 優(yōu)化建模 即按照模式 2切割 15根原料鋼管，按模式 5切割 5根，按模式 7切割 5根，共 27根，可算出總余料量為 35米。與上面得到的結(jié)果相比，總余料量增加了 8米，但是所用的原料鋼管的總根數(shù)減少了 2根。在余料沒有什么用途的情況下，通常選擇總根數(shù)最少為目標(biāo)。 優(yōu)化建模 問題 2）的求解 問題分析 按照解問題 1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格增加到4種，所以枚舉法的工作量較大。下面介紹的整數(shù)非線性規(guī)劃模型，可以同時確定切割模式和切割計劃，是帶有普遍性的方法。 同 1）類似，一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸（本題中為 4米），切割計劃中只使用合理的切割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于 3米。此外，這里我們僅選擇總根數(shù)最少為目標(biāo)進(jìn)行求解。 優(yōu)化建模 模型建立 決策變量 由于不同切割模式不能超過 3種，可以用 xi 表示按照第 i種模式（ i=1, 2, 3）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。 設(shè) 所使用的第 i種切割模式下每根原料鋼管生產(chǎn) 4米長、 5米長、 6米長和 8米長的鋼管數(shù)量分別為 r1i, r2i, r3i, r4i（ 非負(fù)整數(shù) ）。 決策目標(biāo) 以切割原料鋼管的總根數(shù)最少為目標(biāo)，即目標(biāo)為 321 xxxMin ??（ 37） 優(yōu)化建模 約束條件 為滿足客戶的需求，應(yīng)有 50313212111 ??? xrxrxr(38) 10323222121 ??? xrxrxr 20333232131 xrxrxr 15343242141 ???(39) (40) (41) 優(yōu)化建模 每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過 19米，也不能少于 16米（余量不能大于 3米），于是 19865416 41312111 ????? rrrr(42) 19865416 42322212 ????? rrrr(43) 19865416 43332313 ????? rrrr(44) 優(yōu)化建模 模型求解 （ 37） ~（ 44）構(gòu)成這個問題的優(yōu)化模型。由于在（ 38） ~（ 41）式中出現(xiàn)了決策變量的乘積，所以這是一個整數(shù)非線性規(guī)劃模型，雖然用 LINGO軟件可以直接求解，但我們發(fā)現(xiàn)在較低版本的 LINGO軟件中需要運行很長時間也難以得到最優(yōu)解。為了減少運行時間，可以增加一些顯然的約束條件，從而縮小可行解的搜索范圍。 例如，由于 3種切割模式的排列順序是無關(guān)緊要的，所以不妨增加以下約束： 321 xxx ??（ 45） 優(yōu)化建模 又例如，我們注意到所需原料鋼管的總根數(shù)有著明顯的上界和下界。首先，無論如何，原料鋼管的總根數(shù)不可能少于 2619 158206105504 ??????? ???????（根） 其次，考慮一種非常特殊的生產(chǎn)計劃：第一種切割模式下只生產(chǎn) 4米鋼管，一根原料鋼管切割成 4根 4米鋼管，為滿足 50根 4米鋼管的需求，需要 13根原料鋼管；第二種切割模式下只生產(chǎn) 5米、 6米鋼管，一根原料鋼管切割成 1根 5米鋼管和 2根 6米鋼管，為滿足 10根 5米和 20根 6米鋼管的需求，需要 10根原料鋼管； 優(yōu)化建模 第三種切割模式下只生產(chǎn) 8米鋼管，一根原料鋼管切割成 2根 8米鋼管，為滿足 15根 8米鋼管的需求，需要 8根原料鋼管。于是滿足要求的這種生產(chǎn)計劃共需 13+10+8=31根原料鋼管，這就得到了最優(yōu)解的一個上界。所以可增加以下約束： 3126 321 ???? xxx(46) 將（ 37） ~（ 46）構(gòu)成的模型輸入 LINGO如下： 優(yōu)化建模 將（ 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 =19。 4*r12+5*r22+6*r32+8*r42 =19。 4*r13+5*r23+6*r33+8*r43 =19。 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 = 31。 x1=x2。 x2=x3。