第2章-对偶理论和灵敏度分析-第4节.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 对偶理论和灵敏度分析,第,4,节 线性规划的对偶理论,从理论上讨论线性规划的对偶问题,1,4.1,原问题与对偶理论,原问题（,LP,）：,2,2025/4/20 周日,对偶问题,(DP),3,2025/4/20 周日,标准型原问题与对偶问题的关系,4,2025/4/20 周日,例,2,根据表,2-3,写出原问题与对偶问题的表达式。,表,2-3,x y,x,1,x,2,b,y,1,1,2,8,y,2,4,0,16,y,3,0,4,12,c,2,3,5,2025/4/20 周日,标准形式的变换,关系为对称形式,原问题（,LP,）对偶问题,(DP),6,2025/4/20 周日,非对称形式,的变换,关系,原问题的约束条件中含有等式约束条件时，按以下步骤处理。,设等式约束条件的线性规划问题,7,2025/4/20 周日,第一步：先将等式约束条件分解为两个不等式约束条件。,8,2025/4/20 周日,第二步：按对称形式变换关系可写出它的对偶问题,设,y,i,是对应,(2-13),式的对偶变量,y,i,是对应,(2-14),式的对偶变量。,这里,i=1,2,，,m,9,2025/4/20 周日,10,2025/4/20 周日,将上述规划问题的各式整理后得到,11,2025/4/20 周日,综合上述，线性规划的原问题与对偶问题的关系，其变换形式归纳为表,2-4,中所示对应关系。,12,2025/4/20 周日,13,2025/4/20 周日,例,3,试求下述线性规划原问题的对偶问题,14,2025/4/20 周日,则由表,2-4,中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题，,15,2025/4/20 周日,4.2,对偶问题的基本性质,(1),对称性 对偶问题的对偶是原问题；,(2),弱对偶性 若,X,是原问题的可行解，,Y,是对偶问题的可行解。则存在,CXYb,；,(3),无界性,若原问题,(,对偶问题,),为无界解，则其对偶问题,(,原问题,),无可行解；,(4),可行解是最优解时的性质；,(5),对偶定理 若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等；,(6),互补松弛性；,(7),原问题检验数与对偶问题解的关系。,16,2025/4/20 周日,(1),对称性,对偶问题的对偶是原问题,证明：,设原问题是,max z=CX;AXb;X0,根据对偶问题的对称变换关系，可以找到它的对偶问题是,min=Yb;YAC;Y0,若将上式两边取负号，又因,min=max(-),可得到,max(-)=-Yb;-YA-C;Y0,根据对称变换关系，得到上式的对偶问题是,min(-)=-CX;-AX-b;X0,又因,min(-)=max,可得,max=max z=CX;AXb;X0,这就是原问题。证毕。,17,2025/4/20 周日,(2),弱对偶性,18,2025/4/20 周日,证明,：,19,2025/4/20 周日,(3),无界性,若原问题,(,对偶问题,),为无界解，则其对偶问题,(,原问题,),无可行解,证：由性质（,2,）可知，,例：,20,2025/4/20 周日,从两图对比可明显看到原问题无界，其对偶问题无可行解,y1,y2,21,2025/4/20 周日,(4),可行解是最优解时的性质,设 是原问题的可行解，是对偶问题的,可行解，,当 时，是最优解。,22,2025/4/20 周日,证明：,23,2025/4/20 周日,(5),对偶定理 若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。,24,2025/4/20 周日,(6),互补松弛性,25,2025/4/20 周日,将原问题目标函数中的系数向量,C,用,C=YA-Y,S,代替后，得到,z=(YA-Y,S,)X=YAX-Y,S,X (2-15),将对偶问题的目标函数中系数列向量,b,，用,b=AX+X,S,代替后，,得到,=Y(AX+X,S,)=YAX+YX,S,(2-16),26,2025/4/20 周日,27,2025/4/20 周日,(7),原问题检验数与对偶问题解的关系,设原问题是,max z=CX;AX+X,S,=b;X,X,S,0,它的对偶问题是,min=Yb;YA-Y,S,=C;Y,Y,S,0,则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系见表,2-5,。,28,2025/4/20 周日,表,2-5,对应关系,Y,S1,是对应原问题中基变量,X,B,的剩余变量，,Y,S2,是对应原问题中非基变量,X,N,的剩余变量。,29,2025/4/20 周日,证,:,设,B,是原问题的一个可行基，于是,A=(B,N),；原问题可以改写为,max z=C,B,X,B,+C,N,X,N,BX,B,+NX,N,+X,S,=b,X,B,X,N,X,S,0,相应地对偶问题可表示为,min=Yb,YB-Y,S1,=C,B,(2-17),YN-Y,S2,=C,N,(2-18),Y,Y,S1,Y,S2,0,这里,Y,S,=(Y,S1,Y,S2,),。,30,2025/4/20 周日,当求得原问题的一个解：,X,B,=B,-1,b,其相应的检验数为,C,N,-C,B,B,-1,N,与,-C,B,B,-1,现分析这些检验数与对偶问题的解之间的关系：,令,Y=C,B,B,-1,，代入,(2-17),式，,(2-18),式得,Y,S1,=0,-Y,S2,=C,N,-C,B,B,-1,N,证毕。,31,2025/4/20 周日,例,4,已知线性规划问题,max z=x,1,+x,2,-x,1,+x,2,+x,3,2,-2x,1,+x,2,-x,3,1,x,1,x,2,x,3,0,试用对偶理论证明上述线性规划问题无最优解。,32,2025/4/20 周日,上述问题的对偶问题为,min=2y,1,+y,2,-y,1,-2y,2,1,y,1,+y,2,1,y,1,-y,2,0,y,1,，,y,2,0,由第,1,约束条件，可知对偶问题无可行解,因原问题有可行解，故无最优解,。,33,2025/4/20 周日,例,5,已知线性规划问题,min=2x,1,+3x,2,+5x,3,+2x,4,+3x,5,x,1,+x,2,+2x,3,+x,4,+3x,5,4,2x,1,-x,2,+3x,3,+x,4,+x,5,3,x,j,0,，,j=1,2,5,已知其对偶问题的最优解为,y,1,*,=4/5,，,y,2,*,=3/5,；,z=5,。试用对偶理论找出原问题的最优解,。,34,2025/4/20 周日,解：先写出它的对偶问题,max z=4y,1,+3y,2,y,1,+2y,2,2 ,y,1,-y,2,3 ,2y,1,+3y,2,5 ,y,1,+y,2,2 ,3y,1,+y,2,3 ,y,1,，,y,2,0,35,2025/4/20 周日,将,y,1,*,=,4/5,y,2,*,=3/5,的值代入约束条件，,得,=1/53,=17/55,=7/52,它们为严格不等式；,由互补松弛性得,x,2,*,=x,3,*,=x,4,*,=0,。,因,y,1,y,2,0,；原问题的两个约束条件应取等式，故有,x,1,*,+3x,5,*,=4,2x,1,*,+x,5,*,=3,求解后得到,x,1,*,=1,x,5,*,=1,；故原问题的最优解为,X,*,=(1,，,0,，,0,，,0,，,1),T,；,*,=5,36,2025/4/20 周日,课堂练习（继第,1,章）,用单纯形法求解下列线性规划问题。,Max Z=x,1,+x,2,+3x,3,x,1,+x,2,+2x,3,40,x,1,+2x,2,+x,3,20,x,2,+x,3,15,x,1,、,x,2,、,x,3,0,写出对偶问题并求出对偶问题的最优解。,37,2025/4/20 周日,C,j,1,1,3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,5,0,-2,0,1,-1,-1,1,x,1,5,1,1,0,0,1,-1,3,x,3,15,0,1,1,0,0,1,C,j,-Z,j,0,-3,0,0,-1,-2,最后一张单纯形表,X=(5,0,15),T,，,Z=50,38,2025/4/20 周日,习题,P74 2.3(1),(2),P75 2.7,39,2025/4/20 周日,