《对偶理论与灵敏度分析》由会员分享，可在线阅读，更多相关《对偶理论与灵敏度分析（51页珍藏版）》请在金锄头文库上搜索。
1、第三章 对偶理论与灵敏度分析p 对偶线性规划 p 对偶定理 p 对偶最优解的经济解释影子价格 p 对偶单纯形法 p 灵敏度分析1对偶理论是线性规划的重要内容之一。随着线性规划问题研究的深入，人们发现对应于每个线性规划问题都伴生一个相应的线性规划问题。前者是由矩阵，右端向量和价值向量定义的，称之为原问题；后者也是由相同的数据集合，和构成的，称之为原文题的对偶问题。一对原问题和对偶问题是紧密关联的，它们不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解。对偶理论深刻地指示了原问题和对偶问题的内在联系，由对偶问题引伸出来的对偶解还有着重要
2、的经济意义，是研究经济学的重要概念和工具之一。 2n对偶问题的提出 例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同 设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们 销售后所能获得的利润，以及这三种设备在计划期内能提供的有限 台时数均列于表。试问如何安排生产计划，即甲,乙两种产品各生产 多少吨，可使该厂所获得利润达到最大。 p对偶线性规划设备每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 3假设计划期内甲乙两种产品各生产 吨，用图解法或单纯形法可求得最优解 (元) 即在计划期内甲产品生产 吨
3、，乙产品生产8吨，可以使总利润达到最大，为 元。设备每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 4现在从另一个角度来考虑该工厂的生产问题:假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。设 分别为设备A，B，C每台时的租价，约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润目标函数：所获租金总额尽量少5由此可得两个对称的线性规划：矩阵形式：6n对偶线性规划考虑如下具有“”不等式约束的线性规划问题加入松弛变量X
4、S=(xn+1,xn+2,xn+m)T以后可得标准型若B是系数矩阵（A , I）中的一个可行基，并假设（A , I）可表示为（B, N），则线性规划问题可改写为 可得基本可行解 ,目标函数值 ，若非基变量检验数 则 为最优解7因为基变量检验数 , 最优解判别准则又可表述为 。 上述表达式又可写成 即 ，其中 称为单纯形乘子。 所以当 为最优解，且单纯形乘子 用符号示时 ，可以推得： 且由 ，所以 只存在最小值。 由此可以得到另一个线性规划： 称之为原线性规划问题的对偶问题，8n 线性规划问题标准型的对偶问题考虑一个标准形式的线性规划问题由于任何一个等式约束都可以用两个不等式约束等价地表示，所以
5、标准形线性规划问题可等价表示为：它的对偶规划为： 若令 线性规划标准型的对偶规划为：9n对偶线性规划的求法从任何一个线性规划出发，都可以求出相应的对偶规划，在 实际求解过程中，通常不通过求标准型，而是利用如下反映原始 问题与对偶问题对应关系的原始对偶表：目标函数变量系数 约束条件右端项 约束条件右端项 目标函数变量系数 约束条件个数：n个 决策变量个数：n个 对偶变量个数：m个 约束条件个数：m个 目标函数minW 目标函数maxZ 对偶问题（或原问题） 原问题（或对偶问题） 10例2 写出下列线性规划的对偶问题解：设对于原问题4个约束条件的对偶变量分别为由4个约束条件的类型，可知4个对偶变量
6、分别为0，0，0和无约束；又因为原问题有3个决策变量 ，因此对偶规划有3个约束条件，由3个决策变量的符号，可知对偶规划3个约束条件的类型分别为，=。由此可得上述问题的对偶规划：11本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。定理1：对偶问题的对偶是原问题。证明：设原问题为 对偶问题为改写对偶问题为 对偶问题的对偶为p对偶定理12定理2：弱对偶定理若 是原（极大化）问题的可行解， 是对偶（极小化）问题的可行解，那么证明：因为 是对偶问题的可行解，所以满足约束条 且；又因为 是原问题的可行解，可得 ， ,所以 。推论1：原（极大化）问题的最优目标函数值以对偶
7、问题任一可行解的 目标函数值为上界。对偶（极小化）问题的最优目标函数值以原问题任一可行解的目 标函数值为下界。推论2：如果原问题没有上界（即maxZ+），则对偶问题不可行。如果对偶问题没有下界（即minW-），则原问题不可行。13定理3：最优性定理若 是原问题的可行解， 是对偶问题的可行解，而且两者的目标函数值相等，即 ，则 和 分别是原问题和对偶问题的最优解。证明：由弱对偶定理，对于原始问题的所有可行解 ，都有 因此 是原问题的最优解。同理，对于对偶问题的所有可行解 ，都有所以 是对偶问题的最优解。 14定理4: 强对偶定理如果原问题有最优解，那么对偶问题也有最优解，而且目标函数值相等。证明
8、：设 是原问题的最优解，则它们对应的基必有，且松弛变量检验数 。若定义 ，则 ，且 ，因此 为对偶问题的可行解，而且 ，由最优性定理， 是对偶问题的最优解。 推论1：若原问题有一个对应于基的最优解，那么此时的单纯形乘子 是对偶问题的一个最优解。 根据这个推论我们可以在原问题的最优单纯形表中直接找到对偶问题的最优解，即松弛变量检验数的相反数 。 15例4、利用单纯形表求例1中原问题的最优解，并由最优单纯形 表推出对偶问题的最优解。解：原问题线性规划模型为：引入松弛变量 ，化标准形得:161 0 -2/3 0 1/34/3x1320 0 1/3 1 -2/33/4X404/2 1 0 0 2 -1
9、4x1324/3 0 0 1 3 -24X308/4/5 1 4/5 0 1/5 08x13212/8/5 0 8/5 1 -3/5 012X3040/5 5 4 0 1 040x4036/3 3 4 1 0 036X300 0 -7/6 0 -19/6Z0 1 3/4 0 -1/48x2300 0 0 7/2 -11/2278Z0 1 0 -9/4 5/45x2300 22/5 0 -32/5 0256Z4/4/5 0 4/5 0 -9/5 14x5032 30 0 0 00Z76/9 9 8 0 0 176x50x1 x2 x3 x4 x5bXBCB32 30 0 0 0 C17由最优表可
10、知，原问题最优解同时不难得到原问题的最优基由强对偶定理的推论可得此时的单纯形乘子 为对偶问题的最优解,即松弛变量检验数 的相反数。 C32 30 0 0 0CBXBbx1 x2 x3 x4 x50 32 30x4 x1 x23/4 4/3 80 0 1/3 1 -2/31 0 -2/3 0 1/30 1 3/4 0 -1/4 Z 0 0 -7/6 0 -19/618定理5：互补松弛定理 如果 分别是原问题的对偶问题的可行解，那么和 为最优解的充要条件是 其中 为原问题的松弛变量， 是对偶问题的剩余变量。通常称 为互补松弛条件。 若令则 的含义是：要么 ，要么 若令则 的含义是：要么 ，要么 1
11、9例5、已知线性规划问题: 其对偶问题的最优解。试用互补松弛定理找出原问题的最优解。解：原问题的对偶问题为：由对偶问题最优解 可知 ，由互补松弛定理，原问题的松弛变量解方程组 所以原问题最优解20对偶问题可改写为定理6：原问题的检验数对应对偶问题的一个基本解。证明：设是原问题的一个可行基，且则原问题可以写为其中 分别为原问题决策变量中基变量和非基变量所对应的对偶约束 的剩余变量。 对偶问题也可等价表示为：对原问题可行基，可得可行解 对应于 的检验数分别为。不难验证， 为对偶问题的一个基本解。 21由强对偶定理可知，如果原问题有最优解 ，那么对偶问题也有最优解 ，而且它们的目标函数值相等，即有：
12、其中 是线性规划原问题约束条件的右端数据向量，它代表各种资源的拥有量。为对偶问题最优解，它代表在资源最优利用条件下对各种单位资源的估价，这种估计不是资源的市场价格，而是根据资源在生产中所作出的贡献（如创造利润，产值等）而作出估价，为区别起见，称之为影子价格(shadow price)。p对偶最优解的经济解释影子价格 22影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。如果第i种资源供大于求，即在达到最优解时，该种资源没有用完，或松弛变量 ，由互补松弛定理，在对偶最优解 中，第i种资源的影子价格 。反之如果第i种资源的影子价格 ，那么由互补松弛定理，原问题的第i个约束为严格等式，即 ，这表明第i种资源已经用完，成为稀缺资源。 资源的影子价格同时也是一种机会成本，在市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进这种资源用于扩大生产；相反当某种资源的市场价格高于影子价格时，企业应卖出这种资源。随着资源的买进卖出，企业资源的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。23设备每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 例：对偶最优解其中 为设备A的影子价格，在资源最优利用的条件下，
