运筹学部分课后习题解答

1、运筹学部分课后习题解答P47 用图解法求解线性规划问题min z=2x1 3x24x1 6x2 6a ) 1 2s.t. 4x1 2x2 4x1,x2 0解：由图 1 可知，该问题的可行域为凸集 MABC，N且可知线段 BA上的点都为3最优解，即该问题有无穷多最优解，这时的最优值为 zmin =2 3 3 0 3min 2P47 用图解法和单纯形法求解线性规划问题 max z=10x1 5x2 3x1 4x2 9a ) 1 2s.t. 5x1 2x2 8x1,x2 0T1,3 T2解：由图 1 可知，该问题的可行域为凸集 OABC，O且可知 B 点为最优值点，即 3x1 4x2 9 3 ，即最

2、优解为 x* 5x1 2x2 8x22这时的最优值为 zmax=10 1 5 23 325单纯形法：原问题化成标准型为max z=10x1 5x23x1 4x2 x3 9cj10500CBXBbx1x2x3x40x3934100x485201Cj Z j105000x321/5014/51-3/510x18/512/501/5Cj Z j010-25x23/2015/14-3/1410x1110-1/72/7Cj Z j00-5/14-25/14s.t. 5x1 2x2 x4 8x1,x2,x3,x40maxz2x14x2x3 x4x13x2x482x1x26x2x3x46x1x2x39x1,

3、x2,x3,x40所以有 x*1,3210 1 5 32352P78 已知线性规划问题：求: (1) 写出其对偶问题；(2)已知原问题最优解为 X* (2,2,4,0) ，试根据对偶理论，直接求出对偶问题的最优解。 解：(1)该线性规划问题的对偶问题为：2)minw8y16y26y39y4y12y2y423y1y2y3y44y3y41y1y31y1, y2,y3,y40由原问题最优解为*X*(2,2,4,0)，根据互补松弛性得y12y2y423y1 y2y3y44y3y41把 X * (2,2,4,0) 代入原线性规划问题的约束中得第四个约束取严格不等号，即 2 2 489 y40y12y22

4、从而有3y1y2 y34y3 1得 y 4得 y15,y2335,y31,y4 0所以对偶问题的最优解为 y* ( 4 , 3 ,1,0)T ，最优值为 wmin 1655P79 考虑如下线性规划问题：min z 60x1 40x2 80x33x1 2x2 x3 24x1 x2 3x3 42x1 2x2 2x3 3x1, x2 , x3 0（1）写出其对偶问题；（2）用对偶单纯形法求解原问题；解：（1）该线性规划问题的对偶问题为：max w 2y1 4y2 3y33y1 4y2 2y3 602y1 y2 2y3 40y1 3y2 2y3 80y1, y2 , y3 0（2）在原问题加入三个松弛

5、变量 x4,x5,x6 把该线性规划问题化为标准型max z60x1 40x2 80x33x12x2x3x424x1x23x3x542x12x22x3x63xj0, j1,L ,6cj-60-40-80000CBXBbx1x2x3x4x5x60x4-2-3-2-11000x5-4-4-1-30100x6-3-2-2-2001Cj Z j-60-40-800000x410-5/45/41-1/12080x1111/43/40-1/400x6-10-3/2-1/20-1/21Cj Z j0-25-350-1500x411/6005/311/3-5/680x15/6102/30-1/31/640x2

6、2/3011/301/3-2/3Cj Z j00-80/30-20/3-50/3x* (65,23,0) T,zmax 60 56 40 32 80 0 23306 3 6 3 3P81 某厂生产 A、B、C 三种产品，其所需劳动力、材料等有关数据见下表。 要求：（ a）确定获利最大的产品生产计划； （b）产品 A 的利润在什么范围内变动 时，上述最优计划不变；（c）如果设计一种新产品 D，单件劳动力消耗为 8 单位， 材料消耗为 2 单位，每件可获利 3 元，问该种产品是否值得生产 （d） 如果劳 动力数量不增，材料不足时可从市场购买，每单位 元。问该厂要不要购进原材 料扩大生产，以购多少为

7、宜。消 耗 产品ABC可用量（单位）定额资源劳动力63545材料34530产品利润（元 / 件）31 4解：由已知可得，设 xj表示第 j 种产品，从而模型为：max z 3x1 x2 4x36x1 3x2 5x3 45s.t. 3x1 4x2 5x3 30 x1,x2,x3 0a) 用单纯形法求解上述模型为：cj31400CBXBbx1x2x3x4x50x445635100x53034501Cj Z j314000x4153-101-14x363/54/5101/5Cj Z j3/5-11/500-4/53x151-1/301/3-1/34x33011-1/52/5Cj Z j0-20-1/

8、5-3/5得到最优解为 x* (5,0,3) T ；最优值为 zmax 3 5 4 3 27b )设产品 A 的利润为 3 ，则上述模型中目标函数 x1的系数用 3 替代并求解得：cj31400CBXBbx1x2x3x4x53x151-1/301/3-1/34x33011-1/52/5CZjj-20-1/5-3/5CZjj0-2+ /30-1/5- /3-3/5+ /3要最优计划不变，要求有如下的不等式方程组成立10 解得： 35353053230从而产品 A的利润变化范围为： 3 3,3 9 ,即 22 ,445 5 5 5C)设产品 D用 x6表示，从已知可得16 c6 cB B P6 1

9、/ 5P6 B 1P6122所以产品 D 值得生产。55cj314003CBXBbx1x2x3x4x5x63x151-1/301/3-1/324x33011-1/52/5-4/5Cj Z j0-20-1/5-3/51/53x65/21/2-1/601/6-1/614x352/513/151-1/154/150Cj Z j-1/10-59/300-7/30-17/300把 x6 加入上述模型中求解得：从而得最优解 x* (0,0,5,0,0,5 /2)T ；最优值为 zmax 4 5 3 27.5 27 2d)P101 已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最 优解及最小

10、运费。表 3-35解：由已知和最小元素法可得初始方案为检验：由于有两个检验数小于零，所以需调整，调整一：检验：检验：由于还有检验数小于零，所以需调整，调整二：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为： zmin 2 5 2 5 7 10 9 15 11 10 18 0 335表 3-36A184127A2694725A3534326销量10102015B1B2B358产地销地B4产量3解：因为 aii14bj 55 ，即产大于销，所以需添加一个假想的销地，销 j1量为 3，构成产销平衡问题，其对应各销地的单位运费都为0由上表和最小元素法可得初始方案为检验：从上表可以看出所有的

11、检验数都大于零，即为最优方案最小运费为： zmin 6 9 5 1 3 10 1 7 4 13 3 15 0 3 193解：因为 ai 80bj 100 ，即销大于产，所以需添加一个假想的产地，产i 1 j1量为 20，构成产销平衡问题，其对应各销地的单位运费都为0产地销地B1B2B3B4B5产量A18637520A25M84730A36396830A40000020销量2525201020由上表和最小元素法可得初始方案为销地产地B1B2B3B4B5产量A12020A25101530A325530A420020销量2525201020检验：由于有两个检验数小于零，所以需调整，调整一：产地销地B

12、1B2B3B4B5产量A12020A2201030A325530A4501520销量2525201020检验：由于还有检验数小于零，所以需调整，调整二：销地产地B1B2B3B4B5产量A12020A2201030A3525030A402020销量2525201020检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为： zmin 3 20 5 20 4 10 6 5 3 25 8 0 0 20 0 0 305P127 用割平面法求解整数规划问题max z 7x1 9x2x1 3x2 6 a)7x1 x2 35x1,x2 0,且为整数解：该问题的松弛问题为：max z 7 x1 9

13、x2x1 3x2 67 x1 x2 35x1, x2 0则单纯形法求解该松弛问题得最后一单纯形表为：cj7900CBXBbx1x2x3x49x27/2017/221/227x19/210-1/223/22Cj Z j00-28/11-15/11割平面 1为： (3 1/2) x2 (07/ 22)x3(0 1/ 22) x41 7 1711x3x4 x2 3 0x3x4 x52 22 3 22 4 2 从而有22 3222cj79000CBXBbx1x2x3x4x59x27/2017/221/2207x19/210-1/223/2200x5-1/200-7/22-1/221Cj Z j00-2

14、8/11-15/1109x23010017x132/71001/7-1/70x311/70011/7-22/7Cj Z j000-1-8割平面 2为： (4 4/7) x1 (0 1/ 7) x4 ( 1 6/7)x54 1 6 1 6 4 x4 x5 x1 x5 4 0 x4 x5 x67 7 4 7 5 1 5 7 4 7 5 6 7cj790003CBXBbx1x2x3x4x5x69x230100107x132/71001/7-1/700x311/70011/7-22/700x6-4/7000-1/7-6/71Cj Z j000-1-809x230100107x141000-110x31

15、0010-410x4400016-7Cj Z j0000-2-7由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即*Tx* 4,3 T ，最优值为 zmax 7 4 9 3 55P144 用图解 分析法求目标规划模型min Z = P1 d1-+ P2 d2+ P3( 2d3- +1d4- )c )x1 + x 2 + d1- - d1+= 40x1 + x 2 + d2- - d2+= 40+10=50.x1+ d3- - d3+= 24x 2 + d4- - d4+= 30x1 、x2 、d1 、 d1 、d2 、d2 、d3 、d3 、d4 、d4 0解:由下图可知，满

16、足目标函数的满意解为图中的 A 点P170 求下图中的最小树解：避圈法为：得到最小树为：P171 用标号法求下图中点 v1 到各点的最短路P 173 用Ford-Fulkerson 的标号算法求下图中所示各容量网络中从 vs到vt 的最 大流，并标出其最小割集。图中各弧旁数字为容量 cij ，括弧中为流量 fij .B)解：对上有向图进行 2F 标号得到由于所有点都被标号了， 即可以找到增广链， 所以流量还可以调整， 调整量为 1， 得由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小 割为与直线 KK相交的弧的集合，即为(vs, v3 ),( vs ,v4 ),( vs ,v5),( v1,vt ),( v2 ,vt ),( v2, v3)所以从 vs到vt 的最大流为： fs*t 1 2 5 3 2 1 14C)解：对上有向图进行 2F 标号得到由图可知， 标号中断，所以已经是最大流了， 最大流量等于最小割的容量， 最小割为与直线KK 相交的弧的集合，即为(vs,v1),(vs,v3),(v2,v5) ，所以 从vs到vt 的最大流为：fst 5 3 5 13P193 根据下表给定的条件，绘制 PERT网络图 表 7