运筹学3对偶.ppt

第三章线性规划的对偶理论 内容提要 3 1线性规划的对偶问题 3 2线性规划的对偶理论 3 3对偶解的经济解释 3 4对偶单纯形方法 3 5灵敏度分析 3 1线性规划的对偶问题 1 对偶问题的提出2 如何将原问题转化为对偶问题3 原问题与对偶问题的对应关系 对偶问题的提出例3 1 某工厂拥有A B C三种类型的原料 生产甲 乙两种产品 每件产品在生产中消耗的原料数量 每件产品的价格以及三种原料可利用的数量如下表所示 问题 工厂应如何安排生产可获得最大的总收益 解 设变量xi为第i种 甲 乙 产品的生产件数 i 1 2 则有目标函数Maxz 50 x1 100 x2s t x1 x2 3002x1 x2 400 x2 250 x1 x2 x3 x4 x5 0 现在考虑若三种原料都用于转让 试问 三种原料各如何收费才能即保证本厂的利益 有能最有竞争力 设y1 y2 y3分别为每设备工时 或原料 每单位的收取费用 则有 Minf 300y1 400y2 250y3s t y1 2y2 50 不少于甲产品的利润 y1 y2 y3 100 不少于乙产品的利润 y1 y2 y3 0 Minf 300y1 400y2 250y3s t y1 2y2 50y1 y2 y3 100y1 y2 y3 0 Maxz 50 x1 100 x2s t x1 x2 3002x1 x2 400 x2 250 x1 x2 0 对偶问题租赁者模型 原问题管理者模型 一对互为对偶的模型 对偶问题的定义 对称形式 LP maxZ c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1 am1x1 am2x2 amnxn bmx1 x2 xn 0 DP minW b1y1 b2y2 bmyms t a11y1 a21y2 am1ym c1 a1ny1 a2ny2 amnym cny1 y2 ym 0 LP Maxz cTx DP Minf bTys t Ax bs t ATy cx 0y 0则 DP 称为 LP 的对称形式对偶问题 设 例3 2写出下面线性规划的对偶规划模型 解 按照对称形式的对偶关系 其对偶模型为 2 如何将一般问题转化为对偶问题 原问题和对偶问题有很多内在联系 它们之间存在严格的对应关系 目标函数类型之间的对应关系 目标函数系数与右边项的对应关系 约束系数矩阵之间的对应关系 约束类型与变量类型之间的对应关系 非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划 对于非对称形式的规划 可以按照下面的对应关系直接给出其对偶规划 1 将模型统一为 max 或 min 的形式 对于其中的等式约束按下面 2 3 中的方法处理 2 若原规划的某个约束条件为等式约束 则在对偶规划中与此约束对应的那个变量取值没有非负限制 3 若原规划的某个变量的值没有非负限制 则在对偶问题中与此变量对应的那个约束为等式 下面对关系 2 做一说明 对于关系 3 可以给出类似的解释 设原规划中第1个约束为等式 a11x1 a12 a1nxn b1那么 这个等式与下面两个不等式等价 这样 原规划模型可以写成 此时已转化为对称形式 直接写出对偶规划 令y1 y1 y1 于是有 一般情况 我们总结如下 例3 3写出下列问题的对偶问题 解 先将约束条件变形为 形式 再根据非对称形式的对应关系 直接写出对偶规划 3 2线性规划的对偶理论 考虑下面一对对偶问题 Pmaxz CTXDminw bTYs t AX bs t ATY cX 0Y 0 A为m n阶矩阵 A的秩为m 引入松弛变量Xs 得到原规划 P 的标准型为 P1 其中01和I分别为m维的零向量和m维的单位矩阵 记 则上面的标准型可记为 P2 设B为一可行基 并记 得到模型 P2 的另一表示形式 对偶定理 定理3 1 对称性定理 对偶问题的对偶就是原问题 定理3 2 弱对偶定理 设X Y分别是P和D的可行解 则CTX bTY 证 由P和D的约束条件AX b ATY C X 0 y 0可直接推得CTX YTAX YTb bTY 证毕 推论1 对偶定理 若X Y 分别是 P 和 D 的可行解 则它们分别是 P 和 D 的最优解的充要条件是 CTX bTY 证由定理3 1可知 对于规划 D 的任一可行解Y 都有bTY CTX bTY 因此Y 是规划 D 的最优解 类似地可证明 X 是规划 P 的最优解 推论2若规划 P 有可行解 则 P 有最优解的充分必要条件是规划 D 有可行解 推论3若规划 D 有可行解 则 D 有最优解的充分必要条件是规划 P 有可行解 例3 4试用对偶理论判断下面线性规划是否有最优解 解 此规划存在可行解 其对偶规划为 显然 对偶规划没有可行解 因此 原规划没有最优解 例3 5用对偶理论判断下面线性规划是否存在最优解 解 此规划存在可行解 其对偶规划为 对偶规划也存在可行解 因此原规划存在最优解 定理3 3若原规划 P 有最优解 则对偶规划 D 也有最优解 反之亦然 并且两者的目标函数值相等 证 考虑原规划 P 的标准型 P2 设B为模型 P2 的最优基 现在证明对偶规划 D 也有最优解 由单纯形法可知 此时 为对偶规划 D 的可行解 另一方面有 因此 其中 为原规划的最优解 由推论1可知 为对偶规划 D 的最优解 类似地 可以证明 若规划 D 有最优解 则规划 P 也有最优解 从定理3 2的证明可以看到 对偶规划 D 的最优解为 例3 6求解下面线性规划问题 并根据最优单纯形表中的检验数 给出其对偶问题的最优解 解引入松弛变量 将模型化为标准型 经求解后得到其最优单纯形表 对偶规划的最优解为 3 3对偶解的经济解释 1 对偶解与影子价格2 互补松弛定理 1 对偶解与影子价格 对偶解的数学意义 当得到最优解后 目标函数值z CTX bTY z y1b1 y2b2 ymbm将b1 b2 bm看作变量 对右边项求偏导 z bi yi对偶解的意义是 当取得最优解的前提下 右边资源项bi的单位改变量 其他参数不变 所引起目标函数z的改变量 如果把线性规划约束看成广义资源约束 右边项代表资源的可用量 其经济含义是资源对经济目标的边际贡献 目标函数值通常用价值量衡量 对偶解也具有价值内涵 被称为影子价格 影子价格是对偶解十分形象的名称 它既表明对偶解是对资源的一种客观估价 又表明它是虚拟而不是真实的价格 对偶解的经济意义 影子价格有以下几个特点 1 系统资源的最优估价影子价格是综合考虑系统内所有因素和相互之间影响之后对资源在系统内的真实价值的估价 只有系统达到最优状态时才可能赋予该资源这种价值 因此 也有人称之为最优计划价格 2 影子价格与系统价值取向和状态有关影子价格 y CBTB 1 的取值与系统的价值取向有关 反映在CB上 影子价格受系统状态影响 反映在B 1上 系统内部资源数量和价格的任何变化都会引起影子价格的变化 从这种意义上讲 它是一种动态的价格体系 3 影子价格是一种边际值它与经济学中边际成本的概念相同 在管理中有十分重要的应有价值 管理者可以根据资源在本企业内影子价格的大小决定企业的经营策略 4 反映资源在系统内的稀缺程度如果资源在系统内供大于求 其影子价格为零 增加该资源的供应不会给系统目标带来任何变化 如果是稀缺资源 其影子价格大于零价格越高 资源的稀缺程度越高 例 某企业生产A B两种产品 A产品需消耗2个单位的原料和1小时人工 B产品需消耗3个单位的原料和2小时人工 A产品售价23元 B产品售价40元 该企业每天可用于生产的原料为25个单位和15小时人工 每单位原料的采购成本为5元 每小时人工的工资为10元 问该企业如何组织生产才能使销售利润最大 成本数据不直接反映在模型中 maxz 3x1 5x2s t 2x1 3x2 25x1 2x2 15x1 0 x2 0最优解 x 5 5 T z 40 对偶解 y 1 1 构模方法一 构模方法二 成本数据直接反映在模型中maxz 23x1 40 x2 5x3 10 x4s t 2x1 3x2 x3 0 x1 2x2 x4 0 x3 25x4 15x1 0 x2 0 x3 0 x4 0最优解 x 5 5 25 15 z 40 对偶解 y 6 11 1 1 计算影子价格时要注意资源成本是如何反映在目标函数中的 若资源成本显性地反映在目标中影子价格 对偶解若资源成本隐性地反映在目标中影子价格 对偶解 资源成本 按以下原则考虑经营策略 影子价格高于市场价格 或 0 表明资源有获利能力 购入该资源 影子价格低于市场价格 或 0 表明该资源无获利能力 出让该资源 影子价格等于市场价格 或 0 表明该资源处于平衡状态 既不用买入 也不必卖出 2 互补松弛定理 互补松弛定理 又称松紧定理 描述了线性规划达到最优时 原问题 或对偶问题 变量取值和对偶问题 或原问题 约束松紧之间的对应关系 定理3 4 互补松弛定理 如果X Y分别是P和D的可行解 它们是P和D的最优解的充要条件是 C ATY TX 0 b AX TY 0互补松弛定理中还可等价表示为 yi bi aix 0i 1 2 m cj ypj xj 0j 1 2 n 互补松弛定理证明了最优线性规划的下列对应关系 原问题约束为紧 对偶变量 0 原问题约束为松 对偶变量 0 对偶约束为紧 原问题变量 0 对偶约束为松 原问题变量 0 原问题变量 0 对偶约束为紧约束 原问题变量 0 对偶约束可紧可松 互补松弛性的经济意义 若资源的影子价格大于零 yi 0 必为紧缺资源 约束为紧约束 bi aix 0 否则 若该资源仍有剩余 系统还未达到最优状态 利用该资源可使目标进一步得到改善 若资源有剩余 约束为松 bi aix 0 其对偶解必为零 yi 0 否则 若对偶解大于零 增加该资源的使用还可使目标得到改善 互补松弛性的经济意义 在最优状态下 当变量的检验数小于零时 cj ypj 0 说明生产该产品的边际贡献是负的 在最优计划中不该生产它 因此 该变量必为零 xj 0 当变量大于零时 xj 0 该变量的检验数 边际贡献 必为零 cj ypj 0 否则 无论边际贡献取正值或负值 相应地增加或降低该产品的产量都可使目标得到改善 例 7已知线性规划minz 2x1 3x2 5x3 2x4 3x5s t x1 x2 2x3 x4 3x5 42x1 x2 3x3 x4 x5 3x1 x2 x3 x4 x5 0其对偶问题的最优解为 y1 0 8 y2 0 6 试用对偶理论求出它的原问题的最优解 对偶问题 Maxw 4y1 3y2s t y1 2y2 2y1 y2 32y1 3y2 5y1 y2 23y1 y2 3y1 0 y2 0 代入y1 0 8 y2 0 6 松约束 x2 0 紧约束 x1 0 松约束 x3 0 松约束 x4 0 紧约束 x5 0 原问题的约束为紧约束 故有 x1 3x5 42x1 x5 3解得 x1 1 x5 1原问题的最优解为 X 1 0 0 0 1 z 5 3 4对偶单纯形方法 单纯形方法始终保持原问题的解可行 检验数不一定小于等于零 即对偶解不可行 一旦检验数小于等于零 即对偶解变为可行解 则问题达到最优 对偶单纯形方法的基本思想 从对偶规划的一个可行基出发 即保证满足 C CBB 1A 0 一旦原问题可行 即 XB B 1b 0 则找到最优解 最优检验存在以下几种情况 1 如果B 1b 0 该问题已最优 停止 2 如果B 1b存在至少一个负分量 且 i 0 i i1 i2 in ij B 1pj i 由线性规划的典则方程 再由条件 B 1b i 0和 i 0 xB i不可能变为正 因此原问题无可行解 3 如果B 1b中存在至少一个负分量 且每个负分量对应的行向量 i存在小于零的元素 此时原问题解不可行 仍需继续迭代 保持对偶可行的条件可表示为 因此可得入基变量的检验条件为 对偶单纯形算法 1 找初始对偶可行解 2 最优检验 B 1b r min B 1b ii JB 如果 B 1b r 0 已找到最优解 停止 如果 B 1b r 0且 r 0 问题不可行 停止计算 否则选变量xr出基 转到3 3 确定入基变量 令 j cj cBB 1pj 计算 令xk入基 4 以 rk为转轴进行旋转迭代得到一个新的单纯形表 转到2 原问题和对偶问题的对应关系 原始与对偶单纯形法的对比 例3 8用对偶单纯形方法求解 解 1 引入松弛变量x3 x4 x5化为标准形 并在约束等式两侧同乘 1 得到 取x3 x4 x5为基变量 此式即为典式形式 并且检验数皆非正 因此可构初始对偶单纯形表 例3 9用对偶单纯形法求解下面线性规划 解 构造对偶单纯形表进行迭代 从最后的表可以看到 B 1b列元素中有 2 0 并且 2所在行各元素皆非负 因此 原规划没有可行解 对偶单纯形法适合于解如下形式的线性规划问题 在引入松弛变量化为标准型之后 约束等式两侧同乘 1 能够立即得到检验数全部非正的原规划基本解 可以直接建立初始对偶单纯形表进行求解 非常方便 2 5灵敏度分析 使用LP求解管理问题时 管理者需要了解当环境和数据发生变化时 线性规划得出的结论还是否有效 资源供应发生变化会有什么影响 成本变化后利润会发生什么变化 如果模型使用的数据不精确会有什么影响 数据允许在什么范围内变化 灵敏度分析主要内容 1 目标函数系数变化的灵敏度分析2 右边项变化的灵敏度分析3 约束条件中的系数变化的灵敏度分析4 增加新变量的灵敏度分析5 增加约束条件的灵敏度分析6 灵敏度分析的几何意义 1 目标函数系数变化的灵敏度分析 假定只有一个cj变化 假定cj从cj变到cj cj cj 当 cj在什么范围内变化时 不会影响最优解 1 分析什么 2 怎么分析 最优解不变的充要条件是 假定只有一个cj变化 分两种情况讨论 1 cj是非基变量的系数设cj变化量为 cj 若希望cj变化后最优基不变 检验数应满足以下条件 j cj cj cBB 1pj cj cBB 1pj cj j cj 0得到 cj j 由 cj j及最优条件 j 0 cj只在增加方向受限制 在下降方向不受限制 cj增加时 变量对目标函数的贡献增加 增加足够大时 检验数会大于零 使该变量入基而引起最优基改变 cj下降时 变量对目标函数的贡献下降 检验数变得更负 最优基不会变化 非基变量目标系数允许变化范围为 cj jj JN满足以上条件 解和目标值不会改变 2 cj是基变量的系数基变量的cj变化会引起cBB 1变化 从而引起所有检验数变化 若要使所有检验数满足最优条件 有以下条件 k ck cB cB B 1pk 0k JN假定cj是当前基的第r个基变量 即 cj cB r cB 0 cB r 0 0 cj 0 从而有 k ck cB cB B 1pk ck cBB 1pk 0 cB r 0 B 1pk k cj B 1pk r 0k JN令 rk B 1pk r得 k k cj rk 0k JN 在上述变化范围内 目标函数值的改变量 z cjxj对偶解的改变量 y cBB 1原问题的最优基和最优解不会改变 解不等式组 k k cj rk 0k JN得 cj的变化范围 maxk k rk rk 0 cj mink k rk rk 0 例 对例1 1的目标函数系数进行敏感性分析 解 家具厂问题的最优单纯形表 c1 x1在基的第二行 r 2 非基变量下标k 3和4 23 1 2 24 3 2 可得 max 15 1 5 c1 min 5 0 5 10 c1 10 c2 x2在基的第一行 r 1 13 1 14 2 可得 max 5 1 c2 min 15 2 5 c2 7 5 2 右边项发生变化的灵敏度分析 1 分析什么 假定只有一个br变化 假定br从br变到br br br 当 br在什么范围内变化时 不会影响最优基 不改变产品种类 只调整数量 2 怎么分析 最优基不变的充要条件是 为了保持最优基不变 应使 即 解不等式组 得 例 对例1 1的右边项进行敏感性分析 1 对b1进行分析 i 1对应基的第一列 11 13 1 21 23 0 5max 20 1 b1 min 15 0 5 20 b1 30 2 对b2进行分析 i 2对应基的第二列 12 14 2 22 24 1 5max 15 1 5 b2 min 20 2 10 b2 10 灵敏度分析一览表 3 约束条件中的系数变化 假设只有一个aij变化 其他数据不变 并且只讨论aij为非基变量的系数的情况 因此 aij的变化只影响一个检验数 当 aij在什么范围内变化时 不会影响最优解 1 分析什么 2 怎么分析 最优解不变的充要条件是 其中Y为对偶最优解 yi为Y的第i个分量 为使最优解不变 要使 即 4 增加新变量的灵敏度分析 在管理中经常遇到的问题 已知一种新产品的技术经济指标 在原有最优生产计划的基础上 怎样最方便地决定该产品是否值得投入生产 可在原线性规划中引入新的变量 无论增加什么样的新变量 新问题的目标函数只能向好的方向变化 例 家具厂设计了一种新柜子 市场售价为100元 生产一个柜子需9个木工工时 3 5个油漆工工时 问柜子是否应投产 解 令x5代表柜子产量 新模型为 maxz 50 x1 30 x2 100 x5s t 4x1 3x2 x3 9x5 1202x1 x2 x4 3 5x5 50 x1 x2 x3 x4 x5 0 B 1p5 新变量及其系数放在原单纯形表的最后一列 新向量需经过左乘基的逆矩阵后才能写入最优单纯形表 计算新产品影子 机会 成本 由y1 5 y2 15 影子成本ypj为 9 5 3 5 15 97 5 100 5 增加一个新约束的分析 当出现新的资源限制时 模型要加入新约束 可在原最优解的基础上进行分析 最优解满足新约束 最优解不变 最优解不满足新约束 应继续寻找新的最优解 无论加入什么类型约束 目标函数值都不会改善 例 如果家具厂每月可用的木材只有10立方米 生产一个桌子需木材0 3立方米 椅子需0 4立方米 问应该如何生产 解 加入新约束为 3x1 4x2 100 引入松弛变量x5并令其入基 加入原最优表后得到的不是标准单纯形表 需要通过矩阵的初等变换将其化为标准表 再进一步用对偶单纯形法求解 例 设某厂使用甲 乙 丙三种原料生产A B C三种产品 每种产品的原料消耗和销售价格见下表 已求得最优单纯形表见下表 该厂需要做以下敏感性分析 1 至少生产A产品30件 会有什么变化 2 要留下300公斤原料丙 对生产会有什么样的影响 3 C产品已滞销 不能再生产 会有什么变化 4 新产品D消耗原料甲3公斤 乙2公斤 丙1公斤 问如何定价工厂才能获利 如果单价定为55元 是否应进行生产 1 强制生产30件A x1必须等于30 目标值下降 下降程度可用x1的检验数进行计算 z x1检验数 变化数量 15 30 450 x2 400 1 30 370生产B产品370件x3 50 1 3 30 40生产C产品40件x4 350 5 3 30 300甲剩余300公斤新方案生产30件A 370件B 40件C 甲原料剩余300公斤 2 丙原料剩余300 资源减少300 目标改变量 影子价格 资源改变数量 z y b 25 300 7500 还可理解为松弛变量x6 300 目标改变量 检验数 x6改变数量 z