大学精品课件：运筹学（二）.ppt

1、第二章第二章线性规划的线性规划的对偶理论与灵敏度分析对偶理论与灵敏度分析主要内容：主要内容：第一节第一节 线性规划的对偶问题线性规划的对偶问题第二节第二节 对偶问题的基本性质对偶问题的基本性质第三节第三节 影子价格影子价格第四节第四节 对偶单纯形法对偶单纯形法第五节第五节 灵敏度分析灵敏度分析第一节第一节线性规划的对偶问题线性规划的对偶问题一、对偶问题的提出一、对偶问题的提出 例例1 1（回顾第一章）（回顾第一章）：美佳公司计划制造：美佳公司计划制造，两种家电产品。已知各制造一件两种家电产品。已知各制造一件时分别占用的设备时分别占用的设备A,BA,B的台时、调试时间、的台时、调试时间、调试工序

2、及每天可用于这两种家电的能调试工序及每天可用于这两种家电的能力、各售出一件的获利情况，如表力、各售出一件的获利情况，如表1-11-1所所示。问该公司应制造两种家电各多少件，示。问该公司应制造两种家电各多少件，使获取的利润为最大。使获取的利润为最大。表表1-1项目项目每天可用能力每天可用能力设备设备A（h)0515设备设备B（h)6224调试工序（调试工序（h)115利润（元）利润（元）21 设设x x1 1,x,x2 2 分别代表分别代表，两种家电两种家电的生产量，的生产量，此问题的数学模型为：此问题的数学模型为：目标函数目标函数 约束条件约束条件212maxxxz 0,52426155.21

3、21212xxxxxxxst 例例2 2：在例：在例1 1中，若有某个公司想把美佳公司的中，若有某个公司想把美佳公司的资源收购过来，它至少付出多大的代价，才能使资源收购过来，它至少付出多大的代价，才能使美佳公司愿意放弃生产活动，出让自己的资源美佳公司愿意放弃生产活动，出让自己的资源。但少生产一件但少生产一件产品，则产品，则丧失了丧失了1元的利润元的利润少生产一件少生产一件产品，则可以节省设产品，则可以节省设备备A、设备、设备B和调试工序和调试工序5、2、1个小时，把这些资源出租，每小时个小时，把这些资源出租，每小时租金分别为租金分别为y1，y2，y3，就可以获就可以获得租金得租金5y1+2y2

4、+y3?但少生产一件但少生产一件I产品，则产品，则丧失了丧失了2元的利润元的利润同样，少生产一件同样，少生产一件I产品，则可以产品，则可以节省设备节省设备A、设备、设备B和调试工序和调试工序0、6、1个小时，把这些资源出租，个小时，把这些资源出租，就可以获得租金就可以获得租金0y1+6y2+y3 所以，只有当所以，只有当 时，才可能出让。时，才可能出让。总的出让费总的出让费 ，最低出让费即为：最低出让费即为：2632 yy125321 yyy32152415minyyyw 32152415yyy 因此，该问题的数学模型为：因此，该问题的数学模型为：32152415minyyyw 2632 yy

5、125321 yyy0,321 yyy.t s二、对称形式下对偶问题的一般形式二、对称形式下对偶问题的一般形式 满足下列条件的线性规划问题称为具满足下列条件的线性规划问题称为具有有对称形式对称形式：其变量均具有非负约束，其约束条件其变量均具有非负约束，其约束条件当目标函数求极大时均取当目标函数求极大时均取“”，当目，当目标函数求极小时均取标函数求极小时均取“”。,n),(jxbxaxaxa bxaxaxabxaxaxas.t.jmnmnmmnnnn21022112222212111212111nnxcxcxcZ 2211maxmmybybybW2211min ,m),(iycyayaya cy

6、ayayacyayayas.t.inmmnnnmmmm21022112222211211221111原问题原问题对偶问题对偶问题CXZ maxbYWmin0bXAXts.0YCYAts.原问题原问题对偶问题对偶问题A A约束系数矩阵约束系数矩阵约束系数矩阵的转置约束系数矩阵的转置b b约束条件右端向量约束条件右端向量目标函数中的价值系数向量目标函数中的价值系数向量C C目标函数中的价值系数向量目标函数中的价值系数向量约束条件右端向量约束条件右端向量目标函数目标函数约束条件约束条件决策变量决策变量CXz maxbYwminbAXCYA0X0Y对称形式下原问题与对偶问题的对应关系：对称形式下原问题

7、与对偶问题的对应关系：即：即：对偶问题对偶问题212maxxxz 0,5 2426155 .2121212xxxxxxxst32152415minyyyw 2632 yy125321 yyy0,321 yyy.t s原问题原问题对偶问题对偶问题如：如：三、非对称形式原三、非对称形式原-对偶问题的关系对偶问题的关系332211maxxcxcxcz 约约束束无321333323213123232221211313212111,0,0.xxxbxaxaxabxaxaxabxaxaxast求下述线性规划问题的对偶问题：求下述线性规划问题的对偶问题：:则则0,0,x x,x x,x x,x xx xx

8、x,x xx x令令3 33 32 23 33 33 32 22 2 33332211maxxcxcxcxcz 03213321333333323213123233232221211313313212111x,x,x,x)(bxaxaxaxa)(bxaxaxaxa)(bxaxaxaxast.约束（约束（2-2）和约束（）和约束（3）两边同乘以）两边同乘以“-1”，则变换为：，则变换为：约束（约束（2）可以用以下两个约束来表示：）可以用以下两个约束来表示：2)-(2 1)-(2 23233232221212323323222121bxaxaxaxabxaxaxaxa 令各约束对应的对偶变量为：令

9、各约束对应的对偶变量为：，则其对偶问题为：，则其对偶问题为：33222211minybybybybw 0,.32213333223223113333322322311323322222221121331221221111yyyycyayayayacyayayayacyayayayacyayayayast3221,yyyy 33332211maxxcxcxcxcz 0,.33213333333232131232332322212123233232221211313313212111xxxxbxaxaxaxabxaxaxaxabxaxaxaxabxaxaxaxast，则有：，则有：令令33222,

10、yyyyy 332211minybybybw 0,0 .3213333223113333322311323322221121331221111yyycyayayacyayayacyayayacyayayast无无约约束束整理，得：332211minybybybw 0,0.321333322311323322221121331221111yyycyayayacyayayacyayayast无无约约束束因此，线性规划原问题与对偶问题的关系见下表：因此，线性规划原问题与对偶问题的关系见下表：原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函

11、数目标函数 min约约束束条条件件m个个m个个变变量量0000=无约束无约束变变量量n个个n个个约约束束条条件件0000无约束无约束=约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项正常对正常，反常对反常正常对正常，反常对反常 在正常的情况下，线性规划的所有变量都是在正常的情况下，线性规划的所有变量都是0的，的，求最大化问题的约束是求最大化问题的约束是型的，而求最小化问题的约束是型的，而求最小化问题的约束是型的。型的。所谓所谓“正常对正常，反常对反常正常对正常，反常对反常”，是指，是指：只要原模型中的只要原模型中的

12、变量和约束变量和约束都符合这些规律，对偶模都符合这些规律，对偶模型中对应的型中对应的约束和变量约束和变量也一定符合这些规律；也一定符合这些规律；如果原模型中的变量和约束违反了这些规律，则对偶如果原模型中的变量和约束违反了这些规律，则对偶模型中的约束和变量也一定违反这些规律。模型中的约束和变量也一定违反这些规律。记忆口诀记忆口诀321362minxxxW无约束321321321321,0,060434803x 430 xxxxxxxxxxx例例3：写出下列线性规划问题的对偶问题：写出下列线性规划问题的对偶问题：正常正常正常正常反常反常反常反常321608030maxyyyZ0,034 363 4

13、24 321321321321yyyyyyyyyyyy无约束该问题的对偶问题为：该问题的对偶问题为：正常正常反常反常反常反常正常正常第二节第二节对偶问题的基本性质对偶问题的基本性质一、单纯形法的矩阵描述一、单纯形法的矩阵描述0bCXXAXtsz.max 考虑线性规划问题（有考虑线性规划问题（有n个变量，个变量，m个约束条件）：个约束条件）：引入松弛变量引入松弛变量TmnnnSxxxX),(21将其转化为标准形式，得到：将其转化为标准形式，得到：0,.0max SSSXXIXAXtsXz0bCX其中其中I为为mm阶单位矩阵。阶单位矩阵。设设A中存在一个可行基中存在一个可行基B，则变量，则变量X可

14、分为基变量可分为基变量XB和和非基变量非基变量XN，相应地，矩阵，相应地，矩阵A可以分为可以分为B和和N，价值系，价值系数数C可以分为可以分为CB和和CN，即：，即：),(NBXXX),(NBA),(NBCCC 则上述线性规划问题可写成如下形式：则上述线性规划问题可写成如下形式：0,.0max SSNBSNNBBXXIXNXBXtsXz0bXCXC列出初始单纯形表：列出初始单纯形表：CBCNC0BC0BxbSXbBXNXSXBNIzc BCNC0因为因为B为一个可行基，因此，可以通过迭代（上表中第三行为一个可行基，因此，可以通过迭代（上表中第三行左乘左乘B-1）得到另外一个单纯形表）得到另外一

15、个单纯形表：CBCNC0BCBCBxbBXbB1BXNXSXBB1NB11Bzc BBCCBB1NBCCBN11BCBCBCNC0BCBCBxbBXbB1BXNXSXBB1NB11Bzc BBCCBB1NBCCBN11BCB若若XB为最优基变量，则对应的目标函数值为为最优基变量，则对应的目标函数值为：bBCXzBSNNBB10 XCXC且对于上表中各检验数，有：且对于上表中各检验数，有：把上面三个式子的前两个式子合并，得到：把上面三个式子的前两个式子合并，得到：01 BBCCBB01 NBCCBN01 BCB01ABCCB01BCBbYWmin0YCYAts.可见，当原问题得到最优解时，其松弛

16、变量检验数的相反数可见，当原问题得到最优解时，其松弛变量检验数的相反数 是该问题的对偶问题的一个可行解。是该问题的对偶问题的一个可行解。该线性规划问题的对偶问题为：该线性规划问题的对偶问题为：1BCBCABCB101BCB212maxxxz0,5 2426155 .2121212xxxxxxxst32152415minyyyw2632 yy125321yyy0,321yyy.ts原问题原问题对偶问题对偶问题例：例：分别引入松弛变量和剩余变量，化为标准形式：分别引入松弛变量和剩余变量，化为标准形式：543210002maxxxxxxz0,5 2426155 .5432152142132xxxxx

17、xxxxxxxxst543210052415minyyyyyw26432yyy1255321yyyy0,54321yyyyy.ts原问题原问题对偶问题对偶问题0001210011500102624000 15015000012jjzcjcBCBxb4x2x3x4x5x3x1x5x021000015/20015/4-15/227/21001/4-1/213/2010-1/43/2000-1/4-1/2jjzc jcBCBxb1x2x3x4x5x3x1x2x原问题初始单纯形表：原问题初始单纯形表：原问题最终单纯形表：原问题最终单纯形表：110260501B6102103054*B4B2/34/10

18、2/14/102/154/51*1BBB2/32/72/152/1562/56052/15244/5151524152/34/102/14/102/154/511bB21000015/20015/4-15/227/21001/4-1/213/2010-1/43/2000-1/4-1/2jjzc jcBCBxb1x2x3x4x5x3x1x2x原问题最终单纯形表：原问题最终单纯形表：对偶问题最终单纯形表：对偶问题最终单纯形表：2100001/4-5/410-1/41/411/215/2011/2-3/215/2007/23/2jjzc jcBCBxb3y2y3y4y5y2y1y1.1.对称性对称性

19、2.2.弱对偶性弱对偶性3.3.最优性最优性4.4.强对偶性强对偶性5.5.互补松弛性互补松弛性二、对偶问题的基本性质二、对偶问题的基本性质对称性：对称性：对偶问题的问偶即原问题对偶问题的问偶即原问题证明证明：CXZ maxbYWmin0bXAXts.0YCYAts.对偶问题对偶问题原问题原问题对偶问题中若令对偶问题中若令w=-w,则该对偶问题可改写为：则该对偶问题可改写为：bYWmax0YCYAts.（1）bYWmax0YCYAts.CXzmin0XbAXts.对偶问题对偶问题原问题原问题CXz max0XbAXts.zz令即为原问题（即为原问题（1）把对偶问题作为原问题，写出其对偶问题如下

20、：把对偶问题作为原问题，写出其对偶问题如下：弱对偶性：弱对偶性：如果如果 是原问题的可行解，是原问题的可行解，是其对偶问题的可行是其对偶问题的可行解，则恒有：解，则恒有：XYbYXCCXZ maxbYWmin0bXAXts.0YCYAts.对偶问题对偶问题证明证明：因为因为 是原问题的可行解，故有：是原问题的可行解，故有：XbXA式子两边左乘式子两边左乘 (是对偶问题的可行解，因此是对偶问题的可行解，因此 ），得到：），得到：YY0YbYXAY 同理，因为同理，因为 是对偶问题的可行解，故有：是对偶问题的可行解，故有：YCYA式子两边右乘式子两边右乘 (是原问题的可行解，因此是原问题的可行解，

21、因此 ），得到：），得到：X0XXCXAYXCAY(1)(1)(2)(2)综合式子（综合式子（1）和（）和（2），得到：），得到：bYXAYXC推论：推论：（1）原问题任一可行解的目标函数值是其对偶问题目标）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。是其原问题目标函数值的上界。（2）在一对对偶问题中，若其中一个问题可行但目标函）在一对对偶问题中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。数无界，则另一个问题不可行；反之不成立。（3）在一对对偶问题

22、中，若一个问题可行，而另一个问）在一对对偶问题中，若一个问题可行，而另一个问题不可行，则该可行的问题的目标函数无界。题不可行，则该可行的问题的目标函数无界。因此因此 是原问题的最优解。是原问题的最优解。最优性：最优性：若若 和和 分别是原问题和对偶问题的可行解分别是原问题和对偶问题的可行解,且且 ，则则 和和 分别是原问题和对偶问题的最优解。分别是原问题和对偶问题的最优解。*X*YbYCX*X*Y证明证明：设：设 是原问题的任一可行解，由弱对偶性的推是原问题的任一可行解，由弱对偶性的推论论1，可得：，可得：XbYXC*又因为：又因为：，故有：，故有：bYCX*CXXC*X同理，可证同理，可证

23、是对偶问题最优解。是对偶问题最优解。*Y强对偶性：强对偶性：若一对对偶问题的原问题和对偶问题都有可行解，则它若一对对偶问题的原问题和对偶问题都有可行解，则它们都有最优解，且目标函数的最优值相等。们都有最优解，且目标函数的最优值相等。设设 是原问题的最优解，对应的最优基是是原问题的最优解，对应的最优基是B，我们已经证明，我们已经证明过过 是对偶问题的可行解。且对应的目标函数都为是对偶问题的可行解。且对应的目标函数都为 。因此，由最优性可知，因此，由最优性可知，是对偶问题的最优解。是对偶问题的最优解。结论得证。结论得证。*X1BCBbBCB11BCB证明证明：因为原问题和对偶问题都有可行解，由弱对

24、偶性推论：因为原问题和对偶问题都有可行解，由弱对偶性推论1可知，原问题和对偶问题都有界，即它们一定存在最优解。可知，原问题和对偶问题都有界，即它们一定存在最优解。综上所述，一对对偶问题的解，只能有下面三综上所述，一对对偶问题的解，只能有下面三种情况之一出现：种情况之一出现：（1）都有最优解，分别设为）都有最优解，分别设为 和和 ，且必，且必有有 ；（2）一个问题无界，另一个问题无可行解；）一个问题无界，另一个问题无可行解；（3）两个都无可行解。）两个都无可行解。*X*YbYCX*互补松弛性：互补松弛性：若若 和和 分别是原问题和对偶问题的可行解分别是原问题和对偶问题的可行解,为原问题的松弛变量

25、的值，为原问题的松弛变量的值，为对偶问题剩余变量为对偶问题剩余变量的值。的值。和和 分别是原问题和对偶问题最优解的分别是原问题和对偶问题最优解的充分必要条件是充分必要条件是 。*X*YSYSX0*XYXYSS*X*Y 若若 和和 分别是原问题和对偶问题的可行解。则有：分别是原问题和对偶问题的可行解。则有：左乘（左乘（1）证明：证明：(1)(1)充分性的证明充分性的证明 由上述所设，可知：由上述所设，可知：(1)*bIXAXS(2)*CIYAYS*X*Y(3)*bYXYAXYS(4)*CXXYAXYS*Y右乘（右乘（2）*X（3）-（4），得到：），得到：*CXbYXYXYSS若若 0*XYXY

26、SS，则，则 *CXbY由最优性可知，由最优性可知，和和 分别是原问题和对偶问题的最优解。分别是原问题和对偶问题的最优解。*X*Y(2)(2)必要性的证明必要性的证明(1)*bIXAXS(2)*CIYAYS 若若 和和 分别是原问题和对偶问题的最优解。则有：分别是原问题和对偶问题的最优解。则有：*X*Y左乘（左乘（1）(3)*bYXYAXYS(4)*CXXYAXYS*Y右乘（右乘（2）*X（3）-（4），得到：），得到：*CXbYXYXYSS由强对偶性可知，由强对偶性可知，因此，因此 *CXbY 0*XYXYSS由假设可知：由假设可知：例子：例子：已知如下线性规划问题已知如下线性规划问题543

27、2132532minxxxxxw.ts43254321xxxxx33254321xxxxx0,54321xxxxx 的对偶问题最优解为：的对偶问题最优解为：，最优目标值为，最优目标值为5 5。试用对偶理论确定原问题的最优解。试用对偶理论确定原问题的最优解。54*1y53*2y 解：首先写出原问题的对偶问题如下解：首先写出原问题的对偶问题如下0,(5)3 3y(4)2 y (3)532y(2)3 y (1)22y .212121212121yyyyyyyst 解：把解：把 的值代入到式子的值代入到式子（1 1）到（）到（5 5），），得得到到（2 2）、（）、（3 3）、（）、（4 4）取严格不

28、等式，即代表他取严格不等式，即代表他们对应的们对应的松弛变量松弛变量00，也就说明它们对应的原问题，也就说明它们对应的原问题的变量的变量 为为0 0（互补松弛性）。（互补松弛性）。*2*1yy和*4*3*2,xxx2134maxyyZ 因为因为 都都0,则代表原问题最优解对应的剩则代表原问题最优解对应的剩余变量值为余变量值为0 0，即原问题两个式子都取等式，即原问题两个式子都取等式(互补松互补松弛性）。弛性）。*2*1yy 和432*5*4*3*2*1 xxxxx332*5*4*3*2*1 xxxxx 已知已知 ，解得：，解得：，0*4*3*2xxx1*1x1*5x因此，原问题的最优解为：因此

29、，原问题的最优解为：TX)1,0,0,0,1(*第三节第三节影影 子子 价价 格（格（shadow price)shadow price)一、影子价格的定义一、影子价格的定义 在一对原问题和对偶问题中，若原问题的某个约在一对原问题和对偶问题中，若原问题的某个约束条件的右端项常数束条件的右端项常数b bi i 增加一个单位时，所引起的目增加一个单位时，所引起的目标函数最优值标函数最优值Z Z*的改变量（可以证明就是的改变量（可以证明就是y y*i i）称为第）称为第 i i 个约束条件的影子价格，又称为边际价格。个约束条件的影子价格，又称为边际价格。CXZ maxbYWmin0bXAXts.0Y

30、CYAts.对偶问题对偶问题原问题原问题CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1 设：设：B是原问题的最优基，则知原问题目标函是原问题的最优基，则知原问题目标函数的最优值为：数的最优值为：Z*=CB B-1b =Y*b =y*1b1+y*2b2+y*ibi+y*mbm 目标函数最优值变为：目标函数最优值变为：Z*=y*1b1+y*2b2+y*i（bi+1）+y*mbm Z*=Z*Z*=y*i 当当bi 变为变为bi+1时（其余右端项不变，假设也不影响时（其余右端项不变，假设也不影响B）也可以写成：也可以写成：即即y*i

31、表示表示Z*对对 bi的变化率。的变化率。)2,1(*miybZii 其经济意义是：在其它条件不变的情况下，单位资源变化其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量所引起的目标函数的最优值的变化。即对偶变量yi 就是第就是第 i 个约束条件的影子价格。个约束条件的影子价格。二、多方面理解影子价格二、多方面理解影子价格见教材见教材P58-59第四节第四节对偶单纯形法对偶单纯形法一、对偶单纯形法的原理一、对偶单纯形法的原理 对偶单纯形法是求解线性规划问题的另一基本方对偶单纯形法是求解线性规划问题的另一基本方法。法。它是根据对偶原理和单纯形法的原理而设

32、计出来它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法不要简单理解为是求解对偶问题的单纯形法。由对偶理论可以知道，对于一个线性规划问题，我由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。们能够通过求解它的对偶问题来找到它的最优解。同原始单纯形求法一样，求解对偶问题，也可以从同原始单纯形求法一样，求解对偶问题，也可以从对偶问题的一个基本可行解开始，从一个基本可行解对偶问题的一个基本可行解开始，从一个基本可行解（迭代）到另一个基本可行解，使目标函数值减少。（迭代）到另一个基本

33、可行解，使目标函数值减少。也就是说，求解原问题时，可以从原问题的一个也就是说，求解原问题时，可以从原问题的一个基本解（非基可行解）开始，逐步迭代，使目标函基本解（非基可行解）开始，逐步迭代，使目标函数值（数值（Z=Y b=CB B-1b=CX）减少，当迭代到）减少，当迭代到XB=B-1b0时，即找到了原问题的最优解，这就是对时，即找到了原问题的最优解，这就是对偶单纯形法。偶单纯形法。二、对偶单纯形法的步骤二、对偶单纯形法的步骤1.找出对偶问题的初始基可行解，列出初始单找出对偶问题的初始基可行解，列出初始单纯形表；纯形表；2.进行最优性检验，若得到最优解，停止；若进行最优性检验，若得到最优解，停

34、止；若没有得到最优解，转入步骤没有得到最优解，转入步骤3；3.确定换出基变量；确定换出基变量；4.确定换入基变量；确定换入基变量；5.用换入变量代替换出变量，得到新的单纯形用换入变量代替换出变量，得到新的单纯形表；重新转入步骤表；重新转入步骤2.32152415minyyyw2632 yy125321yyy0,321yyy.ts例子：例子：求解如下线性规划问题：求解如下线性规划问题：26432yyy1255321yyyy0,54321yyyyy.ts543210052415maxyyyyyw26432yyy1255321yyyy0,54321yyyyy.ts解：解：543210052415mi

35、nyyyyyw-15-24-5000-20-6-1100-1-5-2-101-15-24-500jjzc jcBCBxb5y2y3y4y5y4y1y-15-24-500-241/3011/6-1/600-1/3-50-2/3-1/31-150-1-40jjzc jcBCBxb5y2y3y4y5y2y1y-15-24-500-241/4-5/410-1/41/4-51/215/2011/2-3/2-15/200-7/2-3/2jjzc jcBCBxb3y2y3y4y5y2y1y得到最优解。得到最优解。第五节第五节 灵灵 敏敏 度度 分分 析析一、灵敏度分析的含义及思路一、灵敏度分析的含义及思路

36、灵敏度分析，是针对某确定的线性规划问题，灵敏度分析，是针对某确定的线性规划问题，考虑其模型中一个或几个系数（考虑其模型中一个或几个系数（)发发生变化时，已经求得的最优解会发生什么变化，生变化时，已经求得的最优解会发生什么变化，以及这些系数在什么范围内变化时，问题的最以及这些系数在什么范围内变化时，问题的最优解不会发生变化。优解不会发生变化。jiijcba,在研究一个或几个参数变化后模型的最优解在研究一个或几个参数变化后模型的最优解时，自然可以按单纯形法从头计算，但这样既时，自然可以按单纯形法从头计算，但这样既麻烦又没有必要。因为一个或几个参数的变化，麻烦又没有必要。因为一个或几个参数的变化，可

37、能直接在变化前所求的最终单纯形表中反映可能直接在变化前所求的最终单纯形表中反映出来，这就避免了从头计算，而可以从调整后出来，这就避免了从头计算，而可以从调整后的最终表入手，分析是否满足最优解的条件，的最终表入手，分析是否满足最优解的条件，如果不能满足，再从这个表开始进行迭代，求如果不能满足，再从这个表开始进行迭代，求出参数变化后的最优解。出参数变化后的最优解。CBCNC0BCBCBxbBXbB1BXNXSXBB1NB11Bzc BBCCBB1NBCCBN11BCBCBCNC0BC0BxbSXbBXNXSXBNIzc BCNC0二、目标函数中变量系数二、目标函数中变量系数 发生变化发生变化jc（

38、一）（一）变化对最优解的影响变化对最优解的影响jc 目标函数中变量系数发生变化时，只会对最终单纯目标函数中变量系数发生变化时，只会对最终单纯形表的检验数行产生影响。因此可能出现两种情况形表的检验数行产生影响。因此可能出现两种情况：1检验数仍都检验数仍都 0，此时原问题和对偶问题都仍，此时原问题和对偶问题都仍是可行解，且原问题的最优解不变是可行解，且原问题的最优解不变。2存在检验数存在检验数0时，此时原问题仍是可行解，而时，此时原问题仍是可行解，而对偶问题不是可行解，需要用单纯形法继续迭代求对偶问题不是可行解，需要用单纯形法继续迭代求问题的最优解。问题的最优解。例例1 1：在美佳公司的例子中，若

39、家电在美佳公司的例子中，若家电的利润的利润为为1.51.5元元/件，家电件，家电的利润为的利润为2 2元元/件，美佳件，美佳公司的最优生产计划有何变化？公司的最优生产计划有何变化？21000015/20015/4-15/227/21001/4-1/213/2010-1/43/2000-1/4-1/2jjzc jcBCBxb1x2x3x4x5x3x1x2x解：原问题最优单纯形表为：解：原问题最优单纯形表为：1.52000015/20015/4-15/21.57/21001/4-1/223/2010-1/43/20001/8-9/4jjzc jcBCBxb1x2x3x4x5x3x1x2x1.520

40、0006004/51-61.5210-1/50123011/50000-1/100-3/2jjzc jcBCBxb1x2x3x4x5x4x1x2x为第二种情况为第二种情况当系数变化后，调整后的最终单纯形表为：当系数变化后，调整后的最终单纯形表为：（二）（二）在什么范围内变化时最优解不变在什么范围内变化时最优解不变 例例2 2：在美佳公司的例子中，若家电在美佳公司的例子中，若家电的利的利润不变，家电润不变，家电的利润在什么范围变化时，的利润在什么范围变化时，美佳公司的最优生产计划不变？美佳公司的最优生产计划不变？jc 目标函数中变量系数目标函数中变量系数 发生变化时，要想保证发生变化时，要想保证

41、最优解不变，就必须有检验数仍都最优解不变，就必须有检验数仍都0。jc 例例2 2：在美佳公司的例子中，若家电在美佳公司的例子中，若家电的利润不的利润不变，家电变，家电的利润在什么范围变化时，美佳的利润在什么范围变化时，美佳公司的最优生产计划不变？公司的最优生产计划不变？2000015/20015/4-15/227/21001/4-1/23/2010-1/43/2000-1/2+/41-/2jjzc jcBCBxb1x2x3x4x5x3x1x2x2c2c23c若保持最优解不变，则所有检验数必须小于若保持最优解不变，则所有检验数必须小于等于零。等于零。0231042122cc2322 c2c解：解

42、：三、约束条件右边常数三、约束条件右边常数 的变化的变化ib（一）（一）变化对最优解的影响变化对最优解的影响 变化时，最终单纯形表中只有变化时，最终单纯形表中只有b列数字发生改变列数字发生改变,b=b+B B-1-1b b（b b为约束条件右端常数列向量的变为约束条件右端常数列向量的变化量），检验数行则不发生变化。可能出现两种情况：化量），检验数行则不发生变化。可能出现两种情况：1.b列中所有数字都列中所有数字都 0，此时原问题和对偶问题都，此时原问题和对偶问题都仍是可行解，仍是可行解，XB仍是原问题的最优基变量，只是其值仍是原问题的最优基变量，只是其值变为变为b=b+B-1b。2.b列中出现

43、列中出现0时，此时原问题仍是可行解，而对时，此时原问题仍是可行解，而对偶问题不是可行解，需用单纯形法继续迭代求问题的最偶问题不是可行解，需用单纯形法继续迭代求问题的最优解。注意：此时的单纯形表中该非基变量的列向量变优解。注意：此时的单纯形表中该非基变量的列向量变为为B B-1-1(P(Pj j+P Pj j)（P Pj j为非基变量系数列向量的变化为非基变量系数列向量的变化值）。值）。ija（二）基变量的系数列向量（二）基变量的系数列向量Pj的变化的变化 若为基变量的系数列向量，其改变会使检验数行和若为基变量的系数列向量，其改变会使检验数行和b列数字都会发生变化。可能出现四种情况：列数字都会发

44、生变化。可能出现四种情况：(1）检验数都）检验数都0，b列数字仍都列数字仍都0，此时原问题和对偶，此时原问题和对偶问题都仍是可行解，问题都仍是可行解，XB仍是原问题的最优基变量，只是其仍是原问题的最优基变量，只是其值发生了变化。值发生了变化。（2）b列数字都列数字都 0，但出现，但出现0的检验数的检验数,则原问题是可行则原问题是可行解，对偶问题不是可行解，此时需要按单纯形法继续迭代。解，对偶问题不是可行解，此时需要按单纯形法继续迭代。（3）出现）出现0的的b列数字，检验数仍都列数字，检验数仍都0，则原问题不是，则原问题不是可行解，对偶问题是可行解，此时需按对偶单纯形法继续迭可行解，对偶问题是可

45、行解，此时需按对偶单纯形法继续迭代。代。（4）同时出现）同时出现 0的检验数，则此时原问的检验数，则此时原问题和对偶问题都不是可行解。此时通常需要引入人工变量先题和对偶问题都不是可行解。此时通常需要引入人工变量先将原问题的解转化为可行解，再按大将原问题的解转化为可行解，再按大M法进行迭代。法进行迭代。例例5:5:在美佳公司的例子中，若家电在美佳公司的例子中，若家电每件需每件需设备设备A,BA,B和调试工序的时间变为和调试工序的时间变为8h8h、4h4h、1h1h，利润变为利润变为3 3元元/件，试重新确定该公司的最优件，试重新确定该公司的最优生产计划。生产计划。213000015/20011/

46、215/4-15/227/2101/201/4-1/213/2011/20-1/43/2003/20-1/4-1/2jjzc jcBCBxb1x2x3x4x5x3x1x2x2/34/102/14/102/154/511B2/12/12/111482/34/102/14/102/154/51212PBP2x解：解：230000-90014-24221001/2-233010-1/230001/2-5jjzc jcBCBxb1x3x4x5x3x1x2x2x23000-M-M900-1-4241221001/2-2033010-1/23000-M1/2-4M24M-50jjzc jcBCBxb1x3

47、x4x5x6x1x2x2x6x属于第属于第4种情况种情况23000-M03/800-1/24-1/611/24211/410-1/121/601/12315/8011/800-1/800-5/24-1/30-M+5/24jjzc jcBCBxb1x3x4x5x5x1x2x2x6x五、增加一个变量五、增加一个变量1.计算新增变量计算新增变量xj的检验数的检验数2.计算计算Pj3.若检验数若检验数0,则需要用则需要用单纯形法单纯形法继续迭代求出继续迭代求出新的最优解；若检验数新的最优解；若检验数0,则问题最优解不变。则问题最优解不变。例例6 6：在美佳公司的例子中，若考虑增加一个新型产在美佳公司的

48、例子中，若考虑增加一个新型产品品，生产一件该产品需设备，生产一件该产品需设备A,B及调试工序的及调试工序的时间分别为时间分别为3、4、2小时，该产品的预期盈利为小时，该产品的预期盈利为3元元/件，问该产品是否值得投产；若投产，最件，问该产品是否值得投产；若投产，最优生产计划如何变化？优生产计划如何变化？解：设生产该产品解：设生产该产品x x6 6件。件。P P6 6=(3=(3、4 4、2)2)2072432/34/102/14/102/154/51616PBP-1/23/2-1/2-15/202-1/40103/211-1/400001/40017/22-75/410015/2030012j

49、jzc jcBCBxb1x2x3x4x5x3x1x2x6x2-5/43/4-1/2-9/401-1/801/203/430-1/80-1/2001/40017/2203/817/2054/4030012jjzc jcBCBxb1x2x3x4x5x3x1x6x6x因为因为x6的检验数大于的检验数大于0，所以用，所以用单纯形法单纯形法继续迭代：继续迭代：最优生产计划变为生产产品最优生产计划变为生产产品7/2件，产品件，产品3/4件。件。六、增加一个约束条件六、增加一个约束条件 生产中增加生产工序，反映在线性规划模型生产中增加生产工序，反映在线性规划模型中就相当于增加新的约束条件。中就相当于增加新的

50、约束条件。对这种情况的灵敏度分析，是将原问题的最对这种情况的灵敏度分析，是将原问题的最优解带入新增的约束条件，如果满足，则原最优优解带入新增的约束条件，如果满足，则原最优解不变；如不满足，则将新增的约束条件直接反解不变；如不满足，则将新增的约束条件直接反映到最终单纯形表中，采用单纯形法或对偶单纯映到最终单纯形表中，采用单纯形法或对偶单纯形法进行求解形法进行求解。例例6 6：在美佳公司的例子中，若增加一个环境在美佳公司的例子中，若增加一个环境试验工序，可用能力为试验工序，可用能力为1212小时，一件产品小时，一件产品需试验需试验3 3小时，一件产品小时，一件产品需试验需试验2 2小时，问小时，问