《第二章线性规划问题的对偶与灵敏度分析教材课件.ppt》由会员分享，可在线阅读，更多相关《第二章线性规划问题的对偶与灵敏度分析教材课件.ppt（47页珍藏版）》请在三一办公上搜索。
1、2023/4/3,1,第二章 线性规划的对偶与灵敏度分析,1 线性规划的对偶问题 2 对偶问题的基本性质 4 对偶单纯形法 5 灵敏度分析,2023/4/3,2,线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的灵敏度分析,本章内容重点,2023/4/3,3,1 线性规划的对偶问题,提出问题,(LP1)max z=2x1+x2 st.5x215 6x1+2x2 24 x1+x2 5 x1,x20,一个公司要收购美佳公司的资源(设备)，问它至少要付出多大的代价？,设备A,设备B,调试工序,假设y1、y2、y3分别代表单位时间设备A、设备B、调试工序的出让价,y1,y2,y3,
2、2023/4/3,4,美佳出价：出让价应不低于用同等数量的资源由自己组织生产活动时所获得的利润,6y2+y325y1+2y2+y31y1,y2,y30,买家还价：买家在满足上述条件的前提下，希望用最小的代价获得美佳公司的全部资源,Min 15y1+24y2+5y3,2023/4/3,5,(LP2)Min 15y1+24y2+5y3st.6y2+y32 5y1+2y2+y31 y1,y2,y3 0,一个新的线性规划,称(LP1)为原问题，(LP2)为对偶问题,当LP中的变量均具有非负约束，其约束条件当目标函数求极大时均取“”号，而当目标函数求极小时均取“”时，则称这样的LP问题具有对称形式,20
3、23/4/3,6,一般规律,(1)原问题有n个变量，m个约束，对偶问题有m个变量，n个约束。原问题的目标函数求极大，对偶问题的目标函数求极小,(2)原问题的目标函数中变量的系数为对偶问题的约束条件的常数项，反之亦然,(3)原问题与对偶问题的约束方程的系数矩阵互为转置,2023/4/3,7,(LP1)Max z=CX s.t.AX b X 0,(LP2)Min=bT Ys.t.AT Y CT Y 0,非对称形式的对偶问题 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，一般事先转换成对称形式，然后按对应规则写出其对偶问题,2023/4/3,8,Max z=x1+4
4、x2+3x3St.2x1+3x2 5x3 2 3x1 x2+6x3 1 x1+x2+x3=4 x10,x20,x3无约束,y1,y3,y2,Max 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,x30,y3,每个约束方程对应一个对偶变量。原则：是“”的方程直接对应y；是“”的对应y；是“”的分别对应y,y,202
5、3/4/3,9,Min=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 0,Min=2y1+y2+4y3St.2y1+3y2+y31 3y1-y2+y3 4-5y1+6y2+y3=3y1 0,y20,y3无约束,令 y2=y2y3=y3y3,Max z=x1+4x2+3x3St.2x1+3x2 5x3 2 3x1 x2+6x3 1 x1+x2+x3=4 x10,x20,x3无约束,原 问 题,对 偶 问 题,2023/4/3,10,也可以直接利用对应关系写出线性
6、规划问题的对偶问题,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无约束,掌握两者之间的对应系：对偶问题的变量对应原问题的约束方程，对偶问题的约束方程对应原问题的变量（见表2-2）,y1,y2,y3,x1,x2,x3,2023/4/3,11,2 对偶问题的基本性质,一、单纯形法计算的矩阵表示,松弛变量,mm单位矩阵,单纯形法计算时，总取I为初始基，对应的基变量
7、为Xs。迭代若干步后基变量为XB,XB在初始单纯形表中的系数矩阵为B，将A中去掉B后的剩余部分记为N(具体情况见下表),2023/4/3,12,初始单纯形表,迭代若干步,最终单纯形表,2023/4/3,13,2 1 0 0 0,x1 x2 x3 x4 x5,cj,CB 基(变量)b,x3x4x5,000,15245,0 5 1 0 0,6 2 0 1 0,1 1 0 0 1,j,2 1 0 0 0,B-1,B,2023/4/3,14,五点结论,（2）初始单纯形表中的常数项是b，最终单纯形表中B1b,（3）初始单纯形表中系数矩阵为A,I=B,N,I，最终单纯形表中系数矩阵 B1A,B1=B1B,
8、B1N,B1I=I,B1N,B1,（1）对应初始单纯形表中的单位矩阵I，最终单纯形表中为B1(非常重要的指标),2023/4/3,15,（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),2023/4/3,16,如果令YT=cBB1(单纯形乘子)，则(5)、(6)可写为,(7),原问题的对偶问题,从(7)式可以看出，此
9、时原问题的最优解对应的单纯形表中，检验数若取相反数恰好是其对偶问题的一个可行解！而且有,原问题的最优解,当原问题为最优解时，这时其对偶问题有可行解，且两者具有相同的目标函数值,2023/4/3,17,2023/4/3,18,定理1(弱对偶定理）若 x,y 分别为原问题与对偶问题的可行解则恒有 cTx bTy,二、对偶问题的基本性质,定理2(最优性定理)若x,y分别原问题与对偶问题的可行解,且cTx=bTy，那么x,y分别为原问题与对偶问题的最优解。,2023/4/3,19,定理3(对偶定理)若原问题与对偶问题均有可行解，那么它们均有最优解,且最优解的函数值相等。,定理4(互补松弛性定理)(比较
10、重要)若在线性规划问题的最优解中,若对应某一约束条件的对偶变量值为非零，则约束方程取严格等式；反之若约束方程取严格不等式，则其对应的对偶变量一定为零。,2023/4/3,20,对偶单纯形法的基本思想,从对偶问题的可行解出发，去寻求原问题的最优解，此时根据对偶定理，原对偶问题均有最优解,4 对偶单纯形法,2023/4/3,21,对偶单纯形法的基本思路 从原问题的一个基解出发，此基解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原问题的基解是否可行，即是否有负的分量？如果有小于零的分量，则进行迭代，求另一个基解，此基解又对应着另一个对偶可行解（检验
11、数非正）。如果得到的基解的分量皆非负，则该基解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原问题的基解由不可行逐步变为可行。当同时得到对偶问题与原问题的可行解时，便得到原问题的最优解。,2023/4/3,22,对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:单纯形表的检验数全部非正（对偶可行）变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯型表。,2023/4/3,23,1.建立初始对偶单纯形表,对应一个基解,所有检验数均非正,转2；2.若b0,则得到最优解,停止;否则,若有bk0则选k
12、行的基变量为出基变量,转3 3.若所有akj0(j=1,2,n)，则原问题无可行解,停止;否则,若有akj0 则选=minj/akjakj0，j=1,2,n=r/akr那么 xr为进基变量,转4；4.以akr为主元素,作矩阵初等行变换使其变为1,该列其他元变为0,转2。,对偶单纯形法求解线性规划问题计算过程,2023/4/3,24,例3.2：用对偶单纯形法求解线性规划问题：,Min f=15y1+24y2+5y3 S.t.6y2+y3 2 5y1+2y2+y3 1 y1,y2,y3 0,Max z=15y124y2 5y3 S.t.6y2+y3 y4=2 5y1+2y2+y3 y5=1 y1,
13、y2,y3,y4,y5 0,Max z=15y124y2 5y3 S.t.6y2 y3 y4=2 5y12y2y3y5=1 y1,y2,y3,y4,y5 0,2023/4/3,25,对偶问题的最优解 X=(7/2,3/2,15/2,0,0)T原问题的最优解 Y=(0,1/4,1/2,0,0)T,x1,x2,x3,x4,x5,2023/4/3,26,对偶单纯形法的适用范围 对偶单纯形法适合于解如下形式的线性规划问题,2023/4/3,27,2023/4/3,28,进一步理解最优单纯性表中各元素的含义考虑问题 Max z=c1 x1+c2 x2+cn xn s.t.a11x1+a12x2+a1nx
14、n b1 a21x1+a22x2+a2nxn b2.am1x1+am2x2+amnxn bm x1，x2，xn 0,5 灵敏度分析,cj,bi,aij,m,n,参数,2023/4/3,29,当这些参数中的一个或几个发生变化时，线性规划问题的最优解会发生什么变化，或者这些参数在一个多大范围内变化时，问题的最优解不变？,所要解决的问题,重要公式,1、将参数的改变通过下面的公式计算后直接反映到最终单纯形表上,2、检查原问题是否仍有可行解,2023/4/3,30,4、按下表所列情况得出结论或决定继续计算的步骤,3、检查对偶问题是否仍有可行解,2023/4/3,31,一、价值系数cj发生变化,线性规划问
15、题中变量系数cj 的变化仅仅影响到检验数的变化，所以将cj 的变化直接反映到最终单纯形表中，此时只会出现如上表中的前两种情况,1.5,2,1/8,-4/9,1.5,2,2023/4/3,32,因为变量x4对应的检验数大于零，属于第二种情况，所以用单纯形法继续迭代,最优解 XT=(2,3)T,2023/4/3,33,二、常数项b发生变化,常数项的变化反映到最终单纯形表中将引起b列数字的变化，所以可能出现第一或第三两种情况。若是第一种情况，问题的最优基不变，变化后的b列值为最优解；出现第三种情况时，用对偶单纯形法继续找出最优解,2023/4/3,34,15245,15325,转下页,2023/4/
16、3,35,用对偶单纯形法,2023/4/3,36,三、增加一个变量xj的分析,增加一个变量xj在实际问题中反映为增加一个新的产品。其分析步骤为,例如，美佳公司计划推出新产品III，生产每件产品所需设备A、B及调试工序的时间分别为3、4、2小时，该产品的盈利为3元件。试分析新的生产计划,2023/4/3,37,设该公司生产新产品x6，则有c6=3 P6=(3,4,2)T,2023/4/3,38,用单纯形法继续迭代,2023/4/3,39,四、分析参数aij的变化,1、变量xj在最终单纯行表中为非基变量，参照上一段算法2、变量xj在最终单纯行表中为基变量，则相应的B和B-1会发生变化,例如，在美佳
17、公司，若产品II每件所需设备A、B及调试工序的时间分别为8、4、1小时，该产品的盈利为3元件。试分析新的生产计划,先将生产工时变化后的新产品II看成是一种新产品，生产量记为x2，计算步骤与上一段一样,2023/4/3,40,因为x2已经变换为x2，故用x2替换出x2，并在下一个表中不保留x2,2023/4/3,41,添加人工变量,原、对偶问题均为非可行解,2023/4/3,42,结论：最优生产计划为生产家电I 11/4件,家电II15/8件,2023/4/3,43,增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入1个新的非负变量（原约束若是小
18、于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。,五、增加一个约束条件的分析,2023/4/3,44,例如，美佳公司生产的产品还须一道实验工序，家电I:3小时，家电II：2小时，又实验工序的生产能力为12小时。问如何安排最优生产计划？,增加的约束条件为 3x1+2x212,将原最优解代入，得 37/2+23/2=27/2 12,故原问题的最优解不是现在的最优解,假设12，则原问题的最优解是现在的最优解，问题结束,2023/4/3,45,将新的约束条件添加松弛变量3x1+2x2+x6=12,以x6为基变量，将上式反映到最终单纯形表中,将p1,p2变换成单位向量，使获得一个单位矩阵为基,2023/4/3,46,(-3),(-2),对偶单纯型法,2023/4/3,47,结论：最优生产计划为只生产家电I 4件,
