輪胎生產(chǎn)安排計(jì)劃的數(shù)學(xué)模型

1、第三期2004年12月韶關(guān)學(xué)院學(xué)生數(shù)學(xué)建模論文集輪胎生產(chǎn)安排計(jì)劃的數(shù)學(xué)模型何榮堅(jiān)陳曄鄭可逵1.韶關(guān)學(xué)院2002級(jí)電腦系科學(xué)與技術(shù)本3班，廣東韶關(guān)512005;2.韶關(guān)學(xué)院2001級(jí)數(shù)學(xué)系數(shù)學(xué)與應(yīng)用數(shù)學(xué)（1）班，廣東韶關(guān)512005;3.韶關(guān)學(xué)院2002級(jí)數(shù)學(xué)系信息技術(shù)教育2班，廣東韶關(guān)512005摘要：本文是一個(gè)生產(chǎn)安排優(yōu)化問題，在問題中全面分析了輪胎生產(chǎn)問題的約束條件，構(gòu)建了基于整數(shù)規(guī)劃的每一季度的生產(chǎn)時(shí)間與生產(chǎn)個(gè)數(shù)的的數(shù)學(xué)模型.利用Matlab軟件中的線性規(guī)劃函數(shù)Linprog對(duì)每一季度的生產(chǎn)進(jìn)行優(yōu)化求解，對(duì)模型實(shí)行簡(jiǎn)化，加快對(duì)模型的求解.在求解過程中，利用連續(xù)松弛法把該問題更加簡(jiǎn)化，轉(zhuǎn)換

2、成線性規(guī)劃問題.在滿足約束條件的情況下，通過對(duì)變量的取整與調(diào)整，使得解更加逼近最優(yōu)解.關(guān)鍵詞：整數(shù)規(guī)劃；優(yōu)化安排；連續(xù)松馳1問題的提出某汽車輪胎公司能夠生產(chǎn)尼龍和玻璃纖維兩種輪胎，在前三個(gè)季度中將要交付的輪胎數(shù)量如表一：表日期尼龍輪胎玻璃纖維輪胎第一季度40001000第一季度80005000第二季度30005000總計(jì)1500011000該公司有兩臺(tái)硫化機(jī)，其中一臺(tái)惠林硫化機(jī)，一臺(tái)雷格爾硫化機(jī)，還有可用來生產(chǎn)這兩種輪胎的合適的模子。在未來的三個(gè)季度內(nèi)，這兩臺(tái)機(jī)器可供使用的生產(chǎn)小時(shí)數(shù)如表二：表二:日期惠林硫化機(jī)雷格爾硫化機(jī)第一季度7001500第一季度300400第二季度1000300每臺(tái)機(jī)器

3、生產(chǎn)每種輪胎的效率以每只輪胎需要多少小時(shí)表示如下表三:表二：惠林硫化機(jī)雷格爾硫化機(jī)尼龍輪胎玻璃纖維輪胎不管用哪種機(jī)器，也不管生產(chǎn)哪種輪胎，輪胎生產(chǎn)的生產(chǎn)費(fèi)用是每操作一小時(shí)5美元,每只輪胎每個(gè)月的存儲(chǔ)費(fèi)用0.1美元，每只尼龍輪胎和玻璃纖維輪胎的材料費(fèi)用分別為3.10美元和3.90美元，每只輪胎的裝配、包裝和運(yùn)輸費(fèi)用是0.23美元，每只尼龍輪胎的價(jià)格是7.00美元，每只玻璃纖維輪胎的價(jià)格是9.00美元。該公司管理人員提出以下問題：第四季度初到達(dá)，如果支付200美元的小費(fèi)，就可以提前在第三季度到達(dá)，這樣第三季度就可增加172小時(shí)的機(jī)器工作時(shí)間。這臺(tái)硫化機(jī)到底要不要提前到達(dá)？2模型的假設(shè)1）假設(shè)交貨都

4、是在每一季度的最后一天完成的，當(dāng)前季度生產(chǎn)的輪胎不用存儲(chǔ)費(fèi)2）假設(shè)生產(chǎn)貨物過程中以小時(shí)為單位，不足一個(gè)小時(shí)的按一個(gè)小時(shí)來算機(jī)器操作費(fèi)3）假設(shè)第一季度生產(chǎn)白時(shí)候沒有存貨.3符號(hào)說明Xj:第i個(gè)季度第j種機(jī)器加工型輪胎的小時(shí)數(shù).i1,2,3;j1,2;yj:第i個(gè)季度第j種機(jī)器加工型輪胎的小時(shí)數(shù).i1,2,3;j1,2;pj:第j型輪胎的材料費(fèi)的單價(jià).j1,2;n:輪胎的裝配，包裝，運(yùn)輸輪胎的單位費(fèi)用.qi:第i型輪胎的單價(jià).i1,2;i 1,2,3; j 1,2;i 1,2,3; j 1,2;tj:第種i機(jī)器生產(chǎn)第j種輪胎的單位時(shí)間Sj:第i個(gè)季度j型輪胎的生產(chǎn)的實(shí)際數(shù)目U:第i個(gè)季度的機(jī)器操作

5、費(fèi).i1,2,3;Vi:第i個(gè)季度的存儲(chǔ)費(fèi).i1,2,3;wi:第i個(gè)季度完成交貨任務(wù)后的剩余輪胎的總數(shù).i1,2,3;Q:生產(chǎn)的總成本.M:生產(chǎn)的總收益.4模型的分析與建立尼龍輪胎稱為第一種輪胎，同樣把玻璃纖維輪胎稱為第二種輪胎.目標(biāo)函數(shù)與各個(gè)季度各種機(jī)器生產(chǎn)的各種輪胎的數(shù)量限制，與各個(gè)季度各種機(jī)器的生產(chǎn)時(shí)間都為一次線性函數(shù)，故可以用線性規(guī)劃求解.由已知條件可以得出線性規(guī)劃的目標(biāo)函數(shù)，約束方程.1）根據(jù)題意分析可知，機(jī)器操作費(fèi)只與時(shí)間有關(guān)系，并且得出表達(dá)式為2UiXijyji1,2,3;j12）由假設(shè)3可知，第一季度的存儲(chǔ)費(fèi)為0;又第二季度兩種輪胎的存貨即為第一季度生產(chǎn)的總數(shù)減去第一季度的要

6、求交貨量后的數(shù)目，所以第二季度的存儲(chǔ)費(fèi)為：v20.1迎迎4000y1比1000t11t21t12t22同理可知，第三季度的總存儲(chǔ)費(fèi)為第二季度的存貨加上第三季度的生產(chǎn)總數(shù)再減去第三季度的交貨量后的存儲(chǔ)費(fèi)：Xiix124000x21x228000t11t21t11t21V30.1y11y121000y21y225000t12t22t12t223材料費(fèi)用為：由于材料費(fèi)只與輪胎的數(shù)量有關(guān)系,又根據(jù)題意可知，在滿足最小成本的條件下，生產(chǎn)輪胎的數(shù)量就必須等于交貨的總量.故,材料費(fèi)是一定值，即為:23PjSij3.10150003.9011000j1i14裝配、包裝、運(yùn)輸費(fèi)用為：同理由材料費(fèi)的分析可知，裝配

7、、包裝、運(yùn)輸費(fèi)用也只與輪胎的數(shù)量有關(guān)，即為：320.23sji1j1故目標(biāo)函數(shù)即為：總成本=#器操作總費(fèi)用+材料費(fèi)用+總存儲(chǔ)費(fèi)+裝配、包裝、運(yùn)輸費(fèi)用；5）最小總成本的模型為：32minQuij3.10150003.9011000v2v30.231500011000i1j1s.t.x11y11700x12y121500X21y21300x22y22400(2)(4)(5)(6)x11x124000tnt21x21x22XiiX12t11t21t11t21x31x32X21X22t11t21t11t21X32y3270040008000(8)8000X11X1240003000 (9)tnt21X

8、31y311000yiit12y12t221000(10)y21y22y1110005000(11)t12t22t12t22y31y32y21”5000&_y£10005000(12)t12t22t12t22t12t220x11700(13)0y11700(14)0x121500(15)0y121500(16)0x21300(17)0y21300(18)0x22400(19)0y22400(20)0x311000(21)0y311000(22)0x32300(23)0y32300(24)xj,yjZi1,2,3；j1,2；(25)(1)-(6)式表示每一季度的每一種機(jī)器生產(chǎn)每

9、一種輪胎的小時(shí)數(shù)都必須小于或等于每一季度的每一種機(jī)器的最大生產(chǎn)時(shí)間.(7),(10)式分別表示第一季度兩種輪胎生產(chǎn)的總數(shù)都要求大于或者等于第一季度的交貨量.(8),(11)式分別表示第二季度兩種輪胎的生產(chǎn)量加上第一季度的存儲(chǔ)量要求大于或者等于第二季度的交貨量.(9),(12)式分別表示第三季度兩種輪胎的生產(chǎn)量加上第二季度的存儲(chǔ)量要求等于第三季度的交貨量.根據(jù)總收益=總收入-總成本，而由問題一的模型分析可知，總成本是一個(gè)函數(shù)表達(dá)式，而總收入為一定值.又總收入為：23qjSj715000911000j1i123總收益MqjsijQj1i1而Q又為問題一的模型的目標(biāo)函數(shù)，而在要求從問題一的最優(yōu)生產(chǎn)安

10、排中所得到的總收益即為M的最大值.在問題三中，由于一臺(tái)新的惠林硫化機(jī)預(yù)定在第四季度初到達(dá)，如果支付200美元的小費(fèi)，就可以提前在第三季度到達(dá)，這樣第三季度就可增加172小時(shí)的機(jī)器工作時(shí)間.故建立的模型為：目標(biāo)函數(shù)為：3minQui3.10150003.9011000v2v30.231500011000+200i1約束條件為：,(2),(3),(4),(6),(7)(20),(23),(24)同問題一的數(shù)學(xué)模型的約束條件.X31y311172'0X311172(21)'0y311172(22)'5 模型的求解對(duì)于問題一的模型的求解的算法描述，顯然這個(gè)問題為整數(shù)規(guī)劃問題，解

11、此類問題的一般步驟為：用連續(xù)松馳把此整數(shù)規(guī)劃問題轉(zhuǎn)化為線性規(guī)劃問題，使得問題難度降低.再用MATLA瞅件求得該問題的最優(yōu)解，再通過變量取整調(diào)整改良，使得解逐漸逼近最優(yōu)解.用MATLABH勺內(nèi)置函數(shù)Linprog來求得(程序1在附錄略):最優(yōu)解Q116853美元表XiiX12X21X22X31X32yny12y21y22y31y322800400400420030006000再經(jīng)過取整調(diào)整，在調(diào)整的過程中必須注意到各個(gè)約束條件是否符合滿足，得出整數(shù)規(guī)劃的最優(yōu)解為：表二:XiiX12X21X22X31X32y11y12y21y22y31y32時(shí)間28012220400400534200300060

12、00個(gè)數(shù)18667637025002666331350002500050000則在取得最優(yōu)解時(shí)候最小總成本費(fèi)用為Q114556美元此時(shí)的生產(chǎn)計(jì)劃安排如表二所示得:280小時(shí)和1866個(gè):420小時(shí)和3500個(gè):1222小時(shí)和7637個(gè):0小時(shí)和0個(gè):0小時(shí)和0個(gè):300小時(shí)和2500個(gè):400小時(shí)和2500:0小時(shí)和0個(gè):400小時(shí)和2666個(gè):600小時(shí)和5000個(gè):53小時(shí)和331個(gè):0小時(shí)和0個(gè)第一季度第一種機(jī)器生產(chǎn)第一種輪胎的時(shí)間和個(gè)數(shù)分別為第一季度第一種機(jī)器生產(chǎn)第二種輪胎的時(shí)間和個(gè)數(shù)分別為第一季度第二種機(jī)器生產(chǎn)第一種輪胎的時(shí)間和個(gè)數(shù)分別為第一季度第二種機(jī)器生產(chǎn)第二種輪胎的時(shí)間和個(gè)數(shù)分

13、別為第二季度第一種機(jī)器生產(chǎn)第一種輪胎的時(shí)間和個(gè)數(shù)分別為第二季度第一種機(jī)器生產(chǎn)第二種輪胎的時(shí)間和個(gè)數(shù)分別為第二季度第二種機(jī)器生產(chǎn)第一種輪胎的時(shí)間和個(gè)數(shù)分別為第二季度第二種機(jī)器生產(chǎn)第二種輪胎的時(shí)間和個(gè)數(shù)分別為第三季度第一種機(jī)器生產(chǎn)第一種輪胎的時(shí)間和個(gè)數(shù)分別為第三季度第一種機(jī)器生產(chǎn)第二種輪胎的時(shí)間和個(gè)數(shù)分別為第三季度第二種機(jī)器生產(chǎn)第一種輪胎的時(shí)間和個(gè)數(shù)分別為第三季度第二種機(jī)器生產(chǎn)第二種輪胎的時(shí)間和個(gè)數(shù)分別為對(duì)于問題二的模型的最優(yōu)解是與問題一的模型的最優(yōu)解相關(guān)聯(lián)的，當(dāng)問題一的模型取得最優(yōu)解時(shí)，此時(shí)對(duì)應(yīng)的總收益即為所求的解.23故又由于總收入為qjsij71500091100020400膜元j1i1所以

14、對(duì)于問題一的解答中給出的最優(yōu)生產(chǎn)安排計(jì)劃中可以得最小的成本為：Q114556美元所以總收益=總收入-總成本即為：23MsjqjQ20400011455689444美元j1i1所以在問題一中的最優(yōu)化生產(chǎn)安排計(jì)劃中，得到的總收益為132344美元.對(duì)于問題三的求解：在問題三中的所建立的數(shù)學(xué)模型中，運(yùn)用和解決問題一所采用的方法解此模型.利用MATLA井的內(nèi)置函數(shù)Linprog來求得（程序2在附錄略）：最優(yōu)解時(shí)對(duì)應(yīng)的生產(chǎn)小時(shí)數(shù)為：XiiX12X21X22X31X32%iy12y21y22y31y3228004004500420030006000經(jīng)過人工取整調(diào)整后得到XiiX12X21X22X31X32

15、y11y12y21y22y31y32時(shí)間280122204004500420030006000個(gè)數(shù)186376370250030000350002500050000所以最少成本為：5*(280+1222+400+450+420+300+600)+3.10*15000+3.90*11000+0.23*(15000+11000)+(1863+7637-4000+3500-1000)*0.1+200=114740美元而在第三季度沒有那臺(tái)提前到達(dá)的惠林硫化機(jī)的時(shí)候，可以到達(dá)的最優(yōu)化時(shí)的成本為114556美元比114740小，則說明了當(dāng)支付200美元的小費(fèi)，就可以使那臺(tái)惠林硫化機(jī)提前在第三季度到達(dá)，是不

16、必要的.6 模型的評(píng)價(jià)由于Matlab軟件中是沒有現(xiàn)行的函數(shù)來實(shí)現(xiàn)整數(shù)規(guī)劃的，故在求解整數(shù)規(guī)劃過程中得出的只是近似解，要通過人工調(diào)整來實(shí)現(xiàn)整數(shù)規(guī)劃.模型具有較好的通用性，能夠適應(yīng)同類問題的各種變化.模型的算法比較優(yōu)化.參考文獻(xiàn)：1 .姚恩瑜，何勇，陳仕平.數(shù)學(xué)規(guī)劃與組合優(yōu)化M.杭州.浙江大學(xué)出版社.20012 .王沫然.MATLAB6.0與科學(xué)計(jì)算M.北京.電子工業(yè)出版社.20013 .陳理榮.數(shù)學(xué)建*II導(dǎo)論M.北京.北京郵電大學(xué)出版社.1999附錄：程序1:clearclcf=5+1.3333;5+1.250;5+0.6667;5+0.625;5;5;5+1.6667;5+1.4286;5

17、+0.8333;5+0.7143;5;5;a=zeros(6,12);fori=1:6a(i,i)=1;a(i,6+i)=1;endb=zeros(3,12);fori=1:3forj=1:2*iifrem(j,2)=0b(i,j)=-1/0.16;elseb(i,j)=-1/0.15;endendendc=zeros(3,12);fori=1:3forj=1:2*iifrem(j,2)=0c(i,j+6)=-1/0.14;elsec(i,j+6)=-1/0.12;endendendA=a(1,:);a(2,:);a(3,:);a(4,:);a(5,:);a(6,:);b(1,:);b(2,:

18、);c(1,:);c(2,:);bb=700;1500;300;400;1000;300;-4000;-12000;-1000;-6000;Aeq=b(3,:);c(3,:);beq=-15000;-11000;lb=zeros(12,1);x,fval,exitflag,output,lambda=linprog(f,A,bb,Aeq,beq,lb);程序2:clearclcf=5+1.3333;5+1.250;5+0.6667;5+0.625;5;5;5+1.6667;5+1.4286;5+0.8333;5+0.7143;5;5;a=zeros(6,12);fori=1:6a(i,i)=1;a(i,6+i)=1;endb=zeros(3,12);fori=1:3forj=1:2*iifrem(j,2)=0b(i,j)=-1/0.16;elseb(i,j)=-1/0.15;endendendc=zeros(3,12);fori=1:3forj=1:2*ii