【正文】 年 6 月 23 日 2 基于最優(yōu)化理論的鋼管下料問題 [摘要 ] 本題求解的是鋼管下料問題，是一個整數(shù)線性規(guī)劃的優(yōu)化模型。 問題（ 1）求解如何下料最為節(jié)省，對于如何為最節(jié)省，給出兩個目標(biāo)，一個是剩余總余料最省，另一個是切割原料鋼管總根數(shù)最少。 兩個目標(biāo)雖然不同，但是最優(yōu)解中所用的切割模式和切割鋼管根數(shù)是一樣的，因此兩個模型具有等價性?？傎M(fèi)用包括兩個方面的費(fèi)用：一 是用于購買原料鋼管的費(fèi)用，這部分費(fèi)用由購買原料鋼管總根數(shù)決定；二是切割原料鋼管的增加費(fèi)用。根據(jù)事實(shí)依據(jù)增加一些適當(dāng)?shù)募s束條件，使軟件快速和有效地求解。 為了使總費(fèi)用最小 , 應(yīng)如何下料 ? 問題分析 問題（ 1） 要確定如何下了最為節(jié)省，首先要確定哪些切割模式是可行的。顯然，可行的切割模式是很多的。 按照題目的要求，即每根原料鋼管生產(chǎn)的產(chǎn)品不能超過五根，并且每種切割模式的余料不能超過 100mm，合理可行的切割模式一共有 11種，如表 21所示， 表 21 290mm 鋼管數(shù) 315mm 鋼管數(shù) 350mm 鋼管數(shù) 455mm 鋼管數(shù) 余料 (mm) 模式 1 3 0 0 2 70 模式 2 2 1 0 2 45 模式 3 2 0 1 2 10 模式 4 1 2 0 2 20 模式 5 1 1 2 1 90 模式 6 1 0 3 1 55 模式 7 0 3 1 1 100 5 模式 8 0 2 2 1 65 模式 9 0 1 3 1 30 模式 10 0 0 5 0 100 模式 11 0 0 0 4 30 問題化為在滿足客戶需要的條件下，按照哪幾種合理的模式切割多少根原料鋼管，最為節(jié)省。 問題（ 2） 總費(fèi)用包括兩方面的費(fèi)用，一是用于購買原料鋼管的費(fèi)用，這部分費(fèi)用由購買原料鋼管總根數(shù)決定，由于假定購買的原料鋼管都用于切割，所以切割的原料鋼管總根數(shù)越少，費(fèi)用越少。由于切割每根 原料鋼管的增加費(fèi)用與原料鋼管的價值成正比關(guān)系，可以目標(biāo)函數(shù)轉(zhuǎn)化為鋼管根數(shù)的函數(shù)。 按照問題（ 1）的思路，可以通過枚舉法首先確定那些切割模式是可行的。因此必須尋找另外的方法。 模型假設(shè) ，不涉及其它的費(fèi)用如工人工資、設(shè)備損耗費(fèi)、原料鋼管及產(chǎn)品的存儲費(fèi)用，或者認(rèn)為這些費(fèi)用已經(jīng)包含在切割原料鋼管的增加費(fèi)用之中了。 。 ，超出的部分的產(chǎn)品認(rèn)為是被浪費(fèi)了。 2. iM2 ：按照第 i 種模式切割原料鋼管的增加費(fèi)用。 4. ir1 ：按照第 i 種切 割模式下每根原料鋼管生產(chǎn) 290mm 鋼管數(shù)量。 6. ir3 ：按照第 i 種切割模式下每根原料鋼管生產(chǎn) 350mm 鋼管數(shù)量。 模型建立與求解求解 問題（ 1） 模型建立 決策變量 用 ix 表示按照第 i 種模式（ i =1， 2， 3， 4，…，）切割的原料鋼管根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。通過觀察約束條件，可以發(fā)現(xiàn)，每種規(guī)格的鋼管的生產(chǎn)數(shù)量沒有設(shè)定上界，即 每種規(guī)格鋼管的實(shí)際生產(chǎn)數(shù)量都有可能超過客戶的需求，那么，超出客戶需求的產(chǎn)品也應(yīng)該認(rèn)為是余料。 通過對比修改后的目標(biāo)一和目標(biāo)二最優(yōu)解的方案，可以發(fā)現(xiàn)它們是一樣的。 9 （ 2） 模型建立 由于切割模式的種類不能超過 4種，可以用 ix 表示按照第 i 種模式（ i =1， 2， 3，4）切割的原料鋼管根數(shù)，它們是非負(fù)整數(shù)。 決策目標(biāo) 總費(fèi)用最少，假設(shè) x1x2x3, 這對問題沒有影響目標(biāo)為 min=+++ 約束條件 為滿足客戶的條件，應(yīng)有 r11x1+r12x2+r1x3+r14x≥ 15 r21x1+r22x2+r23x3+r24x4≥ 28 r31x1+r32x2+r33x3+r34x4≥ 21 r41x1+r42x2+r43x3+r44x4≥ 30 每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不超過 1850mm，也不能少于 1750mm（余料不大于 100mm），于是 1750≤ 290r11+315r21+350r31+455r41≤ 1850 1750≤ 290r12+315r22+350r32+455r42≤ 1850 1750≤ 290r13+315r23+350r33+455r43≤ 1850 1750≤ 290r14+315r24+350r34+455r44≤ 1850 每種切割模式下每根原料鋼管生產(chǎn)的產(chǎn)品數(shù)不能超過 5根，于是 r11+r21+r31+r41≤ 5 r12+r22+r32+r42≤ 5 r13+r23+r33+r43≤ 5 r14+r24+r34+r44≤ 5 并且 x1x2x3 模型求解 實(shí)際上，上邊的約束條件確定的范圍是很大的，用 LINGO 求解要很長的時間，因此需要加上一些顯然的約束條件，從而縮小可行解的范圍?？梢栽黾蛹s束條件 x1+x2+x3≥ 19 將目標(biāo)函數(shù)和約束條件 構(gòu)成的整數(shù)線性規(guī)劃模型輸入 lingo 求解，得到最優(yōu)解如下： Objective value: Extended solver steps: 267 Total solver iterations: 16069 Variable Value Reduced Cost X1 X2 X3 X4 R11 R12 R13 R14 R21 R22 R23 R24 R31 R32 R33 R34 R41 R42 R43 R44