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

对偶问题的基本性质 例 已知用单纯形法求解下述线性规划问题所得最终表如下，试确 定该问题的对偶问题的最优解. 对偶问题的基本性质 解: 由已知得 CB=(2 0 3), 因此，由对偶定理可得所求问题的对偶问题的最优解为： XB x1 x2 x3 x4 x5 b R x1 1 0 0 1/4 0 4 x5 0 0 -2 0.5 1 4 x2 0 1 0.5 -1/8 0 2 -z 0 0 -3/2 -1/8 0 -14 其中 x3, x4, x5 为 松弛变量。 (Y*)Tb=? 对偶问题的基本性质 对偶问题的基本性质 设原问题为 它的对偶问题是 则原问题单纯性表的检验数行对应其对偶问题的一个基解。 其中， YS1是对应原问题中基变量XB的剩余变量， YS2是对应原问 题中非基变量XN的剩余变量，Y为对偶变量。 原问题 XB XN XS 检验数 0 CN-CBB-1N -CBB-1 对偶问题 YS1 -YS2 -Y 原问题与对偶问题的关系 对偶问题的基本性质 对偶问题的基本性质 原问题 XB XN XS 检验数 0 CN-CBB-1N -CBB-1 对偶问题 YS1 -YS2 -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，所以对偶问题的第一个约束条件以及第三个约束条件 均应取等式，即 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 的市场价格，而是具体工厂根据资源在生产中做出的贡 献而作的估价，称它为 “影子价格 ”。 影子价格是对偶解的一个十分形象的名称，它既表明了对偶 解是对系统内部资源的一种客观估价，又表明它是一种虚 拟的价格，而不是真实的价格。 线性规划对偶问题的经济解释-影子价格 例 某工厂用三台机器生产两种产品,有关数据如下表: 如何组织生产，使总利润最大？ 甲(m) 乙(m) 可供资源(台时) 机器 I 1 2 8 机器 II 4 0 16 机器 III 0 4 12 利润 2 3 x1 , x2 ------分别生产甲、 乙产品的数量 X*=(4, 2)T z*=14 线性规划对偶问题的经济解释-影子价格 问题：若另一工厂想要租赁这三台机器用于生产产品，那么该 工厂应该如何确定合理的租金呢？ y1 ,