二三版兼用《运筹学教程》胡运权主编课后习题答案(第二章)模板

第二章习题解答2.1写出下列线性规划问题的对偶问题。无约束321321321321321,0,,534332243422min)1(xxxxxxxxxxxxstxxxZ无限制对偶问题321321321321321,0,0433424322532max:yyyyyyyyyyyystyyyW第二章习题解答0,0,,8374335522365max)2(321321321321321xxxxxxxxxxxxstxxxZ无约束0,0,3332675254835max321321321321321yyyyyyyyyyyystyyyW无约束对偶问题：.),,1,,,1(0),,1(),,1(min)3(1111njmixnjbxmiaxstxcZijnijijnjiijminjijij第二章习题解答mniynjmicyystybyaWiijmjiminjmjjii,,1),,1,,,1(.max11无限制，对偶问题：）无约束（nnjxnnjxmmmibxammibxastxcZjjnjijijnjijijmjjj,,1),,,,1(0),,2,1(),,1(max)4(11111111第二章习题解答）无约束（对偶问题：mmjymiynnnjcyanjcyastybybybWiimijiijmijiijmm,,1),,1(0),,2,1(),,2,1(min11111112211第二章习题解答第二章习题解答2.2判断下列说法是否正确，为什么?(1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；答：不对！如原问题是无界解，对偶问题无可行解。(2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解；答：不对！道理同上。第二章习题解答(3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；答：不对！如果原问题是求极小，结论相反。(4)任何线性规划问题具有惟一的对偶问题。答：结论正确！第二章习题解答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/4Cj→322000CB基bX1X2X3X4X5X60X1(b)1111000X215(a)120100X3202(c)1001Cj－Zj322000┆┆┆┆┆┆┆┆┆0X45/400(d)(l)-1/4-1/43X125/410(e)03/4(i)2X25/201(f)0(h)1/2Cj－Zj0(k)(g)0-5/4(j)第二章习题解答2.4给出线性规划问题)4,,1(,0332232.6532min432143214321jxxxxxxxxxstxxxxZj(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就可以得到最优解：x1=8/5,x2=1/5。第二章习题解答第二章习题解答2.5给出线性规划问题.,0,022122max321321321321321无约束xxxxxxxxxxxxstxxxZ(1)写出其对偶问题；(2)利用对偶问题性质证明原问题目标函数值z≤1。0,,012122min)1(321321321321321yyyyyyyyyyyystyyyW无约束对偶问题：(2)y1=y3=0,y2=1时对偶问题的一个可行解，目标函数值为1，故原问题的目标函数值小于等于1。第二章习题解答第二章习题解答试根据对偶问题性质证明上述线性规划问题目标函数值无界。)3,,1(,0122.65max3213214321jxxxxxxxstxxxxZj2.6已知线性规划问题第二章习题解答由于(1)和(4)是矛盾约束，故对偶问题无可行解。所以原问题目标函数值无界。)4(0,)3(0)2(1)1(12.2min2121212121yyyyyyyystyyW解：x1=1,x2=x3=0是原问题的可行解。原问题的对偶问题为：第二章习题解答要求：(1)写出其对偶问题；(2)已知原问题最优解为X*=(2，2，4，0)，试根据对偶理论，直接求出对偶问题的最优解。)4,,1(,0966283.42min321432214214321jxxxxxxxxxxxxstxxxxZj2.7给出线性规划问题第二章习题解答(2)已知原问题最优解为X*=(2，2，4，0)，代入原问题，第4个约束不等式成立，故y4=0。有由于x1,x2,x3大于0，上面对偶问题前3个约束取等号，故得到最优解：y1=4/5,y2,=3/5,y3=1,y4=0)4,,1(,01113229668min)1(314343214214321jyyyyyyyyyyyyyyyyWj对偶问题：),,1(,0.min1333122211111njxybxaybxaybxastxcZAjnjjjnjjjnjjjnjjj影子价格问题2.8已知线性规划问题A和B如下：第二章习题解答),,1(,03)3(515155.min13*131312*2211*111njxybbxaaybxaybxastxcZBjnjjjjnjjjnjjjnjjj影子价格问题试分别写出yi同y*i(i＝1，2，3)间的关系式。第二章习题解答*3*2*1321*3*2*1321005/3050005/1100010005/1100050001003010001yyyyyyyyyyyy第二章习题解答)3,,1(,052233.18124min)1(3231321jxxxxxstxxxZj2.9用对偶单纯形法求解下列线性规划问题。)3,,1(,010536423.425min)2(321321321jxxxxxxxstxxxZj第二章习题解答1,2/3,0)3,,1(,053233.18124min)1(3213231321xxxjxxxxxstxxxZj最优解：0,2,3/2)3,,1(,010536423.425min)2(321321321321xxxjxxxxxxxstxxxZj最优解：第二章习题解答第二章习题解答要求：(1)写出其对偶问题；(2)用对偶单纯形法求解原问题；(3)用单纯形法求解其对偶问题；(4)对比(2)与(3)中每步计算得到的结果。.0,,3222434223804060min321321321321321xxxxxxxxxxxxstxxxZ2.10考虑如下线性规划问题：(4)3230Z,350y,320y0,y(3)3230Z0,x,32x,65x(2)0,,8023402260243342max)1(321321321321321321321略对偶问题：yyyyyyyyyyyystyyyW第二章习题解答第二章习题解答先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。解：最优解为x1=6,x2=x3=0,Z=12)3,,1(,0426.2max21321321jxxxxxxstxxxZj2.11已知线性规划问题：46/3Z0,x10/3,x8/3,xx3x2xmaxZ(1)321321最优解：目标函数变为第二章习题解答6,0,34346(2)321Zxxx最优解：变为约束右端项由28/3Z8/3,x0,x10/3,x22xx(3)32131最优解：增添一个新的约束条件第二章习题解答2.12给出线性规划问题用单纯形法求解得最终单纯形表见下表：)3,,1(,033734311313131.32max321321321jxxxxxxxstxxxZj项目23100CB基bX1X2X3X4X52X1610-14-13X21012-11Cj－Zj00-3-5-1试分析下列各种条件下最优解(基)的变化：第二章习题解答31213213x,xx,x10Z1,x0,x,2,x；6的系数变x目标标函数中变(1)最优基从最优解：为量第二章习题解答时最优解不变。时最优解不变；最定确]9,4[c]3,43[c优解不变；在什么什么范围内变动c,c的系数x和x目标标函数中变分别(2)212121。其他变量为优解变为：原问题最有基不变，最01,x5,x；32变为31约束条件右端项由(3)21第二章习题解答。其他变量为最优解为：量0,31x2,x；7＝c，11=P,x增加一个新的变(4)62666。其他变量为最优解为：束01,x2,x。4x+2x+x增添一个新的约(5)51321第二章习题解答2.13分析下列线性规划问题中，当入变化时最优解的变化，并画出Z(入)对入的变化关系图。)4,,1(,0532222.2)(min)1(4214314321jxxxxxxxstxxxxZj25,0,2,5,0)1(3,0,0,2,1]121(22,]21(2,1,0,2,00432143214321ZxxxxZxxxxZZxxxx时，最优解：，时，最优解：，时，最优解不变，，最优解：第二章习题解答.0,11261052)2()3()(min)2(21212121321xxxxxxxxstxxZ24,3,10,0,2,0)2[0,,1,12,10,0,0:)2(12,3,10,0,2,00543215432154321ZxxxxxZxxxxxZxxxxx时，最优解：，时，最优解，，最优解：第二章习题解答)3,,1(,01222.2)(max)3(4324314321jxxxxxxxstxxxxZj2,34,31,0,0)4(6,0,1,0,4:]4(6,0,1,0,40432143214321