线性规划的对偶理论和灵敏度分析 常见疑问解.doc

第二章 线性规划的对偶理论和灵敏度分析 常见疑问解答 1、研究线性规划对偶问题的经济意义何在？因为线性规划往往解决原料、设备、资金、人力等资源的最优配置问题，因此了解资源在最优配置下所创造的（边际）价值即机会成本或机会收益对于成本分析、资源计划、投资计划等都有较重要的作用此外，对偶规划也常和对资源的灵敏度分析联系在一起，对于更好地在变化环境中配置资源有一定的指导意义2、已知原线性规划问题如何写出其对偶问题？（1）如果原问题是MAX问题，则其对偶问题是MIN问题按下表可将其对偶问题写出  原问题（L）一  一  对  应对偶问题（D）max问题min问题有m个约束条件有m个变量第j个约束条件为≤关系第j个变量≥0第j个约束条件为≥关系第j个变量≤0第j个约束条件为等式关系第j个变量无非负约束，是自由变量第i个变量≥0第i个约束条件为≥关系第i个变量≤0第i个约束条件为≤关系第i个变量无非负约束，是自由变量第i个约束条件为＝关系资源向量价值向量价值向量资源向量（2）  如果原问题是MIN问题，则其对偶问题是MAX问题按下表可将其对偶问题写出  原问题（L）一  一  对  应对偶问题（D）min问题max问题有m个约束条件有m个变量第j个约束条件为≤关系第j个变量≤0第j个约束条件为≥关系第j个变量≥0第j个约束条件为等式关系第j个变量无非负约束，是自由变量第i个变量≥0第i个约束条件为≤关系第i个变量≤0第i个约束条件为≥关系第i个变量无非负约束，是自由变量第i个约束条件为＝关系资源向量价值向量价值向量资源向量3、  如何写出下述线性规划问题的对偶模型？ min z=2x1+2x2+4x3    x1+3x2+4x3≥2    2x1+x2+3x3≤3    x1+4x2+3x3＝5    x1≥0, x2≥0, x3无约束。

答：其对偶模型如下，  max z=2y1+3y2+5y3    y1+2y2+y3≤2    3y1+y2+4y3≤2    4y1+3y2+3y3＝4    y1≥0, y2≤0, y3无约束4、 如何快速求出以下只有一个约束方程的线性规划的对偶问题的最优解？   Max Z=c1x1＋c1x2＋…＋cnxn    a1x1＋a1x2＋…＋anxn≤b    x1, x2,…, xn ≥0    ai, ci, b>0, i=1, 2, …, n.答：利用原问题与对偶问题间的相互转换关系，写出其对偶问题的模型如下，  Min f=by     a1y≥c1     a2y≥c2    ……    any≥cn    y≥0因为，y≥ , i=1, 2, …, n. 所以，其对偶问题的最优解y*= .5、 如果原问题是如下所示的追求利润最大的生产计划问题，那么它的对偶问题中变量有何经济含义？ 原问题的模型形式如下         其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.答：其对偶问题即有如下形式，对偶问题中的变量yk, k=1, 2,…, m, 可具有发现某种资源所创造的单位价值并对某种资源定价的经济含义。

简言之，它反映了单位资源在某种配置、利用方式下能创造的价值，即单位资源（可能的）价值6、如果原问题是如下所示的追求利润最大的生产计划问题，当其中某个变量值减少一个生产单位时，所节约的各种资源的量有多少？原问题的模型形式如下其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.答：当其中某个变量值，不妨设xj 的值减少一个生产单位时，所节约的各种资源量为 .它正好是系数矩阵A中变量xj所对应的列向量  7、假设原问题是如下所示的追求利润最大的生产计划问题，它的对偶问题中的变量反映了单位资源可能创造的价值，那么当原问题中某个变量值减少一个生产单位时，所节约的各种资源的价值将如何借助对偶问题中的变量来表示？原问题的模型形式如下其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.答：其对偶问题即有如下形式，.其中，对偶问题中的变量yk, k=1, 2,…, m, 反映了单位资源（所可能创造）的价值。

当原问题中某个变量值，不妨设xj 的值减少一个生产单位时，所节约的各种资源量为 , 则所节约的各种资源的价值可表示为： , 它正好是对偶问题第j个约束条件的左端项8、如果原问题是如下所示的追求利润最大的生产计划问题，当其中某个变量值增加一个生产单位时，所耗费的各种资源的量有多少？原问题的模型形式如下其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.答：当其中某个变量值，不妨设xj 的值增加一个生产单位时，所耗费的各种资源量为 .它正好是系数矩阵A中变量xj所对应的列向量9、假设原问题是如下所示的追求利润最大的生产计划问题，它的对偶问题中的变量反映了单位资源可能创造的价值，那么当原问题中某个变量值增加一个生产单位时，所耗费的各种资源的价值将如何借助对偶问题中的变量来表示？原问题的模型形式如下其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.答：其对偶问题即有如下形式，.其中，对偶问题中的变量yk, k=1, 2,…, m, 反映了单位资源（所可能创造）的价值。

当原问题中某个变量值，不妨设xj 的值增加一个生产单位时，所耗费的各种资源量为 , 则所耗费的各种资源的价值可表示为： , 它正好是对偶问题第j个约束条件的左端项10、在已求出原问题的最优单纯形表后，如何求出对偶问题的最优解？在已求出原问题的最优单纯形表后，可确定出相应的最优基B和及其对应的CB, 然后通过公式Y*=CBB－1, 即可求出对偶问题的最优解，或甚至直接从其最终单纯形表中就能得到对偶问题的最优解11、如何计算影子价格？线性规划问题的对偶问题的最优解被称为影子价格当这个线性规划问题的最优基为B时，通过公式Y*=CBB－1, 或甚至直接从其最终单纯形表中就能得到影子价格12、如何通过公式Y*=CBB－1（B是线性规划问题的最优基）计算以下问题的影子价格及其对偶问题的最优解？max z=x1＋x2＋4x3＋3x4x1＋3x2＋8x3＋4x4≤452x1＋ x2＋ x3＋3x4≤40x1, x2, x3, x4≥0答：a.       将原问题化为标准形max z=x1＋x2＋4x3＋3x4x1＋3x2＋8x3＋4x4＋x5 =452x1＋ x2＋ x3＋3x4 ＋x6=40x1, x2, x3, x4, x5, x6≥0b.       用单纯形法求解，得到原问题的最终单纯形表为c.       在最终单纯形表中观察影子价格   最终单纯形表中松弛变量x5, x6对应的检验数3/5, 1/5, 就是影子价格，即Y*= = (3/5, 1/5). 它也是对偶问题min z'=45y1＋40y2 y1＋2y2≥13y1＋2y2≥18y1＋ y2≥4y1＋3y2≥3y1, y2≥0的最优解。

并且最终单纯形表中松弛变量x5, x6对应的子阵 ，就是原问题最优基B的逆矩阵，即最优基B－1= .14、通过对一个线性规划问题的最优单纯形表的观察直接得到其对偶问题的最优解（影子价格），这种观察法适宜于哪种类型的线性规划问题？ 这种观察法最适宜于如下类型的线性规划问题，.此类线性规划问题正好在每个约束条件上添加了一个松弛变量后才化为标准形因而，在其最优单纯形表上，直接观察那些松弛变量对应的检验数即可得到对偶问题的最优解（影子价格）同时，原问题最优基B的逆矩阵B－1, 也可直接从最优单纯形表上松弛变量的检验数下方的那些列构成的方阵观察得出具体的例子，请参阅本章FAQ（12）15、通过对一个线性规划问题的最优单纯形表的观察直接得到其对偶问题的最优解（影子价格），这种观察法的理论依据何在？ 不妨设线性规划问题具有如下形式，max z=CXAX≤bX≥0.加入松弛变量向量Xs可化为如下标准形，max z=CXAX＋Xs=bX, Xs≥0.其系数矩阵 , 其中E是单位阵设其最优基存在且为B, 则在该基下的最优单纯形表具有如下形式，可以看到，最优基B下松弛变量Xs对应的检验数CBB－1正好是求影子价格和对偶问题最优解的公式Y*=CBB－1（B是线性规划问题的最优基）的右端项，所以，直接观察最优单纯形表松弛变量的检验数即可得到影子价格和对偶问题的最优解。

同时，最优基B的逆矩阵也可直接在检验数正下方的子阵中观察得到16、影子价格的经济意义何在？以原问题是如下所示的追求利润最大的生产计划问题为例其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.其对偶问题即有如下形式，.其中，对偶问题中的变量yk, k=1, 2,…, m, 反映了单位资源（所可能创造）的价值我们知道这个线性规划问题的对偶问题的最优解Y*=CBB-1 （B是原问题的最优基）被称为影子价格因此影子价格自然就反映了资源在最优配置模式下，单位资源所创造的（平均）价值如果我们从经济学的边际概念出发，那么可以看到影子价格实质上是资源最优配置下，关于资源的边际收益或边际成本B是原问题的最优基）此外，从管理会计的角度看，影子价格在资源出售、出租或购入行为决策中，它也可作为机会成本或机会收益予以考虑最后，简单地说，影子价格反映了（稀缺）单位资源在最优配置下所创造的价值。

17、 影子价格和市场价格有何区别？影子价格并不等同于市场价格一般而言，在研究利用资源实现利润或收益等最大化的问题中，如果资源的影子价格低于市场价。