运筹学习题解答(chap2)

第二章对偶问题与灵敏度分析一、写出下列线性规划的对偶问题1、P89,2.1(a)321422minxxxZs.t.,0,;534;332;243321321321321无约束xxxxxxxxxxxx解：原模型可化为321422minxxxZs.t.,0,;534;3-3--2-;243321321321321321无约束xxxyyyxxxxxxxxx于是对偶模型为321532maxyyyWs.t.,0,;4334;243;22321321321321无约束yyyyyyyyyyyy2、P89,2.1(b)321365maxxxxZs.t.0,0,;8374;35;522321321321321xxxxxxxxxxxx无约束解：令033xx原模型可化为321365maxxxxZs.t.0,0,;83-74;3--5-;52-2321321321321321xxxyyyxxxxxxxxx无约束于是对偶模型为321835minyyyWs.t.0,,;332;6752;54321321321321yyyyyyyyyyyy无约束或.0,,;332;6752;54321321321321yyyyyyyyyyyy无约束二、灵敏度分析1、P92,2.11线性规划问题213maxxxZs.t0,1025;74212121xxxxxx最优单纯形表如下CJ3100CBXBbx1x2x3x43x14/3102/3-1/31X25/301-5/34/3j00-1/3-1/3试用灵敏度分析的方法，分析：（1）目标函数中的系数21,cc分别在什么范围内变化，最优解不变？（2）约束条件右端常数项21,bb分别在什么范围内变化，最优基保持不变？解：（1）1c的分析：要使得最优解不变，则需034131003513201413cc即42511cc所以：4251c时可保持最优解不变。2c的分析：要使得最优解不变，则需034313003532302423cc即435622cc所以：56432c时可保持最优解不变。（2）1b的分析：要使得最优基保持不变，则需03405310-2103/43/53/1-3/21111bbbbB即034050310-211bb8511bb所以：851b时可保持最优基不变。2b的分析：要使得最优基保持不变，则需034353-1473/43/53/1-3/22221bbbbB即0343503-1422bb4351412bb所以：144352b时可保持最优基不变。2、P92,2.12已知线性规划问题3212maxxxxZ0,,42632121321xxxxxxxx先用单纯形法求最优解，在讨论下列问题：(1)目标函数中变量321,,xxx的系数在什么范围内变化，最优解不变？(2)两个约束的右端项分别在什么范围内变化，最优基不变？(3)增加一个新的约束2221xx，寻找新的最优解。解：化标准型：04265214321ixxxxxxxx列表求解：jC2-1100BCBXb1x2x3x4x5x04x6【1】111005x4-12001j2-110021x61111005x1003111j0-4-2-30已得最优解10,651xx，其余变量均为0.（1）1c的分析：要使最优解不变，必须000101141312ccc11c2c的分析：要使最优解不变，必须0222c22c3c的分析：要使最优解不变，必须0233c23c（2））1b的分析：要使得最优基不变，则需04411011111bbbbB01b2b的分析：要使得最优基不变，则需06661101111bbbB61b3、P92,2.13已知线性规划问题2123maxxxZ0,21-8262..212212121xxxxxxxxxts用单纯形法求解得最终单纯形表如下。jC320000BCBXb1x2x3x4x5x6x22x4/3012/3-1/30031x10/310-1/32/30005x300-111006x2/300-2/31/301j00-1/3-4/300试用灵敏度分析的方法，分析：（1）目标函数中的系数21,cc在什么范围内变化，最优解不变？（2）约束条件右端常数项43,bb在什么范围内变化，最优基保持不变？（3）增加变量7x，其在目标中的系数TPC)2,3,2,1(,477，重新确定最优解；（4）增加一个新的约束31x，重新确定最优解。解：（1）1c的分析：要使得最优解不变，则需032231003123201413cc1411cc411c2c的分析：要使得最优解不变，则需02c31001c32024236c23c226c232（2）3b的分析：要使得最优基不变，则需0322310342861031320111003231003132331bbbB23b4b的分析：要使得最优基不变，则需0343310341861031320111003231003132441bbbB34b4（3）241023211031320111003231003132P717BP增加变量7x到最终表中，由于07，故需继续迭代找到新的最优解，详见下表：jC3200004BCBXb1x2x3x4x5x6x7x22x4/3012/3-1/300031x10/310-1/32/300105x300-1110406x2/300-2/31/301【2】j00-1/3-4/300122x4/3012/3-1/300031x31001/20-1/2005x5/3001/31/31-2047x1/300-1/31/601/21j000-3/20-1/20所有的0j，故得新的最优解31,35,3437521xxxx，。（4）由于原解不满足31x，故不是可行解。将新约束化为等式约束，即371xx将新约束加到原表中，列表用对偶单纯形法重新计算。jC3200004BCBXb1x2x3x4x5x6x7x22x4/3012/3-1/300031x10/310-1/32/300005x300-1110006x2/300-2/31/301007x31000001j00-1/3-4/300022x4/3012/3-1/300031x10/310-1/32/300005x300-1110006x2/300-2/31/301007x-1/3001/3【-2/3】001j00-1/3-4/300022x3/2011/2000-1/231x3100000105x5/200-1/20103/206x1/200-1/20011/207x1/200-1/2100-3/2j00-1000-2由上表知新的最优解21,21,25,23376521xxxxx，。3、P94，2.16某厂生产A、B、C三种产品，其所需劳动力、材料等等数据见下表。要求：消耗定额产品可用量ABC资源劳动力(h)635450材料（kg）34530产品利润（元/件）301040（1）确定获利最大的产品生产计划；（2）产品A的利润在什么范围内变化时，上述最有计划不需改变？（3）如果设计一种新产品D，单件劳动力消耗为8h，材料消耗为2kg，每件获利30元，问该种产品是否值得生产？（4）如果原材料数量不增，劳动力不足时可从市场雇佣，费用为1.8元/h，问该厂要不要雇佣扩大生产？以雇佣多少为宜？解：(1)设A、B、C三种产品各生产321,,xxx件，建立模型如下：;0,,;30543;450536.401030maxZ321321321321xxxxxxxxxtsxxx材料约束劳动力约束求解该模型，得最优解0,0,10321xxx，最大利润300元。最终表如下：30104000BCBXb1x2x3x4x5x04x3900-5-51-2301x1014/35/301/3j0-30-100-10(2)设A产品的利润为1c，则要使得最优计划不变，需.0310;03540;03410151312ccc024215111ccc241c即A的利润高于24元时不需改变生产计划。（3）设新产品D生产6x件，其资源消耗向量TP)2,8(6，在最终表中的结果为3/24283/1021B61-6PP其检验数为0103/24)30,0(306，增加该产品的生产可以增加总利润。(4)因劳动力的影子价格（4x的检验数）为0（1.8），因而增加劳动力对利润无益，故不需要雇佣劳动力。（或者：最优解情况下，劳动力只用了)450(60106，并未全部用完，故增加劳动力无益于利润的增加。）