《运筹学》课程教学资源（试卷习题）第3章 线性规划对偶理论与灵敏度分析习题

第三章线性规划对偶理论与灵敏度分析习题一、思考题1.对偶问题和对偶变量的经济意义是什么？2.简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？4.如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？5.利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？6.在线性规划的最优单纯形表中，松弛变量（或剩余变量）Xn+k>0，其经济意义是什么？7.在线性规划的最优单纯形表中，松弛变量Xn+的检验数n+>0（标准形为求最小值），其经济意义是什么？8.将aijCj,b,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解将会出现什么变化？有多少种不同情况？如何去处理？二、判断下列说法是否正确1.任何线性规划问题都存在且有唯一的对偶问题。2.对偶问题的对偶问题一定是原问题。3.若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。5.若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。6．已知在线性规划的对偶问题的最优解中，对偶变量y，>0，说明在最优生产计划中，第i种资源已经完全用尽。7.已知在线性规划的对偶问题的最优解中，对偶变量y=0，说明在最优生产计划中，第i种资源一定还有剩余。8.对于αij，Cj，b,来说，每一个都有有限的变化范围，当其改变超出了这个范围之后，线性规划的最优解就会发生变化。9.若某种资源的影子价格为π，则在其它资源数量不变的情况下，该资源增加k个单位，相应的目标函数值增加ku。10.应用对偶单纯形法计算时，若单纯形表中某一基变量x，<0，且x,所在行的所有元素都大于或等于零，则其对偶问题具有无界解。三、写出下列线性规划的对偶问题

第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量） xnk  0 ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量 n k x  的检验数 nk  0 （标准形为 求最小值），其经济意义是什么？ 8．将 i j j bi a ,c , 的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量  0  i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量  0  i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于 i j j bi a ,c , 来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加 k 个单位，相应的目标函数值增加 ku 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量 xi  0 ，且 i x 所在行的 所有元素都大于或等于零，则其对偶问题具有无界解。 三、写出下列线性规划的对偶问题

(1)maxZ=3x +2x2 +x3(2)maxz=2x)+2x2+3x3+x4X+x2+2x≤5X+X2+X+X4≤124x +2x2 -x, ≤72xj -x2 +3x3 =-13xi +2x2 +x3 ≤9X-+x4≥3[ X,x2, ≥012≥0,x,无约束(4)(3) minz = xj -2x2 -3x3minz = Xi +x2 +2x33xj -x2 +2x ≤52x +x2 +2x3 ≤72x -4x2 -x3 ≥72x-3x2-x3 =5-3xj +5x2 -4x, ≥3X+2x2+4x3=10xx2≥0x无约束2≥0,无约束(5)maxz=7xj-4x2+3x3(6)minz=5xj-4x2+3x34x,+2x2-6x2≤242xi+7x, ≥83x -6x2 -4x3 ≥158x+5x2-4x≤155x2 +3x =304x2 +6xg =30≥00无约束[x2,≥0,x无约束四、用对偶单纯形法求解下列线性规划问题(1)minZ=3x +2x2 +x3(2)maxz=2xi+2x2+4x3+X2+≤62i +3x2 +5x≥2-x ≥43xj +x2 +7x3 ≤3xiX2 -Xg ≥3X+4x2+6x3≤5,2,≥0[ ,,≥0（3）minz=12x,+8x+16x3+12x（4)minz=5xj+2x2+4x3≥2[2x+x2+4x3[3xi +x2 +2x4 ≥72x+2x2+4x4≥36xj+3x2+5x3≥12;X1,X2,X3,X4 ≥0[X,X2,X ≥0

（1） max 3 1 2 2 3 Z  x  x  x （2） max 2 1 2 2 3 3 4 z  x  x  x  x                , , 0 3 2 9 4 2 7 2 5 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x ；                  1 2 3 4无约束 1 3 4 1 2 3 1 2 3 4 , 0 , , 3 2 3 1 12 x x x x x x x x x x x x x x ； （3） min 1 2 2 3 3 z  x  x  x （4） min 1 2 2 3 z  x  x  x                 1 2 3无约束 1 2 3 1 2 3 1 2 3 , 0 , 2 4 10 2 4 7 3 2 5 x x x x x x x x x x x x ；                 1 2 3无约束 1 2 3 1 2 3 1 2 3 , 0 , 3 5 4 3 2 3 5 2 2 7 x x x x x x x x x x x x ； （5） max 7 1 4 2 3 3 z  x  x  x （6） min 5 1 4 2 3 3 z  x  x  x                1 3 2无约束 2 3 1 2 3 1 2 2 0 , 0 , 5 3 30 3 6 4 15 4 2 6 24 x x x x x x x x x x x ；              2 3 1无约束 2 3 1 2 3 1 3 , 0 , 4 6 30 8 5 4 15 2 7 8 x x x x x x x x x x 。 四、用对偶单纯形法求解下列线性规划问题 （1） min 3 1 2 2 3 Z  x  x  x （2） max 2 1 2 2 4 3 z  x  x  x              , , 0 3 4 6 1 2 3 2 3 1 3 1 2 3 x x x x x x x x x x ；                , , 0 4 6 5 3 7 3 2 3 5 2 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x ； （３） min 12 1 8 2 16 3 12 4 z  x  x  x  x （４） min 5 1 2 2 4 3 z  x  x  x             , , , 0 2 2 4 3 2 4 2 1 2 3 4 1 2 4 1 2 3 x x x x x x x x x x ；             , , 0 6 3 5 12 3 2 7 1 2 3 1 2 3 1 2 4 x x x x x x x x x ；

五、对下列问题求最优解、相应的影子价格及保持最优解不变时c，与b,的变化范围。(1) maxz= Xj +x2 +3xi（2）maxz=9x,+8x2+50,3+19x42x +x2 +2x3≤2[3x+2x2+10x3+4x4≤183x +2x2 +x,≤3:4x +x4≤6;[X,X2,X3 ≥0[X,X2,X3,X4 ≥0(3)maxz=xj +4x2+3x3（4）maxz=6xi+2x2+10x3+8x4[5x+6x2-4x3-4x4≤20[2x+2x2+x≤43xj-3x2+2x3 +8x4≤25Xj+2x2+2x≤64xi -2x2 + X3 +3x4 ≤10[X,,≥0X,X2,,X4 ≥0六、已知下表（表3一1）为求解某线性规划问题的最终单纯形表，表中x4，xs为松弛变量，问题的约束为≤形式表 3—1XiX2X4XsX35/200X31/211/25/2101/3Xi-1/21/600Cj-zj- 4- 4-2（1）写出原线性规划问题；（2）写出原问题的对偶问题；（3）直接由表3一1写出对偶问题的最优解。七、某厂利用原料A、B生产甲、乙、丙三种产品，已知生产单位产品所需原料数、单件利润及有关数据如表1一4所示，分别回答下列问题：表3—2甲乙丙原料拥有量3A64534530B451单件利润（1）建立线性规划模型，求该厂获利最大的生产计划：（2）若产品乙、丙的单件利润不变，产品甲的利润在什么范围变化，上述最优解不变？（3）若有一种新产品丁，其原料消耗定额：A为3单位，B为2单位，单件利润为2

五、对下列问题求最优解、相应的影子价格及保持最优解不变时 j c 与bi 的变化范围。 （１） max 1 2 3 1 z  x  x  x （２） max 9 1 8 2 50 3 19 4 z x x x    x              , , 0 3 2 3 2 2 2 1 2 3 1 2 3 1 2 3 x x x x x x x x x ；             , , , 0 4 6 3 2 10 4 18 1 2 3 4 3 4 1 2 3 4 x x x x x x x x x x ； （３） max 1 4 2 3 3 z  x  x  x （４） max 6 1 2 2 10 3 8 4 z  x  x  x  x             , , 0 2 2 6 2 2 4 1 2 3 1 2 2 1 2 3 x x x x x x x x x ；                   , , , 0 4 2 3 10 3 3 2 8 25 5 6 4 4 20 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 x x x x x x x x x x x x x x x x ． 六、已知下表（表 3—1）为求解某线性规划问题的最终单纯形表，表中 4 5 x , x 为松弛变 量，问题的约束为  形式 表 3—1 1x 2 x 3 x 4 x 5 x 3 x 5/2 0 1/2 1 1/2 ０ 1x 5/2 1 －1/2 0 －1/6 1/3 j j c  z 0 －４ 0 －４ －２ （１）写出原线性规划问题； （２）写出原问题的对偶问题； （３）直接由表３—１写出对偶问题的最优解。 七、某厂利用原料Ａ、Ｂ生产甲、乙、丙三种产品，已知生产单位产品所需原料数、单 件利润及有关数据如表 1—4 所示，分别回答下列问题： 表 ３—２ 甲 乙 丙 原料拥有量 A B 6 3 3 4 5 5 45 30 单件利润 4 1 5 （1）建立线性规划模型，求该厂获利最大的生产计划； （2）若产品乙、丙的单件利润不变，产品甲的利润在什么范围变化，上述最优解不变？ （3）若有一种新产品丁，其原料消耗定额：Ａ为３单位，Ｂ为２单位，单件利润为２．

5单位：问该种产品是否值得安排生产，并求新的最优计划：（4）若原材料A市场紧缺，除拥有量外一时无法购进，而原材料B如数量不足可去市场购买，单价为0，5，问该厂应否购买，以够劲多少为宜？（5）由于某种原因该厂决定暂停甲产品的生产，试重新确定该厂的最优生产计划八、某厂生产甲、乙、丙三种产品，分别经过A、B、C三种设备加工。已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利润见表3一4。表3——4甲Z丙设备能力（台时）11A11005B41 06002C263001064单位产品利润（元）（1）建立线性规划模型，求该厂获利最大的生产计划：（2）产品丙每件的利润增加到多大时才值得安排生产？如产品丙每件的利润增加到50/6，求最优生产计划。（4）产品甲的利润在多大范围内变化时，原最优计划保持不变？（5）设备A的能力如为100+109，确定保持原最优基不变的e的变化范围。（6）如有一种新产品丁，加工一件需设备A、B、C的台时各为1、4、3小时，预期每件的利润为8元，是否值得安排生产？（7）如合同规定该厂至少生产10件产品内，试确定最优计划的变化

５单位．问该种产品是否值得安排生产，并求新的最优计划； （4）若原材料Ａ市场紧缺，除拥有量外一时无法购进，而原材料Ｂ如数量不足可去市 场购买，单价为０．５，问该厂应否购买，以够劲多少为宜？ （5）由于某种原因该厂决定暂停甲产品的生产，试重新确定该厂的最优生产计划． 八、某厂生产甲、乙、丙三种产品，分别经过Ａ、Ｂ、Ｃ三种设备加工。已知生产单位 产品所需的设备台时数、设备的现有加工能力及每件产品的利润见表３—４。 表 ３——４ 甲 乙 丙 设备能力（台时） Ａ Ｂ Ｃ １ １０ ２ １ ４ ２ １ ５ ６ １００ ６００ ３００ 单位产品利润（元） １０ ６ ４ （１）建立线性规划模型，求该厂获利最大的生产计划； （２）产品丙每件的利润增加到多大时才值得安排生产？如产品丙每件的利润增加到 50/6 ，求最优生产计划。 （４）产品甲的利润在多大范围内变化时，原最优计划保持不变？ （５）设备 A 的能力如为 100+10 ，确定保持原最优基不变的 的变化范围。 （６）如有一种新产品丁，加工一件需设备 A、B、C 的台时各为 1、4、3 小时，预期每 件的利润为 8 元，是否值得安排生产？ （７）如合同规定该厂至少生产 10 件产品丙，试确定最优计划的变化