ch2线性规划对偶理论与灵敏度分析.ppt

第二章线性规划对偶理论与灵敏度分析 教学时数 6学时教学目的与要求 理解线性规划对偶问题理论与影子价格概念 掌握对偶单纯形法及灵敏度分析技巧教学内容 1 线性规划对偶问题及相关理论2 影子价格3 对偶单纯形法4 灵敏度分析及参数规划教学重点 影子价格及灵敏度分析教学难点 对偶理论 第二章讲授内容和知识 第一节线性规划的对偶问题 解 利用第一章的知识 设三种产品的生产量分别为x1 x2和x3 可以建立线性规划模型如下 一 对偶问题的提出 3000 假如企业不进行生产 而是把全部可利用的资源转让给其他企业 此时 企业必须考虑一个合适的资源价格 使得 1 有企业愿意接受转让 2 企业自身没有经济损失 设四种资源的价格确定为y1 y2 y3 y4 y1 y2 y3 y4 而企业自身没有经济损失的要求可做如下思考 生产一件产品 比如A 需要四种资源的量分别为3 2 1 1个单位 由于要把生产A产品的这些资源卖出去 所以 单件总卖值不应比企业自己生产时的收益 2000 低 即 3y1 2y2 y3 y4 2000对产品B 4y1 y2 3y3 2y4 4000对产品C 2y1 2y2 3y3 4y4 3000 则有企业愿意接受转让的条件是极小化资源总价 即w 600y1 400y2 300y3 200y4 原问题 对偶问题 两个线性规划问题的比较中 可以初步发现 原问题的目标函数求极大 对偶问题的目标函数求极小 原问题目标函数中的系数在对偶问题中变为约束条件的右端常数项 约束条件的不等式方向改变了 约束方程的系数矩阵发生了转置 原问题约束数目与对偶问题的变量数相等 对称形式的条件 1 变量全部具有非负约束 2 目标函数求极大值时 约束不等式符号全部为 目标函数为求极小值时 约束不等式的符号全部为 对偶问题的一般形式为 二 对称形式的原始 对偶关系 Y y1 y2 ym 说明 表2的变量行与参数行相乘组成原始问题的约束条件和目标函数 表2的变量列与参数列相乘组成对偶问题的约束条件和目标函数 600 400 300 200 2000 4000 3000 0 非对称形式是指一般情况下的线性规划问题 是目标函数求极小或求极大 约束条件 变量 0 0或者无限制的随意组合 建立非对称形式线性规划问题的对偶模型可采取以下步骤 1 通过变换 把线性规划问题化为具有对称形式的原问题 2 根据原问题 写出对偶问题 此时的对偶并非是原线性规划问题的对偶 3 通过变量代换等 把参数还原为最初的形式 必须做 三 非对称形式的原始 对偶问题 解 1 把原线性规划问题化为对称形式要求的形状 目标函数求极大 约束条件全部为 符号 变量全部非负 第一个约束条件的符号符合要求 保留不变 第二个约束条件分解为 x1 x2 x3 1和x1 x2 x3 1第一个分解式乘以 1变为 x1 x2 x3 1第三个约束条件乘以 1得 2x1 x2 x3 2 2 写出上述对称形式线性规划问题的对偶 3 还原为原来的参数符号 令u1 y1 u2 y2 y3 u3 y4 u1 u2 u3 四 原始 对偶关系一览表 解 根据表3 得出对偶线性规划问题如下 maxw 2y1 y2 4y3 st 2y1 3y2 y3 13y1 y2 y3 4y1 y3 3y1 0 y2 0 y3自由变量 课堂练习 第二节对偶问题的基本性质 本节以对称形式的原始 对偶问题为讨论的基础 除非特别需要 一般不再专门说明 一 单纯形法计算的矩阵描述 原问题通过加入松弛变量Xs可以化为标准形式 其中 I是对应于松弛变量的单位方阵 单纯形法计算时 总是选择I为初始可行基 松弛变量作为初始基变量的 由于松弛变量作为基变量意味着资源没有被利用 所以 单纯形法迭代若干步后 松弛变量会被置换出基变量集合 项目 0Xsb 非基变量 基变量 XBXN Xs BN I 检验数 CBCN 0 设新的基变量组合为XB 在初始单纯形表中的系数矩阵为B 价值系数为CB A去掉B的若干列后 剩余的列向量组成子矩阵N 对应的变量组合记为XN 价值系数记为CN CBXBb1 基变量 非基变量 XB XNXs I 检验数 N1S1 0 N S Xs XB XN x1x2 B I N I N1 S1 N S CBCN 根据上述划分 约束方程可改写为 BXB NXN IXs b XB B 1b B 1NXN B 1Xs 代入目标函数中 得 z maxz CX 0Xs CBXB CNXN 0Xs CB B 1b B 1NXN B 1Xs CNXN 0Xs CBB 1b CBB 1NXN CBB 1Xs CNXN 0Xs z0 CN CBB 1N XN 0 CBB 1 Xs 其中带白色字体的就是非基变量的检验数 z0对应于当前的目标函数值 AX IXs b CN CBB 1N 0 CBB 1 B 1b B 1N B 1 CN CBB 1N CBB 1 XB x1 x3 T XS x4 x5 T XN x2 B 1N B 1 CN CBB 1N CBB 1 如果表中的检验数满足最优性条件 即CN CBB 1N 0 CBB 1 CS CBB 1I 0 由于基变量的检验数可以写为CB CBB 1B 0 所以 上述3个式子可以重写为C CBB 1A 0 令Y CBB 1 单纯形乘子 YA CY 0 当原问题达到最优时 Y CBB 1对应于对偶问题的一个可行解 将该解代入对偶问题的目标函数 可知w Yb CBB 1b z 对偶理论将进一步说明 对偶与原始问题具有相同的最优目标函数值 XB B 1b Y CBB 1 Maxz CX CBB 1b w Yb CBB 1b 原问题的对偶变量y1y2 对偶问题的对偶变量 原问题 x1x2x3 144 9 4 994 1404 性质1 弱对偶性 如果X0 Y0分别是原始问题和对偶问题的可行解 则CX0 Y0b 证明 因为X0 Y0是可行解 它们满足约束条件和非负性限制 二 对偶问题的基本性质 AX0 bX0 0Y0A CY0 0用Y0左乘第一个不等式 X0右乘第二个不等式 得Y0AX0 Y0bY0AX0 CX0比较上面两个不等式可知 弱对偶性成立 推论 1 原问题任一可行解的目标函数值是对偶问题目标函数值的下界 反之 对偶问题任一可行解的目标函数值是原问题目标函数值的上界 2 如果原问题有可行解且目标函数值无界 无界解 则对偶问题无可行解 反之 对偶问题有可行解且目标函数值无界 则原问题无可行解 注意 本性质的逆不成立 因为当对偶不可行时 要么原问题无界 要么原问题无可行解 3 如果原问题有可行解 对偶问题无可行解 则原问题目标函数值无界 反之 对偶问题有可行解 原问题无可行解 则对偶问题的目标函数值无界 maxZ 原问题可行解 minW 对偶可行解 用途 判断线性规划问题有无最优解 因为原始和对偶问题可行解的目标函数值分别是对偶 原始的下 上界 所以 只要找到原始 对偶的可行解 就可断定原始 对偶问题有无最优解 二 对偶问题的基本性质 可以看出 原问题有可行解 比如X 1 1 1 1 T 对偶问题有可行解Y 1 1 所以 原线性规划问题有最优解 性质2 最优性 如果X0 Y0分别是原始问题和对偶问题的可行解 且有CX0 Y0b 则X0 Y0分别是原始问题和对偶问题的最优解 证明 设X Y 分别是原始问题和对偶问题的最优解 根据最优解的定义知 CX0 CX Y0b Y b 又根据弱对偶性 CX Y b 所以 CX Y0b CX0 X0是原问题的最优解 同理 CX Y b Y0b CX0 Y b 所以 Y0是对偶问题的最优解 性质3强对偶性 或对偶定理 如果原始问题和对偶问题都有可行解 则两者都有最优解 并且目标函数值相同 证明 由于两者都有可行解 根据弱对偶性的推论知 原问题目标函数值有上界 对偶问题目标函数值有下界 因此 两者都有有限的最优目标函数值 其次 用单纯形法求原问题最优解时 最优性判断条件是 检验数 0 即C CBB 1A 0 CBB 1 0令Y CBB 1 则 YA C Y 0 即 Y CBB 1是对偶问题的可行解 由于该可行解的目标函数值与原问题的目标函数值相同 由最优性可知 两者都是最优解 根据上述的对偶性质 理论 不难看出原问题和对偶问题的解存在有如下关系 性质4 互补松弛性 或松紧定理 在线性规划问题的最优解中 如果对应于某一约束条件的对偶变量值不为零 则该约束条件取严格的等式符号 反之 如果约束条件取严格不等式符号 则其对应的对偶变量一定取零值 或 如果X0 Y0分别是原始问题和对偶问题的可行解 Xs Ys分别是原问题和对偶问题的松弛变量和剩余变量 则X0 Y0为最优解的条件是YsX0 XsY0 0进一步地 YsX0 0 Y0Xs 0 证明 把可行解X0 Y0 松弛变量Xs Ys代入原问题和对偶问题的约束中 得AX0 Xs bY0A Ys C 前式左乘Y0 后式右乘X0 得Y0AX0 Y0Xs Y0bY0AX0 YsX0 CX0 Y0Xs YsX0 Y0b CX0 显然 如果X0 Y0是最优解 右端为零 互补松弛性成立 由于式中的每一个向量都是非负的 所以 它们的点积 内积 非负 而如果两个非负项相加等于零 那么 每一个非负项必须等于零 即YsX0 0 Y0Xs 0 经济意义 如果某种资源有剩余 约束为严格不等式 则它的价值为零 其对偶问题的最优解为y1 4 5 y2 3 5 试确定原问题的最优解 将对偶问题最优解代入对偶约束中可知 第2 3 4约束为严格不等式 x2 x3 x4 0 对偶问题的解大于零 所以 原问题的约束条件在最优时取等号 即x1 3x5 42x1 x5 3 X 1 0 0 0 1 T 求解后得 x1 1 x5 1 第三节影子价格 二 影子价格的特点和应用 一 影子价格的概念 定义 一 影子价格的概念 定义 从对偶问题的基本性质可以看出 当线性规划原问题求得最优解时 其对偶问题也得到了最优解 且目标函数值相同 即Z CBXB CBB 1b Y b w 由于b是线性规划原问题约束条件的右端常数项 表示企业对资源的拥有量 如果Z 是企业所创造的总收益的话 Y 就是资源在生产中作用和贡献的有效性估价 为区别于资源的市场价格 称Y 为影子价格 影子价格也叫经济价格 它有广泛的含义 一般认为 凡用各种方法计算出来的非自然形成的价格 以及由国际市场引进的价格 只要不在现实生活中发生作用 都可以称为影子价格 1 资源的市场价格是已知数 相对比较稳定 而影子价格则有赖于资源的利用情况 是未知数 企业人 财 物 技术 管理的变化 都会直接引起影子价格的变动 2 影子价格是一种边际价格 目标函数对对偶变量的偏导数表明 影子价格是在其它条件都不变化的情况下 单位资源变化所引起的目标函数最优值的变化量 二 影子价格的特点和应用 在图解法中 我们曾解决过如下问题 maxz 3x1 x2 x1 x2 1x1 x2 2 x1 x2 0 x1 x2 1 x1 x2 2 可行域 Z 3x1 x2 A 3 2 1 2 Z 5 x1 x2 1 B 1 0 Z 3 3 影子价格是一种机会成本 在纯市场经济条件下 如果第二种资源的市场价低于2 可以买进这种资源 相反 当市场价格高于影子价格2时 应该卖出库存的该种资源 因为经过企业加工后 资源不但没有升值 反而贬值了 随着资源的买进卖出 它的影子价格也在变化 一直到影子价格与市场价格相同时 才会处于平衡状态 没有投机的机会 4 影子价格反映了资源利用的状况 根据互补松弛性质 当某种资源未得到充分利用时 该资源的影子价格等于零 当资源的影子价格不等于零时 该资源在生产中已耗费完毕 5 影子价格有助于给新产品定价和确定新产品是否值得生产 各种产品在使用相同资源的情况下 新产品的定价一定要高于它的成本 反映到单纯形表里 就是要求检验数大于零 检验数的第一项是产品的价格 产值 第二项是所耗费资源的隐含成本 检验数大于零说明新产品可以投产 能为企业带来附加收益 6 影子价格能确定资源的相对重要性 有助于决策 影子价格大小指明了资源的相对重要性次序 一般来说 企业的资金是有限的 按照影子价格的大小 决策者可以方便地决定资源采购的先后顺序 7 一般来说 对线性规划问题的求解解决的是最优分配方案 而对对偶问题的求解则主要集中于资源的估价或资源是否得到合理利用问题上 8 上述分析是基于最优可行基不变的前提下展开的 如果最优可行基发生变化 则需要修正所得到的结论 第四节对偶单纯形法 一 对偶单纯形法的思路 二 对偶单纯形法的计算步骤 对偶单纯形法不是解对偶问题的 而是在单纯形表上进行对偶运算的方法 为了了解对偶单纯形法的实质 我们回顾一下单纯形法 单纯形法开始于初始基可行解 如果不满足最优性条件 则要转到能使目标函数值得到改善的邻近顶点上 在这个转换过程中 存在两个原则 一是保持原问题的解仍是可行的 另一个是要求目标函数值有改善 一 对偶单纯形法的思路 当目标函数值无法改善时 因退化出现循环的情况除外 所有的检验数都 0 求极大时 0 求极小时 检验数 0 检验数 0 意味着在获得原问题最优解的同时 也获得了对偶问题的一个可行解 因为原问题与对偶问题的解都可行 并且目标函数值相同 根据对偶理论 这个对偶可行解就是对偶问题的最优解 因此 单纯形法迭代过程的实质是 在保持原问题可行性的前提下 驱使对偶问题从不可行 起始点 中间点 转变为可行的 最优点 发展历程 把上述思想移植到对偶问题上 如果保持对偶问题的可行性 只要检验数 0即可 通过改变对偶问题的可行基 使原问题由不可行变为可行 根据对偶理论 这两个可行解就是原始和对偶问题的最优解 使用对偶单纯形法必须满足两个条件 1 单纯形表中的所有检验数必须符合最优性要求 即对偶可行 2 右端常数项列向量必须有负分量 如果原问题可行 则直接用单纯形法 1 把线性规划问题化为标准形式 找出对偶问题的初始可行基 列出单纯形表 表的格式与第一章的单纯形表完全相同 2 确定换出基的变量 这一点与单纯形法正好相反 那里是先确定换入变量 因为常数项有负分量 所以令br min bi 第i行对应的基变量xr作为换出变量 二 对偶单纯形法的计算步骤 3 确定换入基的变量 这里要注意 单纯形法确定换出变量时用的是换入变量列向量与常数项列的最小比值 对偶单纯形法确定换入变量时则用检验数行与换出变量所在行的最小比值 如果所有的arj 0 则原问题没有可行解 停止计算 如果存在arj 0 则计算最小比值 4 选择ars为主元素 把该列向量变为单位列向量 这里的旋转运算和单纯形法一样 主元素处变为1 其余变为0即可 5 重复步骤 2 4 直至原问题变为可行解为止 在标准形式里 目标函数系数满足使用对偶单纯形法的一个条件 但是 约束条件的右端常数项非负 且没有单位矩阵 为此 把约束方程两边都乘以 1 得 根据对偶单纯形法 首先选择换出变量 显然常数项列最小的元素是 2 所以第一行的基变量x4作为换出变量 换入变量的确定 第一行与检验数行对应分量比值的最小值为 最小比值 24 6 5 1 4 6是主元素 x2是换入变量 负元素是 1 3 第二行基变量x5作为换出变量 换入变量的确定 最小比值 15 5 1 2 3 4 1 3 3 2 2 3是主元素 x3是换入变量 2 3 由于原始 对偶都已经可行 对应的解是最优解 注意 具有本例题形式的线性规划问题在求最优解时 可以不使用人工变量 对偶单纯形法能使求解过程更简便 第五节灵敏度分析 一 线性规划的基本假设 灵敏度分析的概念 是指对系统或事物因周围环境条件发生变化所表现出来的敏感程度的分析 二 灵敏度分析及其步骤 2 检查原问题是否仍可行 基变量的取值是否仍全部 0 3 检查对偶问题是否仍可行 检验数行是否仍满足最优性条件 4 按下表所列情况得出结论 即决定继续计算的步骤 按与变量的对应关系划分 价值系数可分为基变量价值系数和非基变量价值系数两种 由于价值系数的变化直接影响到检验数 所以 价值系数变化的结果只有两个 原始 对偶问题均可行 最优解不变 原始问题可行 但对偶问题不可行 需要用单纯形法继续求解 三 价值系数cj的变化分析 XNXS CNCS CN XB CB CB CB 1 非基变量xj的价值系数cj发生变化 设价值系数的增量为 cj 要保证最优基不变 必须使最终表中的检验数仍 0 即 或者 2 基变量xr的价值系数cr发生变化 所以 非基变量在最终表的检验数变为 如果要求原最优基不变 非基变量的检验数必须满足 0的条件 于是 基变量价值系数cr的变化范围是 上式仅适用于一个基变量价值系数发生变化的情况 注意 在进行灵敏度分析时 可以用上面的公式确定参数的变化范围 也可以把价值系数当作未知数在表上进行直接计算 1 当产品1的价值系数由2变为3 产品2的价值系数从3变为2时 最优解会如何变化 产品2的价值系数的变化范围是什么 四 资源量bi的变化分析 b b 设第r种资源发生变化 资源量从br变为br br 其它系数维持不变 这样 在最终表中的基解相应地改变为 只要XB 0 最终表中的检验数不变 则最优基不变 注意 最优解的值已经改变 为保持最优基不变 资源增量的变化范围如下 这是可行基矩阵B的逆矩阵B 1的第r列 这样 最终表里保持最优基不变的b列元素满足 企业又购进资源A4个单位用于生产 求此时的最优方案 B 1 b 附加资源带来了获利水平的提高 最优的目标函数值为17 资源B在何范围变动时 最优基不变 B 1 b 8 b2 16 五 增加一个新变量xk的分析 XP P CP XP B 1P CP CBB 1P 增加新变量在实践中对应于增加一种新产品 分析步骤是 1 利用新产品的数据计算检验数 cp zp cp Y Pp 2 计算新产品在单纯形表中的系数列向量Pp B 1Pp 3 如果检验数 0 最优基不变 只要把上面计算的结果放在单纯形表的最后一列即可 如果检验数大于零 则要用单纯形法继续迭代 求出最优解 例 在上述模型中 企业打算生产一种新产品 每件产品消耗3种资源的量分别为2 6和3个单位 单件可获利5元 问可否投产 解 1 新产品能否投产关键看能否为企业带来利润 设新产品的生产量为x6 它的检验数为 因为检验数大于零 所以 新产品可以生产 2 计算新产品在单纯形表中的系数列向量P6 B 1P6 B 1P6 01 40 21 211 2 1 80 263 5x6 5 4 3 221 4 参数aij变化使得系数矩阵A也随之发生变化 如果变量xj在最终单纯形表里是非基变量 可以按照增加一个变量的方法处理 如果xj是基变量 则参数ai