第四版运筹学部分课后习题解答模板

1、运筹学部分课后习题解答P471.1用图解法求解线性规划问题minz=2x+3x1 2a)4x+6x>612s.t<4x+2x>412x,x>0v12解：由图1可知，该问题的可行域为凸集MABCN,且可知线段BA上的点都为3最优解，即该问题有无穷多最优解，这时的最优值为z=2x+3x0=3min2P471.3用图解法和单纯形法求解线性规划问题maxz=10x+5x12、3x+4x<9a)12s.t<5x+2x<812x,x>0v123x+4x=9x=1113<12二<3，即最优解为x*=l,315x+2x=8x=L2丿11222解：由图

2、1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点,T即3 35这时的最优值为Zmax=10X1+5X=兀图1单纯形法:原问题化成标准型为maxz=10x+5x123x+4x+x=9123s.t<5x+2x+x=8124x,x,x,x>01234cTj10500CBXBbx1x2x3x40x3934100x485201C-Zjj105000x321/5014/51-3/510x18/512/501/5C-Zjj010-25x23/2015/14-3/1410x1110-1/72/7C-Zjj00-5/14-25/14所以有x*=T,z=10x1+5x-=-5max22P7

3、82.4已知线性规划问题:maxz=2x+4x+x+x1234x+3x+x<81242 x+x<612x+x+x<62 34x+x+x<9123x,x,x,x>01234求：写出其对偶问题；(2)已知原问题最优解为X*二(2,2,4,0)，试根据对偶理论，直接求出对偶问题的最优解。解：(1)该线性规划问题的对偶问题为:minw=8y+6y+6y+9y1234'y+2y+y>21243 y+y+y+y>41234y+y>13 4y+y>113y,y,y,y>01234(2)由原问题最优解为X*=(2,2,4,0)，根据互补松弛性

4、得:y+2y+y=2124<3y+y+y+y=41234y+y=1J34把X*=(2,2,4,0)代入原线性规划问题的约束中得第四个约束取严格不等号,即2+2+4二8<9ny二04y+2y=212从而有<3y+y+y=4123y=1J3z43得y=,y=,y=1,y=01525344 3所以对偶问题的最优解为y*=(-,-,1,0)t，最优值为w=165 5minP792.7考虑如下线性规划问题：minz=60x+40x+80x1233x+2x+x>21234x+x+3x>4V1232x+2x+2x>3123x,x,x>0J123（1）写出其对偶问题；

5、（2）用对偶单纯形法求解原问题;解：(1)该线性规划问题的对偶问题为:maxw=2y+4y+3y123”3y+4y+2y<601232y+y+2y<40V123y+3y+2y<80123y,y,y>0J123(2)在原问题加入三个松弛变量x,x,x把该线性规划问题化为标准型:4 56maxz=-60x-40x-80x1233x-2xx+x=212344x-x3x+x=412352x-2x2x+x=31236x>0,j=1,6jCTj-60-40-80-000CBXBbx1x2x3x4x5x60x4-2-3-2-11000x5-4-4-1-30100x6-3-2-2

6、-2001CZjj-60-40-800000x410-5/45/41-1/12080x1111/43/40-1/400x6-10-3/2-1/20-1/21C-Zjj0-25-350-1500x411/6005/311/3-5/680x15/6102/30-1/31/640x22/3011/301/3-2/3C-Zjj00-80/30-20/3-50/3x*=(5,2,O)T,Z=60X5+40X-+80X0=23063max633P812.12某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。要求：（a）确定获利最大的产品生产计划；（b）产品A的利润在什么范围内变动时，上述最优

7、计划不变；（c）如果设计一种新产品D,单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？（d）如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜。消产品定额、资源ABC可用量（单位）劳动力63545材料34530产品利润（元/件）314解：由已知可得，设x表示第j种产品，从而模型为:jmaxz=3x+x+4x1236x+3x+5x<45123s.t3x+4x+5x<30123x,x,x>0v123a)用单纯形法求解上述模型为:cTj31400CBXBbx1x2x3x4x50x44563510

8、0x53034501C-Zjj314000x4153-101-14x363/54/5101/5C-Zjj3/5-11/500-4/53x151-1/301/3-1/34x33011-1/52/5C-Zjj0-20-1/5-3/5得到最优解为x*二(5,0,3)T；最优值为z二3X5+4X3二27maxb)设产品A的利润为3+九，则上述模型中目标函数x的系数用3+九替代并求1解得:cTj3+九1400CBXBbx1x2x3x4x53xi51-1/301/3-1/34x33011-1/52/5C-Zjj九-20-1/5-3/5（C-Z）jj0-2+九/30-1/5-九/3-3/5+九/3要最优计划

9、不变，要求有如下的不等式方程组成立2+-<03<0解得:533+d05 339124从而产品A的利润变化范围为：3-,3+9，即2-,4-C）设产品D用x表示，从已知可得6b=ccB-1P=1/566B6把x加入上述模型中求解得:6cTj314003CBXBbx1x2x3x4x5x63x151-1/301/3-1/324x33011-1/52/5-4/5CZjj0-20-1/5-3/51/53x65/21/2-1/601/6-1/614x352/513/151-1/154/150CZjj-1/10-59/300-7/30-17/300从而得最优解x*二(0,0,5,0,0,5/2)

10、t；最优值为z=4x5+3x-=27.5>27max2所以产品D值得生产。d）由晚谕才勺他檢旬3T'聊“卢甩十門0.9入伙;氓策入谢川哄梆性）X”M/X,杓TL31(0'匕Z>PT-入w庁>2-命处耒池增杯十詞当入兀于-扌入9切P1013.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。表335检验:检验:解：因为工a二工b，即产销平衡所以由已知和最小元素法可得初始方案为ElB2B3B4行位势A1训釣2151A2015出1016A3呂5四辺禺0调Q)13列位势-111314由于有两个检验数小于零，所以需调整，调整一:逬BlB2

11、B3B4行位势A11A2调I02115纫106A3勺5训04列位势-21314由于还有检验数小于零，所以需调整，调整二:检验:逬BlE2B3B4行位势A15竺Ulio1A210152他6A3©观08列位势-61L310从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：z二2X5+2X5+7X10+9x15+11x10+18x0二335min解：因为工a二58工b二55，即产大于销，所以需添加一个假想的销地，销i=1j=1量为3,构成产销平衡问题，其对应各销地的单位运费都为0。A1841207A26947025A35343026销量101020153产量B1B2B3B4B5产

12、地地由上表和最小元素法可得初始方案为检验:BlB2B3B4B5行位势A17©包1A269引哲130T34A3|J1101315%3列位势2000-4从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：z二6X9+5X1+3X10+lx7+4x13+3x15+0x3二193min解：因为工a二80工b二100，即销大于产，所以需添加一个假想的产地，产iji=1j=1量为20,构成产销平衡问题，其对应各销地的单位运费都为0。:地销地B1B2B3B4B5产量A18637520A25M84730A36396830A40000020销量2525201020由上表和最小元素法可得初始方案

13、为检验:O-由于有两个检验数小于零，所以需调整，调整一:B4©©5创邑6-O-'lfp=lIII52由于还有检验数小于零，所以需调整，调整二:沁B1B2B3B4B5产量A12020A2201030A3525030A402020销量2525201020检验:ElB2B3B4B5行位势A1A2A3A48j(+7)(+8)201(+7)(+2)1065创259)(+j)创00(+|)2i(+5)2o型包型204891列位势-3-6-1-4-1从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：z二3X20+5X20+4X10+6x5+3x25+8x0+0x20+0

14、x0二305minP1274.8用割平面法求解整数规划问题。maxz=7x+9x12a)解：该问题的松弛问题为:-x+3x<612<7x+x<3512x,x>0,且为整数J12maxz=7x+9x12-x+3x<612<7x+x<3512x,x>0v12则单纯形法求解该松弛问题得最后一单纯形表为:cTj7900CBXBbx1x2x3x49x27/2017/221/227x19/210-1/223/22CZjj00-28/11-15/11割平面1为：(3+1/2)二x+(0+7/22)x+(0+1/22)x2341 71cc711xxx3W0x+x

15、x2 223224222322452从而有cTj79000CBXBbx1x2x3x4x59x27/2017/221/2207x19/210-1/223/2200x5-1/200-7/22-1/221CZjj00-28/11-15/1109x23010017x132/71001/7-1/70x311/70011/7-22/7CZjj000-1-8割平面2为：(4+4/7)x+(0+1/7)x+(-1+6/7)x1454 16164一一一x一xx一x一4<0x+x一x7747515747567CTj790003cBXBbX1X2X3X4X5X69X230100107X132/71001/7-

16、1/700X311/70011/7-22/700X6-4/7000-1/7-6/71C-Zjj000-1-809X230100107X141000-110X310010-410X4400016-7C-Zjj0000-2-7由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即X*=(4,3»，最优值为z二7X4+9X3二55maxP1445.3用图解分析法求目标规划模型c）minZ=Pd+Pd+P（2d-+1d-）rx+i+di也+=40%“丿x1+x2+d2-df=40+10=50st*X+df-d3+=24x2+d-d4+=30244Xi、X2、q+、di"

17、;、df、d2>4+、d3、d4+、d4-$0解：由下图可知，满足mind1-的满意解为区域X2CDX1；满足mindg+的满意解为闭区域bcdeb；满足min2q-的满意解为图中的A点，满足minq-的满意解为图中的A点，所以该问题的满意解为图中的点A(24,26)x2xl用图解分析法求目标规划模型minz=Pd+Pd+Pd+112332x+2x+d一一d+=41211x2x+dd+=4<1222x+2x+dd+=81233x,x>0;d、d+>0i=1,2,3'12ii的满意解。解：由下图可知，满足mind+的满意解为区域CDOA；1满足mind+的满意解为

18、闭区域MCDOM；3满足mind+的满意解为图中的阴影部分，即为图中的凸多边形OABCDO。2P1706.4求下图中的最小树12L/><A/7-.></*6F解：避圈法为：(1) %=僅巴=3,匚9耳尺&丹(2) %=仇吕代=©门眉屮口丹=(A,B,Gy2=(C,D,E,F,H(4)=A,B,G,C)y2=D,E,F,HQ)V=AEU6DS=E,玖咼(6)=A,B,G,C,D,Ey2=F,H=(A,B,G,C,D,E,Hy2=F%=F,H九=$得到最小树为：解：如下图所示:10113714比、0117卩48P1736.14用Ford-Fulkerson

19、的标号算法求下图中所示各容量网络中从Vs到"t的最大流，并标出其最小割集。图中各弧旁数字为容量c，括弧中为流量f.B)解：对上有向图进行2F标号得到(0,co5(5)(3)51)為)5)Vif1)2i2C2)5141川4(4由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1,所以已经是最大流了，最大流量等于最小割的容量，最小由图可知，标号中断，割为与直线KK相交的弧的集合，即为(v,v),(v,v),(v,v),(v,v),(v,v),(v,vs3s4s51t2t23所以从v到v的最大流为：f*二1+2+5+3+2+1二14ststC)5t5)8(6)4(4)2(0)2(0)2C2)6(6)6解：对上有向图进行2