(运筹学第章.ppt

第二章 线性规划的对偶理论 线性规划的对偶问题及其变换 线性规划的对偶定理 对偶单纯形法 线性规划的灵敏度分析 2.1对偶问题的提出2.1.1 引例 任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义 例2.1 设A、B资源的出售价格分别为 y1 和 y2 显然商人希望总的收购价越小越好 工厂希望出售资源后所得不应比生产产品所得少 2.1.2 线性规划的规范形式 2.1.3 对偶模型 2.1.3 对偶模型 目标函数由 max 型变为 min 型 对应原问题每个约束行有一个对偶变量 yi，i=1,2,…,m 对偶问题约束为 ? 型，有 n 行 原问题的价值系数 C 变换为对偶问题的右端项 原问题的右端项 b 变换为对偶问题的价值系数 原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵 原问题与对偶问题互为对偶 对偶问题可能比原问题容易求解 对偶问题还有很多理论和实际应用的意义 非标准型的对偶变换 表2.2 对偶变换的规则 约束条件的类型与非负条件对偶 非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的 2.2 对偶问题的基本性质 性质2.2 弱对偶性 定理 对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值，即： CX0 ≦ Y0b 弱对偶定理推论 max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限 如果原max(min)问题为无界解，则其对偶 min (max)问题无可行解 如果原max(min)问题有可行解，其对偶 min (max)问题无可行解，则原问题为无界解 注：存在原问题和对偶问题同时无可行解的情况 性质2.3 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解 证：由弱对偶定理推论1，结论是显然的。 即CX0 = Y0b ? CX, Y0b = CX0 ? Yb 。 证毕。 主对偶定理的证明 证：现证明定理的后一句话，采用反证法。 设 X0 ， Y0分别为原问题和对偶问题的最优解，且 Y0b CX0 根据最优性检验条件，非基变量的检验数满足 CN ?CBB?1N ? 0，而基变量的检验数为0，可写成 CB ?CBB?1B = 0，所以，包括基变量在内的所有变量的检验数满足 C ? CBB?1A ? 0。令 Y= CBB?1，则有 Y A ? C。 另外，对应于松驰变量，有? CBB?1I ? 0，即 Y= CBB?1 ? 0，故 Y为对偶问题的可行解。而 Yb = CBB?1b=CX0 Y0b，与 假设矛盾。故得证。 该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本 即对偶变量的最优解是原问题资源的影子价格 性质2.5 互补松弛性 定理 设X0, Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 = 0 证：由定理所设，可知有 A X0 + U0 = b X0, U0 ?0 (1) Y0 A ? V0 = C Y0, V0 ?0 (2) 分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得 Y0 U0 + V0 X0 = Y0 b ? C X0 若 Y0 U0 + V0 X0 = 0，根据最优解判别定理， X0, Y0分别是原问题和对偶问题最优解。反之亦然。 证毕。 例 max z=2x1+x2 5x2?15 6x1+2x2 ?24 x1 + x2 ?5 x1 , x2 ?0 用单纯形法求得两个问题的最终单纯形表分别见表2.1和表2.2. 表2.1 表2.2 从表2.1和表2.2，可以清楚看出两个问题变量之间的对应关系。同时根据上述对偶问题的性质，我们只需求解其中一个问题，从最优解的单纯形表中同时得到另一个问题的最优解。 又根据上述对偶问题的性质，在单纯形法迭代的每一步，如果原问题是可行解，其对偶问题也是可行解，则相应解分别是两个问题的最优解；如果原问题是可行解，其对偶问题是非