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

1．对偶问题和对偶变量的经济意义是什么？

2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？

3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？

4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？

5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？

6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）xnk0，其经济意 义是什么？

7．在线性规划的最优单纯形表中，松弛变量xnk的检验数 求最小值），其经济意义是什么？

nk0（标准形为

ji的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 8．将ij 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确

1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。

3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。

4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。

5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。

a,c,b6．已知在线性规划的对偶问题的最优解中，对偶变量yi0，说明在最优生产计 划中，第i种资源已经完全用尽。

7．已知在线性规划的对偶问题的最优解中，对偶变量yi0，说明在最优生产计 划中，第i种资源一定还有剩余。

ji来说，每一个都有有限的变化范围，当其改变超出了这个范围 8．对于ij 之后，线性规划的最优解就会发生变化。

a,c,b9．若某种资源的影子价格为u，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 ku。

10．应用对偶单纯形法计算时，若单纯形表中某一基变量xi0，且xi所在行的 所有元素都大于或等于零，则其对偶问题具有无界解。 三、写出下列线性规划的对偶问题

（1）maxZ3x12x2x3 （2）maxz2x12x23x3x4

x1x22x354x12x2x373x12x2x39x,x,x30 12 ； x1x2x3x4122x1x23x31x3x43x1x1,x20,x3,x4无约束 ；

（3）minzx12x23x3 （4）minzx1x22x

3x1x22x352x14x2x37x12x24x310 x1,x20,x3无约束 ； 2x1x22x372x13x2x353x15x24x33x1,x20,x3无约束 ；

（5）maxz7x14x23x3 （6）minz5x14x23x3

4x12x26x2243x16x24x3155x23x330 x10,x30,x2无约束 ； 四、用对偶单纯形法求解下列线性规划问题

7x382x18x15x24x3154x26x330x2,x30,x1无约束 。

（1）minZ3x12x2x3 （2）maxz2x12x24x3

x1x2x36x34x1x2x33 x1,x2,x30 ； 2x13x25x323x1x27x33x14x26x35 x1,x2,x30 ；

（３）minz12x18x216x312x4 （４）minz5x12x24x3

22x1x24x32x12x24x43x,x,x,x034 12 ； 3x1x22x476x13x25x312x,x,x0123 ；

cj五、对下列问题求最优解、相应的影子价格及保持最优解不变时

与bi的变化范围。

（１）maxzx1x23x1 （２）maxz9x18x250x319x4

2x1x22x323x12x2x33x,x,x03 12 ； 3x12x210x34x4184x3x46x,x,x,x034 12 ；

（３）maxzx14x23x3 （４）maxz6x12x210x38x4

5x16x24x34x4202x12x2x343x13x22x38x425x2x2x61224x12x2x33x410x,x,x0x,x,x3,x40123 ； 12 ．

六、已知下表（表3—1）为求解某线性规划问题的最终单纯形表，表中x4,x5为松弛变量，问题的约束为  形式

表 3—1 x1 x2 x3 x4 x5 x3 5/2 5/2 j0 1 0 1/2 －1/2 －４ 1 0 0 1/2 －1/6 －４ ０ 1/3 －２ x1 cjz （１）写出原线性规划问题； （２）写出原问题的对偶问题；

（３）直接由表３—１写出对偶问题的最优解。

七、某厂利用原料Ａ、Ｂ生产甲、乙、丙三种产品，已知生产单位产品所需原料数、单件利

润及有关数据如表1—4所示，分别回答下列问题： 表 ３—２ 甲 乙 丙 原料拥有量 A B 单件利润 6 3 4 3 4 1 5 5 5 45 30

（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）

minw5y17y29y3 （2）

minw12y1y23y3

y12y2y32yy22y14y23y331y2y2y2y13y2y33123yy312yyy11231y,y2,y30y0,y30,y2无约束 1 ； 1（3）maxw5y17y210y3 （4）maxw6y15y23y3

3y12y2y31y14y22y322y1y24y33y10,y20,y3无约束；

2y12y23y31y13y25y312y1y24y32y0,y2无约束，y30 ； 1 （5）minw24y115y230y3 （6）maxz8y115y230y3 4y13y272y18y255y24y342y16y25y346y4y3y31237y14y26y33y0,y20,y3无约束y0,y20,y3无约束 1 ； 1。 四、解：（1）用对偶单纯形法求得的最终单纯形表如下：

表 ３—１ x2 x3 x4 x5 x6 x1 ０ －３ －２ x4 x1 x2 －１ ４ ３ ０ １ ０ ０ ０ １ １ －１ －１ １ ０ ０ １ －１ ０ １ ０ －１

cjzj

０

０

－６

０

－３

－２

由于基变量x4所在行的

aij值全为非负，故问题无可行解。

T（２）最优解为 z2.8,X[0.2,1.2,0]； （３）最优解为 z14,X[0.5,1,0,0]；

T33（４）最优解为 ；

五、解：用单纯形法求得的最终单纯形表分别见表 ３— ２(1) , 2(2) , 2(3) , 2(4) ． （1）

表 ３—２（１） cjz32,X[4,2,0]T 1 1 3 0 0 CB ３ ０ XB b １ ２ ３ x1 １ ２ ３ －２ x2 0．5 1．5 1．5 －0.5 x3 １ ０ ３ ０ x4 ０.5 －0.5 1.5 －１.5 x5 0 1 0 0 x3 x5 zj jcjz 且 c13 由此表可以看出，资源1的影子价格为1.5 ，资源2的影子价格为0 。 ,c21.5,2c3 ；

0b16,1b2。 (2)

表 3 — 2（2） cj 9 8 50 19 0 0 CB 19 50 XBb 2 1 ３ x1 2 －０.5 1３ －4 x2 4/3 －1/3 26/3 －2/3 x3 0 1 x4 １ ０ 19 0 x5 2/3 －1/6 13/3 x6 －5/3 2/3 5/3 x4 x3 zj j50 ０ cjz －13/3 －5/3 由此表可以看出，资源1的影子价格为13/3 ，资源2的影子价格为5/3 。 且 c113,c2263,47.5c352,18.5c420 ；

15b124,4.5b27.2 。

（3）

表 3—2（3） cj 1 1 3 0 0 CB 4 3 XBb １ ２ 10 x1 １.5 －１ ３ x2 1 0 4 x3 0 1 ３ x4 1 －1 1 x5 －0.5 1 1 x2 x3 zj cjz且 c13j －２ 0 ０ －１ －１ 由此表可以看出，资源1的影子价格为1 ，资源2的影子价格为1 。 ,3c26,2x34 ；

3b16,4b28 。

(4)

表 3—2（4） cj 2 3 5 0 0 0 0 CB 0 2 5 3 XBb 1 1 2 3/2 16.5 jx1 0 1 0 0 2 0 x2 0 0 0 1 3 0 x3 0 0 1 0 5 ０ x4 １ 0 0 ０ 0 0 x5 －3/2 3/2 －１ 3/4 1/4 －1/4 x6 －1/8 －1/8 1/4 x7 1/4 －3/4 1/2 x4 x1 x3 x2 －3/16 －1/8 7/16 5/8 zj cjz－7/16 －5/8 由此表可以看出，资源1的影子价格为0 ，资源2的影子价格为1/4 ， 资源3的影子价格为7/16 ，资源2的影子价格为5/8 。 且 1.833c12.833,83c2163,1x3214 ；

11b1,223b2263,8b324,8b4403 。 六、解：（１）原线性规划问题：maxz6x12x210x3

x22x253x1x2x310x,x02 1 ；

（２）原问题的对偶规划问题为：

minw5y110y2

3y26y1y222y1y210 y1,y20 ；

（３）对偶规划问题的最优解为：Y(4,2)。 七、解：（１）设x1,x2,x3分别为产品甲、乙、丙的产量，其模型为 maxz4x1x25x3

6x13x25x3453x14x25x330x,x,x03 12 ；

得此问题的最终单纯形表如下：（表 3—3）

表 3—3 cj 4 1 5 0 0 CB 4 5 XBb 5 3 ３5 x1 １ 0 4 0 x2 －1/3 1 11/3 －8/3 x3 0 1 5 ０ x4 1/3 －0.2 1/3 －１/3 x5 －1/3 0．4 2/3 －2/3 x1 x3 zj jcjz可得X [5,0,3]，z35；

（2）产品甲的利润变化范围为 [ 3，6 ] 。

（3）安排生产丁有利，新最优计划为生产产品丁15件，而x1x2x30； （4）购进原料B 15单位为宜；

T,z30 。 （5）新计划为 X[0,0,6]八、解：（1）设x1,x2,x3分别为产品甲、乙、丙的产量，其模型为

maxz10x16x24x3

x1x2x310010x14x25x36002x12x26x3300 x1,x2,x30 ；得此问题的最终单纯形表如下：（表 3—4） 表3——4 Tcj 10 6 4 0 0 0 CB 6 10 0 XBb 200/3 100/3 100 x1 0 1 0 x2 1 0 0 x3 5/6 1/6 4 x4 5/3 －2/3 －２ x5 －1/6 1/6 0 x6 0 0 1 x2 x1 x6 zj j2200/3 10 0 T6 0 20/3 －8/3 10/3 －10/3 2/3 －2/3 0 0 cjz 可得X[100/3,200/3,0]，z2200/3；

 （2）X[175/6,275/6,25]；

T （3）6c115； （4）45； （5）该产品值得安排生产；

6）X[95/3,175/3,10]T。

（