第一次培訓(xùn)資料(共5頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 線性（整數(shù)）規(guī)劃線性規(guī)劃是中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個重要分支,它是輔助人們進(jìn)行科學(xué)管理的一種方法.在、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動中，提高經(jīng)濟(jì)效果是人們不可缺少的要求，而提高經(jīng)濟(jì)效果一般通過兩種途徑：一是技術(shù)方面的改進(jìn)，例如改善生產(chǎn)工藝，使用新設(shè)備和新型原材料.二是與計劃的改進(jìn)，即合理安排人力物力資源.線性規(guī)劃所研究的是：在一定條件下，合理安排人力物力等資源，使經(jīng)濟(jì)效果達(dá)到最好.一般地，求線性目標(biāo)函數(shù)在線性下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題。滿足線性約束條件的解叫做，由所有可行解組成的集合叫做可行域。、約束條件、目標(biāo)函數(shù)是線性規(guī)劃的三要素.只

2、要確定、約束條件、目標(biāo)函數(shù)就能建立相應(yīng)的線性規(guī)劃模型。示例某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客要求的長度進(jìn)行切割，稱為下料。假定進(jìn)貨時得到的原料鋼管長度都是19m。1）現(xiàn)有一客戶需要50根長4m、20根長6m和15根長8m的鋼管。應(yīng)如何下料最節(jié)?。?）零售商如果采用的不同切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本。所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外。該客戶除需要1）中的3種鋼管外，還要10根長5m的鋼管。應(yīng)如何下料最節(jié)??？問題分析：對于下料問題首先要確定采用哪些切割模式。所謂切割模式，是指按照顧客要求的長度在原料鋼管上安排切割的一種組合。例如，我們可以

3、將19m的鋼管切割成3根長4m的鋼管，余料為7m；或者將長19m的鋼管切割成長4m、6m和8m的鋼管各1根，余料為1m。顯然，可行的切割模式是很多的。其次，應(yīng)當(dāng)明確哪些切割模式是合理的。合理的切割模式通常還假設(shè)余料不應(yīng)大于或等于客戶需要鋼管的最小尺寸。例如，可以將長19m的鋼管切割成3根4m的鋼管是可行的，但余料為7m，可進(jìn)一步將7m的余料切割成4m鋼管（余料為3m），或者將7m的余料切割成6m鋼管（余料為1m）。經(jīng)過簡單的計 算可知，問題1）的 合理切割模式一共有7種，如表1所示模式4m鋼管根數(shù)6m鋼管根數(shù)8m鋼管根數(shù)余料/m140032310132013412035111160301700

4、22表1 鋼管下料問題1）的合理切割模式于是問題轉(zhuǎn)化為在滿足客戶需要的條件下，按照哪幾種合理的模式，每種模式切割多少根原料鋼管最為節(jié)省。而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)，一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最少。下面將對這兩個目標(biāo)分別討論。問題1） 用xi表示按照表1第i種模式（i=1,2,7）切割的原料鋼管的根數(shù)，若以切割后剩余的總余料量最小為目標(biāo)，則按照表1最后一列可得minZ1 = 3x1+x2+3x3+3x4+x5+x6+3x7 若以切割原料鋼管的總根數(shù)最少為目標(biāo)，則有MinZ2 = x1+x2+x3+x4+x5+x6+x7約束條件為客戶的需求，按照表1應(yīng)有4x1+3x2+

5、2x3+x4+x5 50x2+2x4+x5+3x6 20x3+x5+2x7 15最后，切割的原料鋼管的根數(shù)xi顯然應(yīng)當(dāng)是非負(fù)整數(shù)（用Z表示整數(shù)集合，Z+表示非負(fù)整數(shù)集合）：xi Z+ ， i=1,2,7 于是，問題1）歸結(jié)為在約束條件下，使目標(biāo)達(dá)到最小。顯然這是線性整數(shù)規(guī)劃模型。問題2） 如果按照問題1）的辦法處理，首先要通過枚舉法確定哪些切割模式是合理的，并從中選出不超過3種模式。而由于需求的鋼管規(guī)格增加到4種，所以枚舉法的工作量較大。下面介紹一種帶有普遍性的方法，可以同時確定切割模式和切割數(shù)量。同問題1）一樣，只使用合理的切割模式，其余料不應(yīng)大于3m（因為客戶需要的鋼管最小尺寸為4m，而本

6、題中參數(shù)都是整數(shù)）。由于不同切割模式不能超過3種，可以用用xi表示按照第i種模式（i=1,2,3）切割的原料鋼管的根數(shù)。又設(shè)使用第i種切割模式下每根原料鋼管生產(chǎn)長4m、5m、6m和8m的鋼管數(shù)量分別為r1i，r2i，r3i，r4i。僅以使用的原料總根數(shù)最少為目標(biāo)，即min x1+x2+x3滿足客戶需求的約束條件為r11x1+r12x2+r13x3 50 r21x1+r22x2+r23x3 10 r31x1+r32x2+r33x3 20 r41x1+r42x2+r43x3 15每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過19m，也不能少于16m（余料不能大于3m），于是164r

7、11+5r21+6r31+8r41 19164r12+5r22+6r32+8r42 19164r13+5r23+6r33+8r43 19 最后，加上非負(fù)整數(shù)約束：xi，rji Z+ ， i=1,2,3, j=1,2,3,4 于是，問題2）歸結(jié)為在在約束條件下，求xi和r1i，r2i，r3i，r4i（i=1,2,3）使目標(biāo)達(dá)到最小。當(dāng)然，這是一個整數(shù)非線性規(guī)劃模型。用LINGO求解整數(shù)規(guī)劃LINGO軟件用于線性或非線性規(guī)劃（無論是連續(xù)規(guī)劃還是整數(shù)規(guī)劃），因此包含了LINDO的功能。在LINGO中，所有的函數(shù)均以“”符號開始，如約束中g(shù)in(x1)表示x1為整數(shù)。鋼管下料問題1）的求解以切割后剩余

8、的總余料量最小為目標(biāo)，建立LINGO模型：min= 3*x1+x2+3*x3+3*x4+x5+x6+3*x7;4*x1+3*x2+2*x3+x4+x5 >=50; x2+2*x4+x5+3*x6 >= 20;x3+x5+2*x7 >= 15;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);即按照模式2切割12根原料鋼管，按照模式5切割15根原料鋼管，共27根，總余料量27m。顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式2和模式5的余料為1m），這會導(dǎo)致切割原料鋼管的總根數(shù)較多。以切割原

9、料鋼管的總根數(shù)最少為目標(biāo)，建立LINGO模型：min= x1+x2+x3+x4+x5+x6+x7;4*x1+3*x2+2*x3+x4+x5 >=50; x2+2*x4+x5+3*x6 >= 20;x3+x5+2*x7 >= 15;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);即按照模式2切割15根原料鋼管，按照模式5切割5根原料鋼管，按照模式7切割5根原料鋼管，共25根，總余料量35m。與上面得到的結(jié)果相比，總余料量增加了8m，但是所用的原料鋼管的總根數(shù)減少了2根，在余料沒有什么用途的情況下，通常選擇總根數(shù)最少

10、為目標(biāo)。鋼管下料問題2）的求解LINGO模型為：min=x1+x2+x3;r11*x1+r12*x2+r13*x3>=50; r21*x1+r22*x2+r23*x3>=10; r31*x1+r32*x2+r33*x3>=20; r41*x1+r42*x2+r43*x3>=15; 4*r11+5*r21+6*r31+8*r41<=19; 4*r12+5*r22+6*r32+8*r42<=19; 4*r13+5*r23+6*r33+8*r43<=19; 4*r11+5*r21+6*r31+8*r41>=16; 4*r12+5*r22+6*r32+8

11、*r42>=16;4*r13+5*r23+6*r33+8*r43>=16;x1+x2+x3>=26;x1+x2+x3<=31;x1>=x2;x2>=x3;gin(x1);gin(x2);gin(x3);gin(r11);gin(r12);gin(r13);gin(r21);gin(r22);gin(r23);gin(r31);gin(r32);gin(r33);gin(r41);gin(r42);gin(r43);即按照模式1，2，3分別切割10根，10根，8根原料鋼管，使用原料鋼管總根數(shù)為28根。第一種切割模式下一根原料鋼管切割成3根4m鋼管和1根6m鋼管；第二種切割模式下一根原料鋼管切割成2根4m鋼管，1根5m鋼管和1根6m鋼管；第三種切割模式下一根原料鋼管切割成2根8m鋼管。思考題某投資公司擬制定今后5年的投資計劃，初步考慮下面四個投資項目：項目A：從第1年到第4年每年年初可以投資，于次年年末收回成本，并可獲利潤15%；項目B：第3年年初可以投資，到第5年年末可以收回成本，并獲得利潤25%，但為了保證足夠的資金流動，規(guī)定該項目的投資金額上限為不超過總金額的40%；項目C：第2年年初可以投資，到第5年年末可以收回成本，并獲得利潤40%，但公司規(guī)定該項目的最大投資金額不超過總金額的30%；項目D：5年內(nèi)每年年初可以購買公債，于