whut运筹学-7 矩阵表示 对偶问题 理论 影子价格.ppt

1、对偶理论与灵敏度分析 (Dual Theories and Sensitivity Analysis),单纯形法的矩阵描述 线性规划的对偶问题 对偶问题的基本性质 对偶问题的经济解释 -影子价格 对偶单纯形法 灵敏度分析,例,单纯形法的矩阵描述 (Matrices Description),CB=2 0 3,CN=0 0,单纯形法的矩阵描述,B,CB,XB,CN,XN,N,b,单纯形法的矩阵描述,单纯形法的矩阵描述,B-1 N,B-1 b,单纯形法的矩阵描述,考虑线性规划问题的标准型,A Cmn, R(A)=m .,单纯形法的矩阵描述,单纯形法的矩阵描述,单纯形法的矩阵描述,继续讨论上例,CB

2、=2 0 3,CBB -1=1.5 1/8 0,单纯形法的矩阵描述,例 用单纯形法求解下述线性规划问题.,解: 把原问题化为标准型,单纯形法的矩阵描述,用单纯形法求解如下:,单纯形法的矩阵描述,单纯形法的矩阵描述,线性规划问题的对偶问题 (Dual Problems),1. 对偶问题的提出 (Dual Problem),例1 某工厂用两台机器生产三种产品,有关数据如下表:,如何组织生产，使总利润最大？,x1 , x2 , x3 -分别生产甲、 乙、丙产品的数量,例2 若另一工厂想要租赁这两台机器用于生产产品，那么该 工厂应该如何确定合理的租金呢？,线性规划问题的对偶问题,y1 , y2 -机器

3、I与机器II 的每台时的租金,例1与例2是一个问题的两个方面 两个线性规划模型是一对对偶问题,线性规划问题的对偶问题,2. 原问题与对偶问题的关系,对称性关系,例 3 求下列问题的对偶问题,对称性形式的对偶关系,线性规划问题的对偶问题,非对称性关系,练习：,线性规划问题的对偶问题,原问题与对偶问题对偶关系对照表,线性规划问题的对偶问题,例 4 求下列问题的对偶问题,线性规划问题的对偶问题,例 5 求下列问题的对偶问题,线性规划问题的对偶问题,考虑对称性关系的对偶：,对偶问题的基本性质(Basic Properties),对偶问题的对偶是原问题。,若原(对偶)问题有无界解，则对偶(原)问题无可行

4、解.,对偶问题的基本性质,不可行,不可行,无界,不可行,若原问题有最优解，相应的最优基为 B, 则对偶问题也有最优解，且最 优解为 (CBB -1)T ；并且目标函数值相等，均为 CBB-1b .,对偶问题的基本性质,对偶问题的基本性质,设原问题是 它的对偶问题是 则原问题单纯性表的检验数行对应其对偶问题的一个基解：,例 已知用单纯形法求解下述线性规划问题所得最终表如下，试确 定该问题的对偶问题的最优解.,对偶问题的基本性质,解: 由已知得 CB=(2 0 3),因此，由对偶定理可得所求问题的对偶问题的最优解为：,(Y*)Tb=?,对偶问题的基本性质,令 原问题的可行解， 是对偶问题的可行解，

5、则它们分别是原问题 与对偶问题的最优解的充要条件是:,例 6 已知线性规划问题,且其最优解为x*1=2, x*2=0, x*3=8. 试用对偶问题的性质求其对 偶问题的最优解。,对偶问题的基本性质,解: 此线性规划问题的对偶问题是：,将 x*1=2, x*2=0, x*3=8 代入原线性规划问题的约束条件中，可知第一个约束 条件为严格不等式，则由互补松弛性得 y*1=0.,对偶问题的基本性质,又因 x*1 x*30，所以对偶问题的第一个约束条件以及第三个约束条件 均应取等式，即 8y*1+4 y*2+2y*3=60， y*1+1.5y*2+0.5y*3=20. 解之得 y*2=10, y*3=

6、10.,因此，对偶问题的最优解为 y*1=0 , y*2=10, y*3=10.,线性规划对偶问题的经济解释-影子价格 (Shadow Prices),设 与 分别是原问 题与对偶问题的最优解，则由对偶问题的基本性质有,由此，,变量 的经济意义是：在其他条件不变的情况下， 第 i种资源的单位改变量所引起的目标函数值的增加量。,1 影子价格的解释,变量 的值代表对第 i 种资源的估价。这种估价不是资 源 i 的市场价格，而是具体工厂根据资源在生产中做出的贡 献而作的估价，称它为 “影子价格 ”。,影子价格是对偶解的一个十分形象的名称，它既表明了对偶 解是对系统内部资源的一种客观估价，又表明它是一

7、种虚 拟的价格，而不是真实的价格。,线性规划对偶问题的经济解释-影子价格,例 某工厂用三台机器生产两种产品,有关数据如下表:,如何组织生产，使总利润最大？,甲(m) 乙(m) 可供资源(台时) 机器 I 1 2 8 机器 II 4 0 16 机器 III 0 4 12 利润 2 3,x1 , x2 -分别生产甲、 乙产品的数量,线性规划对偶问题的经济解释-影子价格,问题：若另一工厂想要租赁这三台机器用于生产产品，那么该 工厂应该如何确定合理的租金呢？,y1 , y2 , y2 -机器I、机器II与机器III 的每台时的租金,线性规划对偶问题的经济解释-影子价格,2 影子价格的作用,影子价格的大小反映了资源在系统内的稀缺程度,根据互补松弛性，某种资源的影子价格为 0 时，该种资源未充分利 用，仍有剩余；某种资源的影子价格不为 0 时，该种资源在生产中 已消耗完毕，目前比较稀缺，此时如果管理者增加该资源的供应 量，则总收益就会增加。,线性规划对偶问题的经济解释-影子价格,影子价格对市场有调节