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

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