运筹学学习课件教学课件电子教案PPT线性规划的对偶理论.ppt

第二章线性规划的对偶理论 dualitytheory 第一节线性规划的对偶问题 一 问题的提出 例2 1 第一章例1 1中讨论了某企业利用三种资源生产甲乙两种产品的生产计划问题 得到其线性规划问题为 下面从另一个角度来讨论这个问题 假定该企业决定自己不生产产品 而将现有的资源转让或出租给其他企业 那么该如何确定资源的转让价格 分析问题 1 定价不能太高 否则买方无法接受 并且对买方来说 其目的是越低越好 2 定价不能太低 否则企业不愿意放弃生产 出让资源 合理的价格应是对方用最少的资金购买该企业的全部资源 而该企业所获得的利润又不低于自己组织生产时所获得的利润 设分别用y1 y2和y3代表单位时间 h 设备 每公斤材料a 材料b的出让代价 则有 lp2 对偶问题 从以下方面比较 lp1 与 lp2 系数矩阵目标函数价格系数向量约束条件右端项目标函数约束条件决策变量 lp2 二 对称形式下对偶问题的一般形式 满足下列条件的线性规划问题称为具有对称形式 1 变量均满足非负约束 2 约束条件当目标函数求极大时取 号 目标函数求极小时取 号注 对称形式与线性规划标准型是两种不同的形式 对称形式中约束条件的符号由目标函数决定 原问题 对偶问题 若原问题为求极小形式的对称形式线性规划问题 对偶问题应该具有什么形式 若一个线性规划问题是另一个线性规划问题的对偶问题 则它们互为对偶问题对偶问题的对偶问题是原问题 例2 2 写出下述线性规划问题的对偶问题 例中目标函数为max 若为对称形式 则约束条件应为 号 所有变量均应 0 非对称形式 三 非对称形式的原 对偶问题关系 2 变量均有非负约束令则 1 目标函数为求极大 故约束条件应均为 号约束b两边乘 1 约束c写成两个不等式约束 令 则 例2 3 写出下列线性规划问题的对偶问题 练习 写出下列线性规划问题的对偶问题 第二节对偶问题的基本性质 一 单纯形法计算的矩阵描述 设b是一个可行基 也称基矩阵 若将系数矩阵a分为 b n 两块 这里n是非基变量的系数矩阵 对应于基b的变量为xb 其它非基变量用xn表示 则 同时也将c分为两块 cb cn cb是目标函数中基变量xb的系数行向量 cn是目标函数中非基变量xn的系数行向量 于是 此时 若b 1b为最优解 则 1 初始表中单位阵在迭代后单纯形表中对应的位置就是b 12 对于原问题的最优解 各松弛变量检验数的相反数恰好是其对偶问题的一个可行解 且两者具有相同的目标函数值 根据下面介绍的对偶问题的基本性质还将看到 若原问题取得最优解 则对偶问题的解也为最优解 二 对偶问题的基本性质 1 对称性 对偶问题的对偶问题是原问题 证明 注 lp求极大 ld求极小 推论1 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界 反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界 推论2 如原问题有可行解且目标函数值无界 具有无界解 则其对偶问题无可行解 反之对偶问题有可行解且目标函数值无界 则其原问题无可行解 注 本点性质的逆不成立 当对偶问题无可行解时 其原问题或具有无界解或无可行解 反之亦然 推论3 若原问题有可行解而其对偶问题无可行解 则原问题目标函数值无界 反之 对偶问题有可行解而其原问题无可行解 则对偶问题的目标函数值无界 证 设和分别是原问题和对偶问题的任一可行解由弱对偶性故 证 设是原问题的最优解 由单纯形法的矩阵表示 故是对偶问题的可行解代入目标函数有由最优性是对偶问题的最优解 证 设由弱对偶性 在线性规划问题的最优解中 如果对应某一约束条件的对偶变量值为非零 则该约束条件取严格等式 反之如果约束条件取严格不等式 则其对应的对偶变量一定为零 也即 若 则有 即 若 即 则有 推论 证明 例2 4 已知原问题的最优解为x 0 0 4 z 12试求对偶问题的最优解 解 1 2 3 将x 0 0 4 代入原问题中 有下式 所以 根据互补松弛条件 必有y 1 y 2 0 代入对偶问题 3 式 y3 3 因此 对偶问题的最优解为y 0 0 3 w 12 练习 对于线性规划问题 已知其对偶问题的最优解为y1 4 5 y2 3 5 z 5 试利用对偶理论找出原问题的最优解 综上所述 一对对偶的线性规划问题的解只能有下面三种情况之一出现 都有最优解 分别设为x 和y 则必有cx y b 一个问题无界 则另一个问题无可行解 两个都无可行解 第三节对偶问题的经济解释 影子价格 在单纯形法的迭代过程中 目标函数z cbb 1b和检验数cn cbb 1n中都有单纯乘子y cbb 1 那么y的经济意义是什么 从上节对偶问题的基本性质看出 当线性规划原问题求得最优解时 其对偶问题也得到最优解 且代入各自的目标函数后有式中 bi是线性规划原问题约束条件的右端项 它代表第i种资源的拥有量 即y i表示z 对bi的变化率 其经济意义是 在其它条件不变的情况下 单位资源变化所引起的目标函数的最优值的变化 设b是问题p的最优基 z cbb 1b y b y 1b1 y 2b2 y ibi y mbm在上式中令z 对bi求偏导 得 左图为第一章例1 1用图解法求解时的情形 图中阴影部分标出了问题的可行域 点q3 4 12 是最优解 代入目标函数得z 1200 如果将例1 1中的第2个约束条件右端项增加l 变为3x1 2x2 37 可行域边界线由 b 移至 b 见右图 最优解变为q3 5 11 代入目标函数得z 1220 说明第2种资源每增加1个单位即可多获利20 例如 由此可以看出 yi表示对第i种资源的估价 这种估价不同于资源的市场价格 是根据资源在生产中做出的贡献而作的估价 它是针对具体企业的具体产品而存在的一种特殊价格 为区别起见 称它为 影子价格 一般说对线性规划问题的求解是确定资源的最优分配方案 而对于对偶问题的求解则是确定对资源的恰当估价 这种估价直接涉及到资源的最有效利用 正确理解影子价格 可帮助决策者分析经济活动 作出有利决策 资源的影子价格实际上是一种机会成本 在完全市场经济条件下 若第i种资源的单位市场价格低于影子价格 企业愿意购进这种资源 用于扩大生产 而当某种资源的市场价格高于影子价格时 则企业应有偿转让这种资源 否则 企业无利可图 甚至亏损 可见 影子价格对市场价格有调节作用 直到影子价格与市场价格保持同等水平才处于平衡状态 正确理解影子价格将有利于更好地调节生产规模 资源的影子价格是一种边际产出 影子价格反映了在其他条件不变的情况下 第i种资源增加1个单位所带来的收益 因此可用于评估生产要素对产出贡献的分解 大致估计各种资源分别产生了多少利润 从影子价格的含义考察互补松弛性的意义 表明生产过程中如果某种资源未得到充分利用时 该种资源的影子价格为零 资源的影子价格不为零时 表明该种资源在生产中已耗费完毕 由此看出 影子价格可以反映资源的稀缺程度 影子价格是企业生产过程中资源的一种隐含的潜在价值 从影子价格的含义考察单纯形法检验数的意义 cj代表第j种产品的产值 是生产该种产品所消耗各项资源的影子价格的总和 即隐含成本 当产品的产值大于隐含成本时 表明生产该项产品有利 可在计划中安排 否则 转而安排生产其他产品 第四节对偶单纯形法 设lp 则ld 一 对偶单纯形法的基本思路 化为标准型 lp ld 设b为lp的一个基 可记a b n c cb cn x xb xn t 此时 lp 的标准型可写为 lp ld 若b为 lp 的可行基 则xb b 1b为 lp 的一个基可行解 相应的检验数为0 cn cbb 1n cbb 1 令y cbb 1 代入 ld 的约束条件中 可发现检验数行恰为对偶问题的一组基解的相反数 对偶单纯形法的基本思路 若 ld 取得一组基可行解y 对应的x为 lp 的基可行解 则y为 ld 的最优解 此时 x也为 lp 的最优解 由单纯形法原理 当所有检验数均不大于零时 lp 取得最优解 此时 y为 ld 的可行解 结论 若 lp 取得一组基可行解x 且对应的y为 ld 的基可行解 则x为 lp 的最优解 由对偶问题的基本性质 y也为 ld 的最优解 注 不要简单地把对偶单纯形法理解为是求解对偶问题的单纯形法 对偶单纯形法不是对对偶问题使用单纯形法 而是求解线性规划的另一有效方法 它之所以被称为 对偶单纯形法 是因为该方法在求解过程中是以对偶原理和单纯形法原理为理论依据的 1 建立初始单纯形表 二 对偶单纯形法的计算步骤 2 最优性判断 检查b列的数字 若都为非负 检验数都为非正 则已得到最优解 停止计算 若b列有负数 其中某负数对应的行没有负数 则问题无可行解 若b列有负数 而且所有负数对应的行都有负数 则转入下一步 3 得出新的单纯形表 4 重复2 3步 若要令迭代后的为可行解 必有 即b列的数应不小于0 故需将小于0的xi从基中换出 若x存在一个以上分量小于0 则首先将其中最小的xr换出 出基变量xs应满足 1 使迭代后的解为可行解 即要使迭代后的ars 1 首先应将第r行均除以ars因为 若要 只能 2 保持y为对偶问题的基可行解 即 例2 5 用对偶单纯形法求解下述线性规划问题 解 先将 约束条件 a b 两端乘以 1 得 写为一般形式有 初始解可以是非可行解 当约束条件右端项 0时 不必划为标准型 当约束条件为 时 不必引入人工变量对于变量多于约束条件的线性规划问题 用对偶单纯形法计算可以减少计算工作量对偶单纯形法的重要应用 灵敏度分析对许多线性规划问题 因为很难找到一个初始可行基 因而有局限性对偶单纯形法是对特殊问题的特殊解法 而单纯形法适用于所有线性规划问题 是线性规划问题的一般解法 所以 原问题最优解为 y 20 30 0 0 0 其对偶问题的最优解为 x 4 12 练习 用对偶单纯形法求解下述线性规划问题 解 将模型转化为 所以 原问题最优解为 x 11 5 2 5 0 0 0 其对偶问题的最优解为 y 8 5 1 5 第五节灵敏度分析 市场条件改变 产品利润发生变化 则价格系数cj变化 资源条件改变 资源可用数量变化 则右端项bi变化 工艺条件改变 系数矩阵变化 则aij发生变化 增加一种产品 则线性规划问题中增加一个变量 增加一道工序 则线性规划问题中增加一个约束条件 问题 1 当这些参数中的一个或几个发生变化时 已求得的线性规划问题的最优解有什么变化 2 这些参数在什么范围内变化时 线性规划问题的最优解或最优基不变 灵敏度分析 方法 将个别参数的变化直接在计算得到最优解的最终单纯形表上反映出来 并进行检查和分析 表1某企业生产计划安排最终单纯形表 表2单纯形法计算表 4 1 3 2 5 一 价值系数cj的变化分析 线性规划目标函数中变量系数cj的变化仅仅影响到检验数的变化 此时只可能出现表中前两种情况 若原问题和对偶问题均为可行解 则最优解不变 若原问题为可行解 对偶问题为非可行解 则用单纯形法继续迭代求最优解 例2 6 在第一章某企业的例子中 1 若甲产品的利润降至85元 件 而乙产品的利润增至95元 件时 该企业的最优生产计划有何变化 2 若甲产品的利润不变 则乙产品的利润在什么范围内变化时 该企业的最优生产计划将不发生变化 解 1 将甲 乙产品的利润变化直接反映到最终单纯形表中 得下表 因变量x4的检验数大于零 故需继续用单纯形法迭代计算得 即该企业随产品甲 乙的利润变化应调整为生产甲3件 乙13件 2 设产品乙的利润为 70 元 反映到最终单纯形表中 得表 即家电 的利润c2的变化范围应满足 二 资源限量bi的变化分析 当右端项发生变化后 会引起单纯型表中b列数字的变化 此时可能出现表中第一或第三种情况 当出现第一种情况时 问题最优解不变 当出现第三种情况时 用对偶单纯形法继续迭代找到最优解 例2 7 在某企业的例子中 1 若设备和材料b的现有资源不变 而材料a的现有资源增加到51公斤时 分析企业最优计划的变化 2 材料a和b的现有资源不变 则设备的现有资源在什么范围内变化时 问题的最优基不变 解 1 将其反映到最终单纯形表中得 因上表中原问题为非可行解 故用对偶单纯形法继续计算得表 由此美佳公司的最优计划改为只生产甲产品16件 2 设调试工序每天可用能力为 16 小时 因有 将其反映到最终单纯形表中 其b列数字为 当b 0时问题的最优基不变 解得 4 1 3 由此调试工序的能力应在12小时 49 3小时之间 三 增加一个新变量的分析 例2 8 在某企业的例子中 设企业又计划推出新型号的产品丙 生产一件所需设备台时及材料a b分别为1小时 4公斤 3公斤 该产品的预期利润为115元 件 试分析该种产品是否值得投产 如投产 该企业的最优生产计划有何变化 解设该企业生产丙产品x6件 有c6 115 p6 1 4 3 t 将其反映到最终单纯形表中得表 故用单纯形表继续迭代计算得表 故美佳公司新的最优生产计划应为生产甲产品11 4件 乙产品101 8件 丙产品5 8件 四 技术系数aij的变化分析 例2 9 在某企业的例子中 进行工艺改进后若甲产品每件需设备 材料a和材料b变为0台时 1公斤和1公斤 该产品的利润变为100元 件 试重新确定企业的最优生产计划 解先将生产消耗变化后的新产品甲看作是一种新产品 生产量为 仿本节三的步骤直接计算和并反映到最终单纯形表中 其中 将其反映到最终单纯形表中 因已变换为 故用单纯形法将替换出基变量中的 得 原问题与对偶问题均为非可行解 故变化后重新使用单纯形法第三个约束引入人工变量 该企业的最优生产计划为只生产工艺改进后的甲产品36件 五 增加一个约束条件的分析 增加一个约束条件在实际问题中相当增添一道工序 分析的方法是先将原问题最优解的变量值代入新增的约束条件 如满足 说明新增的约束未起到限制作用 原最优解不变 否则 将新增的约束直接反映到最终单纯形表中再进一步分析 例2 10 仍以某企业为例 设甲乙产品生产完后 还需经过一道环境试验工序 甲产品每件须环境试验2小时 乙产品每件1 5小时 又环境试验工序拥有资源为24小时 试分析增加该工序后企业的最优生产计划 解先将原问题的最优解x1 4 x2 12代入环境试验工序的约束条件2x1 1 5x2 24 故原问题最优解不是本例的最优解 以x6为基变量 将上式反映到最终单纯形表中得表 由于x1 x2 x5 x6为基变量 对应的列向量应为单位向量 故需进行变换 得 原问题为非可行解