管理运筹学 第六章单纯形法的灵敏度分析与对偶 单纯形表的灵敏度分析 线性规划的对偶问题 对偶规划的基本性质 对偶单纯形法种特殊情况 单纯形表的灵敏度分析 线性规划的对偶问题 对偶规划的基本性质 对偶单纯形法种特殊情况 1 单纯形表的灵敏度分析 一 目标函数中变量系数ck灵敏度分析 1 在最终的单纯形表里 xk是非基变量 由于行行初等变换 约束方程增广矩阵不变 基变量系数cB不变 zj都不变 包括zk 若要原来的最优解不变 1 单纯形表的灵敏度分析 2 在最终的单纯形表中 xk是基变量 由于行行初等变换 约束方程增广矩阵不变 基变量系数cB变化 对所有的zj都变化 包括zk 6 1 原最优单纯形表可表示如下 单纯形表的灵敏度分析 1 单纯形表的灵敏度分析 由于 j cj zj 1 单纯形表的灵敏度分析 当j k时 当j k时 若要最优解不变 1 单纯形表的灵敏度分析 例用单纯形表求解下列线性规划问题 第二章例1 目标函数 maxz 50 x1 100 x2约束条件 x1 x2 300 2x1 x2 400 x2 250 x1 x2 0 最优单纯表如下表 1 单纯形表的灵敏度分析 先对非基变量s1的目标函数的系数c3行灵敏度分析 这里 3 50 所以当c3的增量 c3 50时 c 3 50时 最优解不变 1 单纯形表的灵敏度分析 当 50 c1 50 即在0 c1 100时最优解不变 再对基变量x1的目标函数系数c1行灵敏度分析 1 单纯形表的灵敏度分析 2 从 3 0 得 c 1 0 即c 1 0 1 用c 1代替原来的c1 50 3 从 5 0 得c 1 100 0 c 1 100 若c 1超出取值范围 必存在检验数 0 可通过迭代来得到新的最优解 1 单纯形表的灵敏度分析 当 ck k 即 ck zk时 xk变为入基变量 由 c3 50 最优解不变 剩余单位台时数设备 从不获利到获利50元时 从而设备台时数的对偶价格为z3 50元 同样可知原料A的对偶价格为z4 0元 原料B的对偶价格为z5 50元 c3 0 50 若有人出50元买1个设备台时 厂家则不必为生产 产品而使用完所有的设备台时 1 单纯形表的灵敏度分析 由最终单纯形表对于不同约束类型的对偶价格的取值如下表 从对偶价格的定义可知 当对偶价格为正 将改目标函数值 当对偶价格为负 将 恶化 目标函数值 1 单纯形表的灵敏度分析 在求目标函数最大值的线性规划中 对偶价格等于影子价格 求目标函数最小值时 影子价格为对偶价格的相反数 1 单纯形表的灵敏度分析 求使所得新的解仍可行 0 的bj的变化范围 即使其新的最优解的基变量 最优基 都不变 且其对偶价格不变的 二 约束方程中常数项的灵敏度分析 由于行行初等变换 最终单纯形表系数矩阵不变 基变量系数cB不变 zj都不变 j都不变 基变量都不变 1 单纯形表的灵敏度分析 原始的约束方程组 迭代 对原系数矩阵行初等行变换 变成以B为基的最终单纯形表 即对原来约束方程组左乘B 1 原始的最终单纯形表中系数矩阵 原始的最终单纯形表中基变量xB的解为 1 单纯形表的灵敏度分析 原始的最终单纯形表中基变量xB变为x B 其中Dk为B 1的第k列 1 单纯形表的灵敏度分析 为使新的基本解x B的各分量均非负即 1 单纯形表的灵敏度分析 以第二章例1在最终单纯形表上对行b1灵敏度分析 在第一个约束方程中含有松弛变量s1 其对应的列为 1 2 0 T xB为 50 50 250 T 由 得到时第1个约束条件的对偶价格不变 实际意义 当设备台时数在250与325之间变化时 该约束条件即设备台时数的对偶价格不变 都为每设备台时50元 1 单纯形表的灵敏度分析 三 约束方程系数矩阵A灵敏度分析 1 最终单纯形表上xk是非基变量xk的初始单纯形表的系数列 xk的系数列 zk以及 k变化 其他均不变 最终单纯形表中新的系数列 z k k 若 k 0 则原最优解仍然为最优解 若 k 0 则继续行迭代以求出最优 1 单纯形表的灵敏度分析 例1 以第二章例1为基础 该厂除生产 种产品外 现试制新产品 已知生产产品 每件需要设备2台时 A原料0 5公斤 B原料1 5公斤 获利150元 问该厂是否该生产该产品 生产多少 分析 这是一个增加新变量的问题 可以认为是改变x3在初始表上的系数列的问题 1 单纯形表的灵敏度分析 1 首先 在最终单纯形表中直接插入新的列 2 在最终单纯形表中找到B 1 求出B 1p6 替换该列系数 3 求出该列zj j 新变量的 6 0 所以原问题的最优解就是新问题的最优解 是否可以在最终单纯形表中直接插入x3这一新的列 1 单纯形表的灵敏度分析 例2 假设例1中产品 的工艺结构有了改 生产1件 产品需要用1 5台设备 原料A为2千克 原料B为1千克 每件 产品的利润为160元 问该厂的生产计划是否要修改 1 单纯形表的灵敏度分析 解 首先求出x3在最终表上的系数列B 1P 6 zj j 由于 6 0 可知此解不是最优解 需要行第3次迭代 1 单纯形表的灵敏度分析 1 单纯形表的灵敏度分析 2 在初始表上的变量xk的系数pk改变为p k 经过迭代后 在最终表上xk是基变量 该情况原最优解的可行性和最优解都可能被破坏 问题变得复杂 一般不修改原最终表 而是重新计算 1 单纯形表的灵敏度分析 第二章例1 若该厂除在设备台时及原材料A B上有限制外 还有电力供应限制 最高供应电量为5000度 而生产一个产品 需用电10度 一个产品 需用电30度 试分析此时该厂获得最大利润的生产计划 四 增加一个约束条件的灵敏度分析 1 单纯形表的灵敏度分析 解 将原问题的最优解x1 50 x2 250代入用电量的约束条件10 x1 30 x2 5000得10 50 30 250 500 7500 5000 所以原题的最优解不是本题的最优解 需要将新的约束条件标准化加入到原问题最终单纯形表中继续迭代 1 单纯形表的灵敏度分析 1 在用电量的约束条件中加入松弛变量s4后得 10 x1 30 x2 s4 5000把这个约束条件加入到原最终单纯形表上 其中s4为基变量 1 单纯形表的灵敏度分析 表中的x1 x2不是单位向量 故需行初等行变换 把上表中的s4行的约束可以写为 10s1 20s3 s4 3000 上式两边乘以 1 加上人工变量a1 10s1 20s3 s4 a1 3000a1代替s1成为基变量 1 单纯形表的灵敏度分析 1 单纯形表的灵敏度分析 最优解为x1 140 x2 120 s1 40 s2 s4 a1 0 s3 130即该工厂在添加了用电限量以后的最优生产计划为 产品生产140件 产品生产120件 线性规划的对偶问题 单纯形表的灵敏度分析 对偶规划的基本性质 对偶单纯形法种特殊情况 2 线性规划的对偶问题 每一个线性规划问题 都存在一个与它密切相关的线性规划的问题 称其中一个为原问题 另一个为对偶问题 例 某厂在计划生产 和 两种产品 生产单位产品所需设备A B C台时如表所示 该厂每生产1单位产品 获利50元 1单位产品 获利100元 该厂应分别生产多少 和 产品 才能获利最多 2 线性规划的对偶问题 解 设x1为产品 的计划产量 x2为产品 的计划产量 目标函数 maxz 50 x1 100 x2约束条件 x1 x2 3002x1 x2 400 x2 250 x1 x2 0 2 线性规划的对偶问题 从另一个角度来考虑该问题 假如有另外一个工厂要求租用该厂的设备A B C 那么该厂的厂长应该如何来确定合理的租金呢 2 线性规划的对偶问题 对出租者 生产单位 产品所需各设备台时的总租金不应低于原利润50元 y1 2y2 50同样对于产品 y1 y2 y3 100 设y1 y2 y3为设备A B C的每台时的租金 扣除成本后的利润 对租用者 在出租者愿意出租的前提下 尽量要求全部设备台时的总租金越低越好 min300y1 400y2 250y3 2 线性规划的对偶问题 目标函数 minf 300y1 400y2 250y3约束条件 y1 2y2 50y1 y2 y3 100y1 y2 y3 0 模型如下 目标函数 maxz 50 x1 100 x2约束条件 x1 x2 3002x1 x2 400 x2 250 x1 x2 0 最大利润 最小租金 原问题 对偶问题 2 线性规划的对偶问题 两个模型的关系 2 线性规划的对偶问题 原问题 对偶问题 Am n为矩阵 原问题有m个约束条件n个变量 AT是A的转置 变量 系数矩阵 目标系数 bT是b的转置 cT是c的转置 常数项 2 线性规划的对偶问题 用单纯形法求对偶问题的解 加上剩余变量s1 s2和人工变量a1 把对偶问题化成标准形式 max f 300y1 400y2 250y3 Ma1约束条件 y1 2y2 s1 a1 50y1 y2 y3 s2 100y1 y2 y3 s1 s2 a1 0 2 线性规划的对偶问题 最优解 y1 50 y2 0 y3 50 s1 0 s2 0 a1 0 f的最大值为 27500 目标函数f最小值为27500元 2 线性规划的对偶问题 每台时的租金 A 50元 B 0元 C 50元 所有设备出租共得租金27500元 对租用者来说是出租者愿意出租设备的最小费用 最优解 y1 50 y2 0 y3 50 s1 0 s2 0 a1 0 目标函数f最小值27500元 对偶问题的最优解即最佳租金 恰好等于原问题各种设备的对偶价格 两个问题的最优值相等 2 线性规划的对偶问题 如何写出一个线性规划问题的对偶问题 例 写出下列问题的对偶问题maxz 3x1 4x2 6x3约束条件 2x1 3x2 6x3 4406x1 4x2 x3 100 5x1 3x2 x3 200 x1 x2 x3 0 2 线性规划的对偶问题 maxz 3x1 4x2 6x3st 2x1 3x2 6x3 440 x1 x2 x3 0 3 约束条件均 0 1 6x1 4x2 x3 100 6x1 4x2 x3 100 5x1 3x2 x3 200 5x1 3x2 x3 200 5x1 3x2 x3 200 2 线性规划的对偶问题 maxz 3x1 4x2 6x3s t 2x1 3x2 6x3 440 6x1 4x2 x3 1005x1 3x2 x3 200 5x1 3x2 x3 200 x1 x2 x3 0 minf 440y1 100y2 200y 3 200y 3s t 2y1 6y2 5y 3 5y 3 3 3y1 4y2 3y 3 3y 3 4 6y1 y2 y 3 y 3 6 y1 y2 y 3 y 3 0 2 线性规划的对偶问题 minf 440y1 100y2 200 y 3 y 3 s t 2y1 6y2 5 y 3 y 3 3 3y1 4y2 3 y 3 y 3 4 6y1 y2 y 3 y 3 6 y1 y2 y 3 y 3 0 y 3 y 3为了表示这两个决策变量都来源于原问题的第三个约束条件 因为在该对偶问题中y 3和y 3的系数为相反数 从而可以 令y3 y 3 y 3 2 线性规划的对偶问题 minf 440y1 100y2 200y3s t 2y1 6y2 5y3 3 3y1 4y2 3y3 4 6y1 y2 y3 6 y1 0 y2 0 y3无非负限制 y3可正 可负 可 0 2 线性规划的对偶问题 当原线性规划的第i个约束条件取 其对偶问题的i个决策变量无非负限制 若原线性规划的第i个决策变量无非负限制时 可用 行替换 其中 0 0 用类似的方法可知其对偶问题中第i个约束条件取 2 线性规划的对偶问题 用 0的两个决策变量之差来代替无非负限制的决策变量也是求解含有无非负限制的决策变量的线性规划问题的一种方法 minf 3x1 9x2 4x3s t x1 2x2 3x3 180 5x1 3x2 240 x1