第三章线性规划对偶理论与灵敏度分析习题一、思考题1.对偶问题和对偶变量的经济意义是什么?2.简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么?3.什么是资源的影子价格?它和相应的市场价格之间有什么区别?4.如何根据原问题和对偶问题之间的对应关系,找出两个问题变量之间、解及检验数之间的关系?5.利用对偶单纯形法计算时,如何判断原问题有最优解或无可行解?6.在线性规划的最优单纯形表中,松弛变量(或剩余变量)0knx,其经济意义是什么?7.在线性规划的最优单纯形表中,松弛变量knx的检验数0kn(标准形为求最小值),其经济意义是什么?8.将ijjibca,,的变化直接反映到最优单纯形表中,表中原问题和对偶问题的解将会出现什么变化?有多少种不同情况?如何去处理?二、判断下列说法是否正确1.任何线性规划问题都存在且有唯一的对偶问题。2.对偶问题的对偶问题一定是原问题。3.若线性规划的原问题和其对偶问题都有最优解,则最优解一定相等。4.对于线性规划的原问题和其对偶问题,若其中一个有最优解,另一个也一定有最优解。5.若线性规划的原问题有无穷多个最优解时,其对偶问题也有无穷多个最优解。6.已知在线性规划的对偶问题的最优解中,对偶变量0iy,说明在最优生产计划中,第i种资源已经完全用尽。7.已知在线性规划的对偶问题的最优解中,对偶变量0iy,说明在最优生产计划中,第i种资源一定还有剩余。8.对于ijjibca,,来说,每一个都有有限的变化范围,当其改变超出了这个范围之后,线性规划的最优解就会发生变化。9.若某种资源的影子价格为u,则在其它资源数量不变的情况下,该资源增加k个单位,相应的目标函数值增加uk。10.应用对偶单纯形法计算时,若单纯形表中某一基变量0ix,且ix所在行的所有元素都大于或等于零,则其对偶问题具有无界解。三、写出下列线性规划的对偶问题(1)32123maxxxxZ(2)4321322maxxxxxz0,,92372452321321321321xxxxxxxxxxxx;无约束43214313214321,,0,313212xxxxxxxxxxxxxx;(3)32132minxxxz(4)3212minxxxz无约束321321321321,0,1042742523xxxxxxxxxxxx;无约束321321321321,0,3453532722xxxxxxxxxxxx;(5)321347maxxxxz(6)321345minxxxz无约束23132321221,0,030351546324624xxxxxxxxxxx;无约束1323232131,0,306415458872xxxxxxxxxx。四、用对偶单纯形法求解下列线性规划问题(1)32123minxxxZ(2)321422maxxxxz0,,3463213231321xxxxxxxxxx;0,,5643732532321321321321xxxxxxxxxxxx;(3)43211216812minxxxxz(4)321425minxxxz0,,,34222424321421321xxxxxxxxxx;0,,12536723321321421xxxxxxxxx;五、对下列问题求最优解、相应的影子价格及保持最优解不变时jc与ib的变化范围。(1)1213maxxxxz(2)4211935089maxxxxzx0,,323222321321321xxxxxxxxx;0,,,6418410234321434321xxxxxxxxxx;(3)32134maxxxxz(4)432181026maxxxxxz0,,622422321221321xxxxxxxxx;0,,,103242582332044654321432143214321xxxxxxxxxxxxxxxx.六、已知下表(表3—1)为求解某线性规划问题的最终单纯形表,表中54,xx为松弛变量,问题的约束为形式表3—11x2x3x4x5x3x5/201/211/201x5/21-1/20-1/61/3jjzc0-40-4-2(1)写出原线性规划问题;(2)写出原问题的对偶问题;(3)直接由表3—1写出对偶问题的最优解。七、某厂利用原料A、B生产甲、乙、丙三种产品,已知生产单位产品所需原料数、单件利润及有关数据如表1—4所示,分别回答下列问题:表3—2甲乙丙原料拥有量AB6334554530单件利润415(1)建立线性规划模型,求该厂获利最大的生产计划;(2)若产品乙、丙的单件利润不变,产品甲的利润在什么范围变化,上述最优解不变?(3)若有一种新产品丁,其原料消耗定额:A为3单位,B为2单位,单件利润为2.5单位.问该种产品是否值得安排生产,并求新的最优计划;(4)若原材料A市场紧缺,除拥有量外一时无法购进,而原材料B如数量不足可去市场购买,单价为0.5,问该厂应否购买,以够劲多少为宜?(5)由于某种原因该厂决定暂停甲产品的生产,试重新确定该厂的最优生产计划.八、某厂生产甲、乙、丙三种产品,分别经过A、B、C三种设备加工。已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利润见表3—4。表3——4甲乙丙设备能力(台时)ABC1102142156100600300单位产品利润(元)1064(1)建立线性规划模型,求该厂获利最大的生产计划;(2)产品丙每件的利润增加到多大时才值得安排生产?如产品丙每件的利润增加到50/6,求最优生产计划。(4)产品甲的利润在多大范围内变化时,原最优计划保持不变?(5)设备A的能力如为100+10,确定保持原最优基不变的的变化范围。(6)如有一种新产品丁,加工一件需设备A、B、C的台时各为1、4、3小时,预期每件的利润为8元,是否值得安排生产?(7)如合同规定该厂至少生产10件产品丙,试确定最优计划的变化。《运筹学》第三章线性规划对偶理论与灵敏度分析习题解答二.解:(1)√(2)√(3)X(4)√(5)√(6)√(7)X(8)X(9)X(10)X三、(1)321975minyyyw(2)321312minyyyw0,,12222334321321321321yyyyyyyyyyyy;无约束2313132121321,0,0133222yyyyyyyyyyyyy;(3)3211075maxyyyw(4)321356maxyyyw无约束321321321321,0,0342224123yyyyyyyyyyyy;0,02421531322321321321321yyyyyyyyyyyy无约束,(5)321301524minyyyw(6)32130158maxyyyz无约束32132132121,0,033464562734yyyyyyyyyyy;无约束3213213221,0,03647445582yyyyyyyyyy。四、解:(1)用对偶单纯形法求得的最终单纯形表如下:表3—11x2x3x4x5x6x0-3-24x1x2x-1430100011-1-11001-1010-1jjzc00-60-3-2由于基变量4x所在行的jia值全为非负,故问题无可行解。(2)最优解为TXz]0,2.1,2.0[,8.2;(3)最优解为TXz]0,0,1,5.0[,14;(4)最优解为TXz]0,2,34[,332;五、解:用单纯形法求得的最终单纯形表分别见表3—2(1),2(2),2(3),2(4).(1)表3—2(1)jc11300BCBXb1x2x3x4x5x33x110.510.5005x221.50-0.51jz331.531.50jjzc-2-0.50-1.50由此表可以看出,资源1的影子价格为1.5,资源2的影子价格为0。且3212,5.1,3ccc;211,60bb。(2)表3—2(2)jc98501900BCBXb1x2x3x4x5x6x194x224/3012/3-5/3503x1-0.5-1/310-1/62/3jz31326/3501913/35/3jjzc-4-2/300-13/3-5/3由此表可以看出,资源1的影子价格为13/3,资源2的影子价格为5/3。且205.18,525.47,326,134321cccc;2.75.4,241521bb。(3)表3—2(3)jc11300BCBXb1x2x3x4x5x42x11.5101-0.533x2-101-11jz1034311jjzc-200-1-1由此表可以看出,资源1的影子价格为1,资源2的影子价格为1。且42,63,3321xcc;84,6321bb。(4)表3—2(4)jc2350000BCBXb1x2x3x4x5x6x7x04x10001-3/2-1/81/421x110003/2-1/8-3/453x20010-11/41/232x3/201003/4-3/16-1/8jz16.523501/47/165/8jjzc0000-1/4-7/16-5/8由此表可以看出,资源1的影子价格为0,资源2的影子价格为1/4,资源3的影子价格为7/16,资源2的影子价格为5/8。且421415,31638,833.2833.1321xcc;3408,248,326322,114321bbbb。六、解:(1)原线性规划问题:3211026maxxxxz0,103522132122xxxxxxx;(2)原问题的对偶规划问题为:21105minyyw0,1022632121212yyyyyyy;(3)对偶规划问题的最优解为:)2,4(Y。七、解:(1)设321,,xxx分别为产品甲、乙、丙的产量,其模型为32154maxxxxz0,,3054345536321321321xxxxxxxxx;得此问题的最终单纯形表如下:(表3—3)表3—3jc41500BCBXb1x2x3x4x5x41x51-1/301/3-1/353x3011-0.20.4jz35411/351/32/3jjzc0-8/30-1/3-2/3可得TX]3,0,5[,35z;(2)产品甲的利润变化范围为[3,6]。(3)安排生产丁有利,新最优计划为生产产品丁15件,而0321xxx;(4)购进原料B15单位为宜;(5)新计划为30,]6,0,0[zXT。八、解:(1)设321,,xxx分别为产品甲、乙、丙的产量,其模型为3214610maxxxxz0,,3006226005410100321321321321xxxxxxxxxxxx;得此问题的最终单纯形表如下:(表3—4)表3——4jc1064000BCBXb1x2x3x4x5x6x62x200/3015/65/3-1/60101x100/3101/6-2/31/6006x100004-20