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

1、第四版运筹学部分课后习题解答运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题min z=2x1+3x2ì4x1+6x2³6a） ïs.tí4x1+2x2³4ïx,x³0î12解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为3最优解，即该问题有无穷多最优解，这时的最优值为zmin=2´+3´0=32运筹学第三版课后习题答案P47 1.3 用图解法和单纯形法求解线性规划问题max z=10x1+5x2ì3x1+4x2£9ïs.t&#

2、237;5x1+2x2£8ïx,x³0î12a）解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，ìx=1Tì3x1+4x2=9ï13æö*Þí即í3，即最优解为x=ç1,÷è2øî5x1+2x2=8ïx2=î2这时的最优值为zmax=10´1+5´335= 22单纯形法： 原问题化成标准型为max z=10x1+5x2ì3x1+4x2+x3=9ï

3、s.tí5x1+2x2+x4=8ïx,x,x,x³0î1234335æ3ö所以有x*=ç1,÷,zmax=10´1+5´=22è2øTP78 2.4 已知线性规划问题：maxz=2x1+4x2+x3+x4+x4£8ìx1+3x2ï2x+x£612ïïx2+x3+x4£6íïx+x+x£9ï123ïîx1,x2,x3,x4³0求: (1)

4、写出其对偶问题；（2）已知原问题最优解为X*=(2,2,4,0)，试根据对偶理论，直接求出对偶问题的最优解。 解：（1）该线性规划问题的对偶问题为：minw=8y1+6y2+6y3+9y4+y4³2ìy1+2y2ï3y+y+y+y³41234ïïy3+y4³1íïy+y3³1ï1ïîy1,y2,y3,y4³0（2）由原问题最优解为X*=(2,2,4,0)，根据互补松弛性得：+y4=2ìy1+2y2ïí3y1+y2+y3+y4=

5、4 ïy3+y4=1î把X*=(2,2,4,0)代入原线性规划问题的约束中得第四个约束取严格不等号，即2+2+4=8<9Þy4=0=2ìy1+2y2ï从而有í3y1+y2+y3=4ïy3=1î43得y1=,y2=,y3=1,y4=05543所以对偶问题的最优解为y*=(,1,0)T，最优值为wmin=1655P79 2.7 考虑如下线性规划问题：minz=60x1+40x2+80x3ì3x1+2x2+x3³2ï4x+x+3x³4ï123íï

6、2x1+2x2+2x3³3ïîx1,x2,x3³0（1）写出其对偶问题；（2）用对偶单纯形法求解原问题； 解：（1）该线性规划问题的对偶问题为：maxw=2y1+4y2+3y3ì3y1+4y2+2y3£60ï2y+y+2y£40ï123íïy1+3y2+2y3£80ïy1,y2,y3³0î（2）在原问题加入三个松弛变量x4,x5,x6把该线性规划问题化为标准型：maxz=-60x1-40x2-80x3=-2ì-3x1-2x2-x3+x4

7、ï-4x-x-3x+x=-4ï1235í+x6=-3ï-2x1-2x2-2x3ïxj³0,j=1,L,6îx*=(,0)T,zmax=60´+40´+80´0=63633P81 2.12 某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。要求：（a）确定获利最大的产品生产计划；（b）产品A的利润在什么范围内变动时，上述最优计划不变；（c）如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ （d） 如果劳动力数量不增，材料不足时可

8、从市场购买，每单位0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。 解：由已知可得，设xj表示第j种产品，从而模型为：maxz=3x1+x2+4x3ì6x1+3x2+5x3£45ïs.tí3x1+4x2+5x3£30ïx1,x2,x3³0îa) 用单纯形法求解上述模型为：得到最优解为x*=(5,0,3)T；最优值为zmax=3´5+4´3=27b）设产品A的利润为3+l，则上述模型中目标函数x1的系数用3+l替代并求解得：要最优计划不变，要求有如下的不等式方程组成立lì-2+

9、£0ï3ï39ï1l-£0-£l£解得： í5355ïï3lï-5+3£0î9ùé3é24ù从而产品A的利润变化范围为：ê3-,3+ú,即ê2,4ú5ûë5ë55ûC）设产品D用x6表示，从已知可得s6=c6-cBB-1P6=1/51ùé1-é2ùêú8éù33P6&#

10、39;=B-1P6=êúêú=ê4úê-12úë2ûê-úë5ûêë55úû把x6加入上述模型中求解得：=27.5>27 2从而得最优解x*=(0,0,5,0,0,5/2)T；最优值为zmax=4´5+3´所以产品D值得生产。P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。 表3-35解：因为åai=åbj，即产销平衡.所以

11、由已知和最小元素法可得初始方案为i=1j=134检验：检验：由于还有检验数小于零，所以需调整，调整二：检验：从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为：zmin=2´5+2´5+7´10+9´15+11´10+18´0=335表34解：因为åai=58>åbj=55，即产大于销，所以需添加一个假想的销地，销i=1j=1量为3，构成产销平衡问题，其对应各销地的单位运费都为0。由上表和最小元素法可得初始方案为检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin=6´

12、;9+5´1+3´10+1´7+4´13+3´15+0´3=193表3-3735解：因为åai=80<åbj=100，即销大于产，所以需添加一个假想的产地，产i=1j=1量为20，构成产销平衡问题，其对应各销地的单位运费都为0。由上表和最小元素法可得初始方案为检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin=3´20+5´20+4´10+6´5+3´25+8´0+0´20+0´0=305P127 4.8

13、用割平面法求解整数规划问题。maxz=7x1+9x2a） ïìíïx,x³0,且为整数î12-x1+3x2£67x1+x2£35解：该问题的松弛问题为：maxz=7x1+9x2ì-x1+3x2£6ïí7x1+x2£35ïx,x³0î12则单纯形法求解该松弛问题得最后一单纯形表为：割平面1为：(3+1/2)=x2+(0+7/22)x3+(0+1/22)x4171711-x3-x4=x2-3£0Þx3+x4-x5=222

14、2222222Þ割平面2为：(4+4/7)=x1+(0+1/7)x4+(-1+6/7)x5Þ164416-x4-x5=x1-x5-4£0Þx4+x5-x6=777777x*=(4,3)，最优值为zmax=7´4+9´3=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 、

15、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,x2³0;di、di

16、³0i=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)解：对上有向图进