第二章对偶理论与灵敏度分析练习题答案

1第二章对偶理论与灵敏度分析练习题答案1．判断下列说法是否正确：(1)任何线性规划问题存在并具有惟一的对偶问题；()(2)根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；()(3)设jˆx，iˆy分别为标准形式的原问题与对偶问题的可行解，*jx，*iy分别为其最优解，则恒有nnmm**jjjjiiiij1j1i1i1ˆˆcxcxbyby；()(4)若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；()(5)已知*iy为线性规划的对偶问题的最优解，若*iy0，说明在最优生产计划中第i种资源已完全耗尽；()(6)已知*iy为线性规划的对偶问题的最优解，若*iy0，说明在最优生产计划中第i种资源一定有剩余；()(7)若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；()(8)应用对偶单纯形法计算时，若单纯形表中某一基变量ix0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；()(9)若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；()(10)在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数cj或在各约束中的相应系数aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。()2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x4、x5为松弛变量。XBｂx1x2x3x4x5x35/201/211/20x15/21-1/20-1/61/3σj0-40-4-2要求：(1)写出原线性规划问题及其对偶问题的数学模型；(2)直接由表写出对偶问题的最优解；(3)其它条件不变时，约束条件右端项b1在何范围内变化，上述最优基不变。(4)若以单价2.5购入第一种资源是否值得，为什么？若有人愿意购买第二种资源应要价多少，为什么？2答案：(1)注：该问题得解法非唯一，以下解法只是其中一种（各解法原理相同）。由题意已知原线性规划问题目标函数为Max（因σj≤0为最优），且c4、c5为0（松弛变量目标函数系数为0）。根据1jjBjcCBP知：23131111ccc422110cc42610c23，得：123c6c2c10根据511222151112632010BA|b10，得：012105A|b3110110则原线性规划问题的数学模型为：12323123123MaxZ6x2x10xx2x53xxx10s.t.x,x,x0其对偶问题的数学模型为：122121212Min5y10y3y6yy2s.t.2yy10y,y0(2)直接由表写出对偶问题得最优解为：*Y4,2(3)令原解()()-1iBiiixXBbb，得br的变化范围为：{}{}iirirriiririiMaxb/a|a0bMinb/a|a0，其中：1iriraB。则：{}{()}15151MaxbMin2226，即15b15，则10b20(4)以单价2.5购入第一种资源是值得的，因其小于该资源“影子价格”（即2.54），可盈利；第二种资源应要价至少为2（影子价格），否则不如自己组织生产。