对偶问题与灵敏度分析PPT课件.ppt

第三章对偶问题与灵敏度分析 第一讲对偶理论第二讲灵敏度分析 1 第一讲对偶理论 例1中该厂的产品销售 现有另一企业想租赁其设备 厂方为了在谈判时心中有数 需掌握设备台时费用的最低价码 以便衡量对方出价 对是否出租做出抉择 一 对偶问题 2 第一讲对偶理论 对原企业而言 它用于出租或转让的资源收益不应低于自行生产产品所获得的利润 才肯出租或转让 在这个问题上厂长面临着两种选择 自行生产或出租设备 首先要弄清两个问题 如何合理安排生产 取得最大利润 为保持利润水平不降低 资源转让的最低价格是多少 问题 的最优解 x1 4 x2 6 Z 42 一 对偶问题 3 第一讲对偶理论 第二个问题 出让定价 假设出让设备A B C所得利润分别为y1 y2 y3原本用于生产甲产品的设备台时 如若出让 不应低于自行生产带来的利润 否则宁愿自己生产 于是有对甲产品y1 0y2 3y3 3同理 对乙产品而言 则有0y1 2y2 4y3 5设备台时出让的收益 租用企业希望出让的收益最少值 MinW 8y1 12y2 36y3显然还有y1 y2 y3 0 4 第一讲对偶理论 称后一个线性规划问题为前一个线性规划问题的对偶问题 对偶问题的最优解 y1 0 y2 1 2 y3 1 W 42两个问题的目标函数值相等 这不是偶然的 上述两个问题实际上是一个问题的两个方面 如果把前者称为线性规划原问题 则后者便是它的对偶问题 反之亦然 对偶问题的最优解对应于原问题最优单纯型法表中 初始基变量的检验数的负值 例1的对偶问题的数学模型 5 第一讲对偶理论 原问题最优单纯型法表 对偶问题的最优解 y1 0 y2 1 2 y3 1对应于原问题最优单纯型法表中 初始基变量x3 x4 x5的检验数的负值 6 线性规划原问题 P 对偶问题 D 对称形式下对偶问题的一般形式 对称形式 变量均为非负 其约束条件当目标函数求极大时均取 当目标函数取极小时均取 7 第一讲对偶理论 若原问题为极大 则对偶问题为极小 对极大的原问题 其约束条件为 而极小化的对偶问题的约束为 原问题的变量个数即为对偶问题的约束条件的个数 而原问题的约束条件的个数 即为对偶问题的变量的个数 原问题的约束条件的右端常数项即为对偶问题的目标函数中变量的系数 而原问题的目标函数中变量的系数即为对偶问题的约束条件的右端常数项 对称形式下对偶模型的特点 8 第一讲对偶理论 对称形式下原问题与对偶问题的对应关系 9 一般形式下对偶关系对应表 10 第一讲对偶理论 例 写出对偶模型 11 第一讲对偶理论 练习 求对偶模型 12 第一讲对偶理论 二 对偶问题的基本性质 对称性 对偶问题的对偶是原问题 弱对偶性 若X0为原问题 P 的可行解 Y0是对偶问题 D 的可行解 则CX0 Y0b 最优解 若X 为 P 的可行解 Y 是 D 的可行解 且CX Y b 则X Y 分别为最优解 强对偶性若 P 有最优解 则 D 也有最优解 反之亦然 且两者目标函数相等 13 第一讲对偶理论 证明 此问题的对偶问题为 例题 已知线性规划问题 试用对偶理论证明此线性规划问题有无界解 即有可行解 但无最优解 14 第一讲对偶理论 说明yi是右端项bi每增加一个单位的第i种资源对目标函数Z的贡献 对偶变量yi在经济上表示原问题第i种资源的边际价值 对偶变量的值yi 所表示的第i种资源的边际价值 称为影子价值 若原问题的价值系数Cj表示单位价格 则yi 称为影子价格 若原问题的价值系数Cj表示单位利润 则yi 称为影子利润 三 对偶问题的经济解释 影子价格 此时 同时达到最优解 bi为第i种资源的拥有量 15 第一讲对偶理论 影子价格不是资源的实际价格 市场价格 而是资源配置结构的反映 是在其它数据相对稳定的条件下对现有资源实现最大效益时的一种估价 它表明资源增加对总效益产生的影响 对资源i总存量的评估 购进or出让对资源i当前分配量的评估 增加or减少 它表明了当前的资源配置状况 告诉经营者应当优先增加何种资源 才能获利更多 告诉经营者以怎样的代价去取得紧缺资源 提示设备出租或原材料转让的基价 告诉经营者补给紧缺资源的数量 不要盲目大量补给 借助影子价格进行内部核算 特别注意 16 第一讲对偶理论 对偶问题的最优解 y1 0 y2 1 2 y3 1 W 42y2 1 2表示设备B的影子价格为1 2元 台时 说明该厂在当前的生产和利润情况下 每增加设备B一台 利润会增加1 2元 影子价格不是固定不变的 它因企业生产资源与利润的不同而不同 而市场价格是已知且相对稳定的 一般地 当某种资源 设备 的市场价格高于影子价格时 可将资源出租或转让 反之 应该从市场买进该种资源 以获得更大的利润 解释例1的对偶问题的数学模型 17 第一讲对偶理论 从原规划的一个对偶可行解 0 出发 从原规划的一个基解出发 此基解不一定可行 但它对应者一个对偶可行解即检验数非正 且保持其对偶变量的解为可行解 检验原规划的一个基解是否为基可行解 即是否有负的分量 若是基可行解 即b B 1b 0 则为最优解 否则进行基变换 得另一个基解 此基解对应着另一个对偶可行解 重复 2 单纯形法的思路 对偶单纯形法的思路 确定初始可行基 初始基可行解 每个分量非负 判断是否最优 是否有所有 非基变量 检验数 0 Max 基变换 18 第一讲对偶理论 适用于 对偶单纯形图表计算步骤 1 列出初始单纯形表 得初始基解 要求所有的检验数 0 2 检验b列 若所有的b B 1b 0 则得到最优解 若bi 0且bi 所在行的各系数aij 0 则原规划无可行解 否则取Min bi bi 0 bl 则相应的xl为离基变量 3 按照 Min j alj alj 0 k alk确定xk进基变量 4 以alk为主元素 按单纯形法的方法进行迭代 得到新的表重复 2 对偶单纯形法 应用于对称形式 19 第一讲对偶理论 例题 使用对偶单纯形法 主元 列初始单纯形表 x5为出基变量 x2为进基变量 20 第一讲对偶理论 对偶单纯形法 续 主元 此时b列皆非负且所有的非基变量检验数 j 0 得最优解Y 0 1 2 1 0 0 T 最优目标函数值W 42 W 42 21 第一讲对偶理论 习题 用对偶单纯形法求解 22 第一讲对偶理论 最优解为X 2 0 0 0 6 2 T 最优值Z 2 23 第二讲灵敏度分析 线性规划研究的是一定条件下的最优化问题 采用优化方案可以达到节约资源 提高效益的目的 但是对 优化方案 必须要有全面的认识 不可机械地对待 优化方案是建立在特定的资源环境和技术条件之上的 而环境和条件总是处在不断地变化之中 如产品价格 原材料成本 加工技术水平 资源消耗系数等时有波动 所以优化方案是个相对稳定的概念 当基础数据 Ci bj aij 发生变化时 最优方案也就变了 基础数据往往是测算估计的数值 虽然在运算过程中要求十分严格 但基础数据的误差是不可避免的 为了对优化结果有更全面的了解和恰当的运用 就需要进行灵敏度分析 灵敏度分析的意义 24 第二讲灵敏度分析 灵敏度分析又称敏感性分析或优化后分析 它研究基础数据发生波动后对最优解的影响 以及在多大的范围内波动才不影响最优基 灵敏度分析就是研究最优解对数据变化的敏感程度 感性太强 则说明最优解的稳定性程度较低 灵敏度分析解决的问题 参数 基础数据 在什么范围变化而最优基不变 已知参数的变化范围 考察最优解 最优基 是否改变 研究在原规划中增加一个变量或一个约束条件对最优解的影响 灵敏度分析的概念 25 第二讲灵敏度分析 在最优单纯形表中 有价值系数Cj变化影响检验数 参数Cj的变化范围 26 第二讲灵敏度分析 非基变量Cj的变化范围非基变量Cj变化 只影响与Cj有关的一个检验数 j的变化 27 第二讲灵敏度分析 基变量CBl的变化范围CBl CBl CBl 引入 CB 0 0 CBl 0 0 则有为是最优解不变 要有n m个 j 0 即有Max j alj alj 0 CBl Min j alj alj 0 28 第二讲灵敏度分析 基变量CBl的变化范围15 4 C1 0时 最优解始终为X 4 6 4 0 0 T 0 C1 15 4 29 第二讲灵敏度分析 例如 参数bi的变化范围 30 第二讲灵敏度分析 31 第二讲灵敏度分析 约束条件系数aij的变化范围若aij为非基变量xj的系数 它的变化只影响一个 j 设aij aij aij 则有这里y T CBB 1是对偶最优解 为是最优解不变 要有 j 0 即有 j yi aij 32 第二讲灵敏度分析 增加新变量的分析设新增变量为xn 1 其目标函数系数为cn 1 相应的系数列向量为pn 1 由当 n 1 0 不影响原最优解 当 n 1 0 在最优单纯形表中加入一列 约束系数列为pn 1 B 1pn 1 考虑xn 1进基 迭代 增加一个约束条件的分析当新增加一个约束条件时 将先得到的最优解带入 若满足 则最优解不变 若不满足 通过引入松弛变量或人工变量 列入最优单纯形表中 迭代 33 第二讲灵敏度分析 灵敏度分析的意义 1 当线性规划模型的系数发生变化或增加变量和约束条件时 最优解是否会改变 2 当系数在什么范围内变化时 原来得到的最优解保持不变 34 第一讲对偶理论 例 某企业生产A B两种产品 A产品需消耗2个单位的原料和1个小时人工 B产品需消耗3个单位的原料和2个小时人工 A产品售价23元 B产品售价40元 该企业每天可用于生产的原料为25个单位和15小时人工 每单位原料的采购成本为5元 每小时人工的工资为10元 问该企业如何组织生产才能使销售利润最大 35 第二讲灵敏度分析 习题1 灵敏度分析 其最优单纯形表格 36 第二讲灵敏度分析 其最优单纯形表格 试分析如下问题 1 b1由20 45 求新的最优解 2 b2由90 95 求新的最优解 3 c3由13 8 是否影响最优解 4