管理运筹学--单纯形法的灵敏度分析与对偶对偶问题.ppt

分别用大M法和两阶段法求解下列线形规划问题 并指出解的类型 minZ 2x1 3x2 x3x1 4x2 2x3 8S t 3x1 2x2 6x1 x2 x3 0时间 1 40 2 10 初始单纯形表格 最终单纯形表格 第六章单纯形法的灵敏度分析与对偶 DUAL 窗含西岭千秋雪 门泊东吴万里船对偶是一种普遍现象 1单纯形表的灵敏度分析 重点 难点 掌握 2线性规划的对偶问题 重点 理解 掌握 3对偶规划的基本性质 重点 应用 4对偶单纯形法 难点 掌握 前面已讲 学习重点与难点 1单纯形表的灵敏度分析 重点 难点 掌握 2线性规划的对偶问题 一 对偶问题实例 例1某工厂生产甲 乙两种产品 要消耗A B和C三种资源 已知每件产品对这三种资源的消耗 这三种资源的现有数量和每件产品可获得的利润如表所示 问 如何安排生产计划 使得既能充分利用现有资源又使总利润最大 该问题的数学模型为 maxZ 1500 x1 2500 x2s t 3x1 2x2 65A资源2x1 x2 40B资源3x2 75C资源x1 x2 0 考虑 1 定价不能太高 2 定价不能太低 假设该厂现自己不生产 因而要转让资源A B和C 请问他们应如何给这三种资源定价 咋办 设A B C资源的出售价格分别为y1 y2和y3 1500 2500 0 原问题 maxZ 1500 x1 2500 x2s t 3x1 2x2 65A资源2x1 x2 40B资源3x2 75C资源x1 x2 0 对偶问题 MinW 65y1 40y2 75y3s t 3y1 2y2 15002y1 y2 3y3 2500y1 y2 y3 0 2103 A 654075 b 15002500 c 20213 A 15002500 b 654075 c max min 对偶问题MinW bTYs t ATY CTY 0 max b A C CT AT bT min m n m n 二 对偶问题的形式1 对称型对偶问题 原问题MaxZ cXs t AX bX 0 对偶关系表 由表可以看出 从行看是原问题 从列看是对偶问题 两个问题的变量系数矩阵互为转置矩阵 原问题 的常数项是对偶问题 的目标系数 反之 原问题 的目标系数是对偶问题 的常数项 原问题 有n个决策变量 对偶问题 有n个约束方程 原问题有m个约束方程 对偶问题就有m个决策变量 原问题的约束是 型 对偶问题的约束是 型 原问题的目标函数是求极大 对偶问题的目标是求极小 maxZ 5x1 4x2 例2请给出下列线性规划问题的对偶问题 对称型线性规划问题 怎么样简单吧 2 非对称型对偶问题表对偶变换的规则 约束条件的类型 规范与否 与非负条件相互对应非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的 好难记呀 例3 Minz 5x1 25x27x1 75x2 98s t 5x1 6x2 7824x1 12x2 54x1 0 x2 0 Maxw 98y1 78y2 54y37y1 5y2 24y3 5s t 75y1 6y2 12y3 25y1 0 y2无限制 y3 0 怎么样 没问题吧 对称形式线形规划问题为 MaxZ cXs t AX bX 0 加上松弛变量化为标准形后为 MaxZ cX 0Xss t AX IXs bX 0 Xs 0 3对偶规划的基本性质 一 单纯形法计算的矩阵描述 检验数 j 当迭代若干步 基变量为XB时 新的单纯形表 b XS 0 Cj XBXNXS BNI CBCN0 CBCN0 检验数 j B 1b XB CB Cj XBXNXS IB 1NB 1 0CN CBB 1N CBB 1 CBCN0 初始单纯形表为 maxZ 3x1 5x2 0 x3 0 x4 0 x5 0 x1 x3 8 2x2 x4 12 3x1 4x2 x5 36 举例 最优基 最优基的逆 最优基和最优基的逆 maxZ 2x1 x25x2 15s t 6x1 2x2 24x1 x2 5x1 x2 0 maxZ 2x1 x2 0 x3 0 x4 0 x55x2 x3 15s t 6x1 2x2 x4 24x1 x2 x5 5x1 x2 x3 x4 x5 0 例4 对称形线性规划问题 标准型 j x3x1x2 021 000 1 4 1 2 x1x2x3x4x5 CBXBb CB j 21000 x3x4x5 000 1505100 2462010 511001 21000 初始单纯形表 最终单纯形表 B P3 P1 P2 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 B 1 P 3 P 4 P 5 初表中 终表中 minZ 2x1 3x2 x3x1 4x2 2x3 8S t 3x1 2x2 6x1 x2 x3 0 初始单纯形表格 最终单纯形表格 maxZ 50 x1 100 x2x1 x2 300s t 2x1 x2 400 x2 250 x1 x2 0 maxZ 50 x1 100 x2 0 x3 0 x4 0 x5x1 x2 x3 300s t 2x1 x2 x4 400 x2 x5 250 x1 x2 x3 x4 x5 0 例5 对称形线性规划问题 x1x2x3x4x5 CBXBb CB j x3x4x5 000 30011100 40021010 25001001 50100000 原问题初始单纯形表 50100000 已知最优基的基变量为x1 x4 x2 请直接写出该线性规划问题的最终单纯形表 并给出其对偶问题的最优解 最优基为B p1 p4 p2 B 1 p3 p4 p5 b B 1b j Cj CBB 1Pj x1x2x3x4x5 CBXBb CB j x1x4x2 500100 501010 1 5000 211 25001001 00 500 50 原问题最终单纯形表 50100000 原问题初始单纯形表 x1x2x3x4x5 CBXBb CB j x3x4x5 000 40021010 25001001 50100000 50100000 30011100 检验数 j 当迭代若干步 基变量为XB时 新的单纯形表 b XS 0 Cj XBXNXS BNI CBCN0 CBCN0 检验数 j B 1b XB CB Cj XBXNXS IB 1NB 1 0CN CBB 1N CBB 1 CBCN0 初始单纯形表为 对应初始单纯表中的单位矩阵I 迭代后的单纯形表中为B 1初始单纯表中的基变量Xs b 迭代后的单纯形表中为XB B 1b初始单纯表中的约束系数矩阵为 A I B N I 迭代后的单纯形表中约束系数矩阵为 B 1A B 1I B 1B B 1N B 1I I B 1N B 1 若初始矩阵中变量xj的系数向量为Pj 迭代后为Pj 则有 Pj B 1Pj 小结 当B为最优基时 迭代后的单纯表中检验数 CN CBB 1N 0 CBB 1 0因XB的检验数可写为 CB CBB 1B故可重写为 C CBB 1A 0 CBB 1 0CBB 1称为单纯形乘子 若令YT CBB 1则 C YTA 0ATY C所以 ATY CTY 0 可见检验数的相反数恰好是其对偶问题的一个可行解 将这个解代入对偶问题的目标函数 有 W YTb CBB 1b Z 当原问题为最优解时 这时对偶问题为可行解 且两者具有相同的目标函数值 根据对偶问题的基本性质 将看到这时对偶问题的解也为最优解 所以从最优解的单纯形表中同时可以得到其对偶问题的最优解 maxZ 2x1 x25x2 15s t 6x1 2x2 24x1 x2 5x1 x2 0 maxZ 2x1 x2 0 x3 0 x4 0 x55x2 x3 15y1s t 6x1 2x2 x4 24y2x1 x2 x5 5y3x1 x2 x3 x4 x5 0 minW 15y1 24y2 5y36y2 y3 y4 2x1s t 5y1 2y2 y3 y5 1x2y1 y2 y3 y4 y5 0 minW 15y1 24y2 5y36y2 y3 2s t 5y1 2y2 y3 1y1 y2 y3 0 例5 对称形线性规划问题 对偶问题 标准型 x1x2x3x4x5 CBXBb CB j 21000 x3x1x2 021 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 000 1 4 1 2 y1y2y3y4y5 CBXBb CB j 15 24 500 y2y3 24 5 1 4 5 410 1 41 4 1 215 2011 2 3 2 15 200 7 2 3 2 y4 y5 y1 y2 y3 x3 x4 x5 x1 x2 原问题最终单纯形表 对偶问题最终单纯形表 松弛变量 对偶变量 剩余变量 决策变量 例6 利用原问题的最优单纯形表求解对偶问题的最优解 s t 100 100 0解 对偶问题为s t 4 3 7 0 最终单纯形表格 x4x5松弛变量 可见原问题的最优解为 X 0 25 25 T其对偶问题的最优解为 y 1 2 2 T 为了便于讨论 下面不妨总是假设 定理1 对称性定理 对偶问题的对偶是原问题 根据对称性定理 在任一对偶问题中 可以把其中的任何一个称为原问题 而把另一个称为其对偶问题 对偶问题 原问题 二 对偶问题的基本性质 证明 由前面可知对偶问题为 等价于该问题 可见此问题为对称型的规划问题 其对偶问题表示为 令Z f 则化简为 即为原问题 可见对偶问题的对偶是原问题 证毕 定理2 弱对偶性定理 对偶问题 min 的任何可行解Y0 其目标函数值总是不小于原问题 max 任何可行解X0的目标函数值 证 假设X0 Y0分别为原问题和对偶问题的可行解 故有 1 2 因为Y0是对偶问题的可行解 用Y0T左乘 1 得 Y0TAX0 Y0Tb转置得 X0TATY0 bTy0因为X0是原问题的可行解 用X0左乘 2 得 X0TATY0 X0TCT转置得 Y0TAX0 CX0可见CX0 Y0TAX0 Y0Tb bTY0即CX0 bTY0 例7 应用弱对偶定理 证明下列线性规划问题的最大值不超过1 证明 该线性问题的对偶问题为 弱对偶定理推论 推论1最优解判别定理 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等 则X0 Y0分别是相应问题的最优解 证 由弱对偶定理可知结论是显然的 即CX0 bTY0 CX bTY0 CX0 Yb 证毕 推论2如果原max min 问题为无界解 则其对偶min max 问题无可行解 反之不然 maxZ x1 x2x1 x2 1s t x1 x2 1x1 x2 0 minW y1 y2y1 y2 1s t y1 y2 1y1 y2 0 原问题和对偶问题同时无可行解 推论3原问题 max 的任何可行解目标函数值是其对偶问题 min 目标函数值的下界 原问题 min 的任何可行解目标函数值是其对偶问题 max 目标函数值的上界推论4如果原问题max min 有可行解 其对偶问题min max 无可行解 则原问题为无界解 例8 应用对偶理论证明下列线性规划问题目标函数值无界 s t 证明 是线性问题的可行解 即该问题存在可行解 又 其对偶问题为 定理3主对偶定理 强对偶性定理 如果原问题和对偶问题都有可行解 则它们都有最优解 且它们的最优解所对应的目标函数值相等 证 由弱对偶定理推论1可知 原问题和对偶问题的目标函数有界 故一定存在最优解 现证明定理的后一句话 设X0为原问题的最优解 它所对应的基矩阵是B X0 B 1b 则其检验数满足C CBB 1A 0令Y0 CBB 1 则有Y0A C显然Y0为对偶问题的可行解 因此有对偶问题目标函数值 W Y0b CBB 1b而原问题最优解的目标函数值为Z CX0 CBB 1b故由最优解判别定理可知Y0为对偶问题的最优解 证毕 定理4互补松弛定理定理设X0 Y0分别是原问题和对偶问题的可行解 U0为原问题的松弛变量的值 V0为对偶问题剩余变量的值 X0 Y0分别是原问题和对偶问题最优解的充分必要条件是Y0U0 V0X0 0 证 由定理所设 可知有AX0 U0 bX0 U0 0 1 Y0A V0 CY0 V0 0 2 分别以Y0左乘 1 式 以X0右乘 2 式后 两式相减 得Y0U0 V0X0 Y0b CX0若Y0U0 V0X0 0 根据最优解判别定理 X0 Y0分别是原问题和对偶问题最优解 反之亦然 证毕 例9 考虑下列原始线性规划 1 写出其对偶问题 2 已知 3 2 0 是上述原始问题的最优解 根据互补松弛定理 求出对偶问题的最优解 3 如果上述规划中的第一个约束为资源约束 写出这种资源的影子价格 解 1 对偶问题 2 由题知原问题的最优解为 由互补松弛定理得 在对偶问题中对应第一 二个约束为紧约束 第三个约束条件为松约束 即 对偶规划问题的最优解 3 影子价格为y1 4 1 4 1 例10 利用互补松弛定理 原问题检验数与对偶问题的解的总结在主对偶定理 强对偶性 的证明中我们有 对偶 min型 变量的最优解等于原问题松弛变量的机会成本 或者说原问题松弛变量检验数的绝对值容易证明 对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的 因此对偶问题的检验数与原问题的解也有类似上述关系 更一般地讲 不管原问题是否标准 在最优解的单纯型表中 都有原问题虚变量 松弛或剩余 的检验数对应其对偶问题实变量 对偶变量 的最优解 原问题实变量 决策变量 的检验数对应其对偶问题虚变量 松弛或剩余变量 的最优解 因此 原问题或对偶问题只需求解其中之一就可以了 4对偶单纯形法 一 对偶单纯形法的基本思路 单纯形迭代要求每步都是基本可行解达到最优解时 检验数cj zj 0 max 但对于所加的剩余变量无法构成初始基础可行解 因此通过加人工变量来解决大M法和二阶段法较繁能否从剩余变量构成的初始基础非可行解出发迭代 但保证检验数满足最优条件 cj zj 0 max 0 0 二 对偶单纯形法的计算步骤 对某线形规划问题存在一个对偶问题的可行基 即必须所有的cj zj 0 bi的值不要求全为正 1 确定换出变量 离基变量 在小于0的b中找出最小者 其所对应的变量xr为换出变量2 确定换入变量 进基变量 min j arj arj 0 k ark其所对应的变量xk为换入变量3 确定主元素 ark为主元素4 用换入变量替换换出变量 继续迭代得到一个新的基5 检查是否所有的bi 0 如是 找到了两者的最优解 否则返回第一步循环进行 例12 对偶单纯形法的计算过程 x1x2x3x4x5 CBXBb CB j 15 5 1100 x4x5 00 5 3 2 210 4 5 1 201 15 5 1100 初始单纯形表 15 35 211 2 j x2x5 50 5 23 21 1 1 20 3 2 7 20 1 1 21 15 20 6 5 20 15 7 65 j 5 15 13 7014 7 5 73 7 3 7102 71 7 2 7 00 27 7 10 7 15 7 x2x1 最终单纯形表 负数中最小者 比值中最小者 检验数 j 当迭代若干步 基变量为XB时 新的单纯形表 b XS 0 Cj XBXNXS BNI CBCN0 CBCN0 检验数 j B 1b XB CB Cj XBXNXS IB 1NB 1 0CN CBB 1N CBB 1 CBCN0 初始单纯形表为 1单纯形表的灵敏度分析 灵敏度分析所研究的问题是 当某一规划的最优解已知的情况下 某数据发生变化后对最优解产生的影响 原数据发生变化的主要原因可能有原始数据不可靠或准确度不高 实际问题的条件模糊不清或被忽略 最优解执行一段时间后环境条件发生变化等 因此我们有必要研究以下问题 当某些系数变化 最优解改变多少 当增加或减少变量 最优解改变多少 当增加或减少约束条件时 问题的最优解改变多少 最优解不改变时 某些系数的允许变化范围又有多大 系数包括 目标函数中的价值系数cj 约束条件中的常数项bi 约束条件中的技术系数aij 灵敏度分析的步骤如下 将参数的改变通过计算反映到最终单纯表上来 检查原问题是否仍为可行解 检查对偶问题是否仍为可行解 按下表所列情况的出结论或决定继续计算的步骤 可行解可行解 问题的最优解或最优基不变 可行解非可行解 非可行解可行解 非可行解非可行解 用单纯形法继续迭代求最优解 用对偶单纯形法继续迭代求最优解 引进人工变量 编制新的单纯形表重新计算 灵敏度分析的主要内容 一 目标函数系数的灵敏度分析二 约束条件的常数项的灵敏度分析三 增加或减少决策变量的灵敏度分析四 系数矩阵的灵敏度分析五 增加或减少约束条件的灵敏度分析 一 目标函数系数的灵敏度分析 目标函数中价值系数Cj的变化只会引起检验数 j的变化 所以将Cj的变化直接反映到最终单纯形表中 只可能出现表中前两种情况 例13佳美公司计划制造 两种产品 已知各制造一个单位产品时 分别占用的设备A B的台时 调试时间 每天设备A B的台时 调试工序可用于这两种产品的能力及各售出一单位时的获利情况 如表所示 1 问应怎样组织生产才能使总利润最多 2 如果产品 的利润降至1 5百元 单位 而产品 的利润增至2百元 单元时 最优生产计划有何变化 3 如果产品 的利润不变 则产品 的利润在什么范围内变化时 该公司的最优生产计划将不发生变化 解 设分别表示 两种产品的生产数量 可建立如下线性规划模型 maxZ 2x1 x25x2 15s t 6x1 2x2 24x1 x2 5x1 x2 0 maxZ 2x1 x2 0 x3 0 x4 0 x55x2 x3 15s t 6x1 2x2 x4 24x1 x2 x5 5x1 x2 x3 x4 x5 0 y Y1Y2y3 j x3x1x2 021 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 000 1 4 1 2 可见原问题具有唯一最优解 思考 对偶问题的最优解和最优值 x1x2x3x4x5 CBXBb CB j 21000 x3x4x5 000 1505100 2462010 511001 000 1 4 1 2 初表 终表 将产品 的利润变化直接反映到最终单纯形表中得表 因非基变量的检验数大于零 故需继续用单纯形法迭代计算 2 如果产品 的利润降至1 5百元 单位 而产品 的利润增至2百元 单元时 最优生产计划有何变化 x1x2x3x4x5 CBXBb CB j 000 x3x1x2 021 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 000 1 4 1 2 21 1 52 01 52 0001 8 9 4 CBXBb CB j 000 x3x1x2 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 1 52 01 52 0001 8 9 4 x1x2x3x4x5 614 j x4x1x2 6004 51 6 210 1 501 3011 500 01 52 00 1 100 3 2 可见变化后的问题具有唯一最优解 X 2 3 T 3 如果产品 的利润不变 则产品 的利润在什么范围内变化时 该公司的最优生产计划将不发生变化 x1x2x3x4x5 CBXBb CB j 2000 x3x1x2 021 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 000 1 4 1 2 1 解 设产品 的利润为c2元 反映到最终单纯形表中 得表 c2 c2 000 1 2 1 4c21 3 2c2 为使表中的解仍为最优解 应有 1 2 1 4c2 01 3 2c2 0 即产品 的利润的变化范围是 2 3 2 解得 2 3 c2 2 二 约束条件的常数项的灵敏度分析 在现实问题中 约束条件的右端常数项 往往代表资源的限制量 一般来说 资源的限制量不是一成不变的 而是随生产条件 市场供应情况进行变动 所以人们常常想知道 对于一个确定的优方案 当资源增加或减少多少时 对方案的影响将有多大 这种类型的灵敏度分析就是处理该类问题的方法 现假定问题的第l种资源限制 由于常数项的改变 对最优判别准则的检验数无关 即是说 最优基对应的单纯变量表中的最后一行不发生变化 而表中的基变量是否可行还需讨论 所以只可能出现表中1 3两种情况 例14在上述佳美公司的例子中 1 若设备A和调试工序的每天能力不变 而设备B每天的能力增加到32小时 分析公司最优计划的变化 2 若设备A和B每天可用能力不变 则调试工序能力在什么范围内变化时 问题的最优基不变 解 1 由题意得变化后的b为b 所以有 B 1b B 1 由最终单纯形表得原最优基的逆矩阵 b 将其反映到最终单纯形表中 CBXBb CB j x3x1x2 021 0015 4 15 2 1001 4 1 2 010 1 43 2 000 1 4 1 2 x1x2x3x4x5 21000 j 1505100 511001 20 401 6 0 100 2 x3x1x4 020 35 211 2 1 2 可见变化后的问题具有唯一最优解 X 5 0 TZ 10 第二种解法利用变化率 所以有 B 1 b 将其反映到最终单纯形表中 因为B 1b B 1 b b B 1b B 1 b 终表中的第三列 b b b 解 CBXBb CB j x3x1x2 021 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 000 1 4 1 2 x1x2x3x4x5 21000 j 1505100 511001 20 401 6 0 100 2 x3x1x4 020 10 35 2 2 11 2 2 1 2 可见变化后的问题具有唯一最优解 X 5 0 TZ 10 2 若设备A和B每天可用能力不变 则调试工序能力在什么范围内变化时 问题的最优基不变 解法一 设调试工序每天可用能力为b3小时 B 1b 要使问题的最优基不变 只要其新的b列数全部大于等于零 即 45 15 2b3 06 1 2b3 0 6 3 2b3 0 4 b3 6 由此调试工序的能力应在4 6小时之间 b 解法二 设调试工序每天可用能力为5 b3 B 1 b 将其反映到最终单纯形表中 其b列数字为 B 1b 当B 1b 0时 问题的最优基不变 解得 1 b3 1 4 5 b3 6 由此调试工序的能力应在4 6小时之间 因为B 1b B 1 b b B 1b B 1 b 终表中的第三列 b b b 三 决策变量的灵敏度分析 在讨论一个规划问题时 从资源的充分利用角度考虑 有时认为多安排一些生产项目是有利的 这反映在线性规划模型上是增添决策变量的问题 另一方面当规划执行一段时间后 资源的供应不能满足要求时 有时也要考虑少安排一些生产项目是有利的 这反映在数模上就是减少决策变量的问题 所以 决策变量个数的变化有两种情况 一是增多 一是减少 现分别在下面讨论 1 增加决策变量的灵敏度分析 设已知增加的新变量xj的目标函数为cj 相应的约束系数为aij 或表示为Pj 其分析步骤为 2 计算检验数 1 计算P j B 1Pj 3 若 j 0 原最优解不变 只需将计算得到P j的 j和直接写入最终单纯形表中 若 j 0 则按单纯形法继续迭代计算找出最优解 例15 在佳美公司例子中 设该公司又计划推出新产品 生产一单位产品 所需设备A B及调试工序的时间分别为3小时 4小时 2小时 该产品的预期盈利为3百元 单位 试分析该新产品是否值得投产 如投产对该公司的最优生产计划有何变化 解 设新产品 的生产数量为x6件 有 将其反映到最终单纯形表中得表 P 6 B 1P6 x1x2x3x4x5 CBXBb CB j 21000 x3x1x2 021 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 000 1 4 1 2 j 51 407 213 8 9 40 7 21001 4 1 20 3 401 20 1 83 41 0 1 20 1 8 5 40 x3x1x6 023 可见变化后的问题具有唯一最优解 X 7 2 0 TZ 37 4 比原方案17 2获利多 所以值得生产 7 0 2 x6 3 1 2 减少决策变量的灵敏度分析 若减少的决策变量不在最优解的基变量之中 是非基变量 对这种情况可以认为决策变量本来就是多余的 减少这个变量不影响最优解 最优值 j 5 15 13 7014 7 5 73 7 3 7102 71 7 2 7 00 27 7 10 7 15 7 x2x1 x1x2x3x4x5 CBXBb CB 15 5 1100 减少决策变量x3 最优生产计划如何 2 减少决策变量的灵敏度分析 若减少的决策变量是基变量 要考虑去掉这个变量的影响 可用单纯形法或对偶单纯形法重新求解 j 5 15 13 7014 7 5 73 7 3 7102 71 7 2 7 00 27 7 10 7 15 7 x2x1 x1x2x3x4x5 CBXBb CB 15 5 1100 j 11 15 13 4011 5 43 4 1 21001 2 1 2 000 25 43 4 x3x1 x1x2x3x4x5 CBXBb CB 15 5 1100 引入人工变量x6 采用大M法继续求解 减少决策变量x2 最优生产计划如何 四 系数矩阵的灵敏度分析 aij的变化使线形规划的约束系数矩阵A发生变化 若变量xj在最终单纯性表中为非基变量 其约束条件中系数aij的变化分析步骤可参照三中增加决策变量的情形 若变量xj在最终单纯性表中为基变量 其约束条件中系数aij的变化将使相应的B和B 1发生变化 因此有可能出现原问题和对偶问题均为非可行解的情况 出现这种情况时 需要引进人工变量先将原问题的解转化为可行解 再用单纯性法求解 下面就变量xj在最终单纯性表中为基变量这种情形举例说明 例16 在佳美公司的例子中 若产品 每单位需设备A B和调试工时8小时 4小时 1小时 该产品的利润变为3百元 单位 试重新确定该公司最优生产计划 解 先将生产工时变化后的产品 看作是一种新产品 生产量为x 2 按本节三的方法直接计算 2和P 2 2 3 0 1 4 1 2 3 2 P 6 将其反映到最终单纯形表中得表 x1x2x3x4x5x 2 CBXBb CB j 210003 x3x1x2 021 15 20015 4 15 211 2 7 21001 4 1 21 2 3 2010 1 43 21 2 000 1 4 1 23 2 原问题与对偶问题均为非可行解 故先设法使原问题变为可行解 j 907 214 240 21001 2 20 301 20 1 231 0 1 201 2 50 x3x1x 2 023 j 3 80 1 24 1 6101 24 11 41 1 121 6001 12 15 801 8001 1 8 0 5 24 1 300 M 5 24 x5x1x 2 023 j 90 1 42401 2101 2 200 300 1 2310 0 M1 2 4M 5 24M00 x6x1x 2 M23 x1x3x4x5x 2x6 CBXBb CB 20003 M x3 4x4 24x5 9 x3 4x4 24x5 x6 9 可见变化后的问题具有唯一最优解 X 11 4 15 8 TZ 89 8 五 增加或减少约束条件的灵敏度分析 增加一个约束条件在实际问题中相当增添一道工序 设在原线性规划问题中 增加一个新的约束条件 代入新增加的约束条件 如果条件满足 则原问题的最优解仍为新问题的最优解 结束 如果条件不满足 则将新增加的约束条件直接反映到最终单纯形表中再进一步分析 则首先把已求得的原问题的最优解 例17 假设产品 经调试后 还需经过一道环境试验工序 产品 每单位须环境试验3小时 产品 每单位须2小时 又环境试验工序每天生产能力为12小时 试分析增加该工序后的佳美公司最优生产计划 解 环境试验工序的约束条件为 3x1 2x2 12将原问题的最优解 x1 7 2 x2 3 2代入环境试验工序的约束条件 3 7 2 2 3 2 27 2 可见新增加的约束条件对原问题的最优解起作用 所以原问题的最优解不是本问题的最优解 12 以x6为基变量将其反映到最终单纯形表中 将3x1 2x2 12化为标准型3x1 2x2 x6 12 x1x2x3x4x5 CBXBb CB j 21000 x3x1x2 021 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 000 1 4 1 2 0 x61232000 0 x600010 1 2 3 4 因为表中x1 x2列不是单位向量 所以需要进行变换 x1x2x3x4x5x6 CBXBb CB j 210000 x3x1x2 021 15 20015 4 15 20 7 21001 4 1 20 3 2010 1 43 20 000 1 4 1 20 0 x6 3 2000 1 4 3 21 1 2 3 4 x1x2x3x4x5x6 CBXBb CB j 210000 x3x1x2 021 150015 20 5 41001 30 1 3 0010 1 201 000 1 60 1 3 0 x510001 61 2 3 可见变化后的问题具有唯一最优解 X 4 0 TZ 8 例18 假设产品 经调试后 还需经过一道环境试验工序 产品 每单位须环境试验3小时 产品 每单位须2小时 又环境试验工序每天生产能力至少为15小时 试分析增加该工序后的佳美公司最优生产计划 解 环境试验工序的约束条件为 3x1 2x2 15将原问题的最优解 x1 7 2 x2 3 2代入环境试验工序的约束条件 3 7 2 2 3 2 27 2 可见新增加的约束条件对原问题的最优解起作用 所以原问题的最优解不是本问题的最优解 以x6为基变量将其反映到最终单纯形表中 将3x1 2x2 15化为标准型 3x1 2x2 x6 15 可以采用大M法 最好采用对偶单纯形法 避免用人工变量 x1x2x3x4x5 CBXBb CB j 21000 x3x1x2 021 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 000 1 4 1 2 0 x6 15 3 2000 0 x600010 1 2 3 4 因为表中x1 x2列不是单位向量 所以需要进行变换 x1x2x3x4x5x6 CBXBb CB j 210000 x3x1x2 021 15 20015 4 15 20 7 21001 4 1 20 3 2010 1 43 20 000 1 4 1 20 0 x6 3 20001 43 21 1 2 3 4 可见变化后的问题没有可行解 对偶问题具有无界解 减少约束条件的灵敏度分析 减少一个约束条件在实际问题中相当去掉一道工序 即在原线性规划问题中 去掉一个约束条件 反映到最终单纯形表中就是去掉一行 重新计算检验数行 可能利用单纯形法继续求解 j x3x1x2 021 15 20015 4 15 2 7 21001 4 1 2 3 2010 1 43 2 000 1 4 1 2 x1x2x3x4x5 CB 21000 终表 CBXBb 010 1 21 该问题存在无界解 假如去掉调试工序 原问题的最优生产方案如何 以上的几种灵敏度分析 仅限于某数值 变量 约束条件的变化对解的影响 这是一些基本的分析方法 若要考虑某区间上一个或几个参数作连续变化的灵敏度分析 请同学们参阅线性规划方面的资料或书籍 对偶问题的经济解释影子价格 补充内容 30 20 10 maxZ 5x1 4x2s t x1 3x2 90 2x1 x2 80 x1 x2 45 x1 x2 0 由图示可知最优点为B 35 10 最优值为215 100 80 60 40 20 20 40 60 80 x1 100 B 1 影子价格含义的图解法 20 10 maxZ 5x1 4x2s t x1 3x2 91 2x1 x2 80 x1 x2 45 x1 x2 0 由图示可知最优点为B 35 10 最优值为215称为资源A的影子价格为0 100 80 60 40 20 20 40 60 80 x1 100 B 30 20 10 maxZ 5x1 4x2s t x1 3x2 90 2x1 x2 81 x1 x2 45 x1 x2 0 由图示可知最优点为B 36 9 最优值为216称为资源B的影子价格为1 100 80 60 40 20 20 40 60 80 x1 100 B 20 10 maxZ 5x1 4x2s t x1 3x2 90 2x1 x2 80 x1 x2 46 x1 x2 0 由图示可知最优点为B 34 12 最优值为218称为资源C的影子价格为3 100 80 60 40 20 20 40 60 80 x1 100 B 可见影子价格的含义是当某约束条件常数项每增加一个单位时 最优目标函数值的增加量 2 影子价格在经营管理中的应用 一 1 影子价格说明增加哪一种资源对增加经济效益最有利 三种资源的影子价格为 0 1 3 说明首先应考虑增加资源C 因为相比之下它能给收益带来的增加最大 2 影子价格与某一约束条件相对应 3 影子价格又是一种机会成本 企业经营决策者可以把本企业资源的影子价格与当时资源的市场价格进行比较 当某种资源的影子价格高于市场价格时 则企业可以买进该种资源 因为资源带来的收益大于购买资源的费用当某种资源的影子价格低于市场价格时 特别是当影子价格为零时 则企业可以卖出该种资源 以获得较大的利润 所以资源的影子价格 机会成本 收益 和市场价格是2个不同的概念 例如甲设备的影子价格为15元 如果通过外包能取得追加的加工工时 且外包加工的工时价格为10元 即影子价格大于市场价格 则通过外包可以增加总收益 因而采取外包是合理的 概念区分 一 生产产品的机会成本和产品的市场价格 收益 也是2个不同的概念 第i种产品的机会成本 CBB 1Pj第i种产品的市场价格 Cj当产品的市场价格 收益 产品的机会成本时 即Cj CBB 1Pj亦即Cj CBB 1Pj 0 也就是检验数大于0 需要继续单纯形法迭代 目标值将增加 因此可以作出生产该产品的决策 或者说公司对生产该产品有吸引力 概念区分 二 当产品的市场价格 收益 产品的机会成本时 即Cj CBB 1Pj亦即Cj CBB 1Pj 0 也就是检验数小于0 不需要继续迭代 目标值将不变 生产该产品反而减少目标值 因此可以作出不生产该产品的决策 或者说公司对生产该产品没有吸引力 例如 Cj CBB 1Pj 5表示每售出一件产品 公司的收入将减少5元 当约束条件常数项增加一个单位时 最优目标函数值改进的数量称之为对偶价格 可见 1 如果对偶价格大于零 则其最优目标函数值得到改进 即求最大值时 最优目标函数值变得更大 求最小值时 最优目标函数值变得更小 2 如果对偶价格小于零 则其最优目标函数值变坏 即求最大值时 最优目标函数值变得更小了 求最小值时 最优目标函数值变得更大了 3 如果对偶价格等于零 则其最优目标函数值不变 3 对偶价格 影子价格 当约束条件中的常数项增加一个单位时 最优目标函数值增加的数量称之为影子价格 对偶价格 当约束条件中的常数项增加一个单位时 最优目标函数值改进的数量称之为对偶价格 当求目标函数的最大值时 增加的数量就是改进的数量 所以影子价格就等于对偶价格 当求目标函数的最小值时 改进的数量应该是减少的数量 所以影子价格即为负的对偶价格 4 对偶价格和影子价格的比较 目标函数是MAX对偶价格Y 10表示该资源每增加1个单位 Z增加10 改进的数量 MIN对偶价格Y 10表示该资源每增加一个单位 Z减少10 变好 对偶价格Y 10表示该资源每增加一个单位 Z减少10 对偶价格Y 10表示该资源每增加一个单位 Z增加10 变坏 影子价格W 10 增加的数量 影子价格W 10 影子价格W 10 影子价格W 10 对偶价格和影子价格的比较 可见 最大化的目标函数中资源的影子价格就等于它的对偶价格 对偶价格的求解方法 因为对偶价格可以在原问题的最终单纯形表中直接得到 即为松弛变量或剩余变量在终表中的检验数的相反数 在目标函数最大化的线性规划问题中 资源的影子价格就等于它的对偶价格 所以此时资源的影子价格就是最终单纯形表中的检验数的相反数 待补充 maxZ 5x1 4x2s t x1 3x2 90 2x1 x2 80 x1 x2 45 x1 x2 0 单纯形表迭代过程 x1x2x3x4x5 CBXBb CB j 21000 x3x4x5 021 9013100 8021010 4511001 21000 maxZ 2x1 x2 0 x3 0 x4 0 x55x2 x3 15s t 6x1 2x2 x4 24x1 x2 x5 5x1 x2 x3 x4 x5 0 y1y2y3 对偶变量即对偶价格 x3x4x5 松弛变量 资源的对偶价格就是相应松弛变量或剩余变量在终表中的检验数的相反数 资源的影子价格就是相应松弛变量或剩余变量在终表中的检验数的相反数 目标函数求的是最大化 所以资源的影子价格等于资源的对偶价格 y 1y 2y 3 当一种资源的影子价格为0时 表明这种资源尚未用完 属于非紧缺资源 增加这种资源不能增加总的利润 相应的约束条件为松约束 而当一种资源的影子价格大于0时 表明这种资源已经用完 属于紧缺资源 增加这种资源可以增加总的利润 相应的约束条件为紧约束 如 y 1 0y 2 1 4y 3 1 2第一个约束为松约束 二 三为紧约束 第二 三种资源为紧缺资源 可以考虑优先购买 5 影子价格在经营管理中的应用 二 补充课外作业 星火公司通常生产3种产品 室外椅子 标准长凳和桌子 这些产品生产过程分2个加工阶段 即 弯管车间和焊接车间 在每个车间里 每种产品所需要的时间 每种单位产品销售中所得到的收益如表所示 公司正在计划安排生产 公司了解到这些产品不管生产多少数量都能在市场上销售出去 但材料供应受到限制 公司手头上现有管材 每种产品需要的管材数也如表所示 请完成以下问题 决策变量不考虑整数要求 星火公司最优生产组合是什么 公司预期能够得到多少收益 弯管时间增加一个单位 最优收益增加多少 管子焊接时间增加一个单位呢 金属管材供应增加一个单位呢 为什么 地方销售者对星火公司提供了一些金属管材 每公斤0 6元 公司买不买这些材料 为什么 假如公司买来500公斤并用最优的方式使用它 公司的收益将增加多少 假如星火公司了解到为了完成它的生产 至少必须生产100条长凳 那么这对公司的收益将有什么影响 设计室已经重新设计了收益较多的长凳 新的设计将1 1小时弯管时间 2 0小时焊接时间和2 0公斤金属管材 这些新产品必须有多大的收益 才能使得这一产品对公司产生吸引力 市场销售部门提出需要一种新的室外帐篷 帐篷需要1 8小时弯管时间 0 5小时焊接时间和1 3公斤金属管材 这些新产品必须有多大的收益 才能使得这一产品对公司产生吸引力 星火公司有机会以每小时1 5元出售一些弯管的能力 假如公司以这个价格出售200小时 这对公司收益将会有什么影响 假如每只椅子的收益减少到2 5元 那么最优生产组合是否有变化 这对公司收益将会有什么影响 每只桌子的收益在什么范围内变化 最优生产组合不变 从而对公司的收益没有影响 假如管材供应减少到1500公斤 那么最优生产组合是否有变化 这对公司收益将会有什么影响 焊接时间在什么范围内变化 最优基不变 解 设x1 x2 x3分别表示星火公司生产的室外椅子 标准长凳和桌子的数量 Z表示公司销售产品获得的收益 根据题意 建立如下线形规划模型 MaxZ 3x1 3x2 5x31 2x1 1 7x2 1 2x3 1000s t 0 8x1 2 3x3 12002x1 3x2 4 5x3 2000 x1 x2 x3 0化为标准型 MaxZ 3x1 3x2 5x3 0 x4 0 x5 0 x61 2x1 1 7x2 1 2x3 x4 1000s t 0 8x1 2 3x3 x5 12002x1 3x2 4 5x3 x6 2000 x1 x2 x3 x4 x5 x6 0 列初始单纯性表进行迭代 x1x2x3x4x5x6 CBXBb CB j 335000 x4x5x6 000 10001 21 71 2100 12000 802 3010 2000234 5001 335000 j 1400 32 39 10010 4 15 1600 9 2 9 23 15001 23 45 4000 94 92 31002 9 7 9 1 3000 10 9 x4x5x3 005 1000 1 21200 2 32000 4 5 800 1000 x1x2x3x4x5x6 335000 400 301 151 2 302 5 CBXBb CB j x1x5x3 305 700127 2003 20 2 5 1000 30 37 3001 31 3 5 0 83 600 7 60 4 5 所以原问题具有唯一最优解 X 700 0 400 3 TZ 2100 2000 3 2766 67即星火公司最优生产组合是室外椅子700 标准长凳0和桌子400 3 公司预期能够得到2766 67元收益 弯管时间增加一个单位 最优收益增加多少 管子焊接时间增加一个单位呢 金属管材供应增加一个单位呢 为什么 x1x2x3x4x5x6 CBXBb CB j 335000 x1x5x3 305 700127 2003 20 2 5 1000 30 37 3001 31 3 5 400 301 151 2 302 5 0 83 600 7 60 4 5 因为资源每增加一个单位 最优收益的增加量就是该种资源的影子价格 由最终单纯性表的检验数行可以知道弯管时间 焊接时间和金属管材的影子价格分别是7 6 0 4 5 所以弯管时间增加一个单位 最优收益增加7 6 管子焊接时间增加一个单位 最优收益不增加 金属管材供应增加一个单位 最优收益增加4 5 地方销售者对星火公司提供了一些金属管材 每公斤0 6元 公司买不买这些材料 为什么 假如公司买来500公斤并用最优的方式使用它 公司的收益将增加多少 由最终单纯性表可知金属管材的影子价格是4 5 表示金属管材供应增加一公斤 最优收益增加0 8元 因为市场价格是0 6元 所以公司购买这些材料 假如公司买来500公斤并用最优的方式使用它 公司的收益将增加 500 0 8 0 6 100元 假如星火公司了解到为了完成它的生产 至少必须生产100条长凳 那么这对公司的收益将有什么影响 这相当于增加一个新的约束条件 x2 100首先将最优解代入该约束条件可知道不满足条件 需要继续求解因为该约束条件中基变量的系数为0 将不影响单纯性表 所以可使约束条件右端项为负数将采用对偶单纯性法求解 在最终单纯性表中增加一行 x2 x7 100因为采用对偶单纯性