第二章 线性规划问题的对偶与灵敏度分析

1、2022-3-121 1 线性规划的对偶问题 2 对偶问题的基本性质 4 对偶单纯形法 5 灵敏度分析2022-3-122 线性规划的对偶问题概念、理论及经济意义 线性规划的对偶单纯形法 线性规划的灵敏度分析本章内容重点2022-3-1231 线性规划的对偶问题提出问题(LP1) max z = 2x1+x2 st. 5x215 6x1+2x2 24 x1+x2 5 x1, x20一个公司要收购美佳公司的资源(设备)，问它至少要付出多大的代价？设备A设备B调试工序假设y1、y2、y3分别代表单位时间设备A、设备B、调试工序的出让价y1y2y32022-3-124美佳出价出价：出让价应不低于用同

2、等数量的资源由自己组织生产活动时所获得的利润6y2+y325y1+2y2+y31y1, y2, y30买家还价还价：买家在满足上述条件的前提下，希望用最小的代价获得美佳公司的全部资源Min 15y1+24y2+5y32022-3-125(LP2) Min 15y1+24y2+5y3st. 6y2+y32 5y1+2y2+y31 y1, y2, y3 0一个新的线性规划称(LP1)为原问题，(LP2)为对偶问题 当LP中的变量均具有非负约束，其约束条件当目标函数求极大时均取“”号，而当目标函数求极小时均取“”时，则称这样的LP问题具有对称形式对称形式2022-3-126一般规律(1) 原问题有n

3、个变量，m个约束，对偶问题有m个变量，n个约束。原问题的目标函数求极大，对偶问题的目标函数求极小(2) 原问题的目标函数中变量的系数为对偶问题的约束条件的常数项，反之亦然(3) 原问题与对偶问题的约束方程的系数矩阵互为转置2022-3-127(LP1) Max z = CX s.t. AX b X 0 (LP2) Min = bT Ys.t. AT Y CT Y 0 非对称形式非对称形式的对偶问题 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划，一般事先转换成对称形式，然后按对应规则写出其对偶问题2022-3-128Max z = x1 + 4x2 + 3x3

4、St. 2x1 + 3x2 5x3 2 3x1 x2 + 6x3 1 x1+x2+x3=4 x10, x20, x3无约束无约束y1y3y2Max z = x1 + 4x2 + 3x3St. 2x1 + 3x2 5x3 2 3x1 x2 6x3 1 x1+x2+x3 4 x1x2x3 4 x10, x20, x3无约束无约束Max z = x1 4x2 + 3x33x3St. 2x1 3x2 5x3 +5x3 2 3x1 x2 6x36x3 1 x1x2+x3 x3 4 x1+x2x3 + x34 x1 , x2 , x3, x30y3每个约束方程对应一个对每个约束方程对应一个对偶变量。原则：

5、是偶变量。原则：是“”的的方程直接对应方程直接对应y；是；是“”的的对应对应y；是；是“”的分别对的分别对应应y, y2022-3-129Min =2y1-y2+4y3-4y3St. 2y1-3y2+y3-y31 -3y1-y2-y3+y3 -4 -5y1-6y2+y3-y3 3 5y1+6y2-y3+y3 -3 y1, y2, y3, y3 0Min =2y1+y2+4y3St. 2y1+3y2+y31 3y1-y2+y3 4 -5y1+6y2+y3 = 3y1 0, y20, y3无约束无约束令令 y2= y2y3= y3y3Max z = x1 + 4x2 + 3x3St. 2x1 +

6、3x2 5x3 2 3x1 x2 + 6x3 1 x1+x2+x3=4 x10, x20, x3无约束无约束原原 问问 题题对对 偶偶 问问 题题2022-3-1210也可以直接利用对应关系写出线性规划问题的对偶问题Max z = 5x1 6x2 7x3St. x1 + 5x2 3x3 15 5x1 6x2 + 10 x3 20 x1x2x3 =5 x1 0, x2 0, x3无约束无约束Min = 15y1+ 20y25y3St. y15y2+ y35 5y16y2y3 6 3y1+ 10y2 y3 = 7 y1 0, y2 0, y3无约束无约束 掌握两者之间的对应系：对偶问题的变量对应原

7、问题的约束方程，对偶问题的约束方程对应原问题的变量（见表2-2）y1y2y3x1x2x32022-3-1211 2 对偶问题的基本性质一、单纯形法计算的矩阵表示0 , 0 .0 maxsssXXbIXAXstXCXz松弛变量mm单位矩阵 单纯形法计算时，总取I为初始基，对应的基变量为Xs。迭代若干步后基变量为XB, XB在初始单纯形表中的系数矩阵为B，将A中去掉B后的剩余部分记为N(具体情况见下表)2022-3-1212非基变量基变量0 Xs bXB XNB N XsIjcB cN0初始单纯形表迭代若干步基变量非基变量cB XB B1 b XBIXN XsB1 N B1 j0cNcBB1 N

8、- - cBB1最终单纯形表2022-3-1213 2 1 0 0 0 x1 x2 x3 x4 x5cjCB 基(变量) bx3x4x500015245 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1j 2 1 0 0 0cj 2 1 0 0 0CB 基(变量) b x1 x2 x3 x4 x50 x3 15/2 0 0 1 5/4 15/22 x1 7/2 1 0 0 1/4 1/21 x2 3/2 0 1 0 1/4 3/2 j 0 0 0 1/4 1/2B- -1B2022-3-1214五点结论五点结论 （2）初始单纯形表中的常数项是b，最终单纯形表中B1b （3）初始单纯形

9、表中系数矩阵为A , I=B, N, I，最终单纯形表中系数矩阵 B1A , B1=B1B, B1N, B1I=I, B1N, B1 （1）对应初始单纯形表中的单位矩阵I，最终单纯形表中为B1(非常重要的指标非常重要的指标)2022-3-1215 （4）初始单纯形表中变量Xj的系数向量为Pj，最终单纯形表中为 Pj = B1Pj (1) （5）当B为最优基时，在最终单纯形表中应有 cNcBB1N0 (2) cBB1 0 (3)因为XB的检验数可写为 cBcBI=cB- - cBB-1B=0 (4)故（4）（2）可以合并写成(5)，(3)直接写成(6) ccBB1 A0 (5) cBB10 (6

10、)2022-3-1216如果令YT=cBB1(单纯形乘子)，则(5)、(6)可写为0YcYATT(7)原问题的对偶问题 从(7)式可以看出，此时原问题的最优解对应的单纯形表中，检验数若取相反数恰好是其对偶问题的一个可行解！而且有zbCBbCBbYYbTTTT11)()(原问题的最优解当原问题为最优解时，这时其对偶问题有当原问题为最优解时，这时其对偶问题有可行解，且两者具有相同的目标函数值可行解，且两者具有相同的目标函数值2022-3-1217项目项目原问题变量原问题变量原问题松弛变量原问题松弛变量 x1 x2 x3 x4 x5x3 15/2x1 7/2x2 3/20 01 00 11 5/4

11、-15/20 1/4 -1/20 -1/4 3/2j j0 0 0 -1/4 -1/2对偶问题的松弛变量对偶问题的松弛变量对偶问题变量对偶问题变量y4 y5y1 y2 y3项目项目对偶问题变量对偶问题变量对偶问题松弛变量对偶问题松弛变量 y1 y2 y3 y4 y5y2 1/4y3 1/2 -5/4 1 0 15/2 0 1 -1/4 1/4 1/2 -3/2j j 15/2 0 0 7/2 3/2原问题松弛变量原问题松弛变量原问题变量原问题变量x3 x4 x5x1 x22022-3-1218定理1 (弱对偶定理） 若 x, y 分别为原问题与对偶问题的可行解则恒有 cTx bTy二、对偶问题

12、的基本性质 定理2 (最优性定理) 若x, y分别原问题与对偶问题的可行解,且cTx=bTy ，那么x, y分别为原问题与对偶问题的最优解。2022-3-1219 定理3 (对偶定理) 若原问题与对偶问题均有可行解，那么它们均有最优解,且最优解的函数值相等。 定理4 (互补松弛性定理)(比较重要比较重要) 若在线性规划问题的最优解中,若对应某一约束条件的对偶变量值为非零，则约束方程取严格等式；反之若约束方程取严格不等式，则其对应的对偶变量一定为零。2022-3-1220对偶单纯形法的基本思想 从对偶问题的可行解出发，去寻求原问题的最优解，此时根据对偶定理，原对偶问题均有最优解 4 对偶单纯形法

13、2022-3-1221 对偶单纯形法的基本思路 从原问题的一个基解基解出发，此基解不一定可行，但它对应着一个对偶可行解对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发； 然后检验原问题的基解是否可行，即是否有负的分量？如果有小于零的分量，则进行迭代，求另一个基解，此基解又对应着另一个对偶可行解（检验数非正）。如果得到的基解的分量皆非负，则该基解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原问题的基解由不可行逐步变为可行。 当同时得到对偶问题与原问题的可行解时，便得到原问题的最优解。2022-3-1222 对偶单纯形法在什么情况下使用 ： 应

14、用前提：有一个基，其对应的基满足: 单纯形表的检验数全部非正（对偶可行） 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯型表。2022-3-1223 1.建立初始对偶单纯形表,对应一个基解,所有检验数均非正,转2； 2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 3.若所有akj0( j = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj12故原问题的最优解不是现在的最优解假设12，则原问题的最优解是现在的最优解，问题结束2022-3-1245将新的约束条件添加

15、松弛变量3x1+2x2+x6 =12以x6为基变量，将上式反映到最终单纯形表中cj 2 1 0 0 0 0CB 基(变量) b x1 x2 x3 x4 x5 x60 x3 15/2 0 0 1 5/4 15/2 02 x1 7/2 1 0 0 1/4 1/2 01 x2 3/2 0 1 0 1/4 3/2 00 x6 12 3 2 0 0 0 1 j 0 0 0 1/4 1/2 0将p1, p2变换成单位向量，使获得一个单位矩阵为基2022-3-1246cj 2 1 0 0 0 0CB 基(变量) b x1 x2 x3 x4 x5 x60 x3 15/2 0 0 1 5/4 15/2 02 x1 7/2 1 0 0 1/4 1/2 01 x2 3/2 0 1 0 1/4 3/2 00 x6 12 3 2 0 0 0 1 j 0 0 0 1/4 1/2 0cj 2 1 0 0 0 0CB 基基(变量变量) b x1 x2 x3 x4 x5 x60 x3 15/2 0 0 1 5/4 15/2 02 x1 7/2 1 0 0 1/4 1/2 01 x2 3/2 0 1 0 1/4 3/2 00