運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第四版胡運(yùn)權(quán)主編課后練習(xí)答案

1、習(xí)題一 P46該問題有無窮多最優(yōu)解，即滿足運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用習(xí)題解答-1.一一一.，4X1+6X2=6且0<X2<-的所有(X1,X2),此時(shí)目標(biāo)函數(shù)值z(mì)=3o(b)X2品用圖解法找不到滿足所有約束條件的公共范圍，所以該問題無可行解。1.2(a)約束方程組的系數(shù)矩陣1236300A=81-4020(30000-1基基解是否基可行解目標(biāo)函數(shù)值X1X2X3X4X5X6P1P2P3c167ccc否0-00036P1P2P40100700是10P1P2P57是30300-02piP2P674_40002iT否PiP3P4005一2800否PiP3P50032080是3PiP3P6i0i200

2、3否PiP4P5000350是0PiP4P65400-20i54否最優(yōu)解X='0,10,0,7,0,0T(b)約束方程組的系數(shù)矩陣A234、<212!基基解是否基可行解目標(biāo)函數(shù)值XiX2X3X4PiP2ii否-4002PiP32ii是43-00555PiP4iii否'0036P2P3cicc是50-202P2P4i否0一022P3P400ii是5最優(yōu)解x=,0,0155)°1.3(a)(1)圖解法最優(yōu)解即為嚴(yán)+4x2=9的解x=(1,-；,最大值z(mì)=355xi2x2=822(2)單純形法首先在各約束條件上添加松弛變量，將問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式maxz=10x15x2

3、0x30x43xi+4x2+x3=9st.5x1+2x2+x4=8則P3,P4組成一個(gè)基。令均=x2=0得基可行解x=(0,0,9,8),由此列出初始單純形表cjT10500cB基bx1x2x3x40x3934100x48520110500cj-zjcr1><T2。0=min|89一,一'、.8二53,55cjT10500CB基bx1x2x3x4c210x30閔135!55“82110x110555cj-zj010-2CT2>0,6=min8314、萬22新的單純形表為cjT10500cB基bx1x2x3x45x232015143一?410x11101_27cjZj0

4、051425743523仃1,仃2 <0,表明已找到問題取優(yōu)解xi=1,x2=-,x3=0,x4=0。取大值z(mì)2(b)最優(yōu)解即為W的解x=(H),最大值z(mì)/(2)單純形法首先在各約束條件上添加松弛變量，將問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式maxz=2x1x20x30x40x55x2x3=15st.6x12x2x4=24xix2x5=5則P3,P4,P5組成一個(gè)基。令xi=x2=0得基可行解x=(0,0,15,24,5),由此列出初始單純形表cjT21000cB基bX1X2X3X4X50X315051000X424620100X5511001cj-zj21000。1仃2。mmmin(L,24"6

5、q1j1=4cjT21000cB基bX1X2X3X4X50X315051002X4411301600X510：2113J0_161cj-zj0130130。2>0,6=min,15,152。2J2新的單純形表為cjT21000cB基bX1X2X3X4X50X315200154_152711xX4100-22423130X5010242cj-zi11000_T423,仃2<0,表明已找到問題最優(yōu)解Xi=1,X2=215X3 = 一2/古*17值z(mì)=2(a)在約束條件中添加松弛變量或剩余變量，"'''且令 X2 =X2 -X2（X2 之 0,X2 之

6、0）1.6X3=%，Z'=-Z該問題轉(zhuǎn)化為.一'''_'maXz'-3xi-X2rz-2X30x4Fx5匚，一_"，.'，一2x1+3x2-3x2+4x3+x4=12.'''_'-4X1X2-X2-2X3-X5=8st.I3x1-x2,x2-3x3=6'''X1,X2,X2,X3,X4,X5-0其約束系數(shù)矩陣為23-3410"A=4112013-11300,在A中人為地添加兩列單位向量p,P8,23-341000”4112011031130001,令maxz

7、9;=-3x1-x2x2-2x30x40x5-Mx6-Mx7得初始單純形表CjT與-11-200-MMCB基bXi'X2''X2'X3X4X5X6X70X41223-341000HMX6841-1-20-110HMX763-11-30001CjZj-43+7M-11-2-5M0-M00z' = -z.'"'八"一(b)在約束條件中添加松弛變量或剩余變量，且令X3=X3-X3(X3>0,X3>0)該問題轉(zhuǎn)化為'''maxz':-3x1-5x2x3-x30x40x5x12x2x3

8、-x3x4=6st.2x1"，x2-3x3-3x31'x§-16'x1+x2+5x3-5x3=10'x1,x2,x3,x3,x4,x至0其約束系數(shù)矩陣為121-1-10、A=213-30-1口15-500,在A中人為地添加兩列單位向量P,P8121-1-1010、213-30100115-50001,'''令maxz'=-3x1-5x2x3-x30x40x5-Mx6-Mx7得初始單純形表CjT-3-51-100-M-MCb基bx1*2x；IFx3x4x5x6x7_Mx66121-1-10100*516213-30100

9、-MX710115-50001cj-zj-32M53M1+6M-1-6M-M0001.7(a)解1:大M法在上述線性規(guī)劃問題中分別減去剩余變量x4,x6,x8,再加上人工變量x5,x7,x9,得maxz=2x1-x22x30x4-Mx50x6-Mx70x8-Mx9x1x2x3-x4x5=6s,t,-2Xi',X3-X6'X7-22X2_X3-Xg.X9-0Xi,X2,X3,X4,X5,X6,X7,X8,X9,0其中M是一個(gè)任意大的正數(shù)。據(jù)此可列出單純形表cjT2-120-M0-M0-M9icb基bX1X2X3X4X5X6X7X8X9-MX56111-1100006-MX7-2-

10、20100-1100-MX9002-10000-110Cj-Z2-M3M-12+M-M0-M0-M0-MX56103/2-11001/2-1/24-MX72-20100-110021X2001-1/20000-1/2-1/2cj-zj2-M05M上322M0-M0M1萬21上3M22-MX53400-113/2-3/21/2-1/23/42X322010011001X2111000-1/21/2-1/21/2cj-zj4M+500_M03M十3-5M-3M-11-3M22222X13/4100-1/41/43/8-3/81/8-1/82X37/2001-1/21/2-1/41/41/41/4_

11、1X27/4010-1/41/4-1/81/8-3/83/8cj-zj0005/4-n”5-M4-3/831VA-9-M-88-M8由單純形表計(jì)算結(jié)果可以看出，。4A0且ai4<0(i=1,2,3),所以該線性規(guī)劃問題有無界解解2：兩階段法。現(xiàn)在上述線性規(guī)劃問題的約束條件中分別減去剩余變量x4,x6,x8，再加上人工變量X5,X7,X9，得第一階段的數(shù)學(xué)模型據(jù)此可列出單純形表cjT0000101019iCb基bX1X2X3X4X5X6X7X8X91X561X7-21X90111-110000-20100-110002-10000-1160cj-Zj1-3-11010101X561x720

12、X20103/2-11001/2-1/2-20100-110001-1/20000-1/2-1/242cj-zj13105/210-10-221X530X320X21400-113/2-3/21/2-1/2-20100-1100-11000-1/21/2-1/21/23/4cj-zj0000101012X13/42x37/2-1x27/4100-1/41/43/8-3/81/8-1/8001-1/21/2-1/41/41/4-1/4010-1/41/4-1/81/8-3/83/8cj-zj000010101377t*第一階段求得的最優(yōu)解X=(一,一,一,0,0,0,0,0,0)T,目標(biāo)函數(shù)的最

13、優(yōu)值8=0。442一、一3-777t因人工變量X5=x7=x9=0,所以X-(-,-,-,0,0,0,0,0,0)是原線性規(guī)劃問題的基可442行解。于是可以進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工變量取消，并填入原問題的目標(biāo)函數(shù)的系數(shù)，進(jìn)行第二階段的運(yùn)算，見下表。cj-zj2-1200006cb基bX1X2X3X4X6X82x13/4100-1/43/8-1/82X37/2001-1/2-1/41/4-1x27/4010-1/4-1/8-3/8cj_Zj0005/4-3/8-9/8由表中計(jì)算結(jié)果可以看出，仃4>0且ai4<0(i=1,2,3),所以原線性規(guī)劃問題有無界解。(b)

14、解1：大M法在上述線性規(guī)劃問題中分別減去剩余變量x4,x6,x8,再加上人工變量x5,x7,x9,得minz=2x13x2x30x40x5Mx6-Mx7x1+4x2+2x3-x4+x6=8st3x1 2x2 - x5 x7 = 6，“2，乂3，乂4，%?6?7?8，%-0其中M是一個(gè)任意大的正數(shù)。據(jù)此可列出單純形表cjt2-120-M0-M0-M9iCb基bXix2x3x4x5x6x7Mx68Mx76142-10103200-10123cj-zj2-4M3-6M1-2MMM003x22Mx721/411/2-1/401/405/20-11/2-1-1/2184/5cj-zj551V，八1V,1

15、31M-3M3cM0MM042242243x29/52x4/5013/5-3/101/103/10-1/1010-2/51/5-2/5-1/52/5cj-zj0001/21/2M-1/2M-1/249由單純形表計(jì)算結(jié)果可以看出，最優(yōu)解X1：4,-,0,0,0,0,0)T,目標(biāo)函數(shù)的最優(yōu)解值55*49z=2父一+3父一=7。X存在非基變量檢驗(yàn)數(shù)仃3=0,故該線性規(guī)劃問題有無窮多最優(yōu)解。55解2:兩階段法。現(xiàn)在上述線性規(guī)劃問題的約束條件中分別減去剩余變量X4, X5,再加上人工變量 X6, X7,得第一階段的數(shù)學(xué)模型min=x6x7x1+4x2+2x3-x4+x6=8st3x1 2x2 -x5 x

16、7 = 6x1,x2,x3,x4,x5,x6,x7,x8,x9,0據(jù)此可列出單純形表cjT00000119icb基bx1又2x3x4x5x6X71x8142-101021x763200-1013cj-zj-4-6-211000x221/411/2-1/401/4081x725/20-11/2-1-1/214/5cj_zj-5/201-1/213/200x29/5013/5-3/101/103/10-1/100x14/510-2/51/5-2/5-1/52/5cj-zj00000114 9t*第一階段求得的最優(yōu)解X(-,-,0,0,0,0,0)，目標(biāo)函數(shù)的最優(yōu)值8=0。5 5一,一、I49因人工

17、變量x6=x7=0,所以(一-00000)T是原線性規(guī)劃問題的基可行解。于是可55以進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工變量取消，并填入原問題的目標(biāo)函數(shù)的系數(shù)，進(jìn)行第二階段的運(yùn)算，見下表。cj-zj23100cb基bX1X2X3X4X53X29/52x14/5013/5-3/101/1010-2/51/5-2/5cj-zj0001/21/249由單純形表計(jì)算結(jié)果可以看出，最優(yōu)解X4,-,0,0,0,0,0)T,目標(biāo)函數(shù)的最優(yōu)解值55*49z=2M+3M=7。由于存在非基變量檢驗(yàn)數(shù)仃3=0,故該線性規(guī)劃問題有無窮多最優(yōu)55解。1.8表1-23x1xx3x4x5x4624-210X1-13

18、201cj-Zj3-1200表1-24x1x2x3x4x5x1312-11/20X510511/21cj-zj075-3201.10354000x1x2x3x4x5x65x28/32/31013000x514/34,305】-23100x62935/304-2301cj-zj-13045300x1x2x3x4x5x65x28/32/31013004x314.15-4/1501-2/151500x689/15411500-2/15-4,51Cj-zj11/1500-17/15-450x1x2x3x4x5x65x250/410101541841_1Q'414x362/41001-64154

19、14413x18941100-2/41-12411541cj_zj000-4541-2441-1141最后一個(gè)表為所求。習(xí)題二P76(a)min z =2x1 2x2 4x3xi +3x2 +4x3 22st2x1 +x2 +3x3 +y4 <3x1 -4x2 3x3 =5x1,x2之0, 十無約束(b)max z =5x1，6x2，3x3,|_ x1 _2x2 .2x3 =5一x1 +5x2 -x3 之 3st. '±±-4x1 +7x2 +3x3 E8M無約束，x2之0,x3 <02.22.1寫出對(duì)偶問題maxw=2y13y25y3/y1+2y2+y

20、3<2對(duì)偶問題為：3y1+y2+4y3<2st.4y13y23y3=4y1之0,y2<0,y3無約束minw=5y1-3y28y3'y1-y2+4y3=5對(duì)偶問題為：2y1+5y2+7y3之6s.t.|2y1-y23y3一3y1無約束，y2<0,y3-0(a)錯(cuò)誤。原問題存在可行解，對(duì)偶問題可能存在可行解，也可能無可行解。(b)錯(cuò)誤。線性規(guī)劃的對(duì)偶問題無可行解，則原問題可能無可行解，也可能為無界解。(c)錯(cuò)誤。(d)正確。2.6對(duì)偶單純形法(a)minz=4x112x218x3x1+3x3之3st.2x2+2x3之5Jx1,x2,X30解：先將問題改寫為求目標(biāo)函

21、數(shù)極大化，并化為標(biāo)準(zhǔn)形式maxz'-4x1-12x2-18x3-0x40x5x1-3x3+x4=-3st.J2x2-2x3+x5=5xi_0i=1,",5列單純形表，用對(duì)偶單純形法求解，步驟如下CjT-4-12-1800Cb基bx1x2x3x4x50x4-30x5-5103100L2201cjzj-4-12-18000x4-3-101-310-512x2一210110-2cj_zj-40-60-618x3111010333-12x2一2111一10332cj-zj-20026最優(yōu)解為x=0,1,目標(biāo)值z(mì)=39。,2(b)minz=5x12x2-4x33x1+x2+2x3之4s

22、t.6x1+3x2+5x3之10x1,x2,x3-0解：先將問題改寫為求目標(biāo)函數(shù)極大化，并化為標(biāo)準(zhǔn)形式maxz'-5x1-2x2-4x30x40x5-3x1-x2-2x3+x4=Tst.J-6x1-3x2-5x3+x5=T0xi-0i=11,5列單純形表，用對(duì)偶單純形法求解CjT-5-2-400cB基bxix2x3x4x50x4。0x5-1041210_6_501cj_zj-52400c-20x4-3-10.1-11-33_|3o102x23215033cj-zj2210033-4X32301-31-2x204105-2cj-zj100-20最優(yōu)解為x=(0,0,2T,目標(biāo)值z(mì)=8o2

23、.8將該問題化為標(biāo)準(zhǔn)形式：maxz=2x1-x2r30x40x5xi-x2'x3'x4=6st.x12x2x5=4xi_0i=1,一5用單純形表求解cjt2-1100cB基bx1x2x3x4x50x46111100x54-12001cj-Zj2-11001-6cB基bx1x2x3x4x52x16111100x51003111cjF0-3-1-20由于5<0,所以已找到最優(yōu)解X=(6,0,0,0,10),目標(biāo)函數(shù)值z(mì)=12(a)令目標(biāo)函數(shù)maxz=(2+兀)x1+(-1+%)x2+(1+%)x3(1)令，電=h=0,將兀反映到最終單純形表中cjT2十五100Cb基bX1X2

24、X3X4X52十九人611110X51003111cj-zj0-3-Z,-1-%-2-九0表中解為最優(yōu)的條件：-3-W0,-1-%E0,2-11E0,從而以之1(2)令，力=一-3=。，將%反映到最終單純形表中cjT2-1+%100Cb基bX1X2X3X4X52X16111100X51003111cj-Zj0Z2-3-1-20表中解為最優(yōu)的條件：%-3E0,從而九2M3%-1 W0,從而'31(3)令1-1=%=0,將%反映到最終單純形表中cjt2-11+%00cB基bX1X2X3X4X52X16111100X51003111cj-Zj0-3力-3-1-20表中解為最優(yōu)的條件:(b)令

25、線性規(guī)劃問題為maxz=2x1x2x3J_Xlx2x3_64st.«-x1+2x2<4十、x>0(i=1,3)(1)先分析的變化b：=B°b二使問題最優(yōu)基不變的條件是b：b=(2)同理有U0+%(c)由于x*=(6,0,0,0,10)代入-x1+2x3=-6<2,所以將約束條件減去剩余變量后的方程x1+2x3-x6=2直接反映到最終單純形表中cjT2-11000Cb基bx1x2x3x4x5x62x161111000x5100311100*6-210-2001cj_Zj0-3-1-200對(duì)表中系數(shù)矩陣進(jìn)行初等變換，得cjT2-11000cB基bx1x2x3x

26、4x5x62x161111000x5100311100x6-80-1-3-101cj-zj0-3-1-20010xi =1，38 x3=322一，x5 =一,取優(yōu)值為53283cjT2-ii000CB基bxi*2x3x4x5*62xi%1%0%0%0x5%0%0%i%0*6%0%i%0_i385icjZj000333因此增加約束條件后，新的最優(yōu)解為2.12(a)線性規(guī)劃問題maxz=3x1x24x36x13x25x3<45st.3xi4x25x3<30xi,x2,x3:0單純形法求解cB基bxix2x3x4x50x445635i00x5303450icj一Zj3i4000x4I53

27、】-i0i-14x363545i0i5cj-Zj35_ii500_453xi5ii30i3134x330ii_i525ccc13cj_zj0-20-255最優(yōu)解為(X1,X2,X3卜(5,0,3),目標(biāo)值z(mì)=27。(a)設(shè)產(chǎn)品A的利潤(rùn)為3+丸，線性規(guī)劃問題變?yōu)閙axz=3：!；，/.x1x24x36x1+3x2+5x3<45st.3x1+4x2+5x3<30x1，x2,x3,0單純形法求解基bxix2x3x4xx44563510x3034501Cj-Zj3+尢1400x4153】-101-1x3634101555cj-zj3一114-+Z00555xi511110333x30111

28、255cj-zj0-2十自01人,3十大35353為保持最優(yōu)計(jì)劃不變，應(yīng)使2十九，3十二人都小于等于0,解得3ele9。3535355(b)線性規(guī)劃問題變?yōu)閙axz=3xix24x33x46x1+3x2+5x3+8x4<45s.t.3x1+4x2+5x3+2x4<30x1,x2,x3,x4-0單純形法求解cB基bx1x2x3x4x5x0x5456358100x630345】201cjzj3143000x4153】-1061-14x3634120155553110704Cjzj55553x151102113334x33412011555113cj_zj0-20555511110x4:

29、01一:226664x3521310185151515cj129717_zj0010153030此時(shí)最優(yōu)解為(X1,X2,X3)=(0,0,5),目標(biāo)值z(mì)=20,小于原最優(yōu)值，因此該種產(chǎn)品不值得生產(chǎn)。(c)設(shè)購(gòu)買材料數(shù)量為y,則規(guī)劃問題變?yōu)閙axz=3xi-X2-4x3-0.4y6-6x1-3x2-5x3<45st.3x14x25x3y_30x1,x2,x3,y_0單純形法求解cB基bx1x2x3yx4x0x5456350100x630345-101cj"zj31425000x4153】-1011-14x363545115015cj.Zj351150250453x151_130

30、口13j13_134X330112-51飛25Cjzj0-20151飛3飛0y153-1011-14X39653510150cjZj359-5002一52-5此時(shí)最優(yōu)解為(xi,X2,X3,y)=(0,0,9,15),目標(biāo)值z(mì)=30,大于原最優(yōu)值，因此材料擴(kuò)大生產(chǎn)，以購(gòu)材料15單位為宜。應(yīng)該購(gòu)進(jìn)原第三章3.1表3.36地銷地B1B2B3B4A198121318A21010121424A38911126A41010111212銷量614355用vogel法求解得AB1B2B3B4A1144A224A360A411用位勢(shì)法檢驗(yàn)，把上表中有數(shù)字的地方換成運(yùn)價(jià)sB1B2B3B4UiA18138A2128A38117A411127Vj1045令v1=1則u1+v2=8所以u(píng)3=7u1+v4=13v3=4u2+v3=12u4=7u3+v1=8v5=8u3+v3=