Chapter3.1-3.2线性规划的对偶和灵敏度分析.ppt

Chapter3线性规划的对偶和灵敏度分析 对偶问题的提出对偶问题的基本性质影子价格对偶单纯形法灵敏度分析 选讲 本章主要内容 3 1对偶问题的提出 对偶理论是线性规划中最重要的理论之一 是深入了解线性规划问题结构的重要理论基础 同时 由于问题提出本身所具有的经济意义 使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具 那么 对偶问题是怎样提出的 为什么会产生这样一种问题呢 对偶问题的提出 两个黄鹂鸣翠柳 一行白鹭上青天 窗含西岭千秋雪 门泊东吴万里船 杜甫 绝句 俩家具制造商间的对话 唉 我想租您的木工和油漆工一用 咋样 价格嘛 好说 肯定不会让您兄弟吃亏 王老板做家具赚了大钱 可惜我老李有高科技产品 却苦于没有足够的木工和油漆工咋办 只有租咯 Hi 王老板 听说近来家具生意好呀 也帮帮兄弟我哦 家具生意还真赚钱 但是现在的手机生意这么好 不如干脆把我的木工和油漆工租给他 又能收租金又可做生意 价格嘛 好商量 好商量 只是 王老板 李老板 引例1 对偶问题的提出 王老板家具厂木器车间生产木门与木窗两种产品 加工木门收入为56元 扇 加工木窗收入为30元 扇 生产一扇木门需要木工4小时 油漆工2小时 生产一扇木窗需要木工3小时 油漆工1小时 该车间每日可用木工总工时为120小时 油漆工总工时为50小时 该车间应如何安排生产才能使每日收入最大 王老板 解 设该车间每日安排生产木门x1扇 木窗x2扇 则数学模型为 设用y1 y2分别表示付给木工和油漆工的价格 王老板在做定价决策时 作如下比较 若用4个小时木工和2个小时油漆工可以生产一扇木门 可获利56元 那么付给加工木门的木工和油漆工的价格应不低于加工一扇木门的利润 这就有 同理付给加工木窗的木工和油漆工的价格应不低于加工一扇木窗的利润 这就有 把每日可用木工和油漆工的总工时出让 其总收入为 只能在满足 所有产品的利润的条件下 其总收入尽可能少 才能成交 王老板的家具生产模型 x1 x2是木门 木窗生产量 Z是家具销售总收入 maxZ 56x1 30 x2s t 4x1 3x2 120 木工 2x1 x2 50 油漆工 x1 x2 0原始线性规划问题 记为 P 王老板的资源出租模型 y1 y2木 油漆工出租价格 W是资源出租租金总收入 minW 120y1 50y2s t 4y1 2y2 563y1 y2 30y1 y2 0对偶线性规划问题 记为 D 所得不得低于生产的获利 不吃亏原则 要使对方能够接受 竞争性原则 两个原则 对偶问题的提出 王老板按 D 的解y1 y2出租其拥有的木 漆工资源 既保证了自己不吃亏 出租资源的租金收入并不低于自己生产时的销售收入 又使得出租价格对李老板有极大的吸引力 李老板所付出的总租金W最少 按时下最流行的一个词 叫什么来着 对偶问题的提出 设三种资源的使用单价分别为y1 y2 y3 y1y2y3 生产单位产品甲的资源消耗所得不少于单位产品甲的获利 生产单位产品乙的资源消耗所得不少于单位产品乙的获利 3y1 2y2 1500 2y1 y2 3y3 2500 通过使用所有设备对外利用所获得的收益 W 65y1 40y2 75y3 对偶问题的提出 根据原则2 对方能够接受的价格显然是越低越好 因此此问题可归结为以下数学模型 MinW 65y1 40y2 75y3 3y1 2y2 15002y1 y2 3y3 2500y1 y2 y3 0 s t 目标函数 约束条件 原线性规划问题称为原问题 此问题为对偶问题 y1 y2 y3为对偶变量 也称为影子价格 对偶问题的提出 2 4线性规划的对偶理论 MaxZ 1500 x1 2500 x2 3x1 2x2 652x1 x2 403x2 75x1 x2 0 s t 原问题 对偶问题 对偶问题 原问题 一 原问题与对偶问题的对应关系 3个约束2个变量 2个约束3个变量 线性规划的对偶理论 对偶问题的形式 定义设原线性规划问题为则称下列线性规划问题 为其对偶问题 其中yi i 1 2 m 称为对偶变量 上述对偶问题称为对称型对偶问题 原问题简记为 P 对偶问题简记为 D 称问题 P 和 D 为一对对偶问题 线性规划的对偶理论 对称型问题的对偶规则 1 给每个原始约束条件定义一个非负对偶变量yi i 1 2 m 2 使原问题的目标函数系数cj变为其对偶问题约束条件的右端常数 3 使原问题约束条件的右端常数bi变为其对偶问题目标函数的系数 4 将原问题约束条件的系数矩阵转置 得到其对偶问题约束条件的系数矩阵 5 改变约束问题不等号的方向 即将 改为 6 原问题为 max 型 对偶问题为 min 型 线性规划的对偶理论 原始问题MaxZ CXs t AX bX 0 b A C Max n m 对偶问题MinW Ybs t YA CY 0 Min C AT b n m 线性规划的对偶理论 当原问题为求极小值时 对偶问题为求极大值 原始问题中目标函数的系数变成对偶问题中约束条件的右端 原始问题中约束条件的右端变成对偶问题中目标函数的系数 原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵 原始问题的约束条件个数决定对偶问题变量的个数 原始问题变量个数 决定对偶问题的约束个数 原始问题的约束方程的匹配形式决定对偶问题变量的符号 原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式 线性规划的对偶理论 求线性规划问题的对偶规划 解 由原问题的结构可知为对称型对偶问题 例1 线性规划的对偶理论 求线性规划问题的对偶规划 解 由原问题的结构可知不是对称型对偶问题 可先化为对称型 再求其对偶规划 例2 线性规划的对偶理论 求线性规划问题的对偶规划 解 由原问题的结构可知不是对称型对偶问题 可先化为对称型 再求其对偶规划 例3 线性规划的对偶理论 上式已为对称型对偶问题 故可写出它的对偶规划 令 则上式化为 线性规划的对偶理论 对偶问题的非对称形式 minz 2x1 4x2 x3s t 3x1 x2 2x36 x1 2x2 3x3122x1 x2 2x38x1 3x2 x315 maxw 6y1 12y2 8y3 15y4s t 3y1 y2 2y3 y42 y1 2y2 y3 3y442y1 3y2 2y3 y4 1y10 y2 y30 y40 unr x1 0 x2 0 x3 unr 线性规划的对偶理论 线性规划的对偶理论 例2 写出下述线性规划问题的对偶问题 解 设对偶变量为 则对偶问题为 例2 5 写出下列线性规划的对偶问题 解 目标函数求最小值 应将表2 1的右边看作原问题 左边是对偶问题 原问题有3个约束4个变量 则对偶问题有3个变量4个约束 对照表2 1的对应关系 对偶问题为 写出下列线性规划的对偶问题 性质1对称性定理 对偶问题的对偶是原问题 3 2对偶问题的基本性质 线性规划的对偶理论 对偶的定义 简要证明 线性规划的对偶理论 性质2弱对偶原理 弱对偶性 设和分别是问题 P 和 D 的可行解 则必有 线性规划的对偶理论 推论1 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界 反之 对偶问题任意可行解的目标函数值是其原问题目标函数值的上界 证明 1 当X和Y为原问题和对偶问题的一个可行解 有 原问题目标函数值 对偶问题目标函数值 线性规划的对偶理论 推论2 在一对对偶问题 P 和 D 中 若其中一个问题可行但目标函数无界 则另一个问题无可行解 反之不成立 这也是对偶问题的无界性 线性规划的对偶理论 推论3 在一对对偶问题 P 和 D 中 若一个可行 如P 而另一个不可行 如D 则该可行的问题目标函数值无界 利用对偶性质判断下面问题有无最优解 例3 6 解 此问题的对偶问题为 不能成立 因此对偶问题不可行 故由推论3知原问题无界 线性规划的对偶理论 课堂练习利用对偶性质判断下面问题有无最优解 解 此问题的对偶问题为 不能成立 因此对偶问题不可行 故由推论3知原问题无界 线性规划的对偶理论 性质3最优性定理 如果是原问题的可行解 是其对偶问题的可行解 则 当且仅当是原问题的最优解 是其对偶问题的最优解 线性规划的对偶理论 性质4强对偶性 若一对对偶问题中的任意一个有最优解 则另一个也有最优解 且目标函数最优值相等 性质5无界解定理 若原问题 对偶问题 的解为无界解 则其对偶问题 原问题 无可行解 线性规划的对偶理论 性质6互补松弛性 设X 和Y 分别是P问题和D问题的可行解 则它们分别是最优解的充要条件是 其中 Xs Ys为松弛变量 在线性规划问题的最优解中 若对应某一约束条件的对偶变量值为非零 则该约束条件取严格等式 另一方面 如果约束条件取严格不等式 则其对应的对偶变量一定为零 线性规划的对偶理论 证 必要性 线性规划的对偶理论 MaxZ CXs t AX XS bX XS 0 MinW Ybs t YA YS CW WS 0 XTYS 0YTXS 0 m n Y YS AT I C n A XS I b n m m X 原始问题和对偶问题变量 松弛变量的维数 线性规划的对偶理论 x1xjxnxn 1xn ixn m 对偶问题的变量对偶问题的松弛变量 原始问题的变量原始问题的松弛变量 xjym j 0yixn i 0 i 1 2 m j 1 2 n 在一对变量中 其中一个大于0 另一个一定等于0 线性规划的对偶理论 性质5的应用 该性质给出了已知一个问题最优解求另一个问题最优解的方法 即已知Y 求X 或已知X 求Y 互补松弛条件 由于变量都非负 要使求和式等于零 则必定每一分量为零 因而有下列关系 若Y 0 则Xs必为0 若X 0 则Ys必为0利用上述关系 建立对偶问题 或原问题 的约束线性方程组 方程组的解即为最优解 线性规划的对偶理论 已知线性规划 的对偶问题的最优解为Y 0 2 求原问题的最优解 解 对偶问题是 例3 7 线性规划的对偶理论 设原问题最优解为X x1 x2 x3 T 由互补松弛性定理知 X 和Y 满足 将Y 带入由方程可知 y3 y5 0 y4 1 y2 2 0 x5 0又 y4 1 0 x2 0 将x2 x5带入原问题约束方程中 得 解方程组得 x1 5 x3 1 所以原问题的最优解为 X 5 0 1 最优值z 12 线性规划的对偶理论 试用对偶原理求解线性规划问题 已知其对偶规划的最优解为 练习 线性规划的对偶理论 解 该问题的对偶规划为 线性规划的对偶理论 代入对偶规划的约束条件得 将最优解 线性规划的对偶理论 设原问题的最优解为 其中 Ys1是对应于原问题中基变量XB的剩余变量 Ys2是对应于原问题中非基变量XN的剩余变量 证明 设B是原始问题的一个可行基 于是A B N 原问题及其对偶问题可改写为 这里有Ys Ys1 Ys2 当求得原问题的一个解XB B 1b XN和Xs的检验数分别为 CN CBB 1N CBB 1 分析XN和Xs的检验数CN CBB 1N和 CBB 1与对偶问题的解之间的关系 令Y CBB 1 将其带入对偶问题的资源约束 可得 命题得证 MaxZ 40 x1 50 x2 x1 2x2 303x1 2x2 602x2 24x1 x2 0 s t y1y2y3 MinW 30y1 60y2 24y3 y1 3y2 0y3 402y1 2y2 2y3 50y1 y2 y3 0 s t MaxW 30y1 60y2 24y3 y1 3y2 0y3 y4 402y1 2y2 2y3 y5 50y1 y2 y3 y4 y5 0 s t 举例说明 线性规划的对偶理论 MaxW 30y1 60y2 24y3 0 y4 y5 M y6 y7 y1 3y2 0y3 y4 y6 402y1 2y2 2y3 y5 y7 50y1 y2 y3 y4 y5 0 s t 线性规划的对偶理论 线性规划的对偶理论 线性规划的对偶理论 原问题与其对偶问题的变量与解的对应关系 在单纯形表中 原问题的松弛变量对应对偶问题的变量 对偶问题的剩余变量对应原问题的变量 线性规划的对偶理论 原问题最优表 对偶问题最优表 对偶规划可以用线性规划的单纯形法求解 由对偶原理可见 原问题与对偶问题之间有紧密联系 因此我们能够通过求解原问题来找出对偶问题的解 反之依然 互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解 对偶问题解的求法 线性规划的对偶理论 思考题 判断下列结论是否正确 如果不正确 应该怎样改正 1 任何