鋼管下料問題

1、湖北汽車工業(yè)學(xué)院2009年大學(xué)生數(shù)學(xué)建模競賽承諾書我們仔細閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵 件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問 題。我們知道，抄襲別人的成果是違反競賽規(guī)則的，如果引用別人的成果或其他 公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正 文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反 競賽規(guī)則的行為，我們將受到嚴肅處理。參賽隊員（姓名，班號，簽名）：1 .馮鵬程，T773-22 .李冠華，T743-73

2、 .吳楠，T723-5日期：2010 年5 月18 日編號： 鋼管下料問題的論文問題的重述某鋼管零售商從鋼管廠進貨，將鋼管按照顧客的要求切割出售從鋼管廠進貨得到的原材料的鋼管的長度都是1850mm ，現(xiàn)在一顧客需要15根 290 mm，28 根 315 mm， 21 根 350 mm 和 30 根 455 mm 的鋼管為了簡化生產(chǎn)過程，規(guī)定所使用的切割模式的種類不能超過4 種， 使用頻率最高的一種切割模式按照一根原料鋼管價值的1/10 增加費用，使用頻率次之的切割模式按照一根原料鋼管價值的 2/10 增加費用，以此類推，且每種切割模式下的切割次數(shù)不能太多（一根原鋼管最多生產(chǎn)5 根產(chǎn)品），此外為

3、了減少余料浪費，每種切割模式下的余料浪費不能超過100 mm,為了使總費用最小，應(yīng)該如何下料？摘要該問題在于確定鋼管切割模式的安排上，顯然是一個優(yōu)化問題。是一個在原料和成品長度等約束下求最小費用的優(yōu)化模型。我們在分析題目的各種限制因素后，找到初步的目標函數(shù)，找到約束條件，建立 IP （整數(shù)優(yōu)化）模型。在求解模型過程中，由于問題的規(guī)模小，我們通過分析約束條件采取枚舉法分析可行域，運用MATLA豉到鋼管切割模式的可行解。然后在目標函數(shù)下，進而求出最優(yōu)解集合。 考慮到實際生活常識，通過對滿足約束條件下的最優(yōu)解來進行分析，找到符合實際的最優(yōu)解。依此來確定最終的切割模式方案。在求解模型的過程中，針對不同

4、的假設(shè)背景下，可以簡化模型的求解過程。我們運用LINDO/LINGO或MATLAB寫程序來進行求解，同時用LINDO/LINGO軟件進行初步的可行性和靈敏度分析。為了使主要結(jié)果的直觀性和形象性，對獲得的數(shù)據(jù)運用MATLABt理成圖表。在文章的最后，我們對模型的改進和模型的應(yīng)用范圍進行了適當?shù)姆治觯岢鲫P(guān)于與模型的相關(guān)問題的見解。關(guān)鍵字切割模式優(yōu)化MATLAB/LINGO靈敏度分析1 .題目提出原料鋼管長度1850mm現(xiàn)要從這一批原料鋼管中切割出15根290mm 28根 315mm 21根350mmffi 30根455mmE種特定長度的成品鋼管。合理的切割模式 確定后，求使切割總費用最小的切割方

5、案。問題中的原料和成品長度都有限定， 切割費用也與切割模式有關(guān)。在閱讀分析題目后，其中限制條件主要有： 1.1原料鋼管長度限制，所以每根鋼管的切割模式總長度不能超過1850mm1.2 一根鋼管最多生產(chǎn)5根成品鋼管，切割后的成品根數(shù)有限制 1.3切割模式的種類不能超過4種1.4 一根鋼管在每種切割模式下的余料不能超過100mm1.5 費用的計算方式是和切割模式的使用頻率有關(guān)2 .符號說明和模型假設(shè)2.1 符號的說明LL表示原料鋼管的長度(LL = 1850mm)Qi表示第i種成品鋼管的需求根數(shù)(i =1,2,3,4)L 表示第i種成品鋼管的長度nj表示在第j種切割模式下切割的原料鋼管的根數(shù)(j

6、= 1,2,m.m< J ) qj表示在第j種切割模式后剩下的需求成品根數(shù)qj表示在第j種切割模式下一根原料鋼管切割出的第i種成品鋼管根數(shù)N 表示一根原料鋼管最多生產(chǎn)的成品根數(shù) l j表示在第j種切割模式下每根原料鋼管的余料J表示切割模式種類的限制(J=4) L 表示每根原料鋼管的余料限制(AL= 100mm)N表示滿足需求下需要的原料鋼管的根數(shù)fj表示在第j種切割模式下的總費用F表示所有切割模式下的總費用kj 表示費用比例因子P表示原料鋼管單價2.2模型的假設(shè)(1)切割過程中原料鋼管不發(fā)生長度損失。(2)在切割過程中，只發(fā)生因切割而產(chǎn)生的費用。(3)切割費用只與切割模式使用頻率有關(guān)，而

7、與其他因素?zé)o關(guān)。(4)在使總費用達到最小的所有模式中，認為余料最小是要比其他同等模式優(yōu)良的切割模式3 .問題的分析和模型的建立3.1 這是一個優(yōu)化問題中的IP問題，即整數(shù)優(yōu)化。主要的問題是求解由一系列合理的切割模式組成的切割方案使切割過程中發(fā)生的費用最少，也就是確定由nj組成的矩陣N o3.2 目標函數(shù)的建立3.2.1 在第j種切割模式下的總費用fjf j = kj Pq(1)3.2.2 所有切割模式下的總費用F =£ fj (2)3.2.3 目標函數(shù)總費用最小MINF fj(3)3.3 約束條件,3.3.1 原料鋼管長度約束二 qij Li _ LL(4)3.3.2 需求數(shù)量約束Q

8、i 21 qij(5)3.3.3 余料約束在第j種切割模式下每根原料鋼管的余料% =LL 八 qij Lil j < AL(6)3.3.4 切割最多根數(shù)約束Z qij 蕓 N(7)3.3.5 切割模式種類約束8)j MJ3.3.6 根數(shù)整數(shù)約束9)qj ,njN3.4 數(shù)學(xué)模型 目標函數(shù)：MINF = '、fjZ qj Li < LLQi <Z qj約束條件:Alj <AL Z qj <N 1 jJ qj ,nj w N注：當 nj = (n1 n2 n3n4箱如下關(guān)系ra n2 An3A 心，則切割費用比例向量中的元素有【kj ：'= kik2k

9、3k4 =10 1034I10 104 .數(shù)學(xué)模型的求解經(jīng)過合理假設(shè)后，問題的關(guān)鍵就變成在約束條件下求解每種切割方式中的鋼管數(shù) 量組成的行向量nj。以下我們分別采用通過編輯LINDO/LINGO呈序求解出目標 函數(shù)取得最優(yōu)解時的口=1和通過遍歷的方法求解（不推薦）4.1 LINDO/LINGOS 序求解4.2 MATLA取現(xiàn)的遍歷求解由于問題簡單（維數(shù)不多），我們可以通過MATLA皿行遍歷求解。由于原料鋼管長度是LL = 1850mm ,成品鋼管的長度是 L =（290 315 350 455）,因此一根表（.）一根原料鋼管切割成品的最大數(shù)量成品長度（mm290315350455最大數(shù)量6.3

10、85.875.294.07這樣通過預(yù)先的原料鋼管能夠生產(chǎn)成品數(shù)量的求解，可以減小遍歷時候的循環(huán) 可以簡化求解過程，同時也能夠?qū)σ院蟮那蠼膺^程進行驗算。因此，在長度和余料AL=100mm限制下，我們可以通過循環(huán)進行遍歷篩選出可 行解。求解的結(jié)果如下表（其中的對應(yīng)切割模式的可能的使用頻率最大值是根據(jù)N =（15 28 21 30 坪:?。┍恚?.2.1 ）可行的第一種切割模式匯總編號L1L2L3L4余料可能的使用頻率最大值10004307200501004301313074022165105031110096103155771121901081202201492012107102102457113

11、002705因為費用與切割模式的使用頻率有顯著的關(guān)系，通過觀察表（4.2.1 ）可以看到編號8的切割模式的可能的使用頻率最大值為最大，并且余料也在 11種模式中也較小。因此，我們第一種切割模式采用8號切割模式，此時可以求得 5=14,1f1 = P 14 , Aq1 =Aqi1 = （1 0 21 2 卜 10可以在第二類成品鋼管需求為0的情況下，進行對切割模式進行遍歷，結(jié)果如下 表（.）可行的第二種切割模式匯總編號L1L2L3L4余料可能的使用頻率最大值10004300200501004310315514201210053002700我們可以這樣做，先采用編號3的模式，因為如果采用2號方案就

12、會造成不能解決約束條件滿足的現(xiàn)象。因此，我們第二種切割模式采用3號切割模式，此時可 以求得 n2=1, fx=kxP1, Aq2=Gq2i=（0 0 18 1）。由于Aq2=（0 0 18 1 ）,只要再切割一根鋼管即能切割完成需求。所以第三種切割模式就選擇表（.）可行的第三種切割模式匯總編號L1L2L3L4余料可能的使用頻率最大值10004300200501003因此，我們第三種切割模式采用表（.）2號切割模式，此時可以求得 %=1,f3 =p 1， %3 =好 =。0 1 2 綜合以上的求解過程，切割方案是即每種切割模式切割的原料鋼管數(shù)量是n=（14 4 1 ）,費用向量是f =（lp 1

13、4 P 4 3 P 1 j,切割方式組成的矩 101010,1202、一-5陣是 q = 0050,最優(yōu)解是MINF=£fj =Pj21012,j模型求解結(jié)果如下表（.）鋼管下料方案編號L1L2L3L4余料使用頻率切割費用1120220141.4P2005010040.8P3101230010.3P小計15282130980192.5P源程序見附件（2.1）,運行結(jié)果見附件（2.2）5 .數(shù)學(xué)模型的評價和進一步討論5.1 數(shù)學(xué)模型的優(yōu)點這是一個經(jīng)濟生活中常見的確定生產(chǎn)方案問題，是運籌學(xué)中很典型的問題。并且在合理的將約束條件簡化條件下，能夠和實際結(jié)果符合的較好。5.1.1 模型思路明朗

14、清晰，結(jié)構(gòu)簡單，有一定的適用范圍能夠較為簡便的解決生 產(chǎn)方案安排問題。5.1.2 模型可以很容易的推廣到在 M種原料下，生產(chǎn)N種成品的情形，方案制定 并進行優(yōu)化（非遍歷解法）。6.1.3 模型（一）能夠根據(jù)不考慮運輸費用的假設(shè)條件下進行合理的簡化大幅度 的減少了工作量。而且模型（三）也能繼承模型（一）的一些有關(guān)的思路。6.1.4 很重要的一點是問題（二）對模型（一）進行了靈敏度的分析和影子價格 的討論，這有很重要的意義，明確的給出了模型的適用范圍和在有關(guān)量發(fā)生變化時對模型中目標函數(shù)最優(yōu)解的影響。這是很有現(xiàn)實意義的，因為有關(guān)量往往是依靠大量觀測值得到的一個統(tǒng)計估計值。這些估計值有一個置信區(qū)間，即

15、不是一個準確的真值，自然會有誤差，而模型（一）對銷售價格的靈敏度分析就能夠證明模型在相關(guān)量的一個變動范圍內(nèi)有效。顯然這是很有實際意義的。5.2 數(shù)學(xué)模型需要改進的地方由于這是在實際基礎(chǔ)上經(jīng)過理想化假設(shè)后抽象出來的數(shù)學(xué)模型，因此這個數(shù)學(xué)模型也存在著一些缺陷5.2.1 必須是建立在靜態(tài)假設(shè)條件下的，即要求在運輸過程中相關(guān)價格量、供給量、需求量等不能發(fā)生變動，5.2.2 模型的解是整數(shù)，即離散的，原因是經(jīng)濟中商品量的變動很多都是單位變動，即離散的，所以模型就不能很好的處理量變化是連續(xù)性的商品運輸問題，6.2.3 對運輸費用的假設(shè)是與里程，即噸*公里成正比的，實際上運輸價格并不一定都是這種關(guān)系，影響運

16、輸費用的因素還有很多，需要考慮的地方還有很多。 并且商品的運輸過程中發(fā)生損失是很難避免的，尤其是水果等鮮貨，這些都會造成模型的解偏離真實值6.2.4 對運輸線路的假設(shè)是直線，而現(xiàn)實中的航線是曲線，主要原因是我們沒有獲得航線里程準確的數(shù)據(jù)，這也會影響模型解的真實性。不過以上的缺陷可以在這個模型的基礎(chǔ)上進行改進，同時如果能夠獲得一些準確的原始數(shù)據(jù)，就能夠較為客觀的反映現(xiàn)實，所以也不能否認這個模型的意義。6.2.5 數(shù)學(xué)模型的適用領(lǐng)域和范圍由于這是一般化的問題，因此能夠?qū)ζ溥M行推廣，應(yīng)用廣泛，可以作為必須滿足需求要求的運輸方案制定的初步參考，同時也可以作為采購運輸銷售經(jīng)營模式的初步參考。可以看到這個

17、數(shù)學(xué)模型在經(jīng)濟運籌學(xué)領(lǐng)域的應(yīng)用很廣。參考文獻1 薛毅，耿美英. 運籌學(xué)與實驗，北京：電子工業(yè)出版社，2008.9.2 張杰，周碩，郭麗杰. 運籌學(xué)模型與實驗，北京：中國電力出版社，2007.3謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件.北京：清華大學(xué)出版社，2005.附件附件（1.1 ）附件（1.2）附件（2.1 ）建模比賽MATLAB 遍歷程序1 clcclearl0=1850;l=290 315 350 455;m=15 28 21 30;for i=0:1:6for j=0:1:5for k=0:1:5for h=0:1:4 n=i,j,k,h;if (i+j+k+h)<=5)&(l0-n*l')<=100)&(l0-n*l')>=0)n=i,j,k,hendendendend end建模比賽MATLAB 遍歷程序2clcclearl0=1850;l=290 315 350 455;m=15 28 21 30;for i=0:1:6for k=0:1:5