清華大學(xué)運籌學(xué)綜合習(xí)題解析.ppt

例1maxz=3x1+x2+3x3s.t.2x1+x2+x32x1+2x2+3x352x1+2x2+x36xi0,i=1,2,3解標(biāo)準化后，寫出單純形表,XBbx1x2x3x4x5x6x422111001x551230105/2x6622100130313000,x222111002x51-301-2101/2x62-20-1-201-2102-100,XBbx1x2x3x4x5x6x215103-101/5x31-301-210-x63-500-411-7003-20,x11/511/503/5-1/50 x38/503/50-1/52/50 x64011-101-27/50-7/50-6/5-3/50,最優(yōu)解為(1/5,0,8/5,0,0,4)Tmax=27/5,例2.max=3x1+2x1+x3-x4s.t.3x1+2x2+x3=15,5x1+x2+2x3=20 x1+2x2+x3+x4=10 x1,x2,x3,x40,解引入人工變量把原問題變成下列形式max=3x1+2x1+x3-x4-M(x5+x6)s.t.3x1+2x2+x3+x5=155x1+x2+2x3+x6=20,最優(yōu)解為(5/2,5/2,5/2,0,0,0)T,max=15,原問題的解為(5/2,5/2,5/2,0)T,max=15.,例3max=2x1+x2+3x3+x4s.t.x1+x2+x3+x452x1-x2+3x3=-4x1-x3+x41x10,x2,x4無約束,x30,min=5y1+4y2-y3s.t.y1-2y2-y32y1+y2=1y1+3y2-y33y1+y3=1,其對偶問題為,y10，y2無約束，y30,2020/6/5,5,令,設(shè)原問題為,為原問題的一最優(yōu)解,則,為對偶問題,的一最優(yōu)解,2020/6/5,6,例4MaxZ=40X1+50X2,X1+2X2303X1+2X2602X224X1,X20,s.t,y1y2y3,MinW=30y1+60y2+24y3,y1+3y2+0y3402y1+2y2+2y350y1,y2,y30,s.t,MaxW=-30y1-60y2-24y3,y1+3y2+0y3y4=402y1+2y2+2y3y5=50y1,y2,y3,y4,y50,s.t,2020/6/5,7,MaxW=-30y1-60y2-24y3+0(y4+y5)-M(y6+y7),y1+3y2+0y3y4+y6=402y1+2y2+2y3y5+y7=50y1,y2,y3,y4,y50,s.t,2020/6/5,8,2020/6/5,9,例5、MaxZ=40X1+50X2,X1+2X2303X1+2X2602X224X1,X20,s.t,X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1X50,s.t,2020/6/5,10,例6.求解下列線性規(guī)劃問題max=x1+2x2+3x3+4x4s.t.x1+2x2+2x3+3x4202x1+x2+3x3+2x420 xj0,j=1,2,3,4,解其對偶問題為min=20y1+20y2s.t.y1+2y212y1+y222y1+3y233y1+2y24y1,y20,(1.2,0.2),1,2,1,2,.,.,y1,y2,用圖解法得最優(yōu)解y1=1.2,y2=0.2,根據(jù)松緊定理，原問題的最優(yōu)解必滿足XS=0及YSX=0,及(y3,y4,y5,y6)=0,x5(y1,y2)x6=0,x1x2x3x4,將y1=1.2,y2=0.2代入對偶問題的約束條件，得y30,y40,所以x1=x2=0,又因y10,y20。所以x5=x6=0，即原問題為等式約束,x1=x2=0 x1+2x2+2x3+3x4=202x1+x2+3x3+2x4=20,即x1=x2=0，x3=4,x4=4原問題的最優(yōu)解為(0,0,4,4)T,例7.max=x1+4x2+3x3s.t.2x1+2x2+x34x1+2x2+2x36xj0,對偶問題為min=4y1+6y2s.t.2y1+y212y1+2y24,y1+2y23y1,y20,初始單純形表為422110612201014300,對偶問題的基本解為y1=0,y2=0，ys1=-1，ys2=-4，ys3=-3,其最終表為,13/2101-1/2210111-102001-1,由原問題的最終表可知，y1=1,y2=1(最優(yōu)解)，ys1=2,2020/6/5,17,例8用單純形法來求解目標(biāo)規(guī)劃Minf=P1（d1+d2+)+P2d3+P3d4-+P4（d1-+2d2-)s.t.x1+d1-d1+=9x2+d2-d2+=84x1+6x2+d3-d3+=6012x1+18x2+d4-d4+=252x1,x2,di-,di+0,i=1,2,3,4.,2020/6/5,18,解:首先處理初始基本可行解對應(yīng)的各級檢驗數(shù)。,2020/6/5,19,（1）k=1，在初始單純形表中基變量為（d1-,d2-,d3-,d4-)T=（9，8，60，252)T；（2）因為P1與P2優(yōu)先級的檢驗數(shù)均已經(jīng)為非負，所以這個單純形表對P1與P2優(yōu)先級是最優(yōu)單純形表；（3）下面考慮P3優(yōu)先級，第二列的檢驗數(shù)為-18，此為進基變量，計算相應(yīng)的比值bi/aij寫在列。通過比較，得到d2-對應(yīng)的比值最小，于是取a22（標(biāo)為*號）為主元進行矩陣行變換得到新的單純形表；,2020/6/5,20,（4）下面繼續(xù)考慮P3優(yōu)先級，第一列的檢驗數(shù)為-12，此為進基變量，計算相應(yīng)的比值bi/aij，得到d3-對應(yīng)的比值最小，于是取a31（標(biāo)為*號）為轉(zhuǎn)軸元進行矩陣行變換得到新的單純形表；,2020/6/5,21,（5）當(dāng)前的單純形表各優(yōu)先級的檢驗數(shù)均滿足了上述條件,故為最優(yōu)單純形表。我們得到最優(yōu)解x1=3，x2=8。,例9某公司生產(chǎn)A,B兩種塑料布，這兩種產(chǎn)品每小時的產(chǎn)量均為1000米(寬度為2米)，該公司每天采用兩班制生產(chǎn)，每周最大工作時間為80小時。按預(yù)測，A,B兩種塑料布每周市場的最大銷售量分別為70,000米和45,000米，A種塑料布每米的利潤為2.5元，B種塑料布每米的利潤是1.5元。試確定公司每周A,B兩種塑料布的生產(chǎn)量x1和x2(單位:千米)，公司的目標(biāo)是：,P1:避免每周80小時生產(chǎn)能力的過少利用；,P2:加班時間限制在10小時以內(nèi)；,P3:A,B兩種塑料布的每周產(chǎn)量分別達到70,000米和45,000米，但不得超出。其權(quán)系數(shù)依它們每米的利潤為準；,P4:盡量減少加班。,解這個問題的目標(biāo)規(guī)劃模型。,1.每周可利用的工作時間約束,x1+x2+d1-d1+=80,2.每周可利用的加班時間約束,d1+d11-d11+=10,3.每周塑料布產(chǎn)量約束,x1+d2=70,x2+d3=45,權(quán)系數(shù)為2.5:1.5=5:3,目標(biāo)規(guī)劃模型如下：,min=P1d1+P2d11+P3(5d2+3d3)+P4d1+,s.t.x1+x2+d1-d1+=80,x1+d2=70,x2+d3=45,d1+d11d11+=10,x1,x2,di,di+0(i=1,2,3,11),解:用單純形法解對應(yīng)的(LP)問題,如表所示,獲得最優(yōu)解。,初始表,最終表,例10用分支定界法求解整數(shù)規(guī)劃問題（單純形法）,x1=13/4x2=5/2Z(0)=59/414.75選x2進行分枝，即增加兩個約束，2x23有下式：,分別在(LP1)和(LP2)中引入松弛變量x5和x6，將新加約束條件加入上表計算。即x2+x5=2,x2+x6=3得下表:,x1=7/2,x2=2Z(1)=14.5繼續(xù)分枝，加入約束3x14,LP1,LP2,x1=5/2,x2=3Z(2)=13.5Z(2)Z(1)先不考慮分枝,接(LP1)繼續(xù)分枝，加入約束4x13，有下式：,分別引入松弛變量x7和x8，然后進行計算。,x1=3,x2=2Z(3)=13找到整數(shù)解，問題已探明，停止計算。,LP3,x1=4x2=1Z(4)=14找到整數(shù)解，問題已探明，停止計算。,LP4,樹形圖如下：,LP1x1=7/2,x2=2Z(1)29/2=14.5,LPx1=13/4,x2=5/2Z(0)59/4=14.75,LP2x1=5/2,x2=3Z(2)27/2=13.5,LP3x1=3,x2=2Z(3)13,LP4x1=4,x2=1Z(4)14,x22,x23,x13,x14,#,#,#,例11：用割平面法求解數(shù)規(guī)劃問題,初始表,最優(yōu)表,在松弛問題最優(yōu)解中，x1,x2均為非整數(shù)解，由上表有：,將系數(shù)和常數(shù)都分解成整數(shù)和非負真分數(shù)之和,以上式子只須考慮一個即可，解題經(jīng)驗表明，考慮式子右端最大真分數(shù)的式子，往往會較快地找到所需割平面約束條件。以上兩個式子右端真分數(shù)相等，可任選一個考慮?，F(xiàn)選第二個式子，并將真分數(shù)移到右邊得：,引入松弛變量s1后得到下式，將此約束條件加到上表中，繼續(xù)求解。,得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)解，而且此整數(shù)規(guī)劃有兩個最優(yōu)解：X=(0,4),Z=4,或X=(2,2),Z=4。,例12,11,5,7,6,4,戊,6,9,6,3,7,丁,8,6,4,5,8,丙,9,11,7,12,9,乙,11,8,9,5,7,甲,E,D,C,B,A,費工作用人員,-1,-2,l=m=4n=5,l=m=4n=5,此問題有多個最優(yōu)解,Z=28,例13用逆推解法求解問題,用逆推解法，從后先前依次有,利用微分法易知：,已知s1=c，可得各階段的最優(yōu)決策和最優(yōu)值。即,例14分配投資問題,某公司有資金10萬元，若投資于項目k（k=1，2，3）的投資額為xk時，其收益分別為g1（x1）=4x1，g2（x2）=9x2，g3（x3）=2x32，問應(yīng)該如何分配投資數(shù)額才能使總收益最大？該問題表面上看與時間無明顯關(guān)系，其靜態(tài)模型：,Maxz=4x1+9x2+2x32x1+x2+x3=10 xi0（i=1，2，3）,建立動態(tài)規(guī)劃模型與求解,建立DP模型與求解階段k=1，2，3，分別表示項目1，2，3狀態(tài)變量sk：第k段初擁有的資金總量（分配給第k至第3個項目的資金數(shù)量）決策變量xk：第k段的投資量（分配給第k個項目的資金數(shù)量），決策集合Dk（sk）=xk0xksk,4、狀態(tài)轉(zhuǎn)移方程sk+1=sk-xk,5、階段指標(biāo)值（函數(shù)）：vk（sk，xk）=gk（xk）所以指標(biāo)函數(shù)為：6、fk（sk）：第k段初擁有的資金總量為sk時，第k至第3段按最優(yōu)投資策略所獲得的第k至第3段的總收益。,g1（x1）=4x1g2（x2）=9x2g3（x3）=2x32,7.建立動態(tài)規(guī)劃基本方程：（逆序遞推方程）,8.逆序遞推求解動態(tài)規(guī)劃基本方程k=3,f3*（s3）=2s32x3*=s3,可以證明極大值只可能在端點取得，即：1、s29/2時，f2（0）f2（s2），此時x2*=s2f2（s2）=9s22、s29/2時，f2（0）f2（s2），此時x2*=0f2（0）=2s22,k=1第一種情況,當(dāng)f2（s2）=9s2，f1（10）=Max4x1+f2(s2)=Max4x1+9s2,0x110,=Max4x1+9(s1x1)=Max9s15x1=9s1，x1*=0,但此時s2=s1x1=10-09/2與s29/2矛盾，故舍去。,0x110,k=1第二種情況,同樣可以證明極大值只可能在端點取得，比較兩個端點：x1=0時，f1（10）=200，x1=10時，f1（10）=40所以x1*=0,10、順序確定最優(yōu)策略。,最優(yōu)投資方案為全部資金投資于第3個項目，可獲最大收益200萬元。,vs,vt,v1,v3,v2,v4,(3,3),(4,2),(5,1),(2,2),(1,1),(1,1),(5,3),(3,1),(3,1),(cij,fij),截集為：（Vs，V2）,(V1,V3)。割容量為：3+2=5,截集為：（V2，V4）,(V1,V3)。割容量為：4+2=6,截集為：（V4，Vt）,(V1,V3)。割容量為：5+2=7,網(wǎng)絡(luò)最大流的流量=容量最小的割容量,例15:求圖所示網(wǎng)絡(luò)中的最小費用最大流，弧旁的權(quán)是（bij,cij）。,算法：取f(0)=0，一般若在第k-1步得到最小費用流f(k-1)，則構(gòu)造賦權(quán)有向圖W(f(k-1)，在W(f(k-1)中，尋求從vs到vt的最短路。若不存在最短路(即最短路權(quán)是+)，則f(k-1)就是最小費用最大流；若存在最短路，則在原網(wǎng)絡(luò)D中得到相應(yīng)的增廣鏈，在增廣鏈上對f(k-1)進行調(diào)整。,4,vs,vt,v1,v2,v3,4,1,2,3,1,6,2,vs,vt,v1,v2,v3,按最短路根據(jù)弧的容量調(diào)整運量得流量圖下圖.,W(f(0),0,0,0,0,vs,vt,v1,v2,v3,(a),(b),f(1),v(f(1)=5,1,-2,3,1,6,2,vs,vt,v1,v2,v3,-1,-1,W(f(1),(c),作相應(yīng)賦權(quán)有向圖并求出最短路,以0流f(0)=0為初始流構(gòu)造賦權(quán)有向圖并算得最短路如右,0,0,0,5,5,5,(4,10),(1,8),(2,5),(3,10),(1,7),(6,2),(2,4),(bij,cij),（運價，容量）,1,4,0,5,5,0,5,0,0,vs,vt,v1,v2,v3,(b),f(1),v(f(1)=5,1,3,1,6,2,vs,vt,v1,v2,v3,-1,W(f(1),(c),作相應(yīng)賦權(quán)有向圖并求出最短路,0,5,5,0,5,0,0,vs,vt,v1,v2,v3,(d),4,3,-1,6,2,vs,vt,v1,v2,v3,-1,W(f(2),(e),-4,沿最短路調(diào)整,得左下圖,作相應(yīng)賦權(quán)有向圖并求出最短路,bij,若fij0,+,若fij=0,wij=,wji=,-1,2,7,-2,-2,1,2,5,5,0,7,0,0,vs,vt,v1,vs,v2,v3,(d),4,3,-1,6,2,vs,vt,v1,v2,v3,-1,W(f(2),(e),-4,作相應(yīng)賦權(quán)有向圖并求出最短路,4,-2,3,-1,6,2,vs,vt,v2,v3,-1,W(f(3),(g),-4,-2,-3,2,5,5,0,7,0,0,vs,vt,v1,v2,v3,(f),f(3),v(f(3)=10,作相應(yīng)賦權(quán)有向圖并求出最短路,沿最短路調(diào)整流量,bij,若fij0,+,若fij=0,wij=,wji=,8,3,3,-2,2,8,5,3,7,0,3,vt,v1,vs,v2,v3,(h),f(4),v(f(4)=11,4,-2,3,-1,6,2,vs,vt,v2,v3,-1,W(f(3),(g),-4,-2,-3,2,8,5,3,7