对偶理论及灵敏度分析

对偶理论及灵敏度分析 一 基本要求1 了解对偶问题的特点 熟悉互为对偶问题之间的关系2 掌握对偶理论及其性质3 掌握对偶单纯形法4 掌握限制常数和价值系数 约束条件系数的变化对原最优解的影响5 掌握增加新变量和增加新约束条件对原最优解的影响 并求出相应因素灵敏度的范围6 了解影子价格的经济意义 二 重点1 对偶单纯形法2 灵敏度分析 三 难点灵敏度分析 对偶理论对偶单纯形方法灵敏度分析 对偶理论及灵敏度分析 对偶理论 对偶问题概念 任何一个线性规划问题都有一个伴生的线性规划问题 称为其 对偶 问题 对偶问题是对原问题从另一角度进行的描述 其最优解与原问题的最优解有着密切的联系 在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解 反之亦然 对偶理论就是研究线性规划及其对偶问题的理论 是线性规划理论的重要内容之一 问题的导出 问题的导出 假设有客户提出要求 购买工厂所拥有的工时和材料 为客户加工别的产品 由客户支付工时费和材料费 那么工厂给工时和材料制订的最低价格应是多少 才值得出售工时和材料 问题的导出 出卖资源获利应不少于生产产品的获利 约束价格应该尽量低 这样 才能有竞争力 目标价格应该是非负的 问题的导出 用y1和y2分别表示工时和材料的出售价格 总利润最小minW 3y1 9y2保证A产品利润y1 y2 2保证B产品利润y1 4y2 3保证C产品利润y1 7y2 3售价非负y1 0y2 0 问题的导出 问题的导出 对偶问题的定义 对称形式的对偶问题 对偶问题的定义 对称形式的对偶问题 或 对偶问题的定义 对偶问题的特点 若原问题目标是求极大化 则对偶问题的目标是极小化 反之亦然原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵极大化问题的每个约束对应于极小化问题的一个变量 其每个变量对应于对偶问题的一个约束 对偶问题的定义 非对称形式对偶问题的处理等式约束的线性规划问题如下 1 先将等式约束条件分解为两个不等式约束条件 对偶问题的定义 2 按对称形式变换关系写出它的对偶问题 整理得 对偶问题的定义 由此可见 yi不受正负限制 将yi代入上述线性规划问题 得到对偶问题为 对偶问题的定义 一般线性规划问题的对偶问题 对偶问题的定义 一般线性规划问题的对偶问题可归纳如下对应关系 对偶问题的写出 例1标准型对偶问题 对偶问题的写出 例2 例max 2x1 x2 3x3 x4s t x1 x2 x3 x4 52x1 x2 3x3 4x1 x3 x4 1x1 0 x2 x4无约束 x3 0 min 5y1 4y2 y3s t y1 2y2 y3 2y1 y2 1y1 3y2 y3 3y1 y3 1y1 0 y2无约束 y3 0 其对偶问题为 对偶问题的写出 练习写出对偶问题 max x1 x2 5x3 7x4s t x1 3x2 2x3 x4 252x1 7x3 2x4 602x1 2x2 4x3 30 x4 10 x4 5x1 x2 0 x3 x4无约束 练习 max x1 x2 5x3 7x4s t x1 3x2 2x3 x4 252x1 7x3 2x4 602x1 2x2 4x3 30 x4 10 x4 5x1 x2 0 x3 x4无约束 对偶问题的基本性质 1 对称性 对偶问题的对偶问题是原问题 P D 对偶问题的基本性质 2 弱对偶性若互为对偶的线性规划分别有可行解则其相应的目标函数值满足 对偶问题的基本性质 3 无界性若原问题 对偶问题 为无界解 则其对偶问题 原问题 无可行解 对偶问题的基本性质 4 最优性准则定理若X和Y分别是互为对偶的线性规划的可行解 且使CX Yb 则X和Y分别是相应线性规划问题的最优解 对偶问题的基本性质 5 对偶定理若原问题有最优解 那么对偶问题也有最优解 且此时目标函数值相等 证明 设是原问题的最优解 它对应的基矩阵为B 则必定所有检验数 令 则 即是对偶问题的可行解所以对偶问题的目标值 而是原问题的最优解 其目标函数取值为 由最优性准则定理知 是对偶问题的最优解 6 互补松驰性 松紧定理 若 分别是 P D 问题的可行解 那么 为最优解的充要条件是 XS 0 YS 0 即若Ai i 0Ai bi0 Pj Cj0 Pj Cj j 0 对偶问题的基本性质 XS 0 YS 0 原问题第i个约束方程是等式约束 若原问题第i个约束方程是不等式约束 例1 已知下列线性规划问题max x1 2x2 3x3 4x4s t x1 2x2 2x3 3x4 202x1 x2 3x3 2x4 20 xj 0 j 1 2 3 4已知其对偶问题的最优解为y1 1 2 y2 0 2运用对偶理论找出原问题的最优解 解 其对偶问题为min 20y1 20y2s t y1 2y2 12y1 y2 22y1 3y2 33y1 2y2 4y1 y2 0 1 2 0 2 y1 互补松驰性 松紧定理 已知对偶问题的最优解y1 1 2 y2 0 2 因y1 0 y2 0 所以x5 x6 0 即原问题为等式约束 互补松驰性 松紧定理 将y1 1 2 y2 0 2代入对偶问题的约束条件 得y3 0 y4 0 所以x1 x2 0 min 20y1 20y2s t y1 2y2 y3 12y1 y2 y4 22y1 3y2 y5 33y1 2y2 y6 4y1 y2 0 互补松驰性 松紧定理 x1 x2 0 x1 2x2 2x3 3x4 202x1 x2 3x3 2x4 20 即x1 x2 0 x3 4 x4 4 原问题的最优解为 0 0 4 4 T max x1 2x2 3x3 4x4s t x1 2x2 2x3 3x4 202x1 x2 3x3 2x4 20 xj 0 j 1 2 3 4 互补松驰性 松紧定理 7 原问题单纯形表的检验数行对应其对偶问题的一个基解 对偶问题的基解 YS1为对应原问题中基变量XB的剩余变量 YS2是对应原问题中非基变量XN的剩余变量 对偶问题的基解 例 max x1 4x2 3x3s t 2x1 2x2 x3 4x1 2x2 2x3 6xj 0 对偶问题为min 4y1 6y2s t 2y1 y2 12y1 2y2 4y1 2y2 3y1 y2 0 对偶问题的基解 对偶问题的基本解为y1 0 y2 0 ys1 1 ys2 4 ys3 3 对偶问题的基解 X4X5 由原问题的最终表可知 y1 1 y2 1 最优解 ys1 2 ys2 0 ys3 0 其最终表为 对偶问题的基解 X2X3 在单纯形法的每步迭代中 目标函数取值z CBB 1b 和检验数CN CBB 1N中都有乘子Y CBB 1 那么Y的经济意义是什么 设B是 maxz CX AX b X 0 的最优基 则z CBB 1b Y b 对z求偏导数 得 影子价格 变量yi 的经济意义是在其他条件不变的情况下 单位资源变化所引起的目标函数的最优值的变化 yi 的值代表对第i种资源的估价 影子价格 这种估价是针对具体工厂的具体产品而存在的一种特殊价格 称它为 影子价格 影子价格随具体情况而异 在完全市场经济的条件下 当某种资源的市场价低于影子价格时 企业应买进该资源用于扩大生产 而当某种资源的市场价高于企业影子价格时 则企业的决策者应把已有资源卖掉 可见影子价格对市场有调节作用 影子价格 从原始问题最优表求影子价格 当B是原问题的最优基时 Y CBB 1就是影子价格向量 初始表 最优表 影子价格 y1 5 3 y2 1 3即工时的影子价格为5 3 材料的影子价格为1 3 如果目前市场上材料的价格低于1 3 则企业可以购进材料来扩大生产 反之可以卖掉部分材料 如果有客户以高于5 3的价格购买工时 则可以出售一些工时 对偶单纯形法 对偶单纯形法并不是求解对偶问题解的方法 而是利用对偶理论求解原问题的解的方法 根据对偶问题的对称性 单纯形表的迭代过程也可以反过来进行 即保持对偶问题的解始终是基本可行解 即C CBB 1A 0 而使原问题从基本非可行解迭代到基本可行解 从而使原问题和对偶问题同时得到最优解 这种单纯形表的应用方法称之为对偶单纯形法 对偶单纯形法的计算步骤如下 1 根据线性规划问题 列出初始单纯形表 检查b列的数字 若都为非负 检验数都为非正 则已得到最优解 停止计算 若检查b列的数字时 至少还有一个负分量 检验数保持非正 那么进行以下计算 2 确定换出变量按min B 1b i B 1b i 0 B 1b l对应的基变量xl为换出变量 对偶单纯形法 3 确定换入变量在单纯形表中检查xl所在行的各系数 lj j 1 2 n 若所有 lj 0 则无可行解 停止计算 若存在 lj 0 j 1 2 n 计算 按 规则所对应的列的非基变量xk为换入变量 这样才能保持得到的对偶问题解仍为可行解 4 以 lk为主元素 按原单纯形法在表中进行迭代运算 得到新的计算表 重复步骤 1 4 对偶单纯形法 对偶单纯形法举例 例用对偶单纯形法求解 对偶单纯形法举例 对偶单纯形法举例 最优解为y1 5 3 y2 1 3 最优值Z 8 Wmin 8 对偶单纯形法在什么情况下使用 应用前提 有一个基 其对应的基满足 单纯形表的检验数行全部非正 对偶可行 变量取值可有负数 非可行解 注 通过矩阵行变换运算 使所有相应变量取值均为非负数即得到最优单纯形表 对偶单纯形法 例 min 3x1 4x2 5x3s t x1 2x2 3x3 52x1 2x2 x3 6x1 x2 x3 0 解 问题化为maxW 3x1 4x2 5x3s t x1 2x2 3x3 x4 5 2x1 2x2 x3 x5 6x1 x2 x3 x4 x5 0 对偶单纯形法练习 所以最优解为x1 1 x2 2 x3 0 min 11 对偶单纯形法练习 xj 对偶单纯形法的适用范围 适合于解如下形式的线性规划问题 在引入剩余变量化为标准型之后 约束等式两侧同乘 1 能够立即得到检验数全部非正的原规划基本解 可以直接建立初始对偶单纯形表进行求解 非常方便 对于有些线性规划模型 如果在开始求解时不能很快使所有检验数非正 最好还是采用单纯形法求解 因为 这样可以免去为使检验数全部非正而作的许多工作 从这个意义上看 可以说 对偶单纯形法是单纯形法的一个补充 除此之外 在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法 可以简化计算 灵敏度分析 在生产计划线性规划问题的一般形式中 A代表企业的技术状况 b代表企业的资源状况 C代表企业产品的市场状况在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定 在实际生产过程中 上述三类因素均是在不断变化的 如果按照初始的状况制订了最佳的生产计划 而在计划实施前或实施中上述状况发生了改变 则决策者所关心的是目前所执行的计划还是不是最优 如果不是 则最优解如何变化 这就是灵敏度分析 如果不是 应该如何修订原来的最优计划 更进一步 为了防止在各类状况发生时 来不及随时对其变化作出反应 即所谓 计划不如变化快 企业应当预先了解 当各项因素变化时 应当作出什么样的反应 灵敏度分析 灵敏度分析 当系数A b C发生改变时 目前最优基是否还最优 目前的最优解是否还最优 为保持目前最优基或最优解还是最优 系数A b C的允许变化范围是什么 假设每次只有一种系数变化 目标函数系数C变化a 基变量系数发生变化 b 非基变量系数发生变化 右端常数b变化 技术系数A发生变化a 增加一个变量b 增加一个约束 灵敏度分析 若B是最优基 则最优表形式如下 灵敏度分析总是在最优表上进行 灵敏度分析 例线性规划 灵敏度分析 例线性规划 灵敏度分析 例线性规划 3 2 1 3 2 1 当aij bi cj中的一个或几个发生变化时 已求得的线性规划问题的最优解会有什么变化 如何求解新的最优解 价值系数C的改变 a 价值系数CN 非基变量的价值系数 发生改变 C3 C3 4 如果C3 4 则目前解不再是最优解 应该用单纯形方法继续求解 否则解不变 即对于C3而言 使最优解不变的条件是C3 4 价值系数C的改变 价值系数CN发生改变 5 价值系数C的改变 b 价值系数CB 基变量的价值系数 发生改变 C1 3 1 4 3C1 1 3C1 1 C1 3 0 1 4 3C1 0 1 3C1 1 0 C1 3若C1 3 4则x4进基 x1出基若3 C1则x3或x5进基 x2出基 价值系数C的改变 价值系数CB发生改变 1 2 1 2 价值系数C的改变 价值系数CB发生改变 资源数量b变化的分析 右端常数b1的改变范围 b1 4b1 3 3 3 b1 3 9 4 b1 9 3 5b1 3 资源数量b变化的分析 右端常数b1发生改变 2 资源数量b变化的分析 右端常数b1发生改变 12 例 线性规划问题max x2 3x3 2x5s t x1 3x2 x3 2x5 7 2x2 4x3 x4 12 4x2 3x3 8x5 x6 10 xj 0 资源数量b变化的分析 B P2 P3 P6 要使最优基不变 求b2的变动范围 要保持最优基不变 则 14 3 b2 34 若b2超出此范围 则b 0可用对偶单纯形法继续求解 例上题中 若令b2增加 b2 30 则 将上式结果反映到最终表中 得下表 资源数量b变化的分析 求右端常数b2改变范围 b2 4 b2 3 b2 3 1 3 b2 12 b2 3 5 练习 技术系数A发生变化的分析 a 增加一个变量若企业在计划期内 有新的产品可以生产 则在知道新产品的单位利润 单件资源消耗量时 可以在最优表中补充一列 其中的前m行可以由基矩阵的逆矩阵得到 而检验数行也可以由与其它列相同的方法计算得到 若检验数非正 则原最优解仍为最优 原生产计划不变 不生产这种新产品 否则 当检验数为正时 则应以该变量进基 作单纯形迭代 从而找出新的最优解 增加一个变量 例 某工厂计划生产A B C三种产品 需要甲 乙两种资源 资源限量 每种产品的单位利润和单位产品的资源消耗量如下表所示 试确定使利润最大的生产计划 练习 解 以x1 x2 x3分别表示A B C三种产品的产量 则该问题的线性规划模型如下 max 2x1 3x2 x3s t 1 3x1 1 3x2 1 3x3 11 3x1 4 3x2 7 3x3 3x1 x2 x3 0 引入松驰变量 可得初始单纯形表 最终单纯形表为 假设这个工厂研制了一种新产品D 单位新产品D所需耗用的甲乙两种资源分别为1 2和1 2 新产品的利润为4元 问应怎样调整生产计划 max 2x1 3x2 x3s t 1 3x1 1 3x2 1 3x3 11 3x1 4 3x2 7 3x3 3x1 x2 x3 0 P6 B 1P6 技术系数A发生变化的分析 b 增加一个约束为提高产品质量 要增加一道加工工序 即会给原问题增加一个约束条件 若把目前的最优解代入新增加的约束 能满足约束条件 则说明该增加的约束对最优解不构成影响 即不影响最优生产计划的实施 若当前最优解不满足新增加的约束 则应把新的约束添到原问题的最优表内新的一行中去 用对偶单纯形方法来进行迭代 求出新的最优解 技术系数A发生变化的分析 例增加约束 将新的约束条件引入松驰变量后 写入最终单纯形表 并把XB XS的系数列向量化为单位向量 再求解 技术系数A发生变化的分析 增加约束 技术系数A发生变化的分析 c A中某列向量的变化 1 如果系数矩阵A中某一列向量Pj发生了变化 且其对应的