1、第四版运筹学部分课后习题解答运筹学部分课后习题解答http:/ 1.1 用图解法求解线性规划问题min z=2x13x24x16x26a） s.t4x12x24x,x012解：由图 1 可知，该问题的可行域为凸集 MABCN，且可知线段 BA 上的点都为3最优解，即该问题有无穷多最优解，这时的最优值为 zmin=23032运筹学第三版课后习题答案P47 1.3 用图解法和单纯形法求解线性规划问题max z=10x15x23x14x29s.t5x12x28x,x012a）解：由图 1 可知，该问题的可行域为凸集 OABCO，且可知 B 点为最优值点，x1T3x14x2913*即3 ，即最优解为
2、x1,25x12x28x22这时的最优值为 zmax=1015335 22单纯形法： 原问题化成标准型为max z=10x15x23x14x2x39s.t5x12x2x48x,x,x,x012343353所以有 x*1,zmax1015222TP78 2.4 已知线性规划问题：maxz2x14x2x3x4x48x13x22xx612x2x3x46xxx9123x1,x2,x3,x40求: (1) 写出其对偶问题；（2 ）已知原问题最优解为 X*(2,2,4,0)，试根据对偶理论，直接求出对偶问题的最优解。 解：（1）该线性规划问题的对偶问题为：minw8y16y26y39y4y42y12y23
3、yyyy41234y3y41yy311y1,y2,y3,y40（2）由原问题最优解为 X*(2,2,4,0)，根据互补松弛性得：y42y12y23y1y2y3y44 y3y41把 X*(2,2,4,0)代入原线性规划问题的约束中得第四个约束取严格不等号，即22489y402y12y2从而有3y1y2y34y3143得 y1,y2,y31,y405543所以对偶问题的最优解为 y*(,1,0)T，最优值为 wmin1655P79 2.7 考虑如下线性规划问题：minz60x140x280x33x12x2x324xx3x41232x12x22x33x1,x2,x30（1）写出其对偶问题；（2）用对
4、偶单纯形法求解原问题； 解：（1）该线性规划问题的对偶问题为：maxw2y14y23y33y14y22y3602yy2y40123y13y22y380y1,y2,y30（2）在原问题加入三个松弛变量 x4,x5,x6 把该线性规划问题化为标准型：maxz60x140x280x323x12x2x3x44xx3xx41235x632x12x22x3xj0,j1,6x*(,0)T,zmax604080063633P81 2.12 某厂生产 A、B、C 三种产品，其所需劳动力、材料等有关数据见下表。要求：（a）确定获利最大的产品生产计划；（b）产品 A 的利润在什么范围内变动时，上述最优计划不变；（c
5、）如果设计一种新产品 D，单件劳动力消耗为 8 单位，材料消耗为 2 单位，每件可获利 3 元，问该种产品是否值得生产？ （d） 如果劳动力数量不增，材料不足时可从市场购买，每单位 0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。 解：由已知可得，设 xj 表示第 j 种产品，从而模型为：maxz3x1x24x36x13x25x345s.t3x14x25x330x1,x2,x30a) 用单纯形法求解上述模型为：得到最优解为 x*(5,0,3)T；最优值为 zmax354327b）设产品 A 的利润为 3，则上述模型中目标函数 x1 的系数用 3替代并求解得：要最优计划不变，要求有如下
6、的不等式方程组成立2033910解得： 535535309324从而产品 A 的利润变化范围为：3,3, 即2,45555C）设产品 D 用 x6 表示，从已知可得6c6cBB1P61/5112833P6B1P64122555把 x6 加入上述模型中求解得：27.527 2从而得最优解 x*(0,0,5,0,0,5/2)T；最优值为 zmax453所以产品 D 值得生产。P101 3.1 已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。 表 3-35解：因为aibj ，即产销平衡.所以由已知和最小元素法可得初始方案为i1j134检验：检验：由于还有检验数小于零，
7、所以需调整，调整二：检验：从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为：zmin25257109151110180335表 34解：因为ai58bj55 ，即产大于销，所以需添加一个假想的销地，销i1j1量为 3，构成产销平衡问题，其对应各销地的单位运费都为 0。由上表和最小元素法可得初始方案为检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin69513101741331503193表 3-3735解：因为ai80bj100 ，即销大于产，所以需添加一个假想的产地，产i1j1量为 20，构成产销平衡问题，其对应各销地的单位运费都为 0。由上表和最小元素法
8、可得初始方案为检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin320520410653258002000305P127 4.8 用割平面法求解整数规划问题。maxz7x19x2a） x,x0,且为整数12x13x267x1x235解：该问题的松弛问题为：maxz7x19x2x13x267x1x235x,x012则单纯形法求解该松弛问题得最后一单纯形表为：割平面 1 为：(31/2)x2(07/22)x3(01/22)x4171711x3x4x230x3x4x52222222222割平面 2 为：(44/7)x1(01/7)x4(16/7)x5164416x4x5x1x
9、540x4x5x6777777x*4,3，最优值为 zmax749355TP144 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； 满足 min
10、2d3-的满意解为图中的 A 点,满足 mind4-的满意解为图中的 A 点，所以该问题的满意解为图中的点 A（24，26） 。用图解分析法求目标规划模型minzP1d1P2d3P3d2x12x2d1d14x12x2d2d24x2xdd81233x1,x20;di、di0i1,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 标号得到
