第二章 对偶理论与灵敏度分析---课件.ppt

Chapter2线性规划的对偶理论和灵敏度分析 上海工程技术大学 管理学院 本章重点 1 掌握写出对偶问题的方法 原问题与其对偶问题的对应关系2 掌握对偶问题的基本理论和性质3 理解影子价格的定义和意义4 理解并掌握对偶单纯形方法的思想和步骤5 掌握线性规划灵敏度分析 1 资源数量bi发生变化的分析 2 目标函数中价值系数cj发生变化的分析 难点 难点 了解 单纯形的矩阵描述 XS为松弛变量 单纯性法计算时 总选取单位矩阵I为初始基 对应基变量为XS 设迭代若干步后 基变量变为XB XB在初始单纯性表中的系数矩阵为B 则该步的单纯性表中由XB系数组成的矩阵为单位矩阵I 对应XS的系数矩阵在新表中应为B 1 Y CBB 1称为单纯性乘子 对偶变量 2 3对偶问题提出 例2 2 某公司在计划期内要安排生产I II两种产品 已知生产单位产品所需的设备台时及AB两种原材料的消耗如表所示 该工厂每生产一件产品I可获利2元 每生产一件产品II可获利3元 问应该如何安排计划使该工厂获利最多 举例2 Chapter2灵敏度分析 先根据图表来列出模型MaxZ 2X1 3X2X1 2X2 84X1 164X2 12X1 X2 0 举例 设用y1 y2 y3分别表示出租单位设备台时的租金和出让单位原材料A B的附加额 现在从另一个角度来考虑企业的决策问题 假如企业自己不生产产品 而将现有的资源转让或出租给其它企业 那么资源的转让价格是多少才合理 合理的价格应是对方用最少的资金购买本企业的全部资源 而本企业所获得的利润不应低于自己用于生产时所获得的利润 这一决策问题可用下列线性规划数学模型来表示 他在做定价决策时 作如下比较 若用一个单位设备台时和4个单位原材料A可以生产一件产品I 可获利2元 那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润 这就有y1 4y2 2 同理将生产每件产品II的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品II的利润 这就有2y1 4y3 3把工厂所有设备台时和资源都出租和出让 其收入为f 8y1 16y2 12y3 从工厂决策者的角度来看 f当然是越大越好 但从接受者眼光来说f是越少越好 所以工厂决策者只可以在满足 所有产品的利润条件下 使其总收入尽可能的小 因此 我们称这个线性规划问题为线性规划问题 这称为原问题 的对偶问题 各模型中有关数据的 位置 示意图如下 矩阵A 矩阵AT 对偶问题提出 例2 3某工厂拥有A B C三种类型的设备 生产甲 乙两种产品 每件产品在生产中需要占用的设备机时数 每件产品可以获得的利润以及三种设备可利用的时数如下表所示 求获最大利润的方案 表2 3 不难得出下面一对对偶问题 原问题 对偶问题 不少于甲产品的利润 不少于乙产品的利润 例2 4 资源利用问题考虑 资源拥有者为了实现一定的收入目标 将其所拥有的资源出售 给每一种资源如何定价 解 表示出售单位数量的第i种资源的价格 资源拥有者在做出售资源的决策时 考虑出售资源的收入不应该低于生产所获得的收入 则有 如果资源拥有者将所有资源出售 则他得到的总收入f 资源拥有者出售每一种资源的最低估价 可通过求解线性规划问题而得到 对同一个资源利用问题 从不同的角度考虑 可以得到两个相互联系的线性规划模型 这就是线性规划的对偶问题 由上面的例子我们可以知道原问题与对偶问题的关系1 线性规划问题是对称形式Maxz CXMinf Ybs t Ax bs t YA cx 0y 0 Max Min 原问题与对偶问题的关系 列向量 行向量 n个变量 n个约束 例2 5写出下述问题的对偶问题 解 上述问题的对偶问题为 1 若一个模型为目标求 极大 约束为 小于等于 的不等式 则它的对偶模型为目标求 极小 约束是 大于等于 的不等式 即 max 和 min 相对应 如上面例题所示一对对称形式的对偶规划之间具有下面的对应关系 2 从约束系数矩阵看 一个模型中为 则另一个模型中为AT 一个模型是m个约束 n个变量 则它的对偶模型为n个约束 m个变量 3 从数据b C的位置看 在两个规划模型中 b和C的位置对换 4 两个规划模型中的变量皆非负 补充例子 原问题 对偶问题 Chapter2灵敏度分析 2 线性规划问题是非对称形式对于非对称形式的规划 可以按照下面的对应关系直接给出其对偶规划 1 将模型统一为 max 或 min 的形式 对于其中的等式约束按下面 2 3 中的方法处理 2 若原规划的某个约束条件为等式约束 则在对偶规划中与此约束对应的那个变量取值没有非负限制 3 若原规划的某个变量的值没有非负限制 则在对偶问题中与此变量对应的那个约束为等式 综上所述 线性规划的原问题和对偶问题的关系 其变换形式归纳为表2 5 下面我们以一个例子说明上述关系 写出下述线性规划问题的对偶问题 为了写出对偶问题 思路是先将其转化为对称形式 为此 1 约束条件 1a 两端同乘以 1 2 约束条件 3a 变换为和 3 令 4 则线性规划变换成如下的对称形式 令对应上述4个约束的对偶变量分别为写出对偶问题 再令将 3b 和 4b 合并 2b 两端同乘以 1 于是有 例2 6写出下述线性规划问题的对偶问题 补充例题 写出下述线性规划问题的对偶问题 解 对偶问题为 小练习 写出下列问题的对偶问题 作业 2 1 1 2 3 2 4对偶问题的基本性质 性质1 对称性对偶问题的对偶是原问题 P D MaxZ CXMinf Ybs t AX bs t YA CX 0Y 0 Max Min 证 因为X Y 是可行解 故有AX b X 0及Y A C Y 0 将不等式AX b 两边左乘Y 得Y AX Y b 再将不等式Y A C两边右乘X 得CX Y AX 故CX Y AX Y b 这一性质说明了两个线性规划互为对偶时 求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值 不能理解为原问题的目标值不超过对偶问题的目标值 性质2 弱对偶性设X Y 分别为LP max 与DP min 的可行解 则 由这个性质可得到下面几个结论 1 LP 的任一可行解的目标值是 DP 的最优值下界 DP 的任一可行解的目标是 LP 的最优值的上界 2 在互为对偶的两个问题中 若一个问题可行且具有无界解 则另一个问题无可行解 3 若原问题可行且另一个问题不可行 则原问题具有无界解 性质3 最优准则定理设X 与Y 分别是 LP 与 DP 的可行解 则当X Y 是 LP 与 DP 的最优解当且仅当CX Y b 证 若X Y 为最优解 B为 LP 的最优基 则有Y CBB 1 并且 当CX Y b时 由性质1 对任意可行解有 即Y b是 DP 中任一可行解的目标值的下界 CX 是 LP 中任一可行解的目标值的上界 从而X Y 是最优解 性质4 线性规划的对偶原理 1 若原问题有最优解 那么对偶问题也有最优解 而且二者最优值相等 强对偶性 2 若原问题 对偶问题 的解为无界解 则其对偶问题 原问题 无可行解 无界性 注 这个问题的性质不存在逆 看后面例子 证 1 设 LP 有最优解X0 那么对于最优基B必有C CBB 1A 0与 CBB 1 0 即有Y A C与Y 0 这里Y CBB 1 从而Y 是可行解 对目标函数有 由性质3知Y 是最优解 2 由弱对偶性 显然得 注 这个问题的性质不存在逆 例如下述一对问题两者皆无可行解 原问题 对偶问题 对偶问题 原问题 minw x1 x2maxz y1 y2x1 x2 1y1 y2 1 x1 x2 1 y1 y2 1x1 x2 0y1 y2 0 由性质4还可推出另一结论 若 LP 与 DP 都有可行解 则两者都有最优解 若一个问题无最优解 则另一问题也无最优解 性质5 互补松弛定理设X0 Y0分别为 LP 与 DP 的可行解 XS和YS分别是 LP 与 DP 对应的松弛变量向量 则X0和Y0是最优解当且仅当 YSX0 0和Y0XS 0 证 设X 和Y 是最优解 由性质3 CX0 Y0b 由于XS和YS是松弛变量 则有 AX0 XS bY0A YS C 将第一式左乘Y0 第二式右乘X0得 Y0AX0 Y0XS Y0bY0AX0 YSX0 CX0 显然有 Y0XS YSX0 又因为Y Xs Ys X 0 所以有 Y XS 0和YSX 0 成立 反之 当Y XS 0和YSX 0时 有 Y AX Y bY AX CX 显然有Y0b CX 由性质3知X 与Y 是 LP 与 DP 的最优解 证毕 性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法 即已知Y 求X 或已知X 求Y Y XS 0和YSX 0 两式称为互补松弛条件 将互补松弛条件写成下式 由于变量都非负 要使求和式等于零 则必定每一分量为零 因而有下列关系 其中 1 当yi 0时 反之当时yi 0 利用上述关系 建立对偶问题 或原问题 的约束线性方程组 方程组的解即为最优解 性质5的结论和证明都是假定 P 与 D 为对称形式 事实上对于非对称形式 性质5的结论仍然有效 注 上述针对对称形式证明的对偶问题的性质 同样适应于非对称形式 补充例题 已知线性规划 的最优解是求对偶问题的最优解 解 对偶问题是 下面举例说明互补松弛条件的应用 解此线性方程组得y1 1 y2 1 从而对偶问题的最优解为Y 1 1 最优值w 26 因为X1 0 X2 0 所以对偶问题的第一 二个约束的松弛变量等于零 即 性质6 假设原问题是 maxz CX AX Xs b X 0它的对偶问题是 minf Yb YA Ys C Y 0则原问题单纯形表的检验数行对应其对偶问题的一个基解 其对应关系见如下表 这里是对应于原问题中基变量XB剩余变量 是对应于原问题中非基变量XN剩余变量 对于这六个对偶性质 这些性质是研究原问题与对偶问题解的对应关系 下表也许对您了解这些性质有帮助 例2 7 判断下例说法是否正确 为什么 A如果线性规划的原问题存在可行解 则其对偶问题也一定存在可行解B如果线性规划的对偶问题无可行解 则原问题也一定无可行解 C在互为对偶的一对原问题和对偶问题中 不管原问题是求极大或者极小 原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值 解 A不对 因为原问题为无界解时 它当然有可行解 其对偶问题无可行解 B此句为A的逆否命题 所以也不对 C不对 因为哪个问题是原问题 哪个问题是对偶问题是相对而言的 例2 8已知线性规划问题 试用对偶理论证明上述线性规划问题有无界解 即有可行解但无最优解 证明 所给问题的对偶问题为 显然约束条件中与矛盾 即此对偶问题无可行解 因此所给原问题无最优解 它只可以是无界解或者无可行解 然而X 0 0 0 显然是它的可行解 因此它必定有无界解 补充例题 给出线性规划 1 写出对偶问题 2 用对偶理论证明上述线性规划目标函数值无界 解 1 对偶问题为 上述对偶问题中 则 与对偶问题的第一个约束条件矛盾 所以对偶问题无可行解 因而原问题无最优解 它只可以是无界解或者无可行解 然而x 10 4 2 显然是他的可行解 因而它必定有无界解 例2 9已知线性规划问题 已知其对偶问题的最优解为试用对偶理论找出原问题的最优解 解 先写出它的对偶问题 将的值代入约束条件 得到 2 3 4 为严格不等式 由互补松弛性得到因为 原问题的两个约束条件的松弛变量由互补松弛性得到为0 因此两个约束条件应该取等式 所以有 求解后得到所以原问题的最优解为X 1 0 0 0 1 T 补充例题 已知原问题的最优解为X 0 0 4 Z 12 试求对偶问题的最优解 解 对偶问题为 将X 0 0 4 代入原问题中 有下式 Chapter2灵敏度分析 所以 根据互补松弛条件 必有y 1 y 2 0 代入对偶问题约束 3 式 y3 3 因此 对偶问题的最优解为Y 0 0 3 W 12 因为原问题和对偶问题的最优值相等 将线性规划的目标函数表达成资源的函数 故有 即yi是第i种资源的变化率 称yi是第i种资源的边际价格 说明当其它资源供应量bk k i 不变时 bi增加一个单位时目标值Z增加yi个单位 2 5影子价格 影子价格 Shadowprice 原始线性规划问题考虑的是充分利用现有资源 以产品的数量和单位产品的收益来决定企业的总收益 没有考虑到资源的价格 但实际在构成产品的收益中 不同的资源对收益的贡献也不同 它是企业生产过程中一种隐含的潜在价值 经济学中称为影子价格 即对偶问题中的决策变量yi的值 对偶变量yi就是第i个约束的影子价格 边际价格 Chapter2灵敏度分析 影子价格是一个向量 它的分量表示最优目标值随相应资源数量变化的变化率 若x y 分别为 LP 和 DP 的最优解 那么 cTx bTy 根据f bTy b1y1 b2y2 bmym 可知 f bi yi yi 表示bi变化1个单位对目标f产生的影响 称yi 为bi的影子价格 注意 若B是最优基 y CBB 1为影子价格向量 Chapter2灵敏度分析 影子价格的经济含义 1 影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格 对资源的使用有两种考虑 第一 是否将设备用于外加工或出租 若租费高于某设备的影子价格 可考虑出租该设备 否则不宜出租 第二 是否将投资用于购买设备 以扩大生产能力 若市价低于某设备的影子价格 可考虑买进该设备 否则不宜买进 Chapter2灵敏度分析 2 影子价格表明资源增加对总效益产生的影响 根据推论 设x0和y0分别为原规划 P 和对偶规划 D 的可行解 当cx0 bTy0时 x0 y0分别是两个问题的最优解 可知 在最优解的情况下 有关系因此 可以将z 看作是bi i 1 2 m的函数 对bi求偏导数可得到这说明 如果右端常数增加一个单位 则目标函数值的增量将是 Chapter2灵敏度分析 3 根据对偶问题的互补松弛性质中时 当时 这表明生产过程中如果某种资源未得到充分利用时 该种资源的影子价格为零 又当资源的影子价格不为零时 表明该种资源在生产中已耗费完毕 4 影子价格是企业生产过程中资源的一种隐含的潜在价值 表明单位资源的贡献 与市场价格是不同的两个概念 同一种资源在不同的企业 生产不同的产品或在不同时期影子价格都不一样 例如 某种钢板市场价格是每吨8000元 一个企业用来生产汽车 另一个企业用来生产空调外壳 每吨钢板的产值是不一样的 5 影子价格是一个变量 由的含义知影子价格是一种边际产出 与bi的基数有关 在最优基B不变的条件下yi不变 当某种资源增加或减少后 最优基B可能发生了变化 这时yi的值也随之发生变化 根据对偶问题的性质 因为 当 即有 即其对偶问题的解为可行解 由此对偶问题和原问题均为最优解 反之 如果存在一个对偶问题的可行基B 即对这时只要有即原问题的解也为可行解 即两者均为最优解 否则 保持对偶可行性 进行迭代 2 6对偶单纯形法 设原问题是 记为LP 对偶问题是 记为DP 对偶单纯形法的条件是 初始表中对偶问题可行 即极大化问题时 极小化问题时 对偶单纯形法的基本思想是 从原规划的一个基本解出发 此基本解不一定可行 但它对应着一个对偶可行解 检验数非正 所以也可以说是从一个对偶可行解出发 然后检验原规划的基本解是否可行 即是否有负的分量 如果有小于零的分量 则进行迭代 求另一个基本解 此基本解对应着另一个对偶可行解 检验数非正 如果得到的基本解的分量皆非负则该基本解为最优解 Chapter2 对偶单纯形法在什么情况下使用 应用前提 有一个基 其对应的基满足 单纯形表的检验数行全部非正 对偶可行 变量取值可有负数 非可行解 注 通过矩阵行变换运算 使所有相应变量取值均为非负数即得到最优单纯形表 这样的优点在于 一是当问题的模型中存在 的约束条件时 不需要引入人工变量 只要在约束条件方程的两边乘以 1 后加入松弛变量 再按单纯形法求解 二是当约束条件方程个数m大于变量个数n的时候 将原问题变换成对偶问题求解 计算量一般会小些 Chapter2 对偶单纯形法求解线性规划问题步骤 1 建立初始对偶单纯形表 对应一个基本解 所有检验数均非正 转2 2 若b 0 则得到最优解 停止 否则 若有bi 0 3 换出变量 设min bi bi 0 bk 则选k行的基变量为换出变量 4 若所有akj 0 j 1 2 n 则原问题无可行解 停止 否则 若有akj 0则选 min j akj akj 0 r akr那么xr为换入变量 转5 5 以akr 为主元 作矩阵行变换使其变为1 该列其他元变为0 旋转变换 转2 例2 10求线性规划 解 引入松弛变量将上述问题转化为 得对偶单纯形表2 7 表2 7 此时基本解为X 0 0 0 0 2 3 不可行 转第二步 因为min 2 3 3 所以x6为换出变量 又因为Min 2 2 5 1 1 所以x1为换入变量 得到新的单纯形表2 8 表2 8 此时基本解为X 3 2 0 0 0 1 2 0 不可行 转第二步 因为 1 2 0 所以x5为换出变量 又因为Min 4 5 2 4 5 2 9 5 2 1 1 2 8 5 所以x2和x3都可以作为换入变量 任选其中一个x2 做线性变换得到新的单纯形表2 9 表2 9 得到一个基本解为X 8 5 1 5 0 0 0 0 T 因解是可行的 所以满足最优检验下的基本可行解因而也是最优解 Chapter2 从以上求解过程中我们可以看到 对偶单纯形法有以下的优点 1 初始解可以是非可行解 当检验数都为负数时 就可以进行基的变换 这时不需要加入人工变量 因此可以简化计算 2 当变量多于约束条件 对于这样的线性规划问题 用对偶单纯形法计算可以减少计算工作量 因此对于变量较少 而约束条件很多的线性规划问题 可以首先将它变换成为对偶问题 然后用对偶单纯形法来求解 3 在灵敏度分析中 有时需要使用对偶单纯形法 这样可以使问题处理简化 对偶单纯形法的局限在于 对于大多数的线性规划问题 很难找到一个初始可行基 因而这个方法在求解线性规划问题时很少单独应用 从几何图形上看单纯性和对偶单纯性的区别已知Q2为最优解点 B C 单纯形法 OQ1O2或OQ4O3O2对偶单纯性法 ABQ2或BQ2注意 对偶单纯形对迭代点的要求 对偶可行性 1 用对偶单纯形法求解线性规划是一种求解方法 而不是去求对偶问题的最优解 2 初始表中一定要满足对偶问题可行 也就是说检验数满足最优判别准则 3 对偶单纯形法与普通单纯形法的换基顺序不一样 普通单纯形法是先确定进基变量后确定出基变量 对偶单纯形法是先确定出基变量后确定进基变量 4 对偶单纯形法在确定出基变量时 若不遵循规则 任选一个小于零的bi对应的基变量出基 不影响计算结果 只是迭代次数可能不一样 应当注意 2 7灵敏度分析 系数br cj变化 最优解的最优性 可行性是否变化 系数在什么范围内变化 最优解或最优性不变 如何求新的最优解 例2 2 1 求解此线性规划的解2 当C2 2时 新的线性规划问题的解3 当C2 5时 新的线性规划问题的解4 当b1 9时 新的线性规划问题的解5 当b1 12时 新的线性规划问题的解 灵敏度分 SensitivityAnalyisi 就是分析研究LP模型参数aij br cj的取值变化对最优解和最优基的影响 它在应用线性规划解决实际问题的过程中是非常有用的 实际LP问题的最优解 是在模型参数区某一组定值的基础上获得的 而这些定值往往是一些预测和估计的数字 因此或者有一定的误差 或者可能变动 如市场条件出现了变动 cj的值就会发生变化 aij是随着工艺技术条件的改变而改变的 而br值则是根据资源投入后能产出多大经济效果来决定的一种决策选择 因此就会产生以下问题 当这些参数中的一个或几个发生了变化时 问题的最优解会有什么变化 或者这些参数在一个多大的范围内变化时 问题的最优解不变 这就是我们学习灵敏度分析所要研究解决的问题 当然通过上面的学习我们知道 当线性规划问题中的一个或者几个参数变化时 可以用单纯形法从头计算 看最优解有无变化 但是这样做既麻烦又没有必要 因为我们知道单纯形法的迭代运算是从一组基向量变换为另一组基向量 表中每步迭代得到的数字只随基向量的不同选择而改变 因此有可能把个别参数的变化直接在计算得到最优解的单纯形表上面反映出来 这样就不需要从头计算了 而直接对计算得到的最优解的单纯形表进行审查 看一些数字变化后 是否满足最优解的条件 如果不满足的话 再从这个表开始进行迭代计算 求出最优解 Chapter2灵敏度分析 灵敏度分析的步骤可以归纳如下 1 将参数的改变计算反映到最终单纯形表上来 具体的计算方法是 按照相关公式计算出由参数的变化而引起的最终单纯形表上有关数字的变化 2 检查原问题是否仍为可行解 3 检查对偶问题是否仍为可行解 4 我们可以按照书中表中罗列的几种情况得出结论和决定继续计算的步骤 Chapter2灵敏度分析 2 7 1资源数量br发生变化的分析资源数量变化是指系数br发生了变化 br变化为br br br 并假设规划问题的其它系数都没有发生变化 根据讨论 最优解的基变量xB B 1b 这样使得最终表中原问题的解相应的变化为XB B 1 b b 其中 b 0 br 0 0 T 1 资源系数br的灵敏度变化分析 根据讨论 只要保持B 1 b b 0 最终表中检验数不变 则最优基不变 但最优解的值变化 XB B 1 b b 为新的最优解 否则 需要利用对偶单纯形法继续计算 为了使最优基B不变 求br的变化范围 B 1的第r列 这个时候在最终表里面求得的b列的所有元素i 1 2 m 由此可得由此可得 最优基不变 检验数不变 的条件是 例题 问题 某公司在计划期内要安排生产I II两种产品 已知生产单位产品所需的设备台时及AB两种原材料的消耗如表所示 该工厂每生产一件产品I可获利2元 每生产一件产品II可获利3元 问应该如何安排计划使该工厂获利最多 Chapter2灵敏度分析 Chapter2灵敏度分析 最终单纯形表为 若该厂又从别处抽出4台时用于生产I II 求这时该厂生产产品I II的最优方案 这里各列分别对应b1 b2 b3的单一变化下面给出最优基不变时 b1的变化范围 B x1x5x2 可得 b1 2 0 5 4 b1 4 2 2由公式知 b1变化范围 4 2 显然b1变化范围 4 10 因此 当 b1 4时 最优基发生变化 需要用对偶单纯形法继续求解 解 先计算B 1 b 将这个结果放到最终表中得 表中b列中有负数 故可用对偶单纯形法求最优解 最优解见下表 即该厂最优生产方案应改为生产产品I为4件 生产产品II为3件 获利17元 从最优表中看出x3 2 即设备有2小时未被利用 2 7 2价值系数cj的变化分析当目标系数cj变化时 可能引起检验数的变化 从而影响最优性条件是否满足 为了方便起见 分别就对应的是非基变量与基变量两中情况