运筹学习题答案(第二章)

1、 2.1 写出下列线性规划问题的对偶问题。写出下列线性规划问题的对偶问题。 无约束 321 321 321 321 321 ,0, 534 332 243 422min )1( xxx xxx xxx xxx st xxxZ 无限制 对偶问题 321 321 321 321 321 , 0, 0 4334 243 22 532max : yyy yyy yyy yyy st yyyW 0, 0, 8374 335 522 365max )2( 321 321 321 321 321 xxx xxx xxx xxx st xxxZ 无约束 0, 0, 3332 6752 54 835max 32

2、1 321 321 321 321 yyy yyy yyy yyy st yyyW 无约束 对偶问题： . ), 1, 1(0 ), 1( ), 1( min )3( 1 1 11 njmix njbx miax st xcZ ij n i jij n j iij m i n j ijij mniy njmicyy st ybyaW i ijmji m i n j mjjii , 1 ), 1, 1( . max 11 无限制， 对偶问题： ）无约束（nnjxnnjx mmmibxa mmibxa st xcZ jj n j ijij n j ijij m j jj , 1), 1(0 ),

3、2, 1( ), 1( max )4( 11 1 11 1 1 1 ）无约束（ 对偶问题： mmjy miy nnnjcya njcya st ybybybW i i m i jiij m i jiij mm , 1 ), 1(0 ), 2, 1( ), 2 , 1( min 1 1 1 11 1 1 2211 2.2 判断下列说法是否正确，为什么判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行解，则其对偶如果线性规划的原问题存在可行解，则其对偶 问题也一定存在可行解；问题也一定存在可行解； 答：不对！如原问题是无界解，对偶问题无可行答：不对！如原问题是无界解，对偶问题无可行

4、 解。解。 (2)如果线性规划的对偶问题无可行解，则原问题如果线性规划的对偶问题无可行解，则原问题 也一定无可行解；也一定无可行解； 答：不对！道理同上。答：不对！道理同上。 (3)在互为对偶的一对原问题与对偶问题中，不管在互为对偶的一对原问题与对偶问题中，不管 原问题是求极大或极小，原问题可行解的目标函数值原问题是求极大或极小，原问题可行解的目标函数值 一定不超过其对偶问题可行解的目标函数值；一定不超过其对偶问题可行解的目标函数值； 答：不对！如果原问题是求极小，结论相反。答：不对！如果原问题是求极小，结论相反。 (4)任何线性规划问题具有惟一的对偶问题。任何线性规划问题具有惟一的对偶问题。

5、 答：结论正确！答：结论正确！ 2.3 已知某求极大化线性规划问题用单纯形已知某求极大化线性规划问题用单纯形 法求解时的初始单纯形表及最终单纯形表如下表法求解时的初始单纯形表及最终单纯形表如下表 所示，求表中各括弧内未知数的值。所示，求表中各括弧内未知数的值。 解：解： l=1, k=0 , h=-1/2, a=2, c=3, b=10, e=5/4, f=-1/2, d=1/4, g=-3/4, i=-1/4, j=-1/4 Cj322000 CB基基bX1X2X3X4X5X6 0X1(b)111100 0X215(a)12010 0X3202(c)1001 CjZj 322000 0X45

6、/400(d)(l)-1/4 -1/4 3X125/410(e)03/4(i) 2X25/201(f)0(h)1/2 CjZj 0(k)(g)0-5/4(j) 2.4 给出线性规划问题给出线性规划问题 )4 , 1( , 0 332 232 . 6532min 4321 4321 4321 jx xxxx xxxx st xxxxZ j (1)写出其对偶问题；写出其对偶问题；(2)用图解法求解对偶问题；用图解法求解对偶问题； (3)利用利用(2)的结果及根据对偶问题性质写出原问题最优的结果及根据对偶问题性质写出原问题最优 解。解。 0,0 63 53 32 22 . 32min )1( 21

7、21 21 21 21 21 yy yy yy yy yy st yyW 对偶问题： (2) 最优解是：最优解是：y1=-8/5,y2=1/5,目标函数值目标函数值-19/5。 (3)由于由于 y1=-8/5,y2=1/5都不等于零，原问题中的约都不等于零，原问题中的约 束取等号。又上面第束取等号。又上面第4个约束不等号成立，故个约束不等号成立，故x4=0，令，令 x3=0就可以得到最优解：就可以得到最优解： x1=8/5,x2=1/5。 2.5 给出线性规划问题给出线性规划问题 . , 0, 0 22 1 2 2max 321 321 321 321 321 无约束xxx xxx xxx x

8、xx st xxxZ (1)写出其对偶问题；写出其对偶问题；(2)利用对偶问题性质证明利用对偶问题性质证明 原问题目标函数值原问题目标函数值z1。 0, 0 1 2 1 22min )1 ( 321 321 321 321 321 yyy yyy yyy yyy st yyyW 无约束 对偶问题： (2)y1=y3=0,y2=1时对偶问题的一个可行解，目标时对偶问题的一个可行解，目标 函数值为函数值为1，故原问题的目标函数值小于等于，故原问题的目标函数值小于等于1。 试根据对偶问题性质证明上述线性规划问题目标试根据对偶问题性质证明上述线性规划问题目标 函数值无界。函数值无界。 )3 , 1(

9、, 0 12 2 . 65max 321 321 4321 jx xxx xxx st xxxxZ j 2.6 已知线性规划问题已知线性规划问题 由于由于(1)和和(4)是矛盾约束，故对偶问题无可行解。是矛盾约束，故对偶问题无可行解。 所以原问题目标函数值无界。所以原问题目标函数值无界。 )4(0, )3(0 )2(1 )1 (12 . 2min 21 21 21 21 21 yy yy yy yy st yyW 解：解：x1=1,x2=x3=0是原问题的可行解。原问题的对是原问题的可行解。原问题的对 偶问题为：偶问题为： 要求：要求：(1)写出其对偶问题；写出其对偶问题；(2)已知原问题最优

10、解已知原问题最优解 为为X*=(2，2，4，0)，试根据对偶理论，直接求出对偶，试根据对偶理论，直接求出对偶 问题的最优解。问题的最优解。 )4 , 1( , 0 9 6 62 83 . 42min 321 432 21 421 4321 jx xxx xxx xx xxx st xxxxZ j 2.7 2.7 给出线性规划问题给出线性规划问题 (2)已知原问题最优解为已知原问题最优解为X*=(2，2，4，0)，代入，代入 原问题，第原问题，第4个约束不等式成立，故个约束不等式成立，故y4=0。有由于。有由于 x1,x2,x3大于大于0，上面对偶问题前，上面对偶问题前3个约束取等号，故得个约束

11、取等号，故得 到最优解：到最优解： y1=4/5, y2,=3/5, y3=1, y4=0 )4 , 1( , 0 1 1 13 22 9668min ) 1 ( 31 43 4321 421 4321 jy yy yy yyyy yyy yyyyW j 对偶问题： ), 1( ,0 . min 1 333 1 222 1 111 1 njx ybxa ybxa ybxa st xcZ A j n j jj n j jj n j jj n j jj 影子价格 问题 2.8 已知线性规划问题已知线性规划问题A和和B如下：如下： ), 1( , 0 3)3( 5 1 5 1 55 . min 1

12、3 * 1313 1 2 * 22 1 1 * 11 1 njx ybbxaa ybxa ybxa st xcZ B j n j jjj n j jj n j jj n j jj 影子价格 问题 试分别写出试分别写出yi同同y*i(i1，2，3)间的关系式。间的关系式。 * 3 * 2 * 1321 * 3 * 2 * 1321 005/3 050 005/1 100 010 005/1 100 050 001 003 010 001 yyyyyy yyyyyy )3 , 1( , 0 522 33 . 18124min )1 ( 32 31 321 jx xx xx st xxxZ j 2.

13、9 用对偶单纯形法求解下列线性规划问题。用对偶单纯形法求解下列线性规划问题。 )3 , 1( , 0 10536 423 . 425min )2( 321 321 321 jx xxx xxx st xxxZ j 1,2/3,0 )3 , 1( ,0 532 33 . 18124min )1 ( 321 32 31 321 xxx jx xx xx st xxxZ j 最优解： 0,2, 3/2 )3 , 1( ,0 10536 423 . 425min )2( 321 321 321 321 xxx jx xxx xxx st xxxZ j 最优解： 要求：要求：(1)写出其对偶问题；写出其

14、对偶问题；(2)用对偶单纯形法求用对偶单纯形法求 解原问题；解原问题；(3)用单纯形法求解其对偶问题；用单纯形法求解其对偶问题；(4)对比对比(2) 与与(3)中每步计算得到的结果。中每步计算得到的结果。 . 0, 3222 434 223 804060min 321 321 321 321 321 xxx xxx xxx xxx st xxxZ 2.10 考虑如下线性规划问题：考虑如下线性规划问题： (4) 3 230 Z, 3 50 y , 3 20 y 0,y(3) 3 230 Z0, x, 3 2 x, 6 5 x(2) 0, 8023 4022 60243 342max )1 ( 3

15、21 321 321 321 321 321 321 略 对偶问题： yyy yyy yyy yyy st yyyW 先用单纯形法求出最优解，再分析在下列先用单纯形法求出最优解，再分析在下列 条件单独变化的情况下最优解的变化。条件单独变化的情况下最优解的变化。 解：最优解为解：最优解为x x1 1=6,x=6,x2 2=x=x3 3=0,Z=12 =0,Z=12 )3 , 1( , 0 42 6 . 2max 21 321 321 jx xx xxx st xxxZ j 2.11 已知线性规划问题：已知线性规划问题： 46/3Z0,x10/3,x8/3,x x3x2xmax Z(1) 321

16、321 最优解： 目标函数变为 6, 0, 3 4 3 4 6 (2) 321 Zxxx最优解： 变为约束右端项由 28/3Z8/3,x0,x10/3,x 22xx(3) 321 31 最优解： 增添一个新的约束条件 2.12 2.12 给出线性规划问题给出线性规划问题 用单纯形法求解得最终单纯形表见下表：用单纯形法求解得最终单纯形表见下表： )3 , 1( ,0 3 3 7 3 4 3 1 1 3 1 3 1 3 1 . 32max 321 321 321 jx xxx xxx st xxxZ j 项项 目目23100 CB 基基 bX1X2X3X4X5 2 X1 610-14-1 3 X2

17、 1012-11 CjZj00-3-5-1 试分析下列各种条件下最优解试分析下列各种条件下最优解(基基)的变化：的变化： 3121 321 3 x,xx,x 10Z1,x0,x,2,x ；6的系数变x目标标函数中变(1) 最优基从 最优解： 为量 时最优解不变。 时最优解不变； 最 定确 9, 4c 3, 4 3 c 优解不变；在什 么什么范围内变动c,c 的系数x和x目标标函数中变 分别(2) 2 1 21 21 。其他变量为 优解变为：原问题最有基不变，最 01,x5,x ； 3 2 变为 3 1 约束条件右端项由(3) 21 。其他变量为最优解为： 量 0, 3 1 x2, x ；7c，

18、 1 1 =P,x加一个新的 变(4) 62 666 。其他变量为最优解为： 束 01,x2,x 。4x+2x+x添一个新的约(5) 51 321 2.13 分析下列线性规划问题中，当入变化时最优分析下列线性规划问题中，当入变化时最优 解的变化，并画出解的变化，并画出Z(入入)对入的变化关系图。对入的变化关系图。 ) 4 , 1( , 0 5322 22 . 2)(min ) 1 ( 421 431 4321 jx xxx xxx st xxxxZ j 25, 0, 2 , 5, 0)1 ( 3, 0, 0 , 2, 1 1 2 1 ( 22, 2 1 ( 2, 1, 0, 2 , 00 43

19、 21 43 21 432 1 Zxx xx Zxx xx Z Zxxx x 时，最优解：， 时，最优解：， 时，最优解不变， ，最优解： . 0, 1 126 1052 )2()3 ()(min ) 2( 21 21 21 21 321 xx xx xx xx st xxZ 24, 3,10, 0 , 2, 0)2 0, , 1,12,10, 0, 0 :)2( 12, 3,10 , 0, 2, 00 543 21 54321 54 321 Zxxx xx Zxxxxx Zxx xxx 时，最优解：， 时，最优解， ，最优解： ) 3 , 1( , 0 12 22 . 2)(max ) 3(

20、 432 431 4321 jx xxx xxx st xxxxZ j 2, 3 4 , 3 1 , 0, 0 )4( 6, 0, 1, 0,4 :4( 6, 0, 1, 0, 4 0 4321 4321 4321 Zxxxx Zxxxx Zxxxx 最优解： 时， 时，最优解， 最优解： ， 160 , 0, 0, 0,30, 5, 0 0 . 0, 7304 26023 402 523max ) 4( 654321 321 21 31 321 321 Z xxxxxx xxx xx xx xxx st xxxZ ，最优解： Cj325000 CB基基bX1X2X3X4X5X6 2X25-1

21、/4101/2 -1/40 5X3303/20101/20 0X610200-211 CjZj-700-1-20 Cj325000 CB基基bX1X2X3X4X5X6 2X25- -1/4101/2 -1/40 5X330+ 3/20101/20 0X610-3 200-211 CjZj-700-1-20 Cj325000 CB基基bX1X2X3X4X5X6 2X215-7/4 1/410001/4 5X330+ 3/20101/20 0X43 /2 -5-1001-1/2-1/2 CjZj-700-1-20 其他情况原问题无解。 ， 最优解： 时， ， 最优解： 时， 2 3 1650, 0

22、, 5 2 7 ,30, 4 7 2 15 , 0 7 30 3 10 3160310, 0, 0 ,30,5, 0 ) 3 10 30 654 321 654 321 Zxxx xxx Zxxx xxx 2.14 2.14 某厂生产某厂生产A A，B B，C C三种产品，其所需劳动三种产品，其所需劳动 力、材料等有关数据见力、材料等有关数据见下下表表： 产品产品 资源资源 ABC 可用量可用量 （单位）（单位） 劳动力劳动力63545 材料材料34530 产品利润产品利润 （元（元/件）件） 314 要求：要求： (1)(1)确定获利最大的产品生产计划；确定获利最大的产品生产计划； 答：最优

23、生产计划为：答：最优生产计划为：x x1 1=5,x=5,x2 2=0,x=0,x3 3=3,Z=27=3,Z=27； 项项 目目31400 CB 基基 bX1X2X3X4X5 3 X1 51-1/301/3-1/3 4 X3 3011-1/52/5 CjZj0-20-1/5-3/5 (2) (2)产品产品A A的利润在什么范围内变动时，上述最优的利润在什么范围内变动时，上述最优 计划不变；计划不变； 答：产品答：产品A A的利润在的利润在2.42.4，4.84.8内变动，生产计内变动，生产计 划不变划不变(-3/5 (-3/5 9/59/5 ) )； 项项 目目3+ 1400 CB 基基 b

24、X1X2X3X4X5 3+ X1 51-1/301/3-1/3 4 X3 3011-1/52/5 CjZj0 /3 -20- /3 -1/5 /3 -3/5 (3) (3)如果设计一种新产品如果设计一种新产品D D，单件劳动力消耗为，单件劳动力消耗为8 8 单位，材料消耗为单位，材料消耗为2 2单位，每件可获利单位，每件可获利3 3元，问该种产元，问该种产 品是否值得生产品是否值得生产? ? 答：增加新产品答：增加新产品D D，最优解为，最优解为x x1 1=0,x=0,x2 2=0,x=0,x3 3=5, =5, x x6 6=2.5 Z=27.5 =2.5 Z=27.5 项项 目目3140 0 3 CB 基基 bX1X2X3X4 X5 X6 3 X1 51-1/301/3 -1/3 2 4 X3 3011-1/5 2/5 -4/5 CjZj0-20-1/5 -3/5 1/5 (4) (4)如果劳动力数量不增，材料不足时可从市场如果劳动力数量不增，材料不足时可从市场 购买，每单位购买，每单位0.40.4元。问该厂要不要购进原材料扩大元。问该厂要不要购进原材料扩大 生产，以购多少为宜。生产，以购多少为宜。 答：由（答：由（1 1）可知材料的对偶价