第二章 对偶问题101015

第二章线形规划的对偶理论 一 对偶问题的提出 1对偶问题 则设各为A B C D产品的产量 化标准形 求解得 LP1问题 一 对偶问题的提出 从另一个角度提出问题 假定有另一家公司想把这家公司的钢材 塑料 电等资源收买过来 它至少应付出多大的代价 才能使这家公司愿意放弃生产活动 出让资源 设为单位资源出让价格 而A产品 需1工时 4钢材 4塑料 6电 可盈利90元 若小于90 则不愿意出让资源 同理 目标函数 用最小代价收买资源 一 对偶问题的提出 s t 此问题为前面问题的对偶问题 则LP2问题 对偶问题 LP1问题 原问题 一 对偶问题的提出 二 线性规划的原问题与对偶问题的转换 原问题maxz cxs tAx bx 0 c x A b 对偶的转换规则 对偶问题的对偶问题为原问题 二 线性规划的原问题与对偶问题的转换 例 其对偶问题是 二 线性规划的原问题与对偶问题的转换 三 原问题与对偶问题的基本性质 1 单纯形计算的矩阵描述 为松弛变量 为m n的单位阵 单纯形迭代若干步后 基变量为 基矩阵为B 则单纯形表可列如表 初始单纯形表 其中A B N C CB CN 经过若干次迭代后 对照两个表格 1 初始I 2 初始基变量 3 初始 4 系数变量 三 原问题与对偶问题的基本性质 5 假设B为最优基时 检验数 0 令 称单纯形乘子 即为检验数 目标函数 原问题为最优解时 检验数的相反 恰好是对偶问题的可行解 且目标函数值相等 三 原问题与对偶问题的基本性质 6 两边乘Y 两边乘X 因此 可知 原问题为最优解时 其检验数为其对偶问题的最优解 原问题maxz cxs tAx bx 0 对偶问题minW Ybs tYA CY 0 三 原问题与对偶问题的基本性质 2 基本性质 1 对称性 对偶问题的对偶问题就是原问题 推论 a 原问题的目标函数值是对偶问题的下界 反之 对偶问题的目标函数值是原问题的上界 b 原问题有可行解无界 则对偶问题无可行解 反之 对偶问题有可行解无界 则原问题无可行解 c 原问题有可行解 而其对偶问题无可行解 则原问题目标函数无界 反之对偶问题有可行解 而其原问题无可行解 则对偶问题目标函数无界 2 弱对偶性 若X是原问题的可行解 Y是对偶问题的可行解 则 三 原问题与对偶问题的基本性质 3 最优性 若为原问题的可行解 为对偶问题的可行解 当时 分别为各自问题的最优解 4 对偶定理 原问题有最优解 则对偶问题也有最优解 且 B为原问题的最优基 5 原问题的检验数对应对偶问题的一个解 对偶问题的检验数对应原问题的一个解 数值相等 符号相反 三 原问题与对偶问题的基本性质 6 互补松弛性 在原问题的最优解中 如果对应某一约束条件的对偶变量值为非零 则该约束条件取严格等式 即该约束条件的松弛变量为0 反之 如果约束条件严格不等式 松弛变量不为0 则其对应的对偶变量一定为零 原问题检验数与对偶问题解的关系 剩余变量 松弛变量 三 原问题与对偶问题的基本性质 2对偶单纯形法 思路 单纯形法 保持原问题的可行解 通过迭代 对偶问题趋于可行 对偶单纯形法 保持对偶问题的可行解 通过迭代 原问题趋于可行 若是单纯型 得用大M法 例 2对偶单纯形法 2对偶单纯形法 2对偶单纯形法 其对偶问题的解为 Y 1 0 3 0 0 5 y4y5y6y1y2y3 先确定换出变量 最负的那一个 后确定换入变量 消列 成为单位向量 步骤 2对偶单纯形法 对偶单纯形法归纳 2 对偶单纯形法的优点 1 使用对偶单纯形法求解线形规划问题的解时 必须满足两个条件 初始解可以是非可行解 当检验数都为负时 就可以进行基变换 这时不需要加入人工变量来构造单位基矩阵 可以简化计算 当变量多于约束条件 对这样的线形规划问题 用对偶单纯形法 可以减少计算工作量 反之 变量较少 约束条件较多的LP问题 也可用单纯形计算 也可先将它变成对偶问题 再用对偶单纯形法求解 对偶单纯形法一般不单独使用 因为初始检验数全为负 很难实现 主要用于灵敏度分析 整数规划 1 b列至少有一个分量小于零 即原问题的解为非可行解 2 对应于初始可行解的检验数非正 即对偶问题的解保证为可行解 例 2对偶单纯形法 因此对偶问题无界解 所以原问题无可行解 3对偶问题的经济意义 一 影子价格 当线性规划原问题求得最优解时 其对偶问题也得到最优解 带入目标函数 线性规划原问题的约束条件右端项 代表第j种资源的拥有量 对偶变量 代表资源最优利用条件下对单位第i种资源的估价 这不是资源的市场估价 而是根据资源在生产中作出的贡献而作的估价 称为影子价格 shadowprice 二 影子价格性质 1 资源的市场价格是已知数 相对比较稳定 而它的影子价格则有赖于资源的利用情况 未知数 2 影子价格是一种边际价格 表示的值相当于在资源得到最优利用的生产条件下 资源每增加一个单位时 目标函数Z的增量 资源的影子价格越大 表明它对目标函数极值的影响与作用越大 3 资源的影子价格实际上是一种机会成本 当资源市场价格低于影子价格时 买进资源 投入生产 变成产品卖出 当生产产品的数量多 批量生产 时影子价格下降 当资源市场价格高于影子价格时不投入生产 卖出资源 随着买进卖出 生产结构发生变化 影子价格也发生变化直到与市场价格同等 保持平衡 4 在单纯形表中的检验数行经济意义 其中 为第j种产品的产值 市场价格 生产第j种产品所消耗各项资源的影子价格总和 即产品的隐含成本 分量形式 当 0时 表明生产该项产品有利 可在计划中安排 即在迭代中 换为基变量 当 0时 用这些资源来生产别的产品更有利 就不在生产计划中安排 这就是单纯形表中各个检验数的经济意义 5 一般说线性规划问题的求解是 确定资源的最优分配方案 对偶问题的求解是 确定对资源的恰当估价 这种估价值直接涉及到资源的最有效利用 6 由互补松弛性可知 资源的影子价格 对偶变量 非零 则该约束条件取严格等式 说明该资源约束起作用 表明该种资源在生产中已耗费完毕 资源很充分 生产过程中该资源过剩或未得到充分利用 则该资源对目前的目标函数最优值不起作用 即该资源的影子价格为零 在公司内部 可借助资源的影子价格确定一些内部结算价格 以便控制有限资源的使用和考核企业经营好坏 或可对一些最紧缺的资源 借助影子价格规定使用这些资源时 必须上交的利润 以控制一些经济效益低的企业自觉地节约使用紧缺资源 二 影子价格性质 三 影子价格在经济决策中的应用 1 根据影子价格 资源单位边际价值 择优分配资源例题原料 设备能力 能源的分配 2 应用影子价格指导企业的经营决策 买进卖出资源 单位边际利润 影子价格 购置成本 隐含产品价 市场价 利润 0 购进资源 进行生产 变成产品后卖出利润 0 卖出资源 3 应用影子价格来预测产品的价格生产资源的厂家 资源成本价利用资源做产品的厂家 资源的影子价格进行比较 来定价格 而随产品数量增加 影子价格下降 下面考虑影子价格的变化 4线性规划的灵敏度分析 灵敏度分析 指对系统或事物因周围条件变化显示出来的敏感程度的分析 当这些参数发生变化时 问题的最优解会有什么样的变化 在多大的范围内变化时 最优解不变等 这就是灵敏度分析所要研究解决的问题 单纯形法的迭代计算是从一组基向量变换为另一组基向量 表中每步迭代得到的数字只随基向量的不同选择而改变 因此有可能把个别参数的变化直接在计算得到最优解的最终单纯形表上反映出来 思路 思想 从头做单纯形计算 计算量太大 这样不需要从头计算 而直接对最终单纯形表进行审查 看是否满足最优解的条件 若不满足 则从这单纯形表继续迭代 求最优解 4线性规划的灵敏度分析 灵敏度分析步骤 1 将参数的改变计算反映到最终单纯形表上 最终单纯形表中 矩阵 在最优表中 对应于初始基变量的系数矩阵 则的变化 2 检查原问题是否仍为可行解 b列 0 3 检查对偶问题是否仍为可行解 检验数行 0 4 按如下表得到结论和决定继续计算的步骤 灵敏度分析步骤 二 分析b的变化 会出现第一 a 原问题可行解 第三种 c 原问题非可行解情况 a 变化后的b列值为最优解 影子价格不变 检验数不变 1 可用资源数量的变化 只改变b列变化 c 用对偶单纯形继续迭代 影子价格变化 2 最优目标函数的变化 a 增加的目标函数值 c 影子价格变化 到资源过剩时 影子价格为零 二 分析b的变化 例 b2 26改为20和40时的最优解变化 初始单纯形表 最终单纯形表 最终单纯形表 最优基不变化 最优解 x1 12 5 x2 32 5 最优值z c1 x1 c2 x2 b2 20时 二 分析b的变化 b2 40时 b列不全大于零 即原问题没达到可行解 则单纯形表变为 采用对偶单纯形法继续迭代求解 b2的变化范围的计算 二 分析b的变化 三 分析的变化 计算方法 变化的价格系数放到最终单纯形表的上一行 求下一行检验数既可 然后进行判断 价格系数的变化 只影响检验数行 出现第一 a 第二种 b 情况 例 初始单纯形表 最终单纯形表 三 分析的变化 c1 4改为3和5时的最优解变化 3 三 分析的变化 1 5 9 5 3 5 3 5 四 增加一个变量 增加一个变量 表示增加一种新的