數(shù)學(xué)建模-鋼管切割問題

問題某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出，從鋼管廠進(jìn)貨時得到的原料鋼管都是21米的?，F(xiàn)有一客戶需要45根5m，25根7m和20根9m,的鋼管。應(yīng)如何下料最??？零售商如果采用的不同的切割模式太多，將會導(dǎo)致生產(chǎn)過程復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的切割模式不能超過3種。因此，該客戶除需要（1）中的三種鋼管外，還需要15根6m的鋼管。應(yīng)如何下料最節(jié)省。問題（1）的求解問題分析首先，應(yīng)該確定哪些切割模式是可行的。所謂的一個切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。例如：我們將21m的鋼管切割成4根5m的鋼管，余料為1m；或者將21m的鋼管切割成2根5m，1根7m的鋼管，余料是4m。顯然這樣的切割模式很多的。其次，應(yīng)當(dāng)確定哪些切割模式是合理的。通常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或者等于客戶需要的鋼管的最小尺寸。在這種合理的假設(shè)下，切割模式一共有7種，如表所示。5m鋼管根數(shù)7m鋼管根數(shù)9m鋼管根數(shù)余料（m）模式14001模式22104模式32012模式41202模式51110模式60300模式70023問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少原料鋼管，最為節(jié)省。而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)：一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最小。下面將對這兩個目標(biāo)分別討論。模型建立決策變量用xi表示按照第i種模式（i=1,2,…，7）切割的原料鋼管的根數(shù)，顯然他們是非負(fù)整數(shù)的。決策目標(biāo)以切割后剩余的總余料量最小為目標(biāo)，則由表可得MinZ1=x1+4x2+2x3+2x4+3x7（1）以切割原料鋼管的總根數(shù)最少為目標(biāo)，則有MinZ2=x1+x2+x3+x4+x5+x6+x7（2）下面分別在這兩種目標(biāo)下求解。約束條件為了滿足客戶的需要，按照表應(yīng)有4x1+2x2+2x3+x4+x5≥45（3）X2+2x4+x5+3x6≥25（4）X3+x5+2x7≥20（5）模型求解將（1），（3），（4），（5）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO如下：求解可以得到最優(yōu)解如下：即按照模式5切割45根原料鋼管，按照模式6切割9根原料鋼管，共54根。總余料為0。顯然，在總余料最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式5和6的余料為0）。將（2）~（5）構(gòu)成的整體線性規(guī)劃模式（加上整數(shù)約束）輸入LINDO求解，可以得到最優(yōu)解如下：即按照模式1切割6根原料鋼管，按照模式3切割1根原料鋼管，按照模式5切割19根原料鋼管，按照模式6切割2根原料鋼管，可算出總余料量為8m。與上面得到的結(jié)果比，總余料量增加了8m，但是所用的原料鋼管總根數(shù)減少了26根。在余料沒有用途的情況下，選擇總根數(shù)最少為目標(biāo)。問題（2）的求解問題分析按照（1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但是由于需求的鋼管規(guī)格增加到了4種，所以枚舉的工作量較大。下面介紹的整數(shù)非線性規(guī)劃模型，可以同時確定切割模式和切割計劃，是帶有普通性的方法。同（1）類似，一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸5m，切割計劃中只能使用合理的切割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于4m。此外，這里僅選擇總根數(shù)最少為目標(biāo)進(jìn)行求解。模型建立決策變量由于不同切割模式不能超過3種，可以用xi表示按照第i種模式（i=1，2，3）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。設(shè)所使用的第i種切割模式下的每根鋼管生產(chǎn)5m,6m,7m和9m的鋼管數(shù)量分別是r1i,r2i,r3i,r4i.決策目標(biāo)切割原料鋼管的總根數(shù)最少，目標(biāo)為Minx1+x2+x3（6）約束條件為了滿足客戶的需求，應(yīng)該有r11x1+r12x2+r13x3≥45（7）r21x1+r22x2+r23x3≥15（8）r31x1+r32x2+r33x3≥25（9）r41x1+r42x2+r43x3≥20（10）每根原料鋼管的成品量不能超過21m，也不能少于17m，于是17≤5r11+6r21+7r31+9r41≤21（11）17≤5r12+6r22+7r32+9r42≤21（12） 17≤5r13+6r23+7r33+9r43≤21（13）模型求解在（7）~（10）式中出現(xiàn)決策變量的乘積，是個整數(shù)非線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但是運(yùn)行很長時間也難得到最優(yōu)解。為了減少時間，可以增加一些顯然的條件。例如：由于3種切割模式的排列順序是無關(guān)緊要的，所以不妨增加一下約束x1≥x2≥x3(14)又如：所需原料鋼管的總根數(shù)有著明顯的上界和下界。首先，無論如何原料鋼管的總根數(shù)不可能少于[(45×5+5×6+25×7+20×9)/21]+=30根。其次，考慮一種非常特殊的生產(chǎn)計劃：第一種切割模式下只生產(chǎn)5m和6m的鋼管，一根原料鋼管切成3根5m和1根6m的鋼管，為了滿足45根5m和15根6m的鋼管要求，需要15根原料鋼管；第二種切割模式下只生產(chǎn)7m的鋼管，一根原料鋼管可以切割成3根7m的鋼管，為了滿足25根7m的鋼管的要求，需要9根原料鋼管；第三種切割模式下只生產(chǎn)9m的鋼管，一根原料鋼管可以切割成2根9m的鋼管，為了滿足20根鋼管需求，需要10根原料鋼管，這就得到了最優(yōu)解得上界。所以可以增加以下約束30≤x1+x2+x3≤34將（6）~（15）構(gòu)成的模型輸入LINGO如下：經(jīng)過運(yùn)行，得到輸出如