运筹学电子教案-LP对偶理论.ppt

1 对偶理论是线性规划中最重要的理论之一 是深入了解线性规划问题结构的重要理论基础 同时 由于问题提出本身所具有的经济意义 使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具 那么 对偶问题是怎样提出的 为什么会产生这样一种问题呢 且看下面详解 线性规划LinearProgramming LP 对偶基本理论 对偶问题 2 唉 我想租您的木工和油漆工一用 咋样 价格嘛 好说 肯定不会让您兄弟吃亏讪 引例 俩家具制造商间的对话 线性规划LinearProgramming LP 对偶基本理论 王老板做家具赚了大钱 可惜我老李有高科技产品 却苦于没有足够的木工和油漆工咋办 只有租咯 Hi 王老板 听说近来家具生意好惨了 也帮帮兄弟我哦 家具生意还真赚钱 但是现在的手机生意这么好 不如干脆把我的木工和油漆工租给他 又能收租金又可做生意 价格嘛 好商量 好商量 只是 王老板 李老板 3 王老板的家具生产模型 x1 x2是椅 桌生产量 Z是家具销售总收入 总利润 maxZ 50 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0原始线性规划问题 记为 P 线性规划LinearProgramming LP 对偶基本理论 王老板的资源出租模型 y1 y2单位木 漆工出租价格 W是资源出租租金总收入 minW 120y1 50y2s t 4y1 2y2 503y1 y2 30y1 y2 0对偶线性规划问题 记为 D 4 线性规划LinearProgramming LP 对偶基本理论 王老板按 D 的解y1 y2出租其拥有的木 漆工资源 既保证了自己不吃亏 出租资源的租金收入并不低于自己生产时的销售收入 又使得出租价格对李老板有极大的吸引力 李老板所付出的总租金W最少 按时下最流行的一个词 叫什么来着 双赢 5 原始 对偶 对偶 原始 关系表 线性规划LinearProgramming LP 对偶基本理论 原问题 对偶问题 对偶问题 原问题 目标函数类型 max 变量个数与约束条件个数的对应关系 目标函数系数与右边项的对应关系 原问题变量类型与对偶问题约束条件类型的对应关系 原问题约束条件类型与对偶问题变量类型的对应关系 min 0变量类型 0无限制 约束条件个数m 变量个数n 右边项的系数对应目标函数系数 目标函数各变量系数对应约束条件右边项的系数 约束条件个数m 变量个数n 约束条件类型 约束条件类型 0变量类型 0无限制 6 对偶理论基本定理 1 对称性定理2 弱对偶定理3 强对偶定理原问题与对偶问题解的对应关系表 线性规划LinearProgramming LP 对偶基本理论 问题与解的状态 无界解 对偶问题 有最优解 无可行解 一定 有最优解 无界解 无可行解 原问题 可能 不可能 不可能 不可能 不可能 不可能 可能 可能 7 对偶问题解的经济解释 影子价格我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他们的解之间的关系 那么对偶问题的解除了前面引例中提到的租金这种经济含义外其深刻的经济含义是什么呢 对偶问题解的经济含义分析 从单纯形法的矩阵描述中 目标函数取值Z CBB 1 和检验数CN CBB 1N中都有乘子Y CBB 1 设B是 maxZ CX AX b X 0 的最优基矩阵 由强对偶定理知Z CX CBB 1b Y b W 由此 线性规划LinearProgramming LP 对偶基本理论 Z b Z bi Y b bi CBB 1 Y 或 yi 8 对偶问题解的经济含义 由上面分析 对偶问题解中变量yi 的经济含义是在其他条件不变的情况下 单位第i种 资源 变化所引起的目标函数最优值的变化 所以 yi 描述了原始线性规划问题达到最优时 各种 资源 都处于最优的配置时 第i种 资源 的某种 价值 故称其为第i种 资源 的影子价格 下面图解阐述影子价格的直观含义 采用单纯形法求解得 P 的最优解 最优基矩阵如下 线性规划LinearProgramming LP 对偶基本理论 P 的最优解为X 15 20 0 0 T B p2 p1 3412 D 的最优解为Y CBB 1 5 15 CB C2 C1 30 50 B 1 1 2 1 23 2 9 王老板的家具生产模型的图解 线性规划LinearProgramming LP 对偶基本理论 x1 x2 4x1 3x2 120 2x1 x2 50 L0 50 x1 30 x2 D 可行域 1350 50 x1 30 x2 15 20 P maxZ 50 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0 10 影子价格的直观含义 线性规划LinearProgramming LP 对偶基本理论 x1 x2 4x1 3x2 120 2x1 x2 50 L0 50 x1 30 x2 D 可行域 P maxZ 50 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0 2x1 x2 51 4x1 3x2 121 1365 50 x1 30 x2 1355 50 x1 30 x2 11 影子价格的特点 影子价格是对偶解的一个十分形象的名称 它既表明对偶解是对系统内部资源在当前的最优利用配置下的一种客观估价 又表明它是一种虚拟的价格 或价值的影象 而不是真实的价格 特点1 影子价格是对系统资源的一种内部最优估价 只有当系统达到最优状态时才可能赋予资源这种价值 特点2 系统资源的一种动态价格体系 影子价格的大小与系统的价值取向有关 并受系统状态变化的影响 系统环境的任何变化都可能会引起影子价格的变化 特点3 影子价格的大小客观地反映资源在系统内的稀缺程度 如果某种资源在系统内供大于求 尽管它有实实在在的市场价格 但它在系统内的影子价格却为零 而影子价格越高 资源在系统内越稀缺 线性规划LinearProgramming LP 对偶基本理论 12 特点4 影子价格是一种边际价值 其与经济学中的边际成本的概念相同 因而 在经济管理中十分重要的应用价值 企业管理者可以根据资源在企业内部的影子价格的大小决定企业的经营策略 特点5 对偶解准确的经济意义与线性规划模型的构造方法有关 模型构造方法的不同有时会导致对偶解的不同经济解释 线性规划LinearProgramming LP 对偶基本理论 13 对偶单纯形法 引例 线性规划LinearProgramming LP 对偶基本理论 maxZ 2x1 x2s t x1 x2 x3 52x2 x3 54x2 6x3 9x1 x2 x3 0 maxZ 2x1 x2s t x1 x2 x3 52x2 x3 x4 54x2 6x3 x5 9x1 x2 x3 x4 x5 0 标准化 准典式 maxZ 1x2 2x3s t x1 x2 x3 52x2 x3 x4 5 4x2 6x3 x5 9x1 x2 x3 x4 x5 0 化典式 14 对偶单纯形表 线性规划LinearProgramming LP 对偶基本理论 基解X1X2X3X4X5 X1511100X4502110X5 90 4 601 检验数0 1 200 比值 1 41 3 X111 410 1 201 4X41 200 211 2X29 4012 30 1 4 检验数00 1 20 1 4 15 线性规划问题参数变化敏感性分析 敏感性分析的重要性在于向决策者提供线性规划问题的最优解所能适应的环境条件变化的范围 环境条件变化时可能对经营状况带来何种影响 产生影响后的解决途径 敏感性分析的类