运筹学习题答案注释(第2章).doc

运筹学习题答案及注释 第 1 页 运筹学习题答案及注释运筹学习题答案及注释 2.3 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表 2-32 所示，求表中各括弧内未知数的值。 cj 322000 CB基bx1x2x3x4x5x6 0 x4（b） 111100 0 x5 15 （a） 12010 0 x6 202 （c） 1001 cj- zj322000 0 x4 5/400(d) (l)-1/4-1/4 3 x1 25/410(e)03/4(i) 2 x2 5/201(f)0(h)1/2 cj- zj0(k)(g)0-5/4(j) 解：最后结果如下： cj 322000 CB基bx1x2x3x4x5x6 0 x4（10） 111100 0 x5 15 （2） 12010 0 x6 202 （3） 1001 cj- zj322000 0 x4 5/400(1/4) (1)-1/4-1/4 3 x1 25/410(5/4)03/4(-1/4) 2 x2 5/201(-1/2)0(-1/2)1/2 cj- zj0(0)(-3/4)0-5/4(-1/4) 注释：注释：由题中初始单纯形表及、最终单纯形表，我们可以看出：在初始单纯形表中，先选 x1进基，选 x5出基，做变换；然后再选 x2进基，选 x6出基，做变换，则得到最终单纯形表。 2.7 给出线性规划问题。 max 4321 42xxxxz st. 0, 9 6 62 83 4321 321 432 21 421 xxxx xxx xxx xx xxx 要求：（1）写出其对偶问题；（2）已知原问题最优解为 X*=（2，2，4，0） ，试根据对偶 理论，直接求出对偶问题的最优解。 解：（1）其对偶问题为： min 4321 9668yyyyw 运筹学习题答案及注释 第 2 页 st. 0, 9 1 43 22 4321 31 432 4321 421 yyyy yy yyy yyyy yyy （2）用单纯形法解原问题，将原问题化成标准形式如下： max 87654321 000042xxxxxxxxz st. 0, 9 6 62 83 87654321 8321 7432 621 5421 xxxxxxxx xxxx xxxx xxx xxxx 因此，可得如下单纯形表： cj 24110000 CB基bx1x2x3x4x5x6x7x8 0 x5 813011000 0 x6 621000100 0 x7 601110010 0 x8 911100001 cj- zj24110000 因 421，所以选 x2进基，因 8/369，故选 x5出基，则得 cj 24110000 CB基bx1x2x3x4x5x6x7x8 4 x2 8/31/3101/31/3000 0 x6 10/35/300-1/3-1/3100 0 x7 10/3-1/3012/3-1/3010 0 x8 19/32/301-1/3-1/3001 cj- zj2/301-1/3-4/3000 因 12/3，所以选 x3进基，因 10/319/3，故选 x7出基，则得 cj 24110000 CB基bx1x2x3x4x5x6x7x8 4 x2 8/31/3101/31/3000 0 x6 10/35/300-1/3-1/3100 1 x3 10/3-1/3012/3-1/3010 0 x8 3100-100-11 cj- zj100-1-10-10 因 10，所以选 x1进基，因（10/3）/（5/3）3/1（8/3）/（1/3） ，故选 x6出基，则得 cj 24110000 CB基bx1x2x3x4x5x6x7x8 4 x2 20102/52/5-1/500 2 x1 2100-1/5-1/53/500 运筹学习题答案及注释 第 3 页 1 x3 40013/5-2/51/510 0 x8 1000-4/51/5-3/5-11 cj- zj000-4/5-4/5-3/5-10 所以，最优解为：X*=（2，2，4，0，0，0，0，1） ，代入目标函数得 z =16。 其对偶问题得最优解为：X*=（4/5，3/5，1，0，0，0，0，4/5） ，代入目标函数得 w=16。 2.9 用对偶单纯形法求解下列线性规划问题。 （2）min 321 425xxxz st. 0, 10536 423 321 321 321 xxx xxx xxx 解：先将问题改写为： max 54321 00425xxxxxz st. 0, 10536 423 54321 5321 4321 xxxxx xxxx xxxx 约束条件两端乘“1”得 max 54321 00425xxxxxz st. 0, 10536 423 54321 5321 4321 xxxxx xxxx xxxx 列出单纯行表，并用对偶单纯形法求解步骤进行计算，其过程如下： cj -5-2-400 CB基bx1x2x3x4x5 0 x4 -4-3-1-210 0 x5 -10-6-3-501 cj- zj-5-2-400 因-10-4，所以选 x5出基，因 2/34/55/6，故选 x2进基，则得 cj -5-2-400 CB基bx1x2x3x4x5 0 x4 -2/3-10-1/31-1/3 -2 x2 10/3215/30-1/3 cj- zj-10-2/30-2/3 选 x4出基，因 12，故选 x1进基，则得 cj -5-2-400 CB基bx1x2x3x4x5 -5 x1 2/3101/3-11/3 -2 x2 20112-1 cj- zj00-1/3-1-1/3 运筹学习题答案及注释 第 4 页 将最优解代入目标函数，得目标值：min 322z 2.10 考虑如下线性规划问题： min 321 804060 xxxz st. 0, 3222 434 223 321 321 321 321 xxx xxx xxx xxx 要求：（1）写出其对偶问题；（2）用对偶单纯形法求解原问题；（3）用单纯形法求解其 对偶问题；(4)对比（2）与（3）中每步计算得到的结果。 解：（1）其对偶问题为： max 321 342yyyw st. 0, 8023 4022 60243 321 321 321 321 yyy yyy yyy yyy （2）将原问题改写为： max 654321 000804060 xxxxxxz st. 0, 3222 434 223 654321 6321 5321 4321 xxxxxx xxxx xxxx xxxx 约束条件两端乘“1”得 max 654321 000804060 xxxxxxz st. 0, 3222 434 223 654321 6321 5321 4321 xxxxxx xxxx xxxx xxxx 因此，可得如下初始单纯形表： cj -60-40-80000 CB基bx1x2x3x4x5x6 0 x4 -2-3-2-1100 0 x5 -4-4-1-3010 0 x6 -3-2-2-2001 cj- zj-60-40-80000 因-4-3-2，所以选 x5出基，因 60/480/340，故选 x1出基，则得 运筹学习题答案及注释 第 5 页 cj -60-40-80000 CB基bx1x2x3x4x5x6 0 x4 10-5/45/41-3/40 -60 x1 111/43/40-1/40 0 x6 -10-3/2-1/20-1/21 cj- zj0-25-350-150 因-10，所以选 x6出基，因 25/（3/2）3070，故选 x2进基，则得 cj -60-40-80000 CB基bx1x2x3x4x5x6 0 x4 11/6005/31-1/3-5/6 -60 x1 5/6102/30-1/31/6 -40 x2 2/3011/301/3-2/3 cj- zj0-25-80/30-20/3-50/3 （3）将其对偶问题改为： max 654321 000342yyyyyyw st. 0, 8023 4022 60243 654321 7321 6321 5321 yyyyyy yyyy yyyy yyyy 因此，可得如下初始单纯形表： cj 243000 CB基by1y2y3y4y5y6 0 y4 60342100 0 y5 40212010 0 y6 80132001 cj- zj243000 因 432，所以选 y2进基，因 60/480/340，故选 y4出基，则得 cj 243000 CB基by1y2y3y4y5y6 4 y2 153/411/21/400 0 y5 255/403/2-1/410 0 y6 35-5/401/2-3/401 cj- zj-101-100 因 10，所以选 y3进基，因 25/(3/2)3070，故选 y5出基，则得 cj 243000 CB基by1y2y3y4y5y6 4 y2 20/31/3101/3-1/30 3 y3 50/35/601-1/62/30 0 y6 80/3-5/300-2/301 cj- zj-11/600-5/6-2/30 (4) 对比（2）与（3）中每步计算得到的结果可知： 运筹学习题答案及注释 第 6 页 （2）中 cj- zj的相反数就是（3）中解；（2）中的解就是（3）中 cj- zj的相反数。 2.11 已知线性规划问题： max 321 2xxxz st. 0, 422 6 321 21 321 xxx xx xxx 先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。 （1）目标函数变为 max ； 321 32xxxz （2）约束右端项由变为； 4 6 4 3 （3）增添一个新的约束条件。22 31 xx 解：先将问题改写为： max 321 2xxxz st. 0, 422 6 54321 521 4321 xxxxx xxx xxxx 列出单纯形表，并用单纯形法求解步骤进行计算，其过程如下： cj 2-1100 CB基bx1x2x3x4x5 0 x4 611110 0 x5 4-12001 cj- zj2-1100 因 210，所以选 x1进基，因 01，故选 x4出基，则得 cj 2-1100 CB基bx1x2x3x4x5 2 x1 611110 0 x5 1003111 cj- zj0-3-1-20 得最优解为：（6，0，0） ，代入目标函数得 z = 12。 （1）目标函数变为 max 时，直接反映到最终单纯形表中得： 321 32xxxz cj 23100 CB基bx1x2x3x4x5 2 x1 611110 0 x5 1003111 cj- zj01-1-20 因 x2的检验数 10，所以原最优解已经不是新问题的最优解；选 x2进基，因 10/36/1， 运筹学习题答案及注释 第 7 页 故选 x5出基，则得 cj 23100 CB基bx1x2x3x4x5 2 x1 8/3102/32/3-1/3 3 x2 10/3011/31/31/3 cj- zj00-4/3-7/3-1/3 得最优解为：（8/3，10/3，0） ，代入目标函数得 z = 46/3 。 （2）约束右端项由变为时；有 4 6 4 3 b 0 3 = b 3 3 0 3 11 01 1b B 将上述结果反映到单纯形表中得： cj 2-1100 CB基bx1x2x3x4x5 2 x1 311110 0 x5 703111 cj- zj0-3-1-20 此时，上表中的解仍为可行解，故最优解为：（3，0，0） ，代入目标函数得 z = 6 。 （3）增添一个新的约束条件。22 31 xx 将原最优解（6，0，0）代入新的约束条件。 ，得知：原最优解不满22 31 xx 足新的约束条件，所以原最优解不是此时的最优解。 在新的约束条件。中，加松弛变量 x6 ，得 ；即22 31 xx22 631 xxx ，反映到单纯形表中得：22 631 xxx cj 2-11000 CB基bx1x2x3x4x5x6 2 x1 6111100 0 x5 10031110 0 x6 -210-2001 cj- zj0-3-1-200 因为 x1列不是单位向量，故需进行变换，得下面单纯形表。下表中行同上表中的 行，下表中行由以下初等变换得到： - cj 2-11000 CB基bx1x2x3x4x5x6 2 x1 6111100 0 x5 10031110 0 x6 -80-1-3-101 cj- zj0-3-1-200 因-80，使用对偶单纯形法求解，选 x6出基，因 1/323，故选 x3进基，则得 运筹学习题答案及注释 第 8 页 cj 2-11000 CB基bx1x2x3x4x5x6 2 x1 10/312/302/301/3 0 x5 22/308/302/311/3 1 x3 8/301/311/30-1/3 cj- zj0-3-1-200 故最优解为：（10/3，0，8/3） ，代入目标函数得 z = 28/3 。 2.12 给出线性规划问题： max 321 32xxxz st. 0, 3 3 7 3 4 3 1 1 3 1 3 1 3 1 321 321 321 xxx xxx xxx 用单纯形法求解得最终单纯形表见表 2-33 。 cj 23100 CB基bx1x2x3x4x5 2 x1 110-14-1 3 x2 2012-11 cj- zj00-3-5-1 试分析下列各种条件下最优解（基）的变化： （1）目标函数中变量 x3的系数变为 6 ； （2）分别确定目标函数中变量 x1和 x2的系数c1、c2在什么范围内变动时最优解不变； （3）约束右端项由变为； 3 1 3 2 （4）增加一个新的变量 x6，, c6 = 7 ； 1 1 6 P （5）增添一个新的约束。42 321 xxx 解：（1）目标函数中变量 x3的系数变为 6 时，得如下单纯形表，并用单纯形法求解步骤 进行计算，其过程如下： cj 23600 CB基bx1x2x3x4x5 2 x1 110-14-1 3 x2 2012-11 cj- zj002-5-1 因 20，所以选 x3进基，因 20，故选 x2出基，则得 cj 23600 运筹学习题答案及注释 第 9 页 CB基bx1x2x3x4x5 2 x1 211/207/2-1/2 6 x3 101/21-1/21/2 cj- zj0-10-4-2 得最优解为：（2，0，1） ，代入目标函数得 z = 10 。 （2）设目标函数中变量 x1和 x2的系数为c1、c2 ，则由原单纯形表得如下单纯形表： cjc1 c2100 CB基bx1x2x3x4x5 c1x1110-14-1 c2 x2 2012-11 cj- zj001+ c1- 2c2 -4c1+ c2c1- c2 若要保持原问题最优解不变，则应有所有检验数均小于等于 0；即 即 0 04 021 21 21 21 cc cc cc 21 12 21 4 12 cc cc cc （3）约束右端项由变为；有 3 1 3 2 b 0 1 = b 1 4 0 1 11 14 1b B 将上述结果反映到单纯形表中得： cj 23100 CB基bx1x2x3x4x5 2 x1 510-14-1 3 x2 1012-11 cj- zj00-3-5-1 此时，上表中的解仍为可行解，故最优解为：（5，1，0） ，代入目标函数得 z = 13 。 （4）增加一个新的变量 x6，, c6 = 7 ； 1 1 6 P 0 3 1 1 11 14 1 66 PBP 检验数 c6- z6 = 7 - 3*2 = 1 ，将上述结果反映到单纯形表中得： cj 231007 CB基bx1x2x3x4x5x6 2 x1 110-14-13 3 x2 2012-110 运筹学习题答案及注释 第 10 页 cj- zj00-3-5-11 因 x6的检验数 10，所以原最优解已经不是新问题的最优解；选 x6进基，因 30，故选 x1出基，则得 cj 231007 CB基bx1x2x3x4x5x6 7 x6 1/31/30-1/34/3-1/31 3 x2 2012-110 cj- zj-1/30-8/3-19/3-2/30 故最优解为：（0，2，0，0，0，1/3） ，代入目标函数得 z = 6 + 7/3 = 25/3 。 （5）增添一个新的约束。42 321 xxx 将原最优解（1，2，0）代入新的约束条件 ，得知：原最优解不满42 321 xxx 足新的约束条件，所以原最优解不是此时的最优解。 在新的约束条件中，加松弛变量 x6 ，得 ，42 321 xxx42 6321 xxxx 反映到单纯形表中得： cj 231000 CB基bx1x2x3x4x5x6 2 x1 110-14-10 3 x2 2012-110 0 x6 4121001 cj- zj00-3-5-10 因为 x1 、x2列不是单位向量，故需进行变换，得下面单纯形表。下表中行同上表中的 行，下表中行由以下初等变换得到： - 2* - cj 231000 CB基bx1x2x3x4x5x6 2 x1 110-14-10 3 x2 2012-110 0 x6 -100-2-2-11 cj- zj00-3-5-10 因-10，使用对偶单纯形法求解，选 x6出基，因 13/25/2，故选 x5进基，则得 cj 231000 CB基bx1x2x3x4x5x6 2 x1 210160-1 3 x2 1010-301 0 x5 100221-1 cj- zj00-3-5-10 故最优解为：（2，1，0） ，代入目标函数得 z = 7 。 运筹学习题答案及注释 第 11 页 2.13 分析下列线性规划问题中，当 变化时最优解的变化，并画出对 的变化关)(z 系图。 （2）min 4321 2 xxxxz st. )4, 1(0 532 22 421 431 jx xxx xxx j 解：首先用两阶段法求解 0 时的线性规划问题的最优解，具体过程如下： 由题意可得如下初始单纯形表： cj 0000-1-1 CB基bx1x2x3x4x5x6 -1 x5 2101210 -1 x6 5210301 cj- zj3115-1-1 因 53