1 矩阵表示 对偶问题 理论 影子价格.ppt

1、对偶理论与灵敏度分析 (Dual Theories and Sensitivity Analysis),单纯形法的矩阵描述 线性规划的对偶问题 对偶问题的基本性质 对偶问题的经济解释 -影子价格 对偶单纯形法 灵敏度分析,单纯形法的矩阵描述,考虑线性规划问题的标准型,A Rmn, R(A)=m .,单纯形法的矩阵描述,单纯形法的矩阵描述,单纯形法的矩阵描述,由此可见：单纯形法的计算过程中，各部分的数字都是用 基的逆矩阵来进行计算的。因此，单纯形法的计算机实现 的关键步骤是对基的逆矩阵的计算。,线性规划的单纯形法,线性规划的单纯形法,单纯形法的矩阵计算,（4）求改进了的基本可行解 以x3为换入变

2、量，x4为换出变量，将换入变量x3所在的列变 为 ，替换二阶单位矩阵中的第1列，得 故新的可行基的逆为,（4）求改进了的基本可行解 以x1为换入变量，x5为换出变量，将换入变量x1所在的列变 为 ，替换二阶单位矩阵中的第2列，得 故新的可行基的逆为,线性规划问题的对偶问题 (Dual Problems),1. 对偶问题的提出 (Dual Problem),例1 某工厂用两台机器生产三种产品,有关数据如下表:,如何组织生产，使总利润最大？,x1 , x2 , x3 -分别生产甲、 乙、丙产品的数量,例2 若该工厂想要出租这两台机器，那么该工厂应 该如何确定合理的租金呢？,线性规划问题的对偶问题,

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

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

5、中基变量XB的剩余变量， YS2是对应原问 题中非基变量XN的剩余变量，Y为对偶变量。,对偶问题的基本性质,对偶问题的基本性质,令 原问题的可行解， 是对偶问题的可行解，则它们分别是原问题 与对偶问题的最优解的充要条件是:,例 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，所以对偶问

6、题的第一个约束条件以及第三个约束条件 均应取等式，即 8y*1+4 y*2+2y*3=60， y*1+1.5y*2+0.5y*3=20. 解之得 y*2=10, y*3=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 时，该种资源在生产中 已消耗完毕，目前比较稀缺，此时如果管理者增加该资源的供应 量，则总收益就会增加。,线性规划对偶问题的经济解释-影子价格,影子价格对市