1、題目 易拉罐下料問(wèn)題摘要當(dāng)代生活中，易拉罐成為新型飲料的載物品，是便捷、輕型的新代表。論文以易拉罐的生產(chǎn)為背景，用經(jīng)濟(jì)、獲利的角度看待生產(chǎn)的分配與規(guī)劃，從中選擇最優(yōu)方案，使得貴公司每周的生產(chǎn)能夠優(yōu)越地運(yùn)行和發(fā)展。題目雖然僅有一問(wèn)，但是里面牽扯的關(guān)系種類因素較為復(fù)雜，我們主要抓住題目目標(biāo)求解，即獲得利潤(rùn)最大，其目標(biāo)也遞進(jìn)暗示了材料的使用率也是需要最大的，則據(jù)此而得：目標(biāo)函數(shù)的變量又涉及到產(chǎn)量的規(guī)劃與材料的使用，然而產(chǎn)量的求解需要易拉罐蓋子和瓶身的共同組合而成，那么蓋子數(shù)量與瓶身的數(shù)目成為解決問(wèn)題的核心，于是易拉罐的真正數(shù)量為其它的時(shí)間，原料的基本數(shù)量等因素的限制引出相關(guān)的不等式，而實(shí)際的計(jì)劃是需

2、要整數(shù)的，因此這題解決的關(guān)鍵是整數(shù)線性規(guī)劃。最后解出的結(jié)果是模式一不使用，模式二使用40125次，模式三使用3750次，模式四使用20000次，可生產(chǎn)易拉罐160250個(gè)，此時(shí)罐身與底罐正好配成無(wú)剩余，獲得最大利潤(rùn)為4298元。 關(guān)鍵詞 整數(shù)規(guī)劃 優(yōu)化問(wèn)題 靈敏度分析一、問(wèn)題背景和重述1.1問(wèn)題背景1959年，美國(guó)俄亥俄州帝頓市DRT公司的（艾馬爾·克林安·弗雷茲）發(fā)明了易拉罐，即用罐蓋本身的材料經(jīng)加工形成一個(gè)鉚釘，外套上一拉環(huán)再鉚緊，配以相適應(yīng)的刻痕而成為一個(gè)完整的罐蓋。這一天才的發(fā)明使金屬容器經(jīng)歷了50年漫長(zhǎng)發(fā)展之后有了歷史性的突破。同時(shí)，也為制罐和飲料工業(yè)發(fā)展奠定了堅(jiān)

3、實(shí)的基礎(chǔ)。1.2問(wèn)題重述生產(chǎn)中常會(huì)遇到切割、裁剪、沖壓等手段，將原材料加工成所需尺寸。按照進(jìn)一步工藝要求、確定下料方案，使用料最省、利潤(rùn)最大。在本文易拉罐下料的問(wèn)題中，某公司采用一套沖壓設(shè)備生產(chǎn)一種罐裝飲料的易拉罐，這種易拉罐是用圓柱狀鍍錫板沖壓成的。已知罐身高，上蓋和下底的直徑均為。兩種不同規(guī)格的鍍錫板原料，規(guī)格的鍍錫板為正方形，邊長(zhǎng)；規(guī)格的鍍錫板為長(zhǎng)方形，長(zhǎng) ，寬；由于生產(chǎn)設(shè)備和生產(chǎn)工藝的限制，不同的規(guī)格有模式限制，并且在不同模式進(jìn)行沖壓所需時(shí)間固定、每周40小時(shí)工作時(shí)間、規(guī)格、的鍍錫板原料數(shù)目的限定，采取相應(yīng)的數(shù)學(xué)模型對(duì)問(wèn)題分析，以資源、效益最優(yōu)化為目的。選擇最佳方法。 二、問(wèn)題分析2.

4、1問(wèn)題的分析針對(duì)易拉罐的下料問(wèn)題，首先要分析題目中所給的已知條件和限制條件。已知條件有：罐身高，上蓋和下底的直徑均為；兩種不同規(guī)格的鍍錫板原料，規(guī)格的鍍錫板為正方形，邊長(zhǎng)；規(guī)格的鍍錫板為長(zhǎng)方形，長(zhǎng) ，寬；限制條件有：不同的規(guī)格在不同的模式下進(jìn)行，并且在不同模式進(jìn)行沖壓所需時(shí)間固定；每周40小時(shí)工作時(shí)間；規(guī)格、的鍍錫板原料數(shù)目固定等；罐身和底、蓋的配套組裝。要求最優(yōu)生產(chǎn)方案使得易拉罐利潤(rùn)扣除原料預(yù)料損失后的凈利潤(rùn)最大。（損失包括不能裝配的罐身、上下底余料。）進(jìn)行線性規(guī)劃中的整數(shù)規(guī)劃去最優(yōu)解表示三、模型假設(shè)3.1為更好進(jìn)行求解我們作出幾點(diǎn)假設(shè)：1、假設(shè)該公司每周生產(chǎn)正常，沒(méi)有意外事故發(fā)生；2、假設(shè)

5、易拉罐接口處的材料用量忽略不計(jì)；3、假設(shè)易拉罐各部分所用的材料相同；4、假設(shè)每個(gè)易拉罐都完好無(wú)損；5、假設(shè)生產(chǎn)過(guò)程的意外事故和員工個(gè)人因素造成損失不計(jì)；6、假設(shè)易拉罐所生產(chǎn)量全部銷售，無(wú)積壓現(xiàn)象。7、假設(shè)原料供應(yīng)充足，排除無(wú)缺料現(xiàn)象。8、假設(shè)無(wú)生產(chǎn)殘次易拉罐現(xiàn)象。四、符號(hào)說(shuō)明和名詞解釋4.1符號(hào)說(shuō)明分別表示四種模式計(jì)劃的數(shù)量制作的罐子數(shù)目浪費(fèi)的原材料的面積多余的罐身和蓋子表示獲得的利潤(rùn)4.2名詞解釋1、靈敏度分析：研究與分析一個(gè)系統(tǒng)（或模型）的狀態(tài)或輸出變化對(duì)系統(tǒng)參數(shù)或周圍條件變化的敏感程度的方法。2、變量值：表示當(dāng)該非基變量增加一個(gè)單位(其它非基變量保持不變)時(shí)目標(biāo)函數(shù)的減少的量。3、整數(shù)規(guī)

6、劃：規(guī)劃中的變量（全部或部分）限制為整數(shù)若在線性模型中。4、整數(shù)線性規(guī)劃：規(guī)劃中的變量（全部或部分）限制為整數(shù)若在線性模型中，變量限制為整數(shù)。五、模型建立與求解5.1問(wèn)題模型的建立與求解針對(duì)題目需要，每一個(gè)條件都是限制大小性的要求，而且從實(shí)際角度考慮，那么每一種模式要求確定的數(shù)量都是整數(shù)，所以建立整數(shù)規(guī)劃模型。我們只要稍加留意就會(huì)發(fā)現(xiàn)銷量很大的飲料的飲料罐的形狀和尺寸幾乎相同?？磥?lái)，這并非偶然，而應(yīng)該是某種意義下的最優(yōu)設(shè)計(jì)。設(shè)四種模式計(jì)劃的數(shù)量分別為能夠制作的罐子數(shù)目為，多余的罐身和蓋子分別為，獲得的利潤(rùn)為。決策變量 設(shè)xi（i=1、2、3、4）為使用第i重模式生產(chǎn)原料的張數(shù)，設(shè)z為一周生產(chǎn)的

7、易拉罐數(shù)，y2為一周生產(chǎn)所不配套的罐身個(gè)數(shù)，y3為一周生產(chǎn)所不配套的上蓋、下底個(gè)數(shù)，y4為最終利潤(rùn)。目標(biāo)函數(shù)依據(jù)題目要求公司生產(chǎn)的利潤(rùn)可能高，確立了目標(biāo)函數(shù)：值函數(shù)能夠制作全的罐子收到罐身和蓋子數(shù)目的制約，即取得數(shù)值較小的一方，然而不排除最后多一個(gè)蓋子和罐身的可能性，所以確定值如下函數(shù)：題目各模式需求表1 四種模式各需求量模式總面積罐身面積底蓋面積余料面積模式1576157.1196.3222.6模式2576314.278.5183.3模式35760314.2261.8模式4896628.398.2169.5多余的罐身和蓋子的函數(shù)如下：先求得浪費(fèi)的原材料的面積：題目約束條件表2 各種模式時(shí)間和

8、損失產(chǎn)量罐身底、蓋沖壓時(shí)間余料損失X11101.5222.6X2242183.3X30161261.8X4453169.5于是限制條件為：最后解出的結(jié)果是模式一不使用，模式二使用40125次，模式三使用3750次，模式四使用20000次，可生產(chǎn)易拉罐160250個(gè)，此時(shí)罐身與底罐正好配成無(wú)剩余，獲得最大利潤(rùn)為4298元。六、模型檢驗(yàn)七、模型優(yōu)缺點(diǎn)和改進(jìn)7.1模型的評(píng)價(jià)7.1.1模型的優(yōu)點(diǎn)1、通過(guò)運(yùn)用數(shù)學(xué)工具和編程的方法，嚴(yán)格地對(duì)模型求解，具有科學(xué)性。2、進(jìn)行靈敏度檢驗(yàn)，極大的證明了模型的穩(wěn)定性與正確性。7.1.2模型的缺點(diǎn)1、建立的模型沒(méi)有聯(lián)系到實(shí)際生活中，所以缺乏精確性。2、沒(méi)有考慮破損和節(jié)

9、假日等情況可能對(duì)結(jié)果有影響。7.2模型的改進(jìn)通過(guò)對(duì)實(shí)際的測(cè)量，得到關(guān)于易拉罐的數(shù)據(jù)。以此提供了數(shù)據(jù)，在問(wèn)題的解答上，選擇最優(yōu)模型。運(yùn)用編程得出答案發(fā)現(xiàn)，理論值與顯示測(cè)量值相符，最后通過(guò)對(duì)模型的改進(jìn)，給出了易拉罐的最優(yōu)設(shè)計(jì)模型。對(duì)罐底和罐壁的厚度等對(duì)比沒(méi)有做深入的研究。期望在此方面加以改進(jìn)，以達(dá)到最經(jīng)濟(jì)的效果。用分支定界算法,采用偽費(fèi)用分支策略劃分問(wèn)題,采用深度優(yōu)先搜索(DFS)策略選擇子問(wèn)題進(jìn)行擴(kuò)展,數(shù)值實(shí)驗(yàn)表明,改進(jìn)的算法能夠有效提高求解效率,當(dāng)問(wèn)題規(guī)模較大時(shí),改進(jìn)效果尤其明顯。八、模型推廣通過(guò)對(duì)題目的解讀我們不難發(fā)現(xiàn)這是一類規(guī)劃問(wèn)題。我們建立了一個(gè)整數(shù)線性規(guī)劃模型。仔細(xì)分析我們建立的模型不

10、難發(fā)現(xiàn)：這個(gè)模型不僅僅適用于出版社的資源配置問(wèn)題，它對(duì)規(guī)劃類問(wèn)題的求解都可以起到指導(dǎo)作用。 規(guī)劃問(wèn)題是運(yùn)籌學(xué)的一個(gè)重要分支。它在解決工業(yè)生產(chǎn)組織、經(jīng)濟(jì)計(jì)劃、組織管理人機(jī)系統(tǒng)中，都發(fā)揮著重要的作用。本模型在實(shí)際應(yīng)用有廣泛的運(yùn)用，線性規(guī)劃的對(duì)偶問(wèn)題，整數(shù)制作用料問(wèn)題，運(yùn)輸問(wèn)題和一些最優(yōu)解問(wèn)題。九、參考文獻(xiàn)1蔡鎖章，數(shù)學(xué)建模：原理與方法，北京，海洋出版社，20002吳翊，吳孟達(dá)，數(shù)學(xué)建模的理論與實(shí)踐，長(zhǎng)沙，國(guó)防科技大學(xué)出版社，1999 3白其崢，數(shù)學(xué)建模案例分析，北京，海洋出版社，2000附錄附錄1model:max=0.1*y1-0.001*(222.6*x1+183.3*x2+261.8*x3+

11、169.5*x4+157.1*y2+19.6*y3); 1.5*x1+2*x2+x3+3*x4<=144000; x1+x2+x3<=50000; x4<=20000; y2=x1+2*x2+4*x4-y1; y3=10*x1+4*x2+16*x3+5*x4-2*y1; y1<=x1+2*x2+4*x4; y1<=(10*x1+4*x2+16*x3+5*x4)/2; gin(x1); gin(x2); gin(x3); gin(x4); gin(y1); gin(y2); gin(y3);End附錄2程序操作圖：附錄3代碼及輸出：Global optimal so

12、lution found.Objective value（目標(biāo)函數(shù)值為）: 4298.337Objective bound（最優(yōu)）: 4298.337Infeasibilities（不可行的約束數(shù)）: 0.000000Extended solver steps（展規(guī)劃求解步驟）: 0Total solver iterations（程序運(yùn)行4部找到最優(yōu)解）: 4Model Class（純整數(shù)規(guī)劃）:Total variables（總變量）: 7Nonlinear variables（非線性）: 0Integer variables（線性）: 7Total constraints（總約束條件）:

13、8Nonlinear constraints（非線性條件）: 0Total nonzeros（非0系數(shù)的總個(gè)數(shù)）: 35Nonlinear nonzeros（非0系數(shù)且非線性個(gè)數(shù)）: 0變量值表示當(dāng)該非基變量增加一個(gè)單位(其它非基變量保持不變)時(shí)目標(biāo)函數(shù)的減少的量Variable Value Reduced Cost Y1 160250.0 -0.1000000 X1 0.000000 0.2226000 X2 40125.00 0.1833000 X3 3750.000 0.2618000 X4 20000.00 0.1695000 Y2 0.000000 0.1571000 Y3 0.000000 0.1960000E-01約束條件接近等于的程度。給出對(duì)偶價(jià)格的值。表示每增