运筹学——2对偶理论和灵敏度分析.ppt

第二章第二章    线性规划的对偶理论线性规划的对偶理论窗窗含含西西岭岭千千秋秋雪雪，，门门泊泊东东吴吴万万里里船船本章主要内容本章主要内容：•线性规划的对偶问题概念、理论及经济意义线性规划的对偶问题概念、理论及经济意义•线性规划的对偶单纯形法线性规划的对偶单纯形法•线性规划的灵敏度分析线性规划的灵敏度分析1第一节第一节 对偶问题的提出对偶问题的提出 材料材料产品产品甲甲乙乙丙丙丁丁单件单件收益收益A32112000B41324000C22343000限额限额600400300200假设工厂考虑不进行生产而把假设工厂考虑不进行生产而把全部资源都转让，问如何定价全部资源都转让，问如何定价这些资源，既能使其获利不低这些资源，既能使其获利不低于安排生产所获得的收益，又于安排生产所获得的收益，又能使资源租让具有竞争力能使资源租让具有竞争力一、引例一、引例Max Z = 2000x1+4000x2+3000x3      s.t.   3x1+4x2+2x3≤600             2x1+  x2+2x3≤400               x1+3x2+3x3≤300 x1+2x2+4x3≤200                    x1, x2, x3≥0 Min W =600y1+400y2+300y3+200y4      s.t.     3y1+2y2+  y3+  y4≥2000               4y1+  y2+3y3+2y4≥4000               2y1+2y2+3y3+4y4≥3000                        y1, y2, y3, y4≥0 x1x2x3y1        y2        y3        y42二、对偶问题二、对偶问题（（1 1）对称）对称LPLP问题的定义问题的定义（（2 2）对称）对称LPLP问题的对偶问题问题的对偶问题第一类对称形式第一类对称形式第二类对称形式第二类对称形式3例例1 1 写出下列写出下列LPLP问题的对偶问题问题的对偶问题对偶对偶 Max Z =2x1+3x2    s.t.     x1+ 2x2≤8           4x1             ≤ 16                   4x2≤ 12                x1 ,x2 ≥0 Min W =8y1+16y2+12y3   s.t.     y1+4y2            ≥2          2y1           +4y3 ≥3                 y1 ,y2,y3 ≥04（（3 3）对偶问题的对偶是原问题）对偶问题的对偶是原问题推导过程推导过程变形对偶变变形形对偶对偶对偶对偶变变形形Max Z=CTXs.t.   AX≤b          X≥0Min W=bTYs.t.   ATY≥C            Y≥0Max W ’= -bTYs.t.  -ATY≤ -C            Y≥0Min Z ’= -CTXs.t.   -(AT)TX≥ -b                  X≥05例例2 2 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解解: : 上述上述LPLP问题的问题的 对偶问题为：对偶问题为：6三、非对称三、非对称LPLP问题的对偶问题问题的对偶问题例例3 3 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解：用解：用x2= -x2’, x3=x3’-x3’’代入上述代入上述LP问题，并将其问题，并将其化为第一类对称形式化为第一类对称形式Max Z = x1+2x2+x3  x1+x2-x3  ≤2  s.t.      x1 -x2+x3  = 1 2x1+x2+x3 ≥2           x1≥0, x2≤0 ,x3无约束无约束 Max Z = x1-2x2’ +x3’-x3’’              x1 -x2’ -x3’+x3’’ ≤ 2 x1+x2’+x3’ -x3’’ ≤ 1s.t.     -x1 -x2’ -x3’+x3’’ ≤-1 -2x1+x2’ -x3’+x3’’ ≤-2 x1, x2’, x3’, x3’’ ≥0 7上述第一类对称形式上述第一类对称形式LP问题的对偶问题为：问题的对偶问题为：则上述问则上述问题变为：题变为：Min W =2y1+y2 -y3-2y4   y1+y2 -y3-2y4 ≥ 1  -y1+y2 -y3 +y4 ≥-2 s.t.      -y1+y2 -y3 -y4 ≥ 1             y1 -y2+y3 +y4 ≥-1  y1, y2, y3, y4 ≥0 Min W =2u1+u2+2u3  u1+u2+2u3 ≥1  s.t.     u1 -u2+ u3  ≤2 -u1+u2+ u3  =1           u1≥0, u3≤0 ,u2无约束无约束 令令 u1= y1      u2=y2-y3  u3=-y48(D)Min W =2u1+u2+2u3  u1+u2+2u3 ≥1  s.t.     u1 -u2+ u3  ≤2 -u1+u2+ u3  =1           u1≥0, u3≤0 ,u2无约束无约束 (L)Max Z = x1+2x2+x3  x1+x2-x3  ≤2  s.t.      x1 -x2+x3  = 1 2x1+x2+x3 ≥2           x1≥0, x2≤0 ,x3无约束无约束 对偶关系：对偶关系：一个问题第一个问题第i个变量的约束情况决定另一问题个变量的约束情况决定另一问题第第i个约束不等式的方向，反之亦然。

个约束不等式的方向，反之亦然正常的对正常的，不正常的对不正常的正常的对正常的，不正常的对不正常的9例例3 3 直接写出直接写出LPLP问题的对偶问题问题的对偶问题1011第二节第二节 LPLP问题的对偶理论问题的对偶理论若若X(0),Y(0)分别为分别为(L),(D)的可行解，则有的可行解，则有CTX(0)≤bTY(0) 定理定理1(1(弱对偶定理弱对偶定理): ): 极大化原问题目标函数值总是不极大化原问题目标函数值总是不大于其对偶问题的目标函数值大于其对偶问题的目标函数值证明：证明：由于由于X(0)是是(L)的可行解，有的可行解，有AX(0)≤b, X(0)≥0.由于由于Y(0)是是(D)的可行解，有的可行解，有Y(0)≥0. Y(0)T左乘不等式组左乘不等式组AX(0)≤b的两边得：的两边得：Y(0)TAX(0)≤ Y(0)Tb.两边同时转置得两边同时转置得X(0)TATY(0) ≤ bTY(0)                                                  （（1））12又又ATY(0) ≥C, X(0)T≥0.所以所以 X(0)TATY(0) ≥X(0)TC = CTX(0)                                  (2)由（由（1），（），（2））得：得：CTX(0) ≤ bTY(0) 13推论推论1 1 若若LPLP问题有无界解，则其对偶问题无可行解；问题有无界解，则其对偶问题无可行解； 若若LPLP问题无可行解，则对偶问题或有无界解或无可行解。

问题无可行解，则对偶问题或有无界解或无可行解推论推论2 2极大化问题的任何一个可行解所对应的目标极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题目标函数值的下界函数值都是其对偶问题目标函数值的下界极小化问题的任何一个可行解所对应的目标极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题目标函数值的上界函数值都是其对偶问题目标函数值的上界推论推论3 314例例4 4 考虑下面一对考虑下面一对LPLP问题问题其对偶问题为：其对偶问题为：由于由于X(0) =(1,1,1,1)T,Y(0)=(1,1)T分别为分别为(L),(D)的可行解，的可行解，故故Z≤40,W≥10.Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 ≤20  s.t.     2x1+  x2+3x3+2x4  ≤20              x1,x2,x3,x4 ≥0 Min W = 20y1+20y2             y1+2y2 ≥ 1 2y1+  y2 ≥ 2 s.t. 2y1+3y2 ≥ 3          3y1+2y2 ≥ 4 y1,y2≥015定理定理2 2（最优性准则）（最优性准则） 当当LPLP问题目标函数值与其对偶问问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为最优解。

题目标函数值相等时，各自的可行解即为最优解若若X(0),Y(0)分别为分别为(L)，，(D)的可行解的可行解, ,且且CTX(0)＝＝bTY(0) ，，则则X(0),Y(0)分别为分别为(L)，，(D)的最优解的最优解证明：证明：由定理由定理1 1可知，对于可知，对于(L)的任意可行解的任意可行解X，有，有CTX ≤ bTY(0) 由于由于CTX(0) = bTY(0) ，故，故X(0)为为 (L) 的最优解的最优解同理同理Y(0)为为(D)的最优解的最优解16例例5 5Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 ≤20  s.t.     2x1+  x2+3x3+2x4  ≤20              x1,x2,x3,x4 ≥0 Min W = 20y1+20y2             y1+2y2 ≥ 1 2y1+  y2 ≥ 2 s.t. 2y1+3y2 ≥ 3          3y1+2y2 ≥ 4 y1,y2≥0由于由于X(0)=(0,0,4,4)T, Y(0)=(6/5,1/5)T是是(L)，，(D)的的可行解且可行解且 CX(0)=bTY(0)=28，所以，所以X(0),Y(0)分别为分别为(L)，，(D)的最优解。

的最优解17定理定理3 3（强对偶定理）（强对偶定理） 若若(L)，，(D)均有可行解，则均有可行解，则(L)，，(D)均有最优解，均有最优解，且目标函数最优值相等且目标函数最优值相等证明：证明： 设设X(0),Y(0)分别为分别为(L)，，(D)的可行解的可行解, ,由弱对偶定理，由弱对偶定理，对于对于(L)的任意可行解的任意可行解X，有，有CTX ≤ bTY(0)，所以，所以CTX在可在可行域内有上界，故行域内有上界，故(L)有最优解有最优解 同理，对于同理，对于(D)的任意可行解的任意可行解Y，，有有bTY ≥CTX(0)，所，所以以bTY在可行域内有下界，故在可行域内有下界，故(D)有最优解有最优解设设(L)的最优解为的最优解为X(0)，且，且X(0)所对应的最优基为所对应的最优基为B，，X(0)可以表示为可以表示为X(0) = = XB(0)   = = B-1b XN(0)            018则则( (σAT, ,σST)= ( (CT, ,0T) –CBTB-1(A, I) ≤0由于由于CT–CBTB-1A≤0，，所以所以CBTB-1A ≥CT即即AT(CBTB-1)T≥C (1)又又0T–CBTB-1I ≤0，，故故(CBTB-1)T≥0. (2). (2)令令Y(0)=(CBTB-1)T，，由由(1) (2)(2)知知Y(0)是是(D)的可行解的可行解. .因为因为CTX(0)=(CBT, CNT)   XB(0)  =CBT XB(0)+CNT XN(0) = CBTB-1b XN(0)而而bTY(0) =bT(CBTB-1)T = CBTB-1b则则CTX(0)=bTY(0)，由最优性准则知，，由最优性准则知， X(0),Y(0)分别为分别为(L)，，(D)的最优解的最优解, , 且目标函数最优值相等。

且目标函数最优值相等19推论：推论： 在用单纯形法求解在用单纯形法求解LPLP问题问题(L)的最优单纯形表中，的最优单纯形表中，松弛变量的检验数的相反数就是其对偶问题松弛变量的检验数的相反数就是其对偶问题(D)的最优解的最优解证明：因为证明：因为σsT=0T-CBTB-1I= -CBTB-1                        y*T=CBTB-1            所以所以  y*= -σs例例5 5 求下列问题对偶问题的最优解求下列问题对偶问题的最优解Max Z =2x1+3x2   s.t.     x1+ 2x2≤8          4x1            ≤ 16                  4x2≤ 12              x1 ,x2 ≥0 解：化为标准型解：化为标准型Max Z =2x1+3x2+0x3+0x4+0x5   s.t.     x1+ 2x2+x3              = 8          4x1                    +x4       =16                  4x2              +x5=12            x1 ,x2 , x3, x4, x5≥0 20cj  2       3        0          0        0   CB XB b  x1        x2         x3            x4          x5       2      x1 0      x5 3      x244 2  1       0        0        1/4       0         0       0       -2        1/2       1         0       1       1/2     -1/8       0        -14  0       0      -3/2     -1/8      0此时达到最优解此时达到最优解X*=(4, 2)T, Max Z=14。

对偶问题的最优解为对偶问题的最优解为Y*=(3/2, 1/8, 0)T运用单纯形法计算得原问题的最终表如下：运用单纯形法计算得原问题的最终表如下：21定理定理4 4（互补松弛定理）（互补松弛定理）在最优情况下，原问题的第在最优情况下，原问题的第i个决策变个决策变量与其对偶问题第量与其对偶问题第i个约束中的松弛变量的乘积恒为零个约束中的松弛变量的乘积恒为零 设设X(0),Y(0)分别为分别为(L),(D)的的可行解，则可行解，则X(0),Y(0)分别为分别为(L),(D)的最优解的充要条件为的最优解的充要条件为 , ,有有 m(1)(1)若若xl(0) >0，，则则∑∑ail yi(0) = Cl i=1 m(2)(2)若若∑∑ail yi(0) > Cl ，，则则xl(0) = 0 i=1 n(3)(3)若若yk(0) >0，，则则∑∑akj xj(0) = bk j=1 n(4)(4)若若∑∑akj xj(0)  < bk ，，则则yk(0) =0 j=122例例6 6 考虑下面问题考虑下面问题Max Z = x1+2x2+3x3 +3x4 x1+2x2+2x3+3x4 ≤20  s.t.     2x1+  x2+3x3+2x4  ≤20              x1,x2,x3,x4 ≥0 Min W = 20y1+20y2             y1+2y2 ≥ 1 2y1+  y2 ≥ 2 s.t. 2y1+3y2 ≥ 3          3y1+2y2 ≥ 4 y1,y2≥0已知已知(D)的的最优解为最优解为 Y*=(6/5,1/5)T 用互补松弛用互补松弛定理求出定理求出(L)的最优解。

的最优解23所以所以x1*=x2*=0.    解：由于解：由于y1*> 0, y2*> 0, ,由互补松弛性知由互补松弛性知解得解得x3*= x4*=4.  所以所以(L)的最优解为的最优解为X*=(0,0,4,4)T因为因为代入代入(1),(2)得得24若若X*,Y* 分别为分别为(L),(D)的最优解，那么的最优解，那么CTX*=bTY* 由由 Z*= bTY* =b1y1*+b2y2*++bmym* 可知可知  Z*/  bi = yi*  yi*表示资源量表示资源量bi 变化变化1 1个单位对目标函数最优值个单位对目标函数最优值Z 产生的影产生的影响，称之为响，称之为第第i 种资源的影子价格种资源的影子价格 第三节第三节 对偶问题的经济解释对偶问题的经济解释--------影子价格影子价格一、影子价格一、影子价格1.1.定义定义 影子价格是最优配置下资源的理想价格影子价格是最优配置下资源的理想价格2.2.含义含义25 1       0       0       1/4     0         0       0      -2       1/2     1         0       1     1/2     -1/8     0        4422      x1 0      x5 3      x2 x1       x2        x3          x4         x5        CB XB b 2       3      0        0 0  cj-14       0       0     -3/2    -1/8    0例例7 7 下面是一张下面是一张LPLP问题的最优单纯形表，其中问题的最优单纯形表，其中x3, x4, x5为为松弛变量松弛变量则对偶问题的最优解为则对偶问题的最优解为Y*=(1.5, 0.125, 0)T26例例8 8X* =(4, 2)T，，Z* =14Q(4, 2)Z=14x1x24x1=164x2=12x1+2x2=844083Q(4.25, 1.875)Z=14.125Q(4, 2.5)Z=15.5Q(4, 2)Z=14   Max Z =2x1+3x2  x1+ 2x2≤8   s.t.   4x1            ≤ 16                   4x2≤ 12               x1 ,x2 ≥0 8X1* =(4, 2.5)T，，Z1*=15.5X2* =(4.25, 1.875)T，，Z2* =14.125X3* =(4, 2)T，，Z3* =1427（（1 1）告诉管理者增加何种资源对企业更有利；）告诉管理者增加何种资源对企业更有利；cj  2       3        0          0        0   CB XB b  x1        x2          x3           x4          x5       2      x1 0      x5 3      x244 2  1       0        0        1/4       0         0       0       -2        1/2       1         0       1       1/2     -1/8       0        -14  0       0      -3/2     -1/8      0（（2 2）告诉管理者花多大代价买进资源或卖出资源）告诉管理者花多大代价买进资源或卖出资源是合适的；是合适的；（（3 3）为新产品定价提供依据。

为新产品定价提供依据 二、影子价格的作用二、影子价格的作用28一、对偶单纯形法的步骤一、对偶单纯形法的步骤(1)(1)化化LP问题的约束条件为问题的约束条件为“≤””形式形式, ,引入松弛变量引入松弛变量, ,建立初始表建立初始表; ;(2)(2)若所有常数项若所有常数项bi≥0，则最优解已经达到，否则，则最优解已经达到，否则bl=Min{bi|bi<0}，，       选取选取bl所对应的变量为出基变量；所对应的变量为出基变量；(3)(3)计算计算θk=Min{σj /alj |alj<0}，，选取选取θk所对应的变量为进基变量；所对应的变量为进基变量；(4)(4)以以alk为主元素进行旋转运算，转第二步为主元素进行旋转运算，转第二步建初始表建初始表 结束结束选择出基和进基变选择出基和进基变量，进行旋转运算量，进行旋转运算YN所有所有bi≥0第四节第四节 对偶单纯形法对偶单纯形法29例例9 9 用对偶单纯形法求解下列用对偶单纯形法求解下列LPLP问题问题解：原问题变形为解：原问题变形为Min Z = x1+2x2+3x3    s.t.    x1 -x2+   x3≥4            x1+x2+2x3≤8 x2  -  x3≥2  x1, x2, x3≥0 Max Z’ = -x1-2x2-3x3 s.t.   -x1+x2 -  x3≤-4         x1+x2+2x3≤8 -x2+  x3≤-2 x1, x2, x3≥0 Max Z’ = -x1-2x2-3x3 s.t.   -x1+x2 -  x3+x4                =-4         x1+x2+2x3        +x5        = 8 -x2+ x3                 +x6=-2 x1, x2, x3, x4, x5, x6≥0 二、对偶单纯形法的算例二、对偶单纯形法的算例30cj CB XBb x1x2x3x4x5x6σj       0     x40     x50     x6-48-2-1      1      -1      1       0       0 1      1       2       0      1        0 0     -1       1      0       0        10      -1     -2     -3     0      0       0cj-1 -2-3000 CB XBb x1x2x3x4x5x6-1    x141-11-1000    x540                211100    x6-20-11001σj       4       0     -3     -2    -1     0      0-1     -2      -3      0       0       031cj-1 -2-3000 CB XBb x1x2x3x4x5x6-1    x16100-10-10    x500               03112-2    x2201-100-1σj       10      0       0      -5     -1      0      -332三、几个问题的讨论三、几个问题的讨论1.1.对偶单纯形法只适用于具有正则解的对偶单纯形法只适用于具有正则解的LPLP问题。

问题 正则解正则解：若：若LP问题存在基解问题存在基解X，且对应于此，且对应于此 基解基解的检验数均的检验数均≤0( (对于极大化问题对于极大化问题) )，则称，则称X为为LP问题的正问题的正则解2.2.若最小比值原则失效，则无可行解若最小比值原则失效，则无可行解3.3.对偶单纯形法所包含的创新思想对偶单纯形法所包含的创新思想331.1.最优性：最优性： j ＝＝cj - CBTB-1Pj≤0（（Max））2.2.可行性：可行性：XB* ＝＝ B-1b≥0二、灵敏度分析常用的两个公式二、灵敏度分析常用的两个公式当当LPLP问题问题中的某些参数中的某些参数发生发生变化时，对最优解的变化情况进行分析变化时，对最优解的变化情况进行分析Max Z = CTXs.t.    AX≤b          X≥0一、灵敏度分析的定义一、灵敏度分析的定义三、灵敏度分析的几种可能结果三、灵敏度分析的几种可能结果 1.1.最优解保持不变最优解保持不变 2.2.最优基不变，但最优解改变最优基不变，但最优解改变 3.3.最优基改变最优基改变第五节第五节 线性规划的灵敏度分析线性规划的灵敏度分析341.1.直接用单纯形表求直接用单纯形表求B-1四、右端项四、右端项 b 的变化分析的变化分析——求求B-1由由AX≤b→ AX+IXS=b （（初始表）初始表）两边左乘两边左乘B-1得得B-1AX+ B-1XS= B-1b （（最优表）最优表）例例1 1 LP LP问题问题   Max Z =2x1+3x2  x1+ 2x2≤8   s.t.   4x1            ≤ 16                   4x2≤ 12               x1 ,x2 ≥0 的初始单纯形表和最优单纯形表如下的初始单纯形表和最优单纯形表如下35最优表：最优表：四、右端项四、右端项 b 的变化分析的变化分析——求求B-1cj23000CBXBbx1x2x3x4x50x38121000x416400100x51204001σj       23000cj23000CBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80σj-1400-3/2-1/80初始表：初始表：362.2.公式推导公式推导             假设假设b只有一个分量只有一个分量br 发生变化，发生变化，br’=br+ br，，则则B 1(b+ b )＝＝B-1b +B-1 b四、右端项四、右端项 b 的变化分析的变化分析——公式推导公式推导 37即即则则解不等式组得解不等式组得  br 的变化范围：的变化范围：注：注：(1) (1) 此时最优基不变，但最优解发生改变。

此时最优基不变，但最优解发生改变 (2) (2) 此变化范围仅适用于此变化范围仅适用于b 的一个分量发生变化的情形的一个分量发生变化的情形四、右端项四、右端项 b 的变化分析的变化分析——公式推导公式推导 38           cj4517000CBXBbx1x2x3x4x5x6x70x512084611000x63013220100x71503852001σ4517000例例2 2 下面是求解同一下面是求解同一LPLP问题的初始单纯形表和最优单纯形表，问题的初始单纯形表和最优单纯形表，求求b b1 1, ,b b2 2, ,b b3 3的变化范围，使原最优基不变的变化范围，使原最优基不变初始表初始表           cj4517000CBXBbx1x2x3x4x5x6x74x11411/32/302/15-1/1507x4804/32/31-1/158/1500x792013/35/30-4/15-13/151σ0-17/3-19/30-1/15-52/150最优表最优表四、右端项四、右端项 b 的变化分析的变化分析——例题例题 39解：解：40cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-11     σ-800-3-3-1例例3 3 下面是某下面是某LPLP问题的单纯形表，问题的单纯形表，x4, x5为松弛变量。

为松弛变量1 1）求）求λλ的取值范围，使得原最优基仍为最优基；的取值范围，使得原最优基仍为最优基；（（2 2）求）求λλ为何值时，使得原最优基不变而目标函数值最大为何值时，使得原最优基不变而目标函数值最大假设原来的假设原来的b被被 b + +λλ b* 代替，其中代替，其中b* =   1                                                                         -1四、右端项四、右端项 b 的变化分析的变化分析——例题例题 41解解: (1) : (1) B-1=  3    -1                           -1    1所以所以 -1/4≤λλ≤1XB* = B-1 b’ = B-1 ( b + +λλ b* )       = B-1b + +B-1      λλ -λ -λ =   1   +   3    -1       λλ           2        -1    1      - - λλ       =   1+4λ λ ≥0≥0 2 -2λλ当当λλ＝＝1时，时，Z*=10，，达到最大。

达到最大42解：解：（（1 1））设设I、、II两种产两种产品的产量分别为品的产量分别为x1, x2建建立该问题的数学模型为立该问题的数学模型为: :例例4 4 I      II设设   备备          1      2      8台时台时 原材料原材料A      4      0      16公斤公斤原材料原材料B      0      4      12公斤公斤工厂每生产一件产品工厂每生产一件产品I可获利可获利2 2元，每生产一件产品元，每生产一件产品II可获利可获利3 3元1 1）应如何安排生产使该厂获利最多？）应如何安排生产使该厂获利最多？（（2 2）工厂新增）工厂新增2424公斤原材料公斤原材料A A，问如何安排新的生产计划以使获，问如何安排新的生产计划以使获利最多？利最多？四、右端项四、右端项 b 的变化分析的变化分析——例题例题43cj  2       3       0       0        0    CB XB b  x1        x2        x3         x4          x5      2      x1 0      x5 3      x2  4  4  2  1       0       0      1/4       0         0       0      -2      1/2       1         0       1     1/2    -1/8       0        σj -14  0       0    -3/2   -1/8       0用单纯形法求得最优单纯形表如下：用单纯形法求得最优单纯形表如下：最优生产计划为：生产最优生产计划为：生产4件产品件产品I，，2件产品件产品II；最大利润为；最大利润为14。

44（（2））工厂新增工厂新增2424公斤原材料公斤原材料A A，则，则cj  2       3       0       0        0    CB XB b  x1        x2        x3           x4           x5      2      x1 0      x5 3      x2  10  16  -1  1       0       0      1/4       0         0       0      -2      1/2       1         0       1     1/2    -1/8       0        σj -14  0       0    -3/2    -1/8        02      x1 0      x5 0      x48128  1       2       1        0         0  0       4       0        0         1  0      -8      -4       1         0σj-16  0      -1       -2       0        0新的最优生产计划为：生产新的最优生产计划为：生产8件产品件产品I，，0件产品件产品II；最大利润为；最大利润为16。

将其代入原最优表，并利用对偶单纯形法迭代：将其代入原最优表，并利用对偶单纯形法迭代：45cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-11       σ00-3-3-1例例5 5 下面是一张下面是一张LPLP问题的最优单纯形表问题的最优单纯形表, ,观察其目标函数观察其目标函数系数的改变对检验数的影响系数的改变对检验数的影响五、价值系数五、价值系数 C 的变化分析的变化分析c cj j 的变化会引起检验数的变化会引起检验数σj= cj -CBTB-1Pj 的变化的变化, ,有两种情况有两种情况: :Ø非基变量的价值系数非基变量的价值系数c cj j 变化，不影响其它检验数变化，不影响其它检验数. .Ø基变量的价值系数基变量的价值系数c cj j 变化，影响所有非基变量检验数变化，影响所有非基变量检验数. .461.1.非基变量价值系数的改变非基变量价值系数的改变若非基变量的价值系数若非基变量的价值系数cj 变为变为cj ’= cj +△△cj ，，讨论：讨论：(1)(1)当当σj’≤0，即，即△△cj ≤ - -σj 时，原最优解不变；时，原最优解不变；(2)(2)当当σj’ > > 0，即，即△△cj > > - -σj 时，原最优解改变。

时，原最优解改变五、价值系数五、价值系数 C 的变化分析的变化分析——公式推导公式推导 则则xj 的检验数为的检验数为47例例6 6 Max Z = -2x1 - 3x2 - 4x3          s.t.       -x1-2x2-x3+x4  = - 3                  -2x1+x2-3x3+x5 = - 4                      x1, x2, x3, x4, x5 ≥0五、价值系数五、价值系数 C 的变化分析的变化分析——例题例题 最优单纯形表为最优单纯形表为cj-2-3-400CBXBbx1x2x3x4x5-3 x2 2/501-1/5-2/51/5-2 x1 11/5107/5-1/5-2/5σj00-9/5-8/5-1/5为使原最优解不变，求为使原最优解不变，求 c3 的变化范围的变化范围48解：最优单纯形表为解：最优单纯形表为从表中看到从表中看到σ3=-9/5+Δc3 , ,可见可见, ,当当Δc3 ≤ 9/5 ，即，即 c3 ≤-4＋＋9/5＝＝-11/5时，原最优解不变时，原最优解不变cj-2-3-400CBXBbx1x2x3x4x5-3 x2 2/501-1/5-2/51/5-2 x1 11/5107/5-1/5-2/5σj00-9/5-8/5-1/5cj-2-3-4+Δc300CBXBbx1x2x3x4x5-3 x2 2/501-1/5-2/51/5-2 x1 11/5107/5-1/5-2/5σj00-9/5+Δc3-8/5-1/5492.2. 基变量价值系数的改变基变量价值系数的改变五、价值系数五、价值系数 C 的变化分析的变化分析——公式推导公式推导 若基变量的价值系数若基变量的价值系数 变为变为 则则即即50例例7 7 下表为最优单纯形表下表为最优单纯形表, ,计算计算 c2 变化的范围，使得变化的范围，使得原最优解不变。

原最优解不变c j23000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213 x2 2011/2-1/80σj00-3/2 -1/80五、价值系数五、价值系数 C 的变化分析的变化分析——例题例题 51当当-3≤Δc2≤1，，即即 0≤c2≤4 时，原最优解不变时，原最优解不变c j23000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213 x2 2011/2-1/80σj00-3/2 -1/80cj23+Δc2000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213+Δc2 x2 2011/2-1/80σj00-3/2 -Δc2/2-1/8+Δc2/80521.1.增减变量增减变量(2)(2)删除变量删除变量删除非基变量最优解不变删除非基变量最优解不变删除基变量的处理方法：删除基变量的处理方法： 将将xj 的系数的系数cj 变为变为-M，迫使，迫使xj＝＝0(1)(1)增加变量增加变量若所增加变量的检验数若所增加变量的检验数≤0≤0，则原最优解不变；，则原最优解不变；否则，用单纯形法迭代求最优解。

否则，用单纯形法迭代求最优解六、技术矩阵六、技术矩阵 A 的变化分析的变化分析532.2.Pj 的变化的变化则最优解不变则最优解不变则原最优解改变则原最优解改变六、技术矩阵六、技术矩阵 A 的变化分析的变化分析543.3.增减约束条件增减约束条件(1)(1)删除约束条件删除约束条件当当σσn+1 1 0 0, ,σσn+2+2 0 0时最优解不变时最优解不变; ;否则否则, ,运用单纯形法运用单纯形法迭代求最优解迭代求最优解六、技术矩阵六、技术矩阵 A 的变化分析的变化分析55(2)(2)增加约束条件增加约束条件六、技术矩阵六、技术矩阵 A 的变化分析的变化分析Ø化约束条件为化约束条件为≤≤的形式，引入松弛变量的形式，引入松弛变量xn+1；；Ø把增加的约束条件直接写入最优表把增加的约束条件直接写入最优表( (以松弛变量以松弛变量xn+1为基为基变量变量) )，得到一个非标准表；，得到一个非标准表；Ø化非标准表为标准表，若化非标准表为标准表，若b n+1’  ００，则最优解仍为最优，则最优解仍为最优解，解，若若bn+1’<００，则用对偶单纯形法迭代找出最优解则用对偶单纯形法迭代找出最优解。

56cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-11 σj-800-3-3-1例例8 8 已知某已知某LPLP问题的最优单纯形表如下：问题的最优单纯形表如下：如果增加约束条件如果增加约束条件x1+x3≥2，，最优解将如何变化？最优解将如何变化？六、技术矩阵六、技术矩阵 A 的变化分析的变化分析57cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-110      σ-800-3-3-10CBXBbx1x2x3x4x5x62x1110-13-103x22012-1100x6-100-23-11      σ-800-3-3-10 x6       -2        -1       0        -1        0       00 x6 0   0   1非标准表非标准表标准表标准表 x1+x3≥2          -x1-x3+x6= -2 58cj231000CBXBbx1x2x3x4x5x62x1210100-13x210102010x51002-31-1     σ-700-1-60-159cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-11      σ-800-3-3-1课堂练习课堂练习 下面是某下面是某LPLP问题的最优单纯形表，当增加约束条问题的最优单纯形表，当增加约束条件件 x1+x2≤4时时，最优解如何变化？，最优解如何变化？60cj231000CBXBbx1x2x3x4x5x62x1110-13-103x22012-1100x64110001     σ-800-3-3-10cj231000CBXBbx1x2x3x4x5x62x1110-13-103x22011-1100x6100-1-201     σ-8000-3-10原最优解不变原最优解不变61。