第四版运筹学部分课后习题解答.doc

第四版运筹学部分课后习题解答运筹学部分课后习题解答/view/0D83519DBCD1BA33.htmlP47 1.1 用图解法求解线性规划问题min z=2x1+3x24x1+6x26a） s.t4x1+2x24x,x012解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为3最优解，即该问题有无穷多最优解，这时的最优值为zmin=2+30=32运筹学第三版课后习题答案P47 1.3 用图解法和单纯形法求解线性规划问题max z=10x1+5x23x1+4x29s.t5x1+2x28x,x012a）解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，x=1T3x1+4x2=913*即3，即最优解为x=1,25x1+2x2=8x2=2这时的最优值为zmax=101+5335= 22单纯形法： 原问题化成标准型为max z=10x1+5x23x1+4x2+x3=9s.t5x1+2x2+x4=8x,x,x,x012343353所以有x*=1,zmax=101+5=222TP78 2.4 已知线性规划问题：maxz=2x1+4x2+x3+x4+x48x1+3x22x+x612x2+x3+x46x+x+x9123x1,x2,x3,x40求: (1) 写出其对偶问题；（2）已知原问题最优解为X*=(2,2,4,0)，试根据对偶理论，直接求出对偶问题的最优解。 解：（1）该线性规划问题的对偶问题为：minw=8y1+6y2+6y3+9y4+y42y1+2y23y+y+y+y41234y3+y41y+y311y1,y2,y3,y40（2）由原问题最优解为X*=(2,2,4,0)，根据互补松弛性得：+y4=2y1+2y23y1+y2+y3+y4=4 y3+y4=1把X*=(2,2,4,0)代入原线性规划问题的约束中得第四个约束取严格不等号，即2+2+4=827 2从而得最优解x*=(0,0,5,0,0,5/2)T；最优值为zmax=45+3所以产品D值得生产。P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。 表3-35解：因为ai=bj，即产销平衡.所以由已知和最小元素法可得初始方案为i=1j=134检验：检验：由于还有检验数小于零，所以需调整，调整二：检验：从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为：zmin=25+25+710+915+1110+180=335表34解：因为ai=58bj=55，即产大于销，所以需添加一个假想的销地，销i=1j=1量为3，构成产销平衡问题，其对应各销地的单位运费都为0。由上表和最小元素法可得初始方案为检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin=69+51+310+17+413+315+03=193表3-3735解：因为ai=80bj=100，即销大于产，所以需添加一个假想的产地，产i=1j=1量为20，构成产销平衡问题，其对应各销地的单位运费都为0。由上表和最小元素法可得初始方案为检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin=320+520+410+65+325+80+020+00=305P127 4.8 用割平面法求解整数规划问题。maxz=7x1+9x2a） x,x0,且为整数12-x1+3x267x1+x235解：该问题的松弛问题为：maxz=7x1+9x2-x1+3x267x1+x235x,x012则单纯形法求解该松弛问题得最后一单纯形表为：割平面1为：(3+1/2)=x2+(0+7/22)x3+(0+1/22)x4171711-x3-x4=x2-30x3+x4-x5=2222222222割平面2为：(4+4/7)=x1+(0+1/7)x4+(-1+6/7)x5164416-x4-x5=x1-x5-40x4+x5-x6=777777x*=(4,3)，最优值为zmax=74+93=55TP144 5.3 用图解分析法求目标规划模型+- -min P1 d1+ P2 d+ P（2d+1d） 2334-+c） x1 + x2 + d1 - d1= 40x1 + x2 + d2- - d2+= 40+10=50 x1 + d3- - d3+= 24 s.t.x2 + d4- - d4+= 30x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- 0-解:由下图可知，满足mind1的满意解为区域X2CDX1；满足mind2+的满意解为闭区域BCDEB； 满足min2d3-的满意解为图中的A 点,满足mind4-的满意解为图中的A 点，所以该问题的满意解为图中的点A（24，26） 。用图解分析法求目标规划模型+minz=P1d1+P2d3+P3d2-x1+2x2+d1-d1+=4-+x1-2x2+d2-d2=4-+x+2x+d-d=81233-+x1,x20;di、di0i=1,2,3的满意解。解：由下图可知，满足mind1+的满意解为区域CDOA； 满足mind3+的满意解为闭区域MCDOM；+满足mind2的满意解为图中的阴影部分，即为图中的凸多边形OABCDO 。P170 6.4 求下图中的最小树解：避圈法为：得到最小树为：P171 6.7 用标号法求下图中点v1到各点的最短路。解：如下图所示：P 173 6.14 用Ford-Fulkerson的标号算法求下图中所示各容量网络中从vs到vt的最大流，并标出其最小割集。图中各弧旁数字为容量cij，括弧中为流量fij.B)解：对上有向图进行2F标号得到由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为(vs,v3),(vs,v4),(vs,v5),(v1,vt),(v2,vt),(v2,v3)*所以从vs到vt的最大流为：fst=1+2+5+3+2+1=14C)解：对上有向图进行2F标号得到由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为(vs,v1),(vs,v3),v(2v,5)，所以从vs到vt的最大流为：*fst=5+3+5=13P193 7.1 根据下表给定的条件