線性規(guī)劃模型PPT課件

.,1,第1節(jié)線性規(guī)劃問題與模型,一、線性規(guī)劃模型從招聘總經理談起,.,2,泰山工廠生產狀況,泰山工廠可以生產兩種產品出售，需要三種資源，已知各產品的利潤、各資源的限量和各產品的資源消耗系數(shù)如下表：目前生產現(xiàn)狀：不生產產品A，生產產品B每天30，獲利3600,.,3,招聘總經理！,約翰：我應聘！在現(xiàn)有資源狀況下，我可以使利潤達到4280！方案是：生產A產品20，生產B產品24可行性：9*20+4*24=2760X(2)不是。,(3)選X1從0，X5=0,X1=min(6/1,36/3,1)=6X1進基，X3出基。,.,47,B3=(P1P4P2),令X3=X5=0X(3)=(6,12,0,18,0)TZ(3)=840,.,48,(2)150X(3)不是,(3)選X5從0，X3=0,X5=min(18/2,12/1/2)=9X5進基，X4出基。,.,49,B4=(P1P5P2),令X3=X4=0X(4)=(15,15/2,0,0,9)TZ(4)=975,.,50,0,(0,0),X2,X1,.,51,兩個重要公式：,.,52,當LP的數(shù)學模型為一般型時,兩個重要公式形如：,.,53,B=(P1P2Pm)=I,.,54,當Xj=0(j=m+1,n)時,.,55,1.5.2單純形法原理,.,56,此時，B=(P1P2Pm),對應的基本可行解為,.,57,定理1：對解X(1)，若檢驗數(shù)j(j=m+1,n)全部0，則X(1)為最優(yōu)解。,定理2：對X(1)，若有某個非基變量Xm+km+k0且相應的Pm+k=(a1m+k,amm+k)T0，則原問題無有限最優(yōu)解。,.,58,定理2證明,X(2)=(b1-a1m+k,bm-amm+k,0,0)T,AX(2)=bX(2)0,Z=Z0+m+k,當時Z,.,59,初始基B1=(P3P4),X(1)=(0,0,10,15)TZ(1)=0,.,60,選中X1從0，X2=0,求X1，X1+,Z+,.,61,換基迭代公式：,(1)、決定換入變量：,(2)、決定換出變量：,bi-aim+kXm+k0(i=1,2,m),.,62,則Xr為換出變量。,.,63,定理3：經單純形法得到的,.,64,若否，因為P1,Pm線性無關,.,65,X(2)是基本解，且是可行解,.,66,單純形法基本步驟,(1)、定初始基，初始基本可行解,(3)、若有k0，Pk全0，停，沒有有限最優(yōu)解；否則轉(4),(2)、對應于非基變量檢驗數(shù)j全0。若是，停，得到最優(yōu)解；若否，轉(3)。,.,67,定Xr為換出變量，arm+k為主元。,由最小比值法求：,.,68,轉(2),(5)、以arm+k為中心，換基迭代,.,69,證明可用歸納法（略）,X在邊界上,X在內部,(01),.,70,證明：設X(1),X(k)為可行域頂點，若X*不是頂點，但maxZ=CX*X*=,定理2：可行域有界，最優(yōu)值必可在頂點得到,iX(i),i=1,0i1,CX*=,iCX(i),iCX(m),=CX(m),設CX(m)Max(CX(i),1ik,.,71,Z(2)-Z(1)=(Cm+k-Zm+k)=m+k0,.,72,1.5.3單純形表,.,73,.,74,本問題的最優(yōu)解X=(15,15/2,0,0,9)TZ=975,.,75,幾點說明：,(1)、例maxZ=X1+2X2,.,76,.,77,.,78,X(1)=(2,3)Z(1)=8,X(2)=(4,2)Z(2)=8,無窮多解,.,79,.,80,.,81,判定定理1：基本可行解X，當全部j0時，X為最優(yōu)解。,判定定理2：對可行基B，當某k0，且Pk=(a1kamk)T0，則原問題無有限最優(yōu)解。,.,82,.,83,.,84,退化解,X*=(0,3/2,0,1/2,0)T,Zmax=18,.,85,(P1P2P3)(P4P2P3)(P4P5P3)(P6P5P3)(P6P7P3)(P1P7P3)(P1P2P3),.,86,(4)例：,.,87,.,88,.,89,本問題無界。,.,90,1.5.4初始基本可行解的求法,(一)、大M法：判定無解條件：當進行到最優(yōu)表時，仍有人工變量在基中，且0，則說明原問題無可行解。,.,91,例1：,.,92,.,93,.,94,.,95,.,96,.,97,解題過程：,.,98,兩階段法原理：,(1)、輔助問題的基本可行解X(0)為最優(yōu)解，對應最小值=0則X(0)的前n個分量是原問題的基本可行解。,.,99,證明：,.,100,(2)、原問題有可行解時，輔助問題最優(yōu)值=0。,.,101,maxZ=-X1+2X2,X1+X22-X1+X21X23X1X20,例2：,.,102,第(1)階段：,.,103,.,104,.,105,例3：,.,106,第(1)階段：,.,107,.,108,.,109,第1階段最優(yōu)基B*min=*,(1)、*0,.,110,1)arj全=0()式多余方程,2)arj有0元，設為ars0,以ars為主元，換基迭代，最后得到,.,111,例4、求,.,112,一,二,.,113,CBXB000005/205/40X21011/4-2/31/20-1/21y200000-3/21-1/40X12101/20101/6,第一階段,三,-40-30X1X2X3X4CBXB-800-100X21011/4-2/3-4X42101/20,第二階段,.,114,的特殊情況:第1階段結束時,有人工變量在基中取0,但Xi系數(shù)全為0,此方程為多余方程。,.,115,例5、求,.,116,一,二,.,117,.,118,-40-30X1X2X3X4CBXB-800000X21010-2/3-3X300010-4X121000,第二階段,的特殊情況，可將人工變量換出,.,119,單純形法小結：,1)、標準型中有單位基。,.,120,建模有問題,5)、退化解問題,.,121,.,122,第三章運籌學優(yōu)化模型,大連海事大學劉巍,.,123,第3節(jié)對偶線性規(guī)劃與影子價格,一、對偶問題再談招聘總經理,.,124,泰山工廠生產狀況,泰山工廠可以生產兩種產品出售，需要三種資源，已知各產品的利潤、各資源的限量和各產品的資源消耗系數(shù)如下表：目前生產現(xiàn)狀：不生產產品A，生產產品B每天30，獲利3600,.,125,招聘總經理！,約翰：我應聘！在現(xiàn)有資源狀況下，我可以使利潤達到4280！方案是：生產A產品20，生產B產品24可行性：9*20+4*24=2763604*20+5*24=2003*20+10*24=300,.,126,怎么達到的？,約翰使用了運籌學中的線性規(guī)劃模型問題：如何安排生產計劃，使得獲利最多？步驟：1、確定決策變量：設生產A產品x1kg,B產品x2kg2、確定目標函數(shù)：maxZ=70X1+120X23、確定約束條件：設備約束9X1+4X2360人力約束4X1+5X2200原材料約束3X1+10X2300非負性約束X10X20,.,127,例1圖示,.,9080604020,020406080100,x1,x2,9x1+4x2360,4x1+5x2200,3x1+10 x2300,A,B,C,D,E,F,G,H,I,Z=70 x1+120 x2,.,128,X1=20,x2=24對應的生產方案：生產A產品20生產B產品24獲利：70*20+120*24=4280,.,129,問題的最優(yōu)解,*最優(yōu)解如下*目標函數(shù)最優(yōu)值為:4280變量最優(yōu)解相差值-x1200 x2240約束松弛/剩余變量對偶價格-18402013.6305.2目標函數(shù)系數(shù)范圍:變量下限當前值上限-x1367096x287.5120233.333常數(shù)項數(shù)范圍:約束下限當前值上限-1276360無上限2150200226.9233227.586300400,.,130,再談招聘總經理,約翰作為總經理將泰山工廠經營的很好了！湯姆來競爭了！競爭口號：不裁員！不減薪！不加班！提高利潤5%！,.,131,可能嗎？,目前約翰的經營已經是資源的最佳利用了！湯姆還有什么絕招增加利潤呢？,.,132,這個問題涉及到：（1）線性規(guī)劃的對偶問題（2）影子價格概念,.,133,原來問題的最優(yōu)解,*最優(yōu)解如下*目標函數(shù)最優(yōu)值為:4280變量最優(yōu)解相差值-x1200 x2240約束松弛/剩余變量對偶價格-18402013.6305.2目標函數(shù)系數(shù)范圍:變量下限當前值上限-x1367096x287.5120233.333常數(shù)項數(shù)范圍:約束下限當前值上限-1276360無上限2150200226.9233227.586300400,.,134,對偶性是線性規(guī)劃問題的最重要的內容之一。每一個線性規(guī)劃（LP）必然有與之相伴而生的另一個線性規(guī)劃問題，即任何一個求maxZ的LP都有一個求minZ的LP。其中的一個問題叫“原問題”，記為“P”，另一個稱為“對偶問題”，記為“D”。,例：資源的合理利用問題已知資料如表所示，問應如何安排生產計劃使得既能充分利用現(xiàn)有資源有使總利潤最大？,對偶問題的提出,.,135,下面從另一個角度來討論這個問題：,假定：該廠的決策者不是考慮自己生產甲、乙兩種產品，而是將廠里的現(xiàn)有資源用于接受外來加工任務，只收取加工費。試問該決策者應制定怎樣的收費標準（合理的）？,.,136,分析問題：1、每種資源收回的費用不能低于自己生產時的可獲利潤；2、定價又不能太高，要使對方能夠接受。,.,137,一般而言，W越大越好，但因需雙方滿意，故,為最好。,該問題的數(shù)學模型為：,.,138,模型對比：,.,139,對稱形式：互為對偶(LP)Maxz=cTx(DP)Minf=bTys.t.Axbs.t.ATycx0y0“Max-”“Min-”一般形式：若一個問題的某約束為等式，那么對應的對偶問題的相應變量無非負限制；反之，若一個問題的某變量無非負限制，那么對應的對偶問題的相應約束為等式。,對偶定義,.,140,對偶問題,令y1=y1-y1,.,141,解：,.,142,(3)、原問題第k個約束為等式，對偶問題第k個變量是自由變量。原問題第k個變量是自由變量，則對偶問題第k個約束為等式約束。,.,143,對偶關系對應表,.,144,例2、寫對偶規(guī)劃,minZ=4X1+2X2-3X3,-X1+2X262X1+3X39X1+5X2-2X3=4X2,X30,.,145,maxW=6y1+9y2+4y3,-y1+2y2+y3=42y1+5y323y2-2y3-3y10,y20,y3自由,.,146,minZ=4X1+2X2-3X3,X1-2X2-62X1+3X39X1+5X2-2X3=4X2,X30,或將原問題變形為,.,147,maxW=-6y1+9y2+4y3,y1+2y2+y3=4-2y1+5y323y2-2y3-3y1,y20,y3自由,對偶規(guī)劃,.,148,產品A，B產量X1，X2，Z為利潤,例1、,.,149,X=(8,24)TZ=184,.,150,.,151,y=(2/9,13/9),Z=184,.,152,觀察結論:,一對對偶問題都有最優(yōu)解，且目標函數(shù)值相等。,最優(yōu)表中有兩個問題的最優(yōu)解。,.,153,1.7.2對偶問題解的性質,.,154,定理1、(弱對偶定理),.,155,推論2、(P)有可行解,但無有限最優(yōu)解，則(D)無可行解。,推論1、(P),(D)都有可行解，則必都有最優(yōu)解。,.,156,.,157,.,158,.,159,定理4(松緊定理)互補松弛性,原問題,.,160,對偶問題,.,161,.,162,.,163,.,164,.,165,例：,min=5y1+y2,.,166,(P)最優(yōu)解(0,9,0,4,64),=9,.,167,.,168,.,169,解：(D)為,.,170,將y1，y2代入，知,為嚴格不等式,x2=x3=x4=0,x=(1,0,0,0,1)TZ=5,.,171,小結：原問題與對偶問題的關系,互為對偶最優(yōu)解的存在性相同。目標函數(shù)值相等。解互為影子價格。,.,172,影子價格在管理決策中的作用,.,173,原來問題的最優(yōu)解,*最優(yōu)解如下*目標函數(shù)最優(yōu)值為:4280變量最優(yōu)解相差值-x1200 x2240約束松弛/剩余變量對偶價格-18402013.6305.2目標函數(shù)系數(shù)范圍:變量下限當前值上限-x1367096x287.5120233.333常數(shù)項數(shù)范圍:約束下限當前值上限-1276360無上限2150200226.9233227.586300400,.,174,4.影子價格可以告訴決策者，用多大的代價增加資源才是合算的。如：第二種資源增加1單位能使收益增加13.6，如果增加這種資源的代價大于13.6就不劃算了。,3.影子價格可以告訴決策者，增加哪一種資源對增加經濟效益最有利。如：本例中三種資源的價格為0，13.6，5.2，說明首先應增加第二種資源，因為相比之下，它能使收益增加得更多。,.,175,5.影子價格可以告訴決策者應如何考慮新產品的價格。如：企業(yè)要生產一種新產品時，如果每件新產品耗用的這三種資源數(shù)量是1，2，3單位，則新產品的定價一定要大于才能增加公司的收益，如售價低于42.8的話，生產是不劃算的。,.,176,湯姆的決策,設備資源的影子價格為0，不需要添加！人力資源的影子價格為13.6，而在市場上人力資源的價格是5，因此，招聘人力26人！原材料的影子價格為5.2，可是市場上這種材料價格是5.9，買入不上算！不增加！,.,177,新的線型規(guī)劃模型,1、確定決策變量：設生產A產品x1kg,B產品x2kg2、確定目標函數(shù)：maxZ=70X1+120X23、確定約束條件：設備約束9X1+4X2360人力約束4X1+5X2226原材料約束3X1+10X2300非負性約束X10X20,.,178,*最優(yōu)解如下*目標函數(shù)最優(yōu)值為:4633.6變量最優(yōu)解相差值-x130.40 x220.880約束松弛/剩余變量對偶價格-12.8802013.6305.2目標函數(shù)系數(shù)范圍:變量下限當前值上限-x1367096x287.5120233.333常數(shù)項數(shù)范圍:約束下限當前值上限-1357.12360無上限2150226226.9233297.517300452,.,179,新的生產計劃：生產A產品30.4生產B產品20.88獲利4633.6相比約翰的經營增加純利潤353.6-130=223！提高5.2%！,.,180,熱烈祝賀湯姆競聘泰山工廠總經理成功！,.,181,問題,可不可以再進一步增加人力資源？從而能否用這種方式使利潤進一步提高？,.,182,將人力資源增加到250人！,1、確定決策變量：設生產A產品x1kg,B產品x2kg2、確定目標函數(shù)：maxZ=70X1+120X23、確定約束條件：設備約束9X1+4X2360人力約束4X1+5X2250原材料約束3X1+10X2300非負性約束X10X20,.,183,計算結果,*最優(yōu)解如下*目標函數(shù)最優(yōu)值為:4646.11變量最優(yōu)解相差值-x130.7690 x220.7690約束松弛/剩余變量對偶價格-104.359223.07703010.256目標函數(shù)系數(shù)范圍:變量下限當前值上限-x13670270 x231.111120233.333常數(shù)項數(shù)范圍:約束下限當前值上限-11203604322226.923250無上限3120300362.069,.,184,效益分析,利潤4646.11增加4646.11-5*50=4391.11相比人力資源為226時的利潤4391.11-4633.6=-142.49,.,185,注意！將人力資源增加到227人時,1、確定決策變量：設生產A產品x1kg,B產品x2kg2、確定目標函數(shù)：maxZ=70X1+120X23、確定約束條件：設備約束9X1+4X2360人力約束4X1+5X2227原材料約束3X1+10X2300非負性約束X10X20,.,186,人力資源為227時最優(yōu)解,*最優(yōu)解如下*目標函數(shù)最優(yōu)值為:4646.11變量最優(yōu)解相差值-x130.7690 x220.7690約束松弛/剩余變量對偶價格-104.3592.07703010.256目標函數(shù)系數(shù)范圍:變量下限當前值上限-x13670270 x231.111120233.333常數(shù)項數(shù)范圍:約束下限當前值上限-1120360360.242226.923227無上限3120300300.207,.,187,原來是這樣??！,此時人力資源的影子價格為0！再增加也不會帶來新的利潤！,.,188,新的問題,靈敏度分析且聽下回分解,.,189,.,190,第三章運籌學優(yōu)化模型,大連海事大學劉巍,.,191,第3節(jié)對偶線性規(guī)劃與影子價格(續(xù)）,靈敏度分析湯姆總經理的失誤,.,192,泰山工廠生產狀況,泰山工廠可以生產兩種產品出售，需要三種資源，已知各產品的利潤、各資源的限量和各產品的資源消耗系數(shù)如下表：目前生產現(xiàn)狀：不生產產品A，生產產品B每天30，獲利3600,.,193,招聘總經理！,約翰：我應聘！在現(xiàn)有資源狀況下，我可以使利潤達到4280！方案是：生產A產品20，生產B產品24可行性：9*20+4*24=2760csMinj/asjasj0brMin-bi/airair0,靈敏度分析（續(xù)）,.,222,例、上例最優(yōu)單純形表如下00.250這里B-1=-20.51各列分別對應b1、b2、b3的單一0.5-0.1250變化。因此，設b1增加4，則x1,x5,x2分別變?yōu)椋?+0*4=4，4+(-2)*4=-40，2+0.5*4=4用對偶單純形法進一步求解，可得：x*=(4,3,2,0,0)Tf*=17,靈敏度分析（續(xù)）,.,223,增加一個變量增加變量xn+1則有相應的pn+1，cn+1。那么，計算出B-1pn+1n+1=cn+1-criarin+1填入最優(yōu)單純形表，若n+10則最優(yōu)解不變；否則，進一步用單純形法求解。例、前例增加x6，p6=(2,6,3)T，c6=5。計算得到,靈敏度分析（續(xù)）,用單純形法進一步求解，可得：x*=(1,1.5,0,0,0,2)Tf*=16.5,.,224,增加一個約束增加約束一個之后，應把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入1個新的非負變量（原約束若是小于等于形式可引入非負松弛變量，否則引入非負人工變量），并通過矩陣行變換把對應基變量的元素變?yōu)?，進一步用單純形法或對偶單純形法求解。例、前例增加3x1+2x215，原最優(yōu)解不滿足這個約束。于是,靈敏度分析（續(xù)）,.,225,A中元素發(fā)生變化（只討論N中某一列變化情況）與增加變量xn+1的情況類似，假設pj變化。那么，重新計算出B-1pjj=cj-criarij填入最優(yōu)單純形表，若j0則最優(yōu)解不變；否則，進一步用單純形法求解。,靈敏度分析（續(xù)）,可得最優(yōu)解：x*=(3.2,0.8,0,0,2.4)Tf*=15.2,.,226,靈敏度分析（續(xù)）,靈敏度分析小結：1Ci發(fā)生變化2Bj發(fā)生變化3增加一個變量4增加一個約束5A中元素發(fā)生變化,返回目錄,.,227,.,228,第三章運籌學優(yōu)化模型,大連海事大學劉巍,.,229,第4節(jié)線性規(guī)劃應用,學以致用，培養(yǎng)學生“用數(shù)學的意識是本節(jié)的重要目的學習線性規(guī)劃的有關知識其最終目的就是運用它們去解決一些生產、生活中問題,.,230,線性規(guī)劃的應用,1人力資源分配的問題2生產計劃的問題3套裁下料問題4配料問題5投資問題,.,231,人力資源分配的問題,例1某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數(shù)如下：設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務人員?,.,232,人力資源分配的問題,解：設xi表示第i班次時開始上班的司機和乘務人員數(shù),這樣我們建立如下的數(shù)學模型。目標函數(shù)：Minx1+x2+x3+x4+x5+x6約束條件：s.t.x1+x660 x1+x270 x2+x360 x3+x450 x4+x520 x5+x630 x1,x2,x3,x4,x5,x60,.,233,人力資源分配的問題,例2一家中型的百貨商場，它對售貨員的需求經過統(tǒng)計分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作5天，休息兩天，并要求休息的兩天是連續(xù)的。問應該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？,.,234,人力資源分配的問題,解：設xi(i=1,2,7)表示星期一至日開始休息的人數(shù),這樣我們建立如下的數(shù)學模型。目標函數(shù)：Minx1+x2+x3+x4+x5+x6+x7約束條件：s.t.x1+x2+x3+x4+x528x2+x3+x4+x5+x615x3+x4+x5+x6+x724x4+x5+x6+x7+x125x5+x6+x7+x1+x219x6+x7+x1+x2+x331x7+x1+x2+x3+x428x1,x2,x3,x4,x5,x6,x70,.,235,2生產計劃的問題,例3某公司面臨一個是外包協(xié)作還是自行生產的問題。該公司生產甲、乙、丙三種產品，都需要經過鑄造、機加工和裝配三個車間。甲、乙兩種產品的鑄件可以外包協(xié)作，亦可以自行生產，但產品丙必須本廠鑄造才能保證質量。數(shù)據(jù)如表。問：公司為了獲得最大利潤，甲、乙、丙三種產品各生產多少件？甲、乙兩種產品的鑄造中，由本公司鑄造和由外包協(xié)作各應多少件？,.,236,生產計劃的問題,解：設x1,x2,x3分別為三道工序都由本公司加工的甲、乙、丙三種產品的件數(shù)，x4,x5分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產品的件數(shù)。求xi的利潤：利潤=售價-各成本之和產品甲全部自制的利潤=23-(3+2+3)=15產品甲鑄造外協(xié)，其余自制的利潤=23-(5+2+3)=13產品乙全部自制的利潤=18-(5+1+2)=10產品乙鑄造外協(xié)，其余自制的利潤=18-(6+1+2)=9產品丙的利潤=16-(4+3+2)=7可得到xi（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。,.,237,生產計劃的問題,通過以上分析,可建立如下的數(shù)學模型:目標函數(shù)：Max15x1+10 x2+7x3+13x4+9x5約束條件：5x1+10 x2+7x380006x1+4x2+8x3+6x4+4x5120003x1+2x2+2x3+3x4+2x510000 x1,x2,x3,x4,x50,.,238,生產計劃的問題,例4永久機械廠生產、三種產品，均要經過A、B兩道工序加工。設有兩種規(guī)格的設備A1、A2能完成A工序；有三種規(guī)格的設備B1、B2、B3能完成B工序?？稍贏、B的任何規(guī)格的設備上加工；可在任意規(guī)格的A設備上加工，但對B工序，只能在B1設備上加工；只能在A2與B2設備上加工。數(shù)據(jù)如表。問：為使該廠獲得最大利潤，應如何制定產品加工方案？,.,239,生產計劃的問題,解：設xijk表示第i種產品，在第j種工序上的第k種設備上加工的數(shù)量。建立如下的數(shù)學模型:s.t.5x111+10 x2116000（設備A1）7x112+9x212+12x31210000（設備A2）6x121+8x2214000（設備B1）4x122+11x3227000（設備B2）7x1234000（設備B3）x111+x112-x121-x122-x123=0（產品在A、B工序加工的數(shù)量相等）x211+x212-x221=0（產品在A、B工序加工的數(shù)量相等）x312-x322=0（產品在A、B工序加工的數(shù)量相等）xijk0,i=1,2,3;j=1,2;k=1,2,3,.,240,生產計劃的問題,目標函數(shù)為計算利潤最大化，利潤的計算公式為：利潤=（銷售單價-原料單價）*產品件數(shù)之和-（每臺時的設備費用*設備實際使用的總臺時數(shù)）之和。這樣得到目標函數(shù)：Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312300/6000(5x111+10 x211)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).經整理可得：Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123,.,241,3套裁下料問題,例5某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應如何下料，可使所用原料最省？解：共可設計下列5種下料方案，見下表,設x1,x2,x3,x4,x5分別為上面5種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學模型。目標函數(shù)：Minx1+x2+x3+x4+x5約束條件：s.t.x1+2x2+x41002x3+2x4+x51003x1+x2+2x3+3x5100 x1,x2,x3,x4,x50,.,242,用計算軟件計算得出最優(yōu)下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；x3=0；x4=50；x5=0；只需90根原材料就可制造出100套鋼架。注意：在建立此類型數(shù)學模型時，約束條件用大于等于號比用等于號要好。因為有時在套用一些下料方案時可能會多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號，這一方案就不是可行解了。,套裁下料問題,.,243,4配料問題,例6某工廠要用三種原料1、2、3混合調配出三種不同規(guī)格的產品甲、乙、丙，數(shù)據(jù)如右表。問：該廠應如何安排生產，使利潤收入為最大？,解：設xij表示第i種（甲、乙、丙）產品中原料j的含量。這樣我們建立數(shù)學模型時，要考慮：對于甲：x11，x12，x13；對于乙：x21，x22，x23；對于丙：x31，x32，x33；對于原料1：x11，x21，x31；對于原料2：x12，x22，x32；對于原料3：x13，x23，x33；目標函數(shù)：利潤最大，利潤=收入-原料支出約束條件：規(guī)格要求4個；供應量限制3個。,.,244,配料問題,利潤=總收入-總成本=甲乙丙三種產品的銷售單價*產品數(shù)量-甲乙丙使用的原料單價*原料數(shù)量，故有目標函數(shù)Max50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33約束條件：從第1個表中有：x110.5(x11+x12+x13)x120.25(x11+x12+x13)x210.25(x21+x22+x23)x220.5(x21+x22+x23),.,245,配料問題,從第2個表中，生產甲乙丙的原材料不能超過原材料的供應限額，故有(x11+x21+x31)100(x12+x22+x32)100(x13+x23+x33)60通過整理，得到以下模型：,.,246,配料問題,例6（續(xù)）目標函數(shù)：Maxz=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33約束條件：s.t.0.5x11-0.5x12-0.5x130（原材料1不少于50%）-0.25x11+0.75x12-0.25x130（原材料2不超過25%）0.75x21-0.25x22-0.25x230（原材料1不少于25%）-0.5x21+0.5x22-0.5x230（原材料2不超過50%）x11+x21+x31100(供應量限制）x12+x22+x32100(供應量限制）x13+x23+x3360(供應量限制）xij0,i=1,2,3;j=1,2,3,.,247,配料問題,例7.汽油混合問題。一種汽油的特性可用兩種指標描述，用“辛烷數(shù)”來定量描述其點火特性，用“蒸汽壓力”來定量描述其揮發(fā)性。某煉油廠有1、2、3、4種標準汽油，其特性和庫存量列于表4-6中，將這四種標準汽油混合，可得到標號為1，2的兩種飛機汽油，這兩種汽油的性能指標及產量需求列于表4-7中。問應如何根據(jù)庫存情況適量混合各種標準汽油，既滿足飛機汽油的性能指標，又使2號汽油滿足需求，并使得1號汽油產量最高？,表4-6,表4-7,.,248,配料問題,解：設xij為飛機汽油i中所用標準汽油j的數(shù)量(L)。目標函數(shù)為飛機汽油1的總產量：,庫存量約束為：,產量約束為飛機汽油2的產量：,由物理中的分壓定律，可得有關蒸汽壓力的約束條件：,同樣可得有關辛烷數(shù)的約束條件為：,.,249,配料問題,綜上所述，得該問題的數(shù)學模型為：,.,250,配料問題,由管理運籌學軟件求解得：,.,251,5投資問題,例8某部門現(xiàn)有資金200萬元，今后五年內考慮給以下的項