《运筹学》-第三章线性规划对偶理论与灵敏度分析习题及-答案

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