运筹学第二章习题答案

1、电话：电话：5108157(H)，5107443(O)E-mail: 2.1 写出下列线性规划问题的对偶问题。写出下列线性规划问题的对偶问题。 无约束321321321321321,0,534332243422min)1(xxxxxxxxxxxxstxxxZ无限制对偶问题321321321321321, 0, 0433424322532max:yyyyyyyyyyyystyyyW0, 0,8374335522365max)2(321321321321321xxxxxxxxxxxxstxxxZ无约束0, 0,3332675254835max321321321321321yyyyyyyyyyyys

2、tyyyW无约束对偶问题：.), 1, 1(0), 1(), 1(min)3(1111njmixnjbxmiaxstxcZijnijijnjiijminjijijmniynjmicyystybyaWiijmjiminjmjjii, 1), 1, 1(.max11无限制，对偶问题：）无约束（nnjxnnjxmmmibxammibxastxcZjjnjijijnjijijmjjj, 1), 1(0), 2, 1(), 1(max)4(11111111）无约束（对偶问题：mmjymiynnnjcyanjcyastybybybWiimijiijmijiijmm, 1), 1(0), 2, 1(), 2

3、 , 1(min11111112211 2.2 判断下列说法是否正确，为什么判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行解，则其对偶如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；问题也一定存在可行解； 答：不对！如原问题是无界解，对偶问题无可行答：不对！如原问题是无界解，对偶问题无可行解。解。 (2)如果线性规划的对偶问题无可行解，则原问题如果线性规划的对偶问题无可行解，则原问题也一定无可行解；也一定无可行解； 答：不对！道理同上。答：不对！道理同上。 (3)在互为对偶的一对原问题与对偶问题中，不管在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极

4、小，原问题可行解的目标函数值原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；一定不超过其对偶问题可行解的目标函数值； 答：不对！如果原问题是求极小，结论相反。答：不对！如果原问题是求极小，结论相反。 (4)任何线性规划问题具有惟一的对偶问题。任何线性规划问题具有惟一的对偶问题。 答：结论正确！答：结论正确！ 2.3 已知某求极大化线性规划问题用单纯形已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。所示，求表中各括弧内未知数的值。 解：解： l=1, k=0

5、 , 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/4Cj322000CB基基bX1X2X3X4X5X60X1(b)1111000X215(a)120100X3202(c)1001CjZj 322000 0X45/400(d)(l)-1/4 -1/43X125/410(e)03/4(i)2X25/201(f)0(h)1/2CjZj 0(k)(g)0-5/4(j) 2.4 给出线性规划问题给出线性规划问题 )4 , 1( , 0332232.6532min432143214321jxxxxxxxxxstxxx

6、xZj (1)写出其对偶问题；写出其对偶问题；(2)用图解法求解对偶问题；用图解法求解对偶问题；(3)利用利用(2)的结果及根据对偶问题性质写出原问题最优的结果及根据对偶问题性质写出原问题最优解。解。 0,063533222.32min)1(212121212121yyyyyyyyyystyyW对偶问题： (2) 最优解是：最优解是：y1=-8/5,y2=1/5,目标函数值目标函数值-19/5。 (3)由于由于 y1=-8/5,y2=1/5都不等于零，原问题中的约都不等于零，原问题中的约束取等号。又上面第束取等号。又上面第4个约束不等号成立，故个约束不等号成立，故x4=0，令，令x3=0就可以

7、得到最优解：就可以得到最优解： x1=8/5,x2=1/5。 2.5 给出线性规划问题给出线性规划问题 ., 0, 022122max321321321321321无约束xxxxxxxxxxxxstxxxZ (1)写出其对偶问题；写出其对偶问题；(2)利用对偶问题性质证明利用对偶问题性质证明原问题目标函数值原问题目标函数值z1。 0, 012122min)1 (321321321321321yyyyyyyyyyyystyyyW无约束对偶问题： (2)y1=y3=0,y2=1时对偶问题的一个可行解，目标时对偶问题的一个可行解，目标函数值为函数值为1，故原问题的目标函数值小于等于，故原问题的目标函

8、数值小于等于1。 试根据对偶问题性质证明上述线性规划问题目标试根据对偶问题性质证明上述线性规划问题目标函数值无界。函数值无界。 )3 , 1( , 0122.65max3213214321jxxxxxxxstxxxxZj 2.6 已知线性规划问题已知线性规划问题 由于由于(1)和和(4)是矛盾约束，故对偶问题无可行解。是矛盾约束，故对偶问题无可行解。所以原问题目标函数值无界。所以原问题目标函数值无界。)4(0,)3(0)2(1)1 (12.2min2121212121yyyyyyyystyyW 解：解：x1=1,x2=x3=0是原问题的可行解。原问题的对是原问题的可行解。原问题的对偶问题为：偶

9、问题为： 要求：要求：(1)写出其对偶问题；写出其对偶问题；(2)已知原问题最优解已知原问题最优解为为X*=(2，2，4，0)，试根据对偶理论，直接求出对偶，试根据对偶理论，直接求出对偶问题的最优解。问题的最优解。 )4 , 1( , 0966283.42min321432214214321jxxxxxxxxxxxxstxxxxZj 2.7 2.7 给出线性规划问题给出线性规划问题 (2)已知原问题最优解为已知原问题最优解为X*=(2，2，4，0)，代入，代入原问题，第原问题，第4个约束不等式成立，故个约束不等式成立，故y4=0。有由于。有由于x1,x2,x3大于大于0，上面对偶问题前，上面对

10、偶问题前3个约束取等号，故得个约束取等号，故得到最优解：到最优解： y1=4/5, y2,=3/5, y3=1, y4=0)4 , 1( , 01113229668min) 1 (314343214214321jyyyyyyyyyyyyyyyyWj对偶问题：), 1( ,0.min1333122211111njxybxaybxaybxastxcZAjnjjjnjjjnjjjnjjj影子价格问题 2.8 已知线性规划问题已知线性规划问题A和和B如下：如下： ), 1( , 03)3(515155.min13*131312*2211*111njxybbxaaybxaybxastxcZBjnjjjj

11、njjjnjjjnjjj影子价格问题 试分别写出试分别写出yi同同y*i(i1，2，3)间的关系式。间的关系式。 *3*2*1321*3*2*1321005/3050005/1100010005/1100050001003010001yyyyyyyyyyyy)3 , 1( , 052233.18124min)1 (3231321jxxxxxstxxxZj 2.9 用对偶单纯形法求解下列线性规划问题。用对偶单纯形法求解下列线性规划问题。 )3 , 1( , 010536423.425min)2(321321321jxxxxxxxstxxxZj1,2/3,0)3 , 1( ,053233.1812

12、4min)1 (3213231321xxxjxxxxxstxxxZj最优解：0,2, 3/2)3 , 1( ,010536423.425min)2(321321321321xxxjxxxxxxxstxxxZj最优解： 要求：要求：(1)写出其对偶问题；写出其对偶问题；(2)用对偶单纯形法求用对偶单纯形法求解原问题；解原问题；(3)用单纯形法求解其对偶问题；用单纯形法求解其对偶问题；(4)对比对比(2)与与(3)中每步计算得到的结果。中每步计算得到的结果。 .0,3222434223804060min321321321321321xxxxxxxxxxxxstxxxZ 2.10 考虑如下线性规划问

13、题：考虑如下线性规划问题： (4)3230 Z,350y ,320y 0,y(3)3230 Z0, x,32 x,65x(2)0,8023402260243342max)1 (321321321321321321321略对偶问题：yyyyyyyyyyyystyyyW 先用单纯形法求出最优解，再分析在下列先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。条件单独变化的情况下最优解的变化。 解：最优解为解：最优解为x x1 1=6,x=6,x2 2=x=x3 3=0,Z=12 =0,Z=12 )3 , 1( , 0426.2max21321321jxxxxxxstxxxZj 2

14、.11 已知线性规划问题：已知线性规划问题： 46/3Z0,x10/3,x8/3,xx3x2xmax Z(1)321321最优解：目标函数变为6, 0, 34346 (2)321Zxxx最优解：变为约束右端项由28/3Z8/3,x0,x10/3,x22xx(3)32131最优解：增添一个新的约束条件 2.12 2.12 给出线性规划问题给出线性规划问题 用单纯形法求解得最终单纯形表见下表：用单纯形法求解得最终单纯形表见下表： )3 , 1( ,033734311313131.32max321321321jxxxxxxxstxxxZj项项 目目23100CB 基基 bX1X2X3X4X52 X1

15、 610-14-13 X2 1012-11CjZj00-3-5-1 试分析下列各种条件下最优解试分析下列各种条件下最优解(基基)的变化：的变化：31213213x,xx,x10Z1,x0,x,2,x ；6的系数 变x目标标函数中变(1)最优基从最优解：为量时最优解不变。时最优解不变；最定确9, 4c3,43c优解不变；在什 么什么范围内变动c,c的系数x和x目标标函数中变 分别(2)212121。其他变量为优解变为：原问题最有基不变，最01,x5,x； 32变为31 约束条件右端项由(3)21。其他变量为最优解为：量0,31x2, x；7c， 11=P,x加一个新的 变(4)62666。其他变

16、量为最优解为：束01,x2,x。4x+2x+x添一个新的约(5)51321 2.13 分析下列线性规划问题中，当入变化时最优分析下列线性规划问题中，当入变化时最优解的变化，并画出解的变化，并画出Z(入入)对入的变化关系图。对入的变化关系图。) 4 , 1( , 0532222.2)(min) 1 (4214314321jxxxxxxxstxxxxZj25, 0, 2, 5, 0)1 (3, 0, 0, 2, 1 121(22,21(2, 1, 0, 2, 00432143214321ZxxxxZxxxxZZxxxx时，最优解：，时，最优解：，时，最优解不变，最优解：.0,11261052)2(

17、)3 ()(min) 2(21212121321xxxxxxxxstxxZ24, 3,10, 0, 2, 0)20, , 1,12,10, 0, 0:)2(12, 3,10, 0, 2, 00543215432154321ZxxxxxZxxxxxZxxxxx时，最优解：，时，最优解，最优解：) 3 , 1( , 01222.2)(max) 3(4324314321jxxxxxxxstxxxxZj2,34,31, 0, 0)4(6, 0, 1, 0,4:4(6, 0, 1, 0, 40432143214321ZxxxxZxxxxZxxxx最优解：时，时，最优解，最优解：，160, 0, 0, 0

18、,30, 5, 00.0,730426023402523max) 4(6543213212131321321ZxxxxxxxxxxxxxxxxstxxxZ，最优解：Cj325000CB基基bX1X2X3X4X5X62X25-1/4 101/2-1/4 05X3303/20101/200X610200-211CjZj-700-1-20Cj325000CB基基 bX1X2X3X4X5X62X25- -1/4 101/2-1/4 05X330+ 3/20101/200X610-3 200-211CjZj-700-1-20Cj325000CB基基bX1X2X3X4X5X62X215-7/4 1/410

19、001/45X330+ 3/20101/200X43 /2 -5-1001-1/2 -1/2CjZj-700-1-20其他情况原问题无解。，最优解：时，最优解：时，231650, 0, 527,30,47215, 07303103160310, 0, 0,30,5, 0)31030654321654321ZxxxxxxZxxxxxx 2.14 2.14 某厂生产某厂生产A A，B B，C C三种产品，其所需劳动三种产品，其所需劳动力、材料等有关数据见力、材料等有关数据见下下表表：产品产品资源资源ABC可用量可用量（单位）（单位）劳动力劳动力63545材料材料34530产品利润产品利润（元（元/

20、件）件）314 要求：要求： (1) (1)确定获利最大的产品生产计划；确定获利最大的产品生产计划； 答：最优生产计划为：答：最优生产计划为：x x1 1=5,x=5,x2 2=0,x=0,x3 3=3,Z=27=3,Z=27； 项项 目目31400CB 基基 bX1X2X3X4X53 X1 51-1/301/3-1/34 X3 3011-1/52/5CjZj0-20-1/5-3/5 (2) (2)产品产品A A的利润在什么范围内变动时，上述最优的利润在什么范围内变动时，上述最优计划不变；计划不变； 答：产品答：产品A A的利润在的利润在2.42.4，4.84.8内变动，生产计内变动，生产计划

21、不变划不变(-3/5 (-3/5 9/5 ) 9/5 )； 项项 目目3+ 1400CB 基基 bX1X2X3X4X53+ X1 51-1/301/3-1/34 X3 3011-1/52/5CjZj0 /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,

22、 =5, x x6 6=2.5 Z=27.5 =2.5 Z=27.5 项项 目目3140 0 3CB 基基 bX1X2X3X4 X5 X63 X1 51-1/301/3 -1/3 2 4 X3 3011-1/5 2/5 -4/5CjZj0-20-1/5 -3/5 1/5 (4) (4)如果劳动力数量不增，材料不足时可从市场如果劳动力数量不增，材料不足时可从市场购买，每单位购买，每单位0.40.4元。问该厂要不要购进原材料扩大元。问该厂要不要购进原材料扩大生产，以购多少为宜。生产，以购多少为宜。 答：由（答：由（1 1）可知材料的对偶价格是）可知材料的对偶价格是0.60.6元，大于元，大于市场价格。故应该购进原材料进行生产。当购进的原市场价格。故应该购进原材料进行生产。当购进的原材料达到材料达到1515时，利润达到最大值时，利润达到最大值36