资源描述
习题一 P46该问题有无穷多最优解，即满足运筹学基础及应用习题解答-1.一一一.，4X1+6X2=6且0X2-的所有(X1,X2),此时目标函数值z=3o(b)X2品用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。1.2(a)约束方程组的系数矩阵1236300A=81-4020(30000-1基基解是否基可行解目标函数值X1X2X3X4X5X6P1P2P3c167ccc否0-00036P1P2P40100700是10P1P2P57是30300-02piP2P674_40002iT否PiP3P4005一2800否PiP3P50032080是3PiP3P6i0i2003否PiP4P5000350是0PiP4P65400-20i54否最优解X=0,10,0,7,0,0T(b)约束方程组的系数矩阵A234、0,6=min8314、万22新的单纯形表为cjT10500cB基bx1x2x3x45x232015143一?410x11101_27cjZj0051425743523仃1,仃2 0,6=min,15,152。2J2新的单纯形表为cjT21000cB基bX1X2X3X4X50X315200154_152711xX4100-22423130X5010242cj-zi11000_T423,仃20,X30)该问题转化为maxz:-3x1-5x2x3-x30x40x5x12x2x3-x3x4=6st.2x1，x2-3x3-3x31x-16x1+x2+5x3-5x3=10x1,x2,x3,x3,x4,x至0其约束系数矩阵为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-MX710115-50001cj-zj-32M53M1+6M-1-6M-M0001.7(a)解1:大M法在上述线性规划问题中分别减去剩余变量x4,x6,x8,再加上人工变量x5,x7,x9,得maxz=2x1-x22x30x4-Mx50x6-Mx70x8-Mx9x1x2x3-x4x5=6s,t,-2Xi,X3-X6X7-22X2_X3-Xg.X9-0Xi,X2,X3,X4,X5,X6,X7,X8,X9,0其中M是一个任意大的正数。据此可列出单纯形表cjT2-120-M0-M0-M9icb基bX1X2X3X4X5X6X7X8X9-MX56111-1100006-MX7-2-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_1X27/4010-1/41/4-1/81/8-3/83/8cj-zj0005/4-n”5-M4-3/831VA-9-M-88-M8由单纯形表计算结果可以看出，。4A0且ai40且ai40(i=1,2,3),所以原线性规划问题有无界解。(b)解1：大M法在上述线性规划问题中分别减去剩余变量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是一个任意大的正数。据此可列出单纯形表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,131M-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由单纯形表计算结果可以看出，最优解X1：4,-,0,0,0,0,0)T,目标函数的最优解值55*49z=2父一+3父一=7。X存在非基变量检验数仃3=0,故该线性规划问题有无穷多最优解。55解2:两阶段法。现在上述线性规划问题的约束条件中分别减去剩余变量X4, X5,再加上人工变量 X6, X7,得第一阶段的数学模型min=x6x7x1+4x2+2x3-x4+x6=8st3x1 2x2 -x5 x7 = 6x1,x2,x3,x4,x5,x6,x7,x8,x9,0据此可列出单纯形表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*第一阶段求得的最优解X(-,-,0,0,0,0,0)，目标函数的最优值8=0。5 5一,一、I49因人工变量x6=x7=0,所以(一-00000)T是原线性规划问题的基可行解。于是可55以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。cj-zj23100cb基bX1X2X3X4X53X29/52x14/5013/5-3/101/1010-2/51/5-2/5cj-zj0001/21/249由单纯形表计算结果可以看出，最优解X4,-,0,0,0,0,0)T,目标函数的最优解值55*49z=2M+3M=7。由于存在非基变量检验数仃3=0,故该线性规划问题有无穷多最优55解。1.8表1-23x1xx3x4x5x4624-210X1-13201cj-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_1Q414x362/41001-6415414413x18941100-2/41-12411541cj_zj000-4541-2441-1141最后一个表为所求。习题二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写出对偶问题maxw=2y13y25y3/y1+2y2+y32对偶问题为：3y1+y2+4y32st.4y13y23y3=4y1之0,y20,y3无约束minw=5y1-3y28y3y1-y2+4y3=5对偶问题为：2y1+5y2+7y3之6s.t.|2y1-y23y3一3y1无约束，y20,y3-0(a)错误。原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。(b)错误。线性规划的对偶问题无可行解，则原问题可能无可行解，也可能为无界解。(c)错误。(d)正确。2.6对偶单纯形法(a)minz=4x112x218x3x1+3x3之3st.2x2+2x3之5Jx1,x2,X30解：先将问题改写为求目标函数极大化，并化为标准形式maxz-4x1-12x2-18x3-0x40x5x1-3x3+x4=-3st.J2x2-2x3+x5=5xi_0i=1,5列单纯形表，用对偶单纯形法求解，步骤如下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最优解为x=0,1,目标值z=39。,2(b)minz=5x12x2-4x33x1+x2+2x3之4st.6x1+3x2+5x3之10x1,x2,x3-0解：先将问题改写为求目标函数极大化，并化为标准形式maxz-5x1-2x2-4x30x40x5-3x1-x2-2x3+x4=Tst.J-6x1-3x2-5x3+x5=T0xi-0i=11,5列单纯形表，用对偶单纯形法求解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最优解为x=(0,0,2T,目标值z=8o2.8将该问题化为标准形式：maxz=2x1-x2r30x40x5xi-x2x3x4=6st.x12x2x5=4xi_0i=1,一5用单纯形表求解cjt2-1100cB基bx1x2x3x4x50x46111100x54-12001cj-Zj2-11001-6cB基bx1x2x3x4x52x16111100x51003111cjF0-3-1-20由于50,所以已找到最优解X=(6,0,0,0,10),目标函数值z=12(a)令目标函数maxz=(2+兀)x1+(-1+%)x2+(1+%)x3(1)令，电=h=0,将兀反映到最终单纯形表中cjT2十五100Cb基bX1X2X3X4X52十九人611110X51003111cj-zj0-3-Z,-1-%-2-九0表中解为最优的条件：-3-W0,-1-%E0,2-11E0,从而以之1(2)令，力=一-3=。，将%反映到最终单纯形表中cjT2-1+%100Cb基bX1X2X3X4X52X16111100X51003111cj-Zj0Z2-3-1-20表中解为最优的条件：%-3E0,从而九2M3%-1 W0,从而31(3)令1-1=%=0,将%反映到最终单纯形表中cjt2-11+%00cB基bX1X2X3X4X52X16111100X51003111cj-Zj0-3力-3-1-20表中解为最优的条件:(b)令线性规划问题为maxz=2x1x2x3J_Xlx2x3_64st.-x1+2x20(i=1,3)(1)先分析的变化b：=Bb二使问题最优基不变的条件是b：b=(2)同理有U0+%(c)由于x*=(6,0,0,0,10)代入-x1+2x3=-62,所以将约束条件减去剩余变量后的方程x1+2x3-x6=2直接反映到最终单纯形表中cjT2-11000Cb基bx1x2x3x4x5x62x161111000x5100311100*6-210-2001cj_Zj0-3-1-200对表中系数矩阵进行初等变换，得cjT2-11000cB基bx1x2x3x4x5x62x161111000x5100311100x6-80-1-3-101cj-zj0-3-1-20010xi =1，38 x3=322一，x5 =一,取优值为53283cjT2-ii000CB基bxi*2x3x4x5*62xi%1%0%0%0x5%0%0%i%0*6%0%i%0_i385icjZj000333因此增加约束条件后，新的最优解为2.12(a)线性规划问题maxz=3x1x24x36x13x25x345st.3xi4x25x330xi,x2,x3:0单纯形法求解cB基bxix2x3x4x50x445635i00x5303450icj一Zj3i4000x4I53】-i0i-14x363545i0i5cj-Zj35_ii500_453xi5ii30i3134x330ii_i525ccc13cj_zj0-20-255最优解为(X1,X2,X3卜(5,0,3),目标值z=27。(a)设产品A的利润为3+丸，线性规划问题变为maxz=3：!；，/.x1x24x36x1+3x2+5x345st.3x1+4x2+5x330x1，x2,x3,0单纯形法求解基bxix2x3x4xx44563510x3034501Cj-Zj3+尢1400x4153】-101-1x3634101555cj-zj3一114-+Z00555xi511110333x30111255cj-zj0-2十自01人,3十大35353为保持最优计划不变，应使2十九，3十二人都小于等于0,解得3ele9。3535355(b)线性规划问题变为maxz=3xix24x33x46x1+3x2+5x3+8x445s.t.3x1+4x2+5x3+2x430x1,x2,x3,x4-0单纯形法求解cB基bx1x2x3x4x5x0x5456358100x630345】201cjzj3143000x4153】-1061-14x3634120155553110704Cjzj55553x151102113334x33412011555113cj_zj0-20555511110x4:01一:226664x3521310185151515cj129717_zj0010153030此时最优解为(X1,X2,X3)=(0,0,5),目标值z=20,小于原最优值，因此该种产品不值得生产。(c)设购买材料数量为y,则规划问题变为maxz=3xi-X2-4x3-0.4y6-6x1-3x2-5x345st.3x14x25x3y_30x1,x2,x3,y_0单纯形法求解cB基bx1x2x3yx4x0x5456350100x630345-101cjzj31425000x4153】-1011-14x363545115015cj.Zj351150250453x151_130口13j13_134X330112-51飞25Cjzj0-20151飞3飞0y153-1011-14X39653510150cjZj359-5002一52-5此时最优解为(xi,X2,X3,y)=(0,0,9,15),目标值z=30,大于原最优值，因此材料扩大生产，以购材料15单位为宜。应该购进原第三章3.1表3.36地销地B1B2B3B4A198121318A21010121424A38911126A41010111212销量614355用vogel法求解得AB1B2B3B4A1144A224A360A411用位势法检验，把上表中有数字的地方换成运价sB1B2B3B4UiA18138A2128A38117A411127Vj1045令v1=1则u1+v2=8所以u3=7u1+v4=13v3=4u2+v3=12u4=7u3+v1=8v5=8u3+v3=11u2=8u4+v3=11v2=0u4+v4=12得检验数表B1B2B3B4A100A2121A320A423表中所有的数字均大于等于零，故所求方案为最优方案3.3解：（a）用运价代替表3.39中有数字的地方，求出位势和检验数B1B2B3B4UiA111112-kA212k911A321Vj1k-11-2k-1令v1=1则u1+v2=1故v3=-2u1+v4=11u2=11u2+v1=12v2=k-11u2+v2=ku1=12-ku2+v3=9v4=k-1u3+v1=2u3=1ABB1B2B3B4A1k-310-kA230-kA324-k1518-k得检验数表得检验数表令表中所有的检验数均大于等于零，得3k05.6解：目标规划模型为Minz=Pidi-+P2（d2-+d2+）+P2（d3-+d3+）+P3（d4-+d4+）+P3d5+s.t.300xi+450x2+di-di+=10000xi+d2-d2+=10x2+d3-d3+=154xi+6x2+d4-d4+=1503xi+2x2+d5-d5+=75xi,x2,di-,di+,di-0,i=1,，5
展开阅读全文