线性规划 Linear Programming(LP) 线性规划的对偶理论 对偶问题的基本性质 对称性——原始问题与对偶问题是两个互为对偶的问题。 2.弱对偶性—两个问题的可行解对应的目标函数值互为上下界。 3.最优性——两个问题最优解的目标函数值必相等。 4.强对偶性——两个问题都有可行解时则两个问题必都有最优解。 5.互补松弛性——两个问题最优解中,一个问题中某个变量取值非零, 则该变量在对偶问题中对应的某个约束条件必为紧约束;反之,如 果约束条件为松约束,则其对应的对偶变量一定取值为零。因此, 该定理又称为松紧定理
11 线性规划 Linear Programming（LP） 线性规划的对偶理论 ▪ 对偶问题的基本性质 1. 对称性——原始问题与对偶问题是两个互为对偶的问题。 2. 弱对偶性——两个问题的可行解对应的目标函数值互为上下界。 3. 最优性——两个问题最优解的目标函数值必相等。 4. 强对偶性——两个问题都有可行解时则两个问题必都有最优解。 5. 互补松弛性——两个问题最优解中，一个问题中某个变量取值非零， 则该变量在对偶问题中对应的某个约束条件必为紧约束；反之，如 果约束条件为松约束，则其对应的对偶变量一定取值为零。因此， 该定理又称为松紧定理
线性规划 Linear Programming(LP) 线性规划的对偶理论 原问题与对偶问题解的对应关系表 问题与解的状态 对偶问题 有最优解无界解无可行解 原有最优解 定 不可能不可能 问无界解不可能不可能可能 题无可行解不可能可能 可能 12
12 线性规划 Linear Programming（LP） 线性规划的对偶理论 原问题与对偶问题解的对应关系表 问题与解的状态 对偶问题 有最优解 无界解 无可行解 原 问 题 有最优解 一定 不可能 不可能 无界解 不可能 不可能 可能 无可行解 不可能 可能 可能
线性规划 Linear Programming(LP) 线性规划的对偶理论 对偶问题解的经济解释—影子价格 我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他 们的解之间的关系,那么对偶问题的解除了前面引例中提到的租金这种经 济含义外其深刻的经济含义是什么呢? 13
13 线性规划 Linear Programming（LP） 线性规划的对偶理论 ▪ 对偶问题解的经济解释——影子价格 我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他 们的解之间的关系，那么对偶问题的解除了前面引例中提到的租金这种经 济含义外其深刻的经济含义是什么呢？
线性规划 Linear Programming(LP) 线性规划的对偶理论 对偶问题解的经济含义分析: 从单纯形法的矩阵描述中,目标函数取值z=CBb,和检验数 cN-CBN中都有乘子Y=CB1 设B是{maxZ=CX|AX≤b,X≥0}的最优基矩阵,由强对偶定理知 Z*ECX*= CB b=yb=w 由此 aZ a b CB=y或az=a(yb) a b a b yi 14
14 线性规划 Linear Programming（LP） 线性规划的对偶理论 ▪ 对偶问题解的经济含义分析： 从单纯形法的矩阵描述中，目标函数取值 Z = CBB -1 b ，和检验数 CN -CBB -1N 中都有乘子 Y = CBB -1 。 设B是{ max Z = CX | AX ≤ b，X ≥0 }的最优基矩阵，由强对偶定理知 Z* =CX*= CBB -1 b=Y*b=W* 由此 Z* b Z* bi （ Y*b） bi = CBB -1 = Y* 或 = = yi *
线性规划 Linear Programming(LP) 线性规划的对偶理论 对偶问题解的经济含义 由上面分析—对偶问题解中变量y的经济含义是在其他条件不变 的情况下,单位第i种“资源”变化所引起的目标函数最优值的变化。所 以,y*描述了原始线性规划问题达到最优时(各种“资源”都处于最优 的配置时),第i种“资源”的某种“价值”,故称其为第i种“资源” 的影子价格。 下面图解阐述影子价格的直观含义:
15 线性规划 Linear Programming（LP） 线性规划的对偶理论 ▪ 对偶问题解的经济含义： 由上面分析——对偶问题解中变量 yi * 的经济含义是在其他条件不变 的情况下，单位第 i 种“资源”变化所引起的目标函数最优值的变化。所 以， yi * 描述了原始线性规划问题达到最优时（各种“资源”都处于最优 的配置时），第 i 种“资源”的某种“价值”，故称其为第 i 种“资源” 的影子价格。 下面图解阐述影子价格的直观含义：