Chapter2对偶理论及灵敏度分析.ppt

线性规划的 对偶理论与灵敏度分析 第二章第二章 1. 1. 介绍对偶问题的写法、基本性质介绍对偶问题的写法、基本性质 及对偶单纯形法；及对偶单纯形法； 2. 2. 介绍影子价格的概念；介绍影子价格的概念； 3. 3. 介绍灵敏度分析的基本方法介绍灵敏度分析的基本方法 Date1 本章目 录 2-1 2-1 线性规划的对偶问题线性规划的对偶问题 2-2 2-2 对偶问题的基本性质对偶问题的基本性质 2-3 2-3 影子价格影子价格 2-4 2-4 对偶单纯形法对偶单纯形法 2-5 2-5 灵敏度分析灵敏度分析 2-6 2-6 参数线性规划参数线性规划 Date2 2-1 线性规划的对偶问题 引言引言 一、一、对偶问题对偶问题 二、二、对称形式对偶问题的一般形对称形式对偶问题的一般形 式式 三、三、非对称形式的原非对称形式的原- -对偶问题对偶问题 四、四、对偶问题的写法对偶问题的写法 返回本章目录 Date3 引 言 在实际问题中，一个问题的优化往往可以从不同 的两个角度提出问题。 譬如，要求在有限资源条件下生产利润最大；或 在一定生产能力条件下使资源消耗最少。 所以，在线性规划中，对任一给定的求最大值问 题，相应也存在一个求最小值的问题。且两者包括 有相同的数据。 若称前者为原问题，则后者便称为对偶问题；或 称前者为对偶问题，而称后者为原问题。两者互为 对偶，具有密切的关系。只要得到其中一个问题的 解，也就能够得到另一个问题的解。因而，从中选 一个问题求解就可以了。 Date4 一、对偶问题 例1 美佳公司利用该公司资源生产两种家电产品的线性 规划模型为： 设y1，y2，y3分别表示设备A、B和 调试工序单位时间的价格。则 0y1+6y2+y32 5y1+2y2+y31 对生产产 品的全部资 源的定价。 假如另一公司想收购美 佳公司的资源，美佳公 司出让自己资源的条件 是什么？ 出让代价不低于用同等 资源组织生产两种产品 所能获得的利润。 对生产产 品的全部资 源的定价。 产品的利润 产品的利润 Date5 原问题与对偶问题的数据比较 原问题 对偶问题 x1x2原关系min w y10515 y26224 y3115 对偶关系 max z = min w max z21 Date6 二、对称形式对偶问题的一般形式 定义：定义：满足下列条件的线性规划问题称为具有对称形式 ：其变量均具有非负约束，其约束条件当目标函数求极大时 取“”号，当目标函数求极小时均取“”号。 则其对偶问题的 一般形式为： 若原问题的一 般形式为： yi(i=1,2,，m) 代表第i种资源 的估价。 Date7 矩阵形式表示的原问题与对偶问题 原问 题： 对偶问题： 令ww 对偶问题 令zz 对偶问题的对对偶问题的对 偶是原问题偶是原问题 Date8 三、非对称形式的原-对偶问题 考虑标准形式的线性规划： max z = CX AX = b X0 max z = CX AX b AX b X0 min w = bT (YY) AT (Y Y ) CT Y0， Y 0 令Y= YY min w = bT Y AT Y CT Y 为自由变量 这就是非对称形式的对 偶关系。在这种形式中 ，Y 不要求非负。 max z = CX AX b AX b X0 Y Y min w = Yb AY C Y 为自由变量 Date9 四、对偶问题的 写法 在写对偶问题时，要特别注意上表中原问题与其对偶问 题的对应关系。 Date10 写对偶问题的步骤： 第一步第一步：根据原问题数学模型的形式统一符号。 若原问题目标函数求极大求极大，则将其约束条件统一 成“ “ ” ”或或“ “” ”的形式；若原问题目标函数为求极小 求极小， 则将其约束条件统一成“ “ ” ”或或“ “” ”的形式。 第二步第二步：假设对偶变量。 对偶变量与原问题的约束条件一一对应，每一个 约束条件都有一个对偶变量与它相对应。所以，对 偶变量数等于原问题的约束方程数。 第三步第三步：根据原问题与对偶问题的关系写出对偶 规划模型。 Date11 例: 写出下面规划问题的对偶规划问题。 原问题： max z = 4x1+x2-5x3-4x4-2x5 2x2+x3+3x4+4x5 = - 6 3x1+x2-x3-x4 2 - 4x1+2x3-2x4 - 5 - 6 x1 18 x2 25 x3,x4 0; x5 不受限制 统一符号（因求max,故约束统一成 “ ”的形式： max z = 4x1+x2-5x3-4x4-2x5 2x2+x3+3x4+4x5 = - 6 - 3x1- x2 +x3 +x4 - 2 - 4x1 +2x3 -2x4 - 5 x1 18 - x1 6 x2 25 x3,x4 0;x1,x2, x5 不受限制 y1 y2 y3 y4 y6 y5 min w = - 6y1-2y2-5y3+18y4+6y5+25y6 -3y2-4y3+y4- y5 = 4 2y1-y2+y6=1 y1+y2+2y3 -5 3y1+y2-2y3 - 4 4y1= - 2 yi 0 ( i=2,3,4,5,6) ; y1为自由变量 对 偶 问 题 第一步：统一符号第一步：统一符号 第二步：假设变量第二步：假设变量 第三步：写对偶问题第三步：写对偶问题 Date12 例2 写出下述线性规划问题的对偶问 题 原问题原问题 ： 令x2x4，x40统一约束 符号： y1 y2 y3 对偶问题：对偶问题： 令令y y 2 2 y y 4 4 ，可得到教可得到教 材上的形式：材上的形式： Date13 教材上例2的解法： 原问题原问题 ： 令x2x2；x3x3x3 用两个不等式约束表示等式约束： 统一约束符号：统一约束符号： Date14 假设变量 ： 写对偶问题：写对偶问题： 令y2y2；y3y3y3 Date15 Date16 2-2 对偶问题的基本性质 一、单纯形法计算的矩阵描 述 原问题原问题对偶问题对偶问题 X X s s 为松弛变量；为松弛变量； X X s s = (= (x xn+1 n+1 , ,x x n+2n+2, ,x xn+m n+m); );I I为 为mm mm阶单位矩阵阶单位矩阵 。 返回本章目录 提纲：提纲： 一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述 二、二、对偶问题的基本性质对偶问题的基本性质 Date17 Date18 表表2-32-3 初始初始单纯单纯单纯单纯 形表形表 非基非基变变变变量量基基变变变变量量 C C j j C CB B C CN N 0 0 C CB B 基基 b b X XB B X XN N X X s s 0 0 X X s sb b B B N N I I c c j j -z -z j j C CB B C CN N 0 0 表表2-4 2-4 最最终单纯终单纯终单纯终单纯 形表形表 基基变变变变量量非基非基变变变变量量 C C j j C CB B C CN N 0 0 C CB B 基基 b b X XB B X XN N X X s s C CB B X XB B B B -1-1 b b I I B B -1-1 N N B B -1-1 c c j j -z -z j j 0 0 C CN N -C-C B BB B -1-1 N N -C-C B BB B -1-1 Date19 基变量XB的检验数为：CBCBI 0 所以，在最终单纯形表中，原变量的检验数可 写为 CCBB-1A0（2.17） CBB-10（2.18） CBB-1称为单纯形乘子。令Y CBB-1，则2.17、 2.18式可以改写为 CCBB-1A0 YACI AYC Y0 可以看出，原问题得到最优解时，其检验数的相反 数是对偶问题的一个可行解。 代入对偶问题的目标函数得 w Yb CBB-1bz 即 原问题得到最优解时，对偶问题为可行解，两 者具有相同的目标函数值。 Date20 例3 两个互为对偶的线性规划问题解的比较 原问题： 对偶问题： Date21 原问题的解 为 X(x1,x2,x3,x4,x5)T(7/2,3/2,15/2,0,0)T 与最优解对应的目标函数值为： 对偶问题的解为对偶问题的解为 Y(y1,y2,y3,y4,y5)T(0,1/4,1/2,0,0)T 与最优解对应的目标函数值为： Date22 例 3 原原变变变变量量松弛松弛变变变变量量 x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x3 3 15/215/2 0 0 0 0 1 1 5/45/4-15/2-15/2 x x1 1 7/27/2 1 1 0 0 0 0 1/41/4-1/2-1/2 x x2 2 3/23/2 0 0 1 1 0 0 -1/4-1/43/23/2 c c j j -z-z j j 0 0 0 0 0 0 -1/4-1/4-1/2-1/2 对对对对偶剩余偶剩余 变变变变量量 对对对对偶偶问题变问题变问题变问题变 量量 y y4 4 y y5 5 y y1 1 y y2 2 y y3 3 对对对对偶偶问题变问题变问题变问题变 量量对对对对偶剩余偶剩余变变变变 量量 y y1 1 y y2 2 y y3 3 y y4 4 y y5 5 y2y21/41/4-5/4-5/4 1 1 0 0 -1/4-1/41/41/4 y3y31/21/215/215/2 0 0 1 1 1/21/2-3/2-3/2 c c j j -z-z j j -15/2-15/2 0 0 0 0 -7/2-7/2-3/2-3/2 原原问题问题问题问题 松弛松弛变变变变量量原原问题变问题变问题变问题变 量量 x x3 3 x x4 4 x x5 5 x x1 1 x x2 2 在最优单纯形表的检验数行，原问题 变量对应的数的相反数，是对偶问题剩余 变量的值；原问题松弛变量对应的数的相 反数，是对偶问题变量的值。反之亦然。 Date23 二、对偶问题的基本性质 1.弱对偶性 ： 证：证： Date24 由弱对偶性得到推论： （1）原问题任一可行解的目标函数值是其对偶 问题目标函数值的下界；反之，对偶问题任一可行 解的目标函数值是其原问题目标函数值的上界。 （2）如原问题有可行解且目标函数值无界（无 界解），则其对偶问题无解；反之，对偶问题有可 行解且目标函数值无界，则其原问题无可行解。 （3）若原问题有可行解而其对偶问题无可行解 ，则原问题目标函数值无界；反之，对偶问题有可 行解而其原问题无可行解，则对偶问题目标函数值 无界。 Date25 2. 最优性 ： 3. 3. 强对偶性（对偶定理）强对偶性（对偶定理）： 若原问题及其对偶问题均具有可行解 ，则两者均具有最优解，且它们最优解 的目标函数值相等。 Date26 4. 互补松弛性 ： 在线性规划问题的最优解中，如果对应某一约束条件的在线性规划问题的最优解中，如果对应某一约束条件的 对偶变量值为非零，则该约束条件取严格等式；反之，如果对偶变量值为非零，则该约束条件取严格等式；反之，如果 约束条件取严格不等式，则其对应的对偶变量一定为零。约束条件取严格不等式，则其对应的对偶变量一定为零。 Date27 2-3 影子价格 当线性规划原问题求得最优解xj*( j =1,2,n )时，其对 偶问题也得到最优解yi*( i =1,2,m )，且两者的目标函数值 相等。即 bi：线性规划原问题右端项，代表第 i 种资源的拥有量； yi*：对偶变量，代表在最优资源利用条件下对单位第 i 种 资源的估价，称为影子价格。 影子价格影子价格(Shadow Price)也称为机会成本(Opportunity Cost),它是根据具体的经济目标、技术水平和资源条件作出的 对资源利用的评价。 市场价格市场价格：是资源在市场上流通的实际价格，它由整个社 会的经济技术状况决定。 返回本章目录 Date28 根据 求 bi 的偏导数得： 这说明，原问题某一约束条件的右边常数原问题某一约束条件的右边常数b b i i 增加一个单位增加一个单位 时，则由此引起最优目标函数值的增加量，就等于与该约束相时，则由此引起最优目标函数值的增加量，就等于与该约束相 对应的对偶变量的最优值对应的对偶变量的最优值。 这样一来，在有限资源条件下使收益最大化这一类问题中 ，就可以把对偶变量的最优值，看成是相应资源每一单位对于 目标函数的贡献，即这些资源被充分利用时所能带来的收益。 从而， yi* 的值就相当于对单位 i 种资源在实现最大利润 时的一种价格估计。这种估计是针对具体企业，具体产品而存 在的一种特殊价格，称之为影子价格，它与市场价格不同。 若仅从经济上考虑，当某种资源的市场价格低于影子价格当某种资源的市场价格低于影子价格 时，企业就可以考虑买进这种资源；当市场价格高于影子价格时，企业就可以考虑买进这种资源；当市场价格高于影子价格 时，企业则可以出售这种资源时，企业则可以出售这种资源。随着资源的买进卖出，它的影 子价格也将随之变化，直到影子价格与市场价格保持同等水平 时，才处于平衡状态。 Date29 影子价格是一种边际价格（图示） Q1 Q3 Q2 Q4 O x1 x2 5x5x 2 2 1515 6x6x 1 1 2x2x 2 2 2424 x x1 1 x x 2 2 5 5 z z2 2z z8.58.5 (3.5(3.5，1.5)1.5) (25)(25) Date30 影子价格的应用 （1）用影子价格判别资源的供求关系 如果线性规划的原问题在得到最优解时，某个约束条件 为严格的不等式，即最优解中该约束的松弛变量的值大于零 ，即 表明该种资源有剩余，供大该种资源有剩余，供大 于求于求。增加这种资源时，目增加这种资源时，目 标函数值不会有任何改善标函数值不会有任何改善。 如果线性规划的原问题在得到最优解时，某个约束条件 为严格的等式，即最优解中该约束的松弛变量的值等于零， 即表明该资源恰恰用完。这种该资源恰恰用完。这种 资源增加一个单位，目标函资源增加一个单位，目标函 数值就改进一个影子价格数值就改进一个影子价格。 由此可见，影子价格大于零，说明资源紧缺；影子价格等于影子价格大于零，说明资源紧缺；影子价格等于 零，说明资源有剩余。影子价格愈大，说明该资源愈紧缺，该零，说明资源有剩余。影子价格愈大，说明该资源愈紧缺，该 种资源每增加一个单位所相应增加的目标函数值愈大种资源每增加一个单位所相应增加的目标函数值愈大。 Date31 如果xn+i=0,必有yi0，资源紧缺； 如果xn+i0,必有yi0，资源剩余。 松弛变量松弛变量x x s s 对偶变量对偶变量y y i i 资源限量资源限量b b i i Date32 （2）应用影子价格来合理分配资源 算出各种资源的影子价格后，可参考影 子价格高低顺序合理分配资源，高者优先投 资。同时，也可以参考资源的影子价格，合 理地确定各种资源的价格。 Date33 2-4 对偶单纯形法 引言引言 前面介绍的单纯形法，是从一个基本可行解开始进 行迭代运算，在迭代过程中，始终保持解的可行性， 当所有检验数都非正时，就得到了原问题的最优解。 根据对偶定理，原问题单纯形表中的检验数实际上 是对偶问题的一组解，但不一定可行，检验数逐渐变 为非正的过程，可以理解为对偶问题解的不可行性逐 渐消失的过程，当对偶问题的解变为可行解时，原问 题就得到了最优解。 因此，我们可以选择在对偶问题的解之间进行迭代 运算，在迭代过程中，始终保持最优判别条件得到满 足，当求出对偶问题的可行解时，也就得到了原问题 的最优解。 返回本章目录 Date34 例4 用对偶单纯形法求解线性规划问题： 将约束条件两边同时乘以“-1”得 ： 标准形式 得到初始基为：得到初始基为： 基变量为基变量为y y 4 4, ,y y5 5 ，非基变非基变 量为量为y y 1 1, ,y y2 2, ,y y3 3 。 令所有的非基变量等于令所有的非基变量等于 0 0，得到该问题的一个解得到该问题的一个解 为：为： Y= ( 0,0,0,-2,-1 )Y= ( 0,0,0,-2,-1 ) T T 这个解不可行，称为这个解不可行，称为正正 则解则解。 对偶单纯形法就是从一对偶单纯形法就是从一 个正则解开始迭代的。个正则解开始迭代的。 Date35 表 2-8 c c j j -15-15-24-24-5-5 0 0 0 0C CB B 基基 b b y y1 1 y y2 2 y y3 3 y y4 4 y y5 50 0 y y4 4 -2-2 0 0 -6-6-1-1 1 1 0 00 0 y y5 5 -1-1-5-5-2-2-1-1 0 0 1 1c c j j z z j j -15-15-24-24-5-5 0 0 0 0 1. 1. 确定换出变量确定换出变量 y4为换出变量 2.2.确定换入变量确定换入变量 y2为换入变量。 3.3.迭代运算，得迭代运算，得 新单纯形表。新单纯形表。 -24-24 y y2 2 1/31/3 0 0 1 1 1/61/6-1/6-1/6 0 00 0 y y5 5 -1/3-1/3-5-5 0 0 -2/3-2/3-1/3-1/3 1 1 c c j j z z j j -15-15 0 0 -1-1-4-4 0 0 -24-24 y y2 2 1/41/4-5/4-5/4 1 1 0 0 -1/4-1/41/41/4 -5-5 y y3 3 1/21/215/215/2 0 0 1 1 1/21/2-3/2-3/2 c c j j z z j j -15/2-15/2 0 0 0 0 -7/2-7/2-3/2-3/2 s s j j 00，最优解最优解Y=(0,1/4,1/2,0,0)Y=(0,1/4,1/2,0,0) T T Min w=15yMin w=15y 1 1 +24y+24y 2 2 +5y+5y 3 3 =17/2=17/2 Date36 2-5 灵敏度分析 对一线性规划问题来说，一旦其约束条件系数矩阵A、 约束条件右侧常数向量b和价值系数向量C给定之后，这个线 性规划问题就确定了。反之，给定一个线性规划问题，就有 确定的一组A、b和C与之对应。 在此之前，我们一直假定A、b和C中的元素是常数，它 们不发生变化。但实际上这些系数往往是通过估计、预测或 人为决策得来的，不可能十分准确和一成不变。 例如：市场条件一变，价值系数cj就会跟着变化；约束 条件系数矩阵A中的元素aij往往随着工艺技术条件的变化而 改变；bi通常取决于现有条件和决策人的决策。 这就是说，随着时间的推移或情况的变化，我们往往需 要修改原来线性规划问题中的若干系数，从而使原来的规划 问题有所改变。 就实际需要来讲，求出最优解，还不能说问题已完全解 决。决策者还需要知道以下一些问题。 返回本章目录 Date37 当这些系数中的一个或几个发生变化时，已求得的最优 解有什么变化？ 这些系数在什么范围内改变时，规划问题的最优解或最 优基不变？ 若最优解变化，如何用最简便的方法找到新的最优解？ FF灵敏度分析就是研究提出在原始计算结果基础上直接分灵敏度分析就是研究提出在原始计算结果基础上直接分 析参数变化对最优解影响的方法析参数变化对最优解影响的方法。 灵敏度分析的步骤：灵敏度分析的步骤： （1）将参数的变化反映到最终单纯形表上； （2）检查原问题是否仍为最优解； （3）检查对偶问题是否仍为最优解； （4）按下表所列情况得出结论，决定继续计算的步骤。 Date38 灵敏度分析的有关计算公 式 表2-9 原原问题问题问题问题对对对对偶偶问题问题问题问题结论结论结论结论 或或继续计继续计继续计继续计 算的步算的步骤骤骤骤 可行解可行解问题的最优解或最优基不变 可行解非可行解用单纯形法继续迭代求最优解 非可行解 可行解用对偶单纯形法继续迭代求最优解 非可行解 非可行解引进人工变量，重新编单纯 形表计 算 Date39 美佳公司用三中资源生产两种产品的线性规划模型初 始单纯形表： 初始初始单纯单纯单纯单纯 形表形表 c c j j 2 2 1 1 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 1515 0 0 5 5 1 1 0 0 0 0 0 0 x x4 4 2424 6 6 2 2 0 0 1 1 0 0 0 0 x x5 5 5 5 1 1 1 1 0 0 0 0 1 1 c c j j z z j j 2 2 1 1 0 0 0 0 0 0 Date40 灵敏度分析的主要内容 一、一、分析分析c c j j 变化变化 二、二、分析分析b b i i 的变化的变化 三、三、增加一个变量增加一个变量x x j j 的分析的分析 四、四、分析参数分析参数a a ij ij 的变化的变化 五、五、增加一个约束条件的分析增加一个约束条件的分析 Date41 （1）美佳公司家电的利润降至1.5元/件，家电的利 润增至2元/件。 一、分析 cj 的变化（例 5 ） 最最终单纯终单纯终单纯终单纯 表表 c c j j 2 2 1 1 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 15/215/2 0 0 0 0 1 1 5/45/4-15/2-15/2 2 2 x x1 1 7/27/2 1 1 0 0 0 0 1/41/4-1/2-1/2 1 1 x x2 2 3/23/2 0 0 1 1 0 0 -1/4-1/43/23/2 c c j j z z j j 0 0 0 0 0 0 -1/4-1/4-1/2-1/2 0 0 x x4 4 6 6 0 0 0 0 4/54/5 1 1 -6-6 1.51.5 x x1 1 2 2 1 1 0 0 -1/5-1/5 0 0 1 1 2 2 x x2 2 3 3 0 0 1 1 1/51/5 0 0 0 0 c c j j z z j j 0 0 0 0 -1/10-1/10 0 0 -3/2-3/2 y1=0, y2=1/4, y3=1/2 1.52 1.5 2 1/8-9/4 返回提要 Date42 家电的利润变化范围： 若要保持最优解不变，必须 (2)家电的利润变为（1）元 最最终单纯终单纯终单纯终单纯 表表 c c j j 2 2 1 1 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 15/215/2 0 0 0 0 1 1 5/45/4-15/2-15/2 2 2 x x1 1 7/27/2 1 1 0 0 0 0 1/41/4-1/2-1/2 1 1 x x2 2 3/23/2 0 0 1 1 0 0 -1/4-1/43/23/2 c c j j z z j j 0 0 0 0 0 0 -1/4-1/4-1/2-1/2 1+l 1+l Date43 二、分析 bi 的变化（ 例 6 ） 最最终单纯终单纯终单纯终单纯 表表 c c j j 2 2 1 1 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 15/215/2 0 0 0 0 1 1 5/45/4-15/2-15/2 2 2 x x1 1 7/27/2 1 1 0 0 0 0 1/41/4-1/2-1/2 1 1 x x2 2 3/23/2 0 0 1 1 0 0 -1/4-1/43/23/2 c c j j z z j j 0 0 0 0 0 0 -1/4-1/4-1/2-1/2 （1）美家公司设备A和调试工序的每天能力不变，设备B 每天的能力增加到32小时，分析公司最优计划的变化。 35/2 11/2 -1/2 0 0 x x3 3 1515 0 0 5 5 1 1 0 0 0 0 2 2 x x1 1 5 5 1 1 1 1 0 0 0 0 1 1 0 0 x x4 4 2 2 0 0 -4-4 0 0 1 1 -6-6 c c j j z z j j 0 0 -1-1 0 0 0 0 -2-2 返回提要 Date44 （2）设备A和设备B可用能力不变，则调试工序能力在 什么范围变化时，问题的最优基不变。 最最终单纯终单纯终单纯终单纯 表表 c c j j 2 2 1 1 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 15/215/2 0 0 0 0 1 1 5/45/4-15/2-15/2 2 2 x x1 1 7/27/2 1 1 0 0 0 0 1/41/4-1/2-1/2 1 1 x x2 2 3/23/2 0 0 1 1 0 0 -1/4-1/43/23/2 c c j j z z j j 0 0 0 0 0 0 -1/4-1/4-1/2-1/2 设调试工序每天可用能力为（5+l）小时 。 调试工序能力在调试工序能力在4 4之之 间变化时，最优基不变。间变化时，最优基不变。 Date45 三、增加一个变量xj的分析 增加一个变量在实际问题中表示增加一种新产品 。 分析步骤： 例7 美佳公司计划推出新型产品 家电，生产一件所需设备A、B及调 试工序的时间分别为3小时、4小时、 2小时，该产品的预期盈利为3元/件 ，试分析该产品是否值得投产；如投 产，该公司生产计划有何变化。 解：设该公司每天生 产家电x6件，则有 c6 = 3; P6 = ( 3,4,2 )T 返回提要 Date46 例 7 最最终单纯终单纯终单纯终单纯 形表形表 c c j j 2 2 1 1 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 15/215/2 0 0 0 0 1 1 5/45/4-15/2-15/2 2 2 x x1 1 7/27/2 1 1 0 0 0 0 1/41/4-1/2-1/2 1 1 x x2 2 3/23/2 0 0 1 1 0 0 -1/4-1/43/23/2 c c j j z z j j 0 0 0 0 0 0 -1/4-1/4-1/2-1/2 x6 3 -7 0 2 1 0 0 x x3 3 3/43/4 0 0 7/27/2 1 1 3/83/8-9/4-9/4 0 0 2 2 x x1 1 7/27/2 1 1 0 0 0 0 1/41/4-1/2-1/2 0 0 1 1 x x6 6 3/43/4 0 0 1/21/2 0 0 -1/8-1/83/43/4 1 1 c c j j z z j j 0 0 -1/2-1/2 0 0 -1/8-1/8-5/4-5/4 0 0 美美佳公司新的最优生产计划应为每天生产家电公司新的最优生产计划应为每天生产家电7/27/2件，件， 家电家电3/43/4件。可获得利润件。可获得利润27/227/210+33/410+33/437/437/4（元）（元） Date47 四、分析参数aij的变化 aij 的变化将引起约束条件系数矩阵 A 发生变化。 例8 在美佳公司的例子中，若家电每件需设备A、B和 调试工时变为8小时、4小时、1小时，该产品的利润变为3元/ 件，试重新确定该公司的最优生产计划。 解：将生产工时变化后的新家电看作是一种新产品， 生产量为x2，则 返回提要 Date48 例 8 最最终单纯终单纯终单纯终单纯 形表形表 c c j j 2 2 1 1 3 3 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 15/215/2 0 0 0 0 11/211/2 1 1 5/45/4-15/2-15/2 2 2 x x1 1 7/27/2 1 1 0 0 1/21/2 0 0 1/41/4-1/2-1/2 1 1 x x2 2 3/23/2 0 0 1 1 1/21/2 0 0 -1/4-1/43/23/2 c c j j z z j j 0 0 0 0 3/23/2 0 0 -1/4-1/4-1/2-1/2 0 0 x x3 3 -9-9 0 0 0 0 1 1 4 4 -24-24 2 2 x x1 1 2 2 1 1 0 0 0 0 1/21/2-2-2 3 3 x x2 2 3 3 0 0 1 1 0 0 -1/2-1/2 3 3 c c j j z z j j 0 0 0 0 0 0 1/21/2-5-5 从上表看出，原问题和对偶问题均为非可行解，故先设 法使原问题变为可行解。 x34x424x59 x34x424x5x69 人 工 变 量 Date49 表2 -19 c c j j 2 2 3 3 0 0 0 0 0 0 MM C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 -M-M x x6 6 9 9 0 0 0 0 -1-1-4-42424 1 1 2 2 x x1 1 2 2 1 1 0 0 0 0 1/21/2-2-2 0 0 3 3 x x2 2 3 3 0 0 1 1 0 0 -1/2-1/2 3 3 0 0 c c j j z z j j 0 0 0 0 -M-M -4M-4M -5+24M-5+24M 0 0 0 0 x x5 5 3/83/8 0 0 0 0 -1/24-1/24-1/6-1/6 1 1 1/241/24 2 2 x x1 1 11/411/4 1 1 0 0 -1/12-1/121/61/6 0 0 1/121/12 3 3 x x2 2 15/815/8 0 0 1 1 1/81/8 0 0 0 0 -1/8-1/8 c c j j z z j j 0 0 0 0 -5/24-5/24 -1/3-1/3 0 0 -M+5/24-M+5/24 因为所有检验数因为所有检验数s s j j 00，所以得到问题的最优解，即美所以得到问题的最优解，即美佳公司公司 的最优生产计划是每天生产家电的最优生产计划是每天生产家电11/411/4件，新家电件，新家电15/815/8件。件。 Date50 c c j j 2 2 1 1 3 3 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 -9-9 0 0 0 0 1 1 4 4 -24-24 2 2 x x1 1 2 2 1 1 0 0 0 0 1/21/2-2-2 3 3 x x2 2 3 3 0 0 1 1 0 0 -1/2-1/2 3 3 c c j j z z j j 0 0 0 0 0 0 1/21/2-5-5 如果不加人工变量，可用对偶单纯形法从正则解开始迭代如果不加人工变量，可用对偶单纯形法从正则解开始迭代 找出最优解。找出最优解。 0 0 x x5 5 3/83/8 0 0 0 0 -1/24-1/24-1/6-1/6 1 1 2 2 x x1 1 11/411/4 1 1 0 0 -1/12-1/121/61/6 0 0 3 3 x x2 2 15/815/8 0 0 1 1 1/81/8 0 0 0 0 c c j j z z j j 0 0 0 0 -5/24-5/24-1/3-1/3 0 0 因为所有检验数因为所有检验数s s j j 00，所以得到问题的最优解，即美家公司所以得到问题的最优解，即美家公司 的最优生产计划是每天生产家电的最优生产计划是每天生产家电11/411/4件，新家电件，新家电15/815/8件。件。 Date51 五、增加一个约束条件的分 析 增加一个约束条件在实际问题中相当于增加一道工序。分析 方法是先将原问题最优解的变量值代入新增的约束条件，如满 足，说明新增的约束条件未起到限制作用，原最优解不变。否 则，将新增的约束直接反映到最终单纯形表中再进一步分析。 例9 设美佳公司家电，家电经调试后，还需经过一道环 境试验工序，家电每件须环境试验3小时，家电每件2小时 ，环境试验工序每天生产能力为12小时。试分析增加该工序后 ，美家公司的最优生产计划。 解：环境试验工序的约束条件为 3x1+2x212 将原问题最优解代入得：37/223/227/212 由此可见，新增约束得不到满足，需加入松弛变量，将其化 为标准形式：3x1+2x2x612 以x6为基变量，将新增约束填入最终单纯形表中。 返回提要 Date52 表 2-21 c c j j 2 2 1 1 0 0 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 0 0 x x3 3 15/15/ 2 2 0 0 0 0 1 1 5/45/4 - - 15/15/ 2 2 0 0 2 2 x x1 1 7/27/2 1 1 0 0 0 0 1/41/4 - - 1/21/2 0 0 1 1 x x2 2 3/23/2 0 0 1 1 0 0 - - 1/41/4 3/23/2 0 0 0 0 x x6 6 1212 3 3 2 2 0 0 0 0 0 0 1 1c c j j -z-z j j 0 0 0 0 0 0 - - 1/41/4 - - 1/21/2 0 0 0 0 x x3 3 15/15/ 2 2 0 0 0 0 1 1 5/45/4 - - 15/15/ 2 2 0 0 2 2 x x1 1 7/27/2 1 1 0 0 0 0 1/41/4 - - 1/21/2 0 0 1 1 x x2 2 3/23/2 0 0 1 1 0 0 - - 1/41/4 3/23/2 0 0 0 0 x x6 6 - - 3/23/2 0 0 0 0 0 0 - - 1/41/4 - - 3/23/2 1 1 c c j j -z-z j j 0 0 0 0 0 0 - - 1/41/4 - - 1/21/2 0 0 0 0 x x3 3 1515 0 0 0 0 1 1 5/25/2 0 0 -5-5 2 2 x x1 1 4 4 1 1 0 0 0 0 1/31/3 0 0 - - 1/31/3 1 1 x x2 2 0 0 0 0 1 1 0 0 - - 1/21/2 0 0 1 1 0 0 x x5 5 1 1 0 0 0 0 0 0 1/61/6 1 1 - - 2/32/3 c c j j -z-z j j 0 0 0 0 0 0 - - 1/61/6 0 0 - - 1/31/3 3 2 用对偶单 纯形法迭 代计算 增加环境试 验工序后， 美佳公司的 最优生产计 划为每天生 产家电4 件。 Date53 2-6 参数线性规划 灵敏度分析中研究cj、bi等参数改变到某一值时对问题最 优解的影响，若令cj、bi沿某一方向连续变动，则目标函数 z 将随 cj 或 bi 的变动而呈线性变动，z 是这个变动参数的线性 函数，因而称为参数线性规划。 参数线性规划的一般形式： cj 连续变化时： bi 连续变化时： C*和b*为变动向量，l为变动参数。 返回本章目录 Date54 例10 分析 l值变化时，下述线性规划最优解的变 化 解：令l0，求 得： 最最终单纯终单纯终单纯终单纯 形表形表 c c j j 2 2 1 1 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 15/215/2 0 0 0 0 1 1 5/45/4-15/2-15/2 2 2 x x1 1 7/27/2 1 1 0 0 0 0 1/41/4-1/2-1/2 1 1 x x2 2 3/23/2 0 0 1 1 0 0 -1/4-1/43/23/2 c c j j z z j j 0 0 0 0 0 0 -1/4-1/4-1/2-1/2 2+l1+2l 2+l 1+2l 若若 1 1，x x 4 4 换入基，换入基，x x 3 3 换出基换出基 Date55 表2 -25 最最终单纯终单纯终单纯终单纯 形表形表 c c j j 2+2+l l1+21+2l l 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x4 4 6 6 0 0 0 0 4/54/5 1 1 -6-6 2+2+l l x x1 1 2 2 1 1 0 0 -1/5-1/5 0 0 1 1 1+21+2l l x x2 2 3 3 0 0 1 1 1/51/5 0 0 0 0 c c j j z z j j 0 0 0 0 0 0 -2-2-l l 所以，所以，l l 1 1时，最优解为时，最优解为X*X*（2 2，3 3，0 0，6 6，0 0） T T z ()= 7+8 z ()= 7+8l l Date56 若l-15，x5为换入变量，x2为换出变量。 最最终单纯终单纯终单纯终单纯 形表形表 c c j j 2+2+1+21+2 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 15/215/2 0 0 0 0 1 1 5/45/4-15/2-15/2 2+2+l l x x1 1 7/27/2 1 1 0 0 0 0 1/41/4-1/2-1/2 1+21+2l l x x2 2 3/23/2 0 0 1 1 0 0 -1/4-1/43/23/2 c c j j z z j j 0 0 0 0 0 0 -1/4-1/4-1/2-1/2 Date57 表2-26 cjcj2+2+l l1+21+2l l 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 1515 0 0 5 5 1 1 0 0 0 0 2+2+l l x x1 1 4 4 1 1 1/31/3 0 0 1/61/6 0 0 0 0 x x5 5 1 1 0 0 2/32/3 0 0 -1/6-1/6 1 1 c c j j -z-z j j 0 0 0 0 0 0 若若 2 2， X X4 4 为换入变量，为换入变量， X X1 1 为换出变量。为换出变量。 Date58 2 c c j j 2+2+l l1+21+2l l 0 0 0 0 0 0 C CB B 基基 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x3 3 1515 0 0 5 5 1 1 0 0 0 0 0 0 x x4 4 2424 6 6 2 2 0 0 1 1 0 0 0 0 x x5 5 5 5 1 1 1 1 0 0 0 0 1 1 c c j j -z-z j j 2+2+l l1+21+2l l 0 0 0 0