运筹学线性规划的对偶理论课件

,军事运筹学,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,*,军事运筹学,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,*,第二章 线性规划,对偶问题的提出,原问题与对偶问题的关系,对偶问题的基本性质,对偶单纯形法,灵敏度分析,1,2,运筹学基础,解：,设生产,x,1,的产品,I,，,x,2,的产品,II,，则,目标函数,max,z,2,x,1,+3,x,2,约束条件,x,1,+ 2,x,2,8,4,x,1,16,4,x,2,12,x,1,x,2,0,线性规划的对偶理论,例,1,某厂可生产产品,和,，生产,I,需,1,台设备，,4,单位原料,A,，生产,II,需,2,台设备，,4,单位原料,B,。该厂每生产一件产品,获利,2,元,每生产一件产品,获利,3,元。现有,8,台设备，,16,单位原料,A,，,12,单位原料,B,，问如何安排计划使获利最多,?,第二章 线性规划,对偶问题的提出,原问题与对偶问题的关系,对偶问题的基本性质,对偶单纯形法,灵敏度分析,3,4,4.1,对偶问题的提出,运筹学基础,我们从另一个角度来讨论这个问题：假设不生产产品,，而将所有资源出租或外售。,问题：考虑每种资源如何定价。,5,4.1,对偶问题的提出,运筹学基础,例,1,产品,：,1,台设备，,4,单位原料,A,，获利,2,元；,产品,：,2,台设备，,4,单位原料,B,，获利,3,元。,现有：,8,台设备，,16,单位原料,A,，,12,单位原料,B,设,y,1,，,y,2,，,y,3,分别表示出售单位设备台时的租金和出让原材料,A,，,B,的附加额。根据题意可得：,y,1,+4,y,2,2,，,2,y,1,+4,y,3,3,，,=8,y,1,+16,y,2,+12,y,3,要实现出租的愿望，只能在满足所有产品的利润条件下，必须使,尽可能的小。,6,4.1,对偶问题的提出,运筹学基础,为此需解决如下的线性规划问题：,y,1,+4,y,2,2,2,y,1,+4,y,3,3,min,=8,y,1,+16,y,2,+12,y,2,y,1,，,y,2,，,y,3,0,max,z,2,x,1,+3,x,2,x,1,2,x,2,8,4,x,1,16,4,x,2,12,x,1,x,2,0,与,关系？,对原模型设：,1 2,4 0,0 4,A,=,C,=(2,，,3),b,=(8,16,12),T,X,=,（,x,1,，,x,2,）,T,Y,=,（,y,1,，,y,2,，,y,3,）,则可得,:,7,4.1,对偶问题的提出,运筹学基础,max,z,=,CX,AX,b,（,5.1,）,X,0,y,1,+4,y,2,2,2,y,1,+4,y,3,3,min,=8,y,1,+16,y,2,+12,y,3,y,1,，,y,2,，,y,3,0,max,z,2,x,1,+3,x,2,x,1,2,x,2,8,4,x,1,16,4,x,2,12,x,1,x,2,0,与,有何关系？,对愿模型设：,1 2,4 0,0 4,A,=,C,=(2,，,3),b,=(8,16,12),T,X,=,（,x,1,，,x,2,）,T,Y,=,（,y,1,，,y,2,，,y,3,）,则可得,:,min,=,Yb,YA,C,（,5.2,）,Y,0,和,我们把（,5.2,）式的问题称为（,5.1,）式问题的,对偶线性规划问题,。,第二章 线性规划,对偶问题的提出,原问题与对偶问题的关系,对偶问题的基本性质,对偶单纯形法,灵敏度分析,8,9,4.2,原问题与对偶问题的关系,运筹学基础,1,对称式的对偶,“”,不等式约束条件的原问题与“”不等式约束条件的对偶问题，称为,对称式,的一对对偶问题。,原问题：,max,z,=,c,1,x,1,+,c,2,x,2,+,c,n,x,n,a,11,a,12,a,1n,a,m1,a,m2,a,mn,x,1,x,n,b,1,b,m,x,1,，,x,2,，,，,x,n,0,对偶问题：,min,=,b,1,y,1,+,b,2,y,2,+,b,m,y,m,a,11,a,12,a,1,n,a,m,1,a,m,2,a,mn,y,1,，,y,2,，,，,y,m, 0,(,y,1,y,2,y,m,),(,c,1,c,2,c,n,),n,个变量，,m,个约束条件,m,个变量，,n,个约束条件,10,运筹学基础,2,约束条件全部为“,=”,的对偶,max,z,=,CX,AX,b,X,0,原问题：,max,z,=,CX,AX,b,X,0,AX,b,等价,max,z,=,CX,AX,b,X,0,AX,b,max,z,=,CX,X,0,A,A,X,b,b,min,=(,Y,1,Y,2,),Y,1,Y,2,0,A,A,C,b,b,(,Y,1,Y,2,),其中,Y,1,=(,y,1,y,2, ,y,m,),，,Y,2,=(,y,m,+1,y,m,+2, ,y,2,m,),等价,等价,min,=,Yb,Y,为无约束,YA,C,min,=(,Y,1,Y,2,),b,Y,1,Y,2,0,(,Y,1,Y,2,),A,C,令,Y,=(,Y,1,Y,2,),对偶问题,对偶问题,11,4.2,原问题与对偶问题的关系,运筹学基础,3,约束条件为“”的对偶,max,z,=,CX,AX,b,X,0,原问题：,max,z,=,CX,AX,b,X,0,min,=,Y,1,(,b,),Y,1,(,A,) ,C,Y,1,0,min,=,Yb,YA,C,Y,0,等价,对偶问题,令,Y,=,Y,1,对偶问题,12,运筹学基础,4,变量,0,的对偶,max,z,=,CX,AX,b,X,0,原问题：,令,X,=,X,1,max,z,=,C,(,X,1,),A,(,X,1,),b,X,1,0,max,z,=(,C,),X,1,(,A,),X,1,b,X,1,0,min,=,Y b,Y,(,A,) ,C,Y,0,min,=,Y b,Y,A,C,Y,0,对偶问题,对偶问题,等价,13,运筹学基础,5,变量无约束的对偶,max,z,=,CX,AX,b,X,无约束,原问题：,令,X,=,X,1,X,2,X,1,，,X,2,0,max,z,=,CX,1,CX,2,X,1,X,2,0,AX,1,AX,2,b,max,z,=(,C,C,),X,1,X,2,0,b,X,1,X,2,(,A,A,),X,1,X,2,等价,min,=,Yb,Y,0,Y,(,A,A,) (,C,C,),对偶,min,=,Yb,YA,C,Y,0,YA,C,min,=,Yb,YA,C,Y,0,min,=,Yb,YA,C,Y,0,YA,C,等价,等价,等价,对偶问题,14,运筹学基础,6,原问题与对偶问题的关系表,原问题（或对偶问题）,对偶问题（或原问题）,目标函数,max,z,n,个变量,变量,0,变量,0,变量无约束,目标函数,min,n,个约束条件,约束,约束,约束,=,m,个约束条件,约束,约束,约束,=,约束条件右端项,目标函数变量系数,m,个变量,变量,0,变量,0,变量无约束,目标函数变量系数,约束条件右端项,15,运筹学基础,例：求下列线性规划问题的对偶问题,max,z,5,x,1,+4,x,2,+6,x,3,x,1,+ 2,x,2,2,x,1,+,x,3,3,3,x,1,+2,x,2,+,x,3,5,x,1,0,x,2,0,x,3,无约束,x,1,x,2,+,x,3,=1,C,=(5,4, 6),b,=(2,3,-5,1),T,1 2 0,1 0 1,-3 2 1,A,=,1 -1 1,解：,因原问题有,3,个变量，,4,个约束条件，所以对偶问题,4,个变量，,3,个约束条件。设变量,Y,=(,y,1,y,2,y,3,y,4,),min,=2,y,1,+3,y,2,5,y,3,+,y,4,于是,y,1,+,y,2,3,y,3,+,y,4,5,2,y,1,+2,y,3,y,4,4,y,2,+,y,3,+,y,4,6,y,1,0,y,2,y,3,0,y,4,无约束,Y A,C,确定约束条件,第二章 线性规划,对偶问题的提出,原问题与对偶问题的关系,对偶问题的基本性质,对偶单纯形法,灵敏度分析,16,17,4.3,对偶问题的基本性质,运筹学基础,1,对称性：,对偶问题的对偶问题是原问题。,证：,设原问题为：,max,z,=,CX,；,AX,b,；,X,0,则,对偶问题为：,min,=,Yb,；,YA,C,；,Y,0,因,min,=max (,),max (,) =,Yb,；,YA,C,；,Y,0,min (,1,)= ,CX,；,AX, ,b,；,X,0,对偶问题,又因,min (,1,),=max (,1,),max (,1,) =,CX,；,AX,b,；,X,0,这就是原问题。,18,4.3,对偶问题的基本性质,运筹学基础,2,弱对偶性：,若,X,(0),是原问题的可行解，,Y,(0),是对偶问题的可行解，则存在,CX,(0),Y,(0),b,。,证：,设原问题为：,max,z,=,CX,；,AX,b,；,X,0,则,因,X,(0),是原问题的可行解，所以,AX,(0),b,又因,Y,(0),是对偶问题的可行解，所以,Y,(0),A,C,Y,(0),A X,(0),Y,(0),b,因此，,CX,(0),Y,(0),A X,(0),Y,(0),b,结论成立。,对偶问题为：,min,=,Yb,；,YA,C,；,Y,0,Y,(0),A X,(0),CX,(0),19,4.3,对偶问题的基本性质,运筹学基础,3,无界性：,若原问题无界解， 则其对偶问题无可行解 。,证：由弱对偶性可知结论成立。,(,CX,(0),Y,(0),b,),4,最优性：,若,X,(0),是原问题的可行解，,Y,(0),是对偶问题的可行解，且,CX,(0),=,Y,(0),b,，则,X,(0),，,Y,(0),是最优解。,证：,设,Y,(1),是对偶问题的任意可行解，由性质,2,可得,Y,(1),b,CX,(0),=,Y,(0),b,，则,Y,(0),是对偶问题的最优解。,设,X,(1),是原问题的任意可行解，由性质,2,可得,CX,(0),=,Y,(0),b,CX,(1),，则,X,(0),是原问题的最优解。,20,4.3,对偶问题的基本性质,运筹学基础,5,对偶定理：,若原问题有最优解， 那么对偶问题也有优解；且目标函数值相等。,证：,设,X,(0),是原问题的最优解，它对应的基,B,，必有,C,C,B,B,-1,A,0,，且,z,=,CX,(0),=,C,B,B,-1,b,。,令,Y,(0),=,C,B,B,-1,显然，,Y,(0),A,C,。,所以,Y,(0),是对偶问题的可行解。,又因,Y,(0),b,=,C,B,B,-1,b,=,CX,(0),由性质,4,可知,Y,(0),是对偶问题的最优解。,因此，结论成立。,21,运筹学基础,6,互补松弛性：,若,X,(0),是原问题的可行解，,Y,(0),是对偶问题的可行解，则,Y,X,(0),=0,和,Y,(0),X,=0,当且仅当,X,(0),，,Y,(0),是最优解。,证：,max,z,=,CX,AX,+,x,=,b,X,0,，,X,0,设原问题和对偶问题的标准型是,min,=,Yb,YA,Y,=,C,Y,0,，,Y,0,将原问题目标函数中的系数向量,C,用,C,=,YA,Y,代替：,z,=(,YA,Y,),X,=,YA X,Y,X,(5.3),对偶问题目标函数中的系数向量，用,b,=,AX,+,X,代替：,=,Y,(,AX,+,X,)=,YA X,+,YX,(5.4),Y,X,(0),=0,和,Y,(0),X,=0,则,Y,(0),b,=,Y,(0),A X,(0),=,CX,(0),X,(0),Y,(0),最优解,则,Y,(0),b,=,Y,(0),AX,(0),=,CX,(0),(,性质,3),所以,Y,X,(0),=0,和,Y,(0),X,=0,。,X,(0),，,Y,(0),是最优解,22,运筹学基础,7,设原问题：,max,z,=,CX,；,AX,+,X,=,b,；,X,X,0,对偶问题：,min,=,Yb,；,YA,Y,=,C,；,Y,Y,0,。则原问题单纯形表的检验数行对应其对偶问题的一个基解。其关系如表：,0,Y,1,C,N,1,C,B,B,-1,N,1,Y,2,C,B,B,-1,Y,这里,Y,1,对应原问题的基变量,X,B,的剩余变量，,Y,2,对应原问题的非基变量,X,N,的剩余变量。,证：,max,z,=,C,B,X,B,+,C,N,X,N,BX,B,+,BX,N,+,X,=,b,X,N,X,B,X,0,设,B,是一可行基，于是,A,=(,B,N,),min,=,Yb,YB,Y,1,=,C,B,(5.5),Y,Y,1,Y,2,0,YN,Y,2,=,C,N,(5.6),23,4.3,对偶问题的基本性质,运筹学基础,证：,max,z,=,C,B,X,B,+,C,N,X,N,BX,B,+,BX,N,+,X,=,b,X,X,B,X,0,设,B,是一可行基，于是,A,=(,B,N,),min,=,Yb,YB,Y,1,=,C,B,(5.5),Y,Y,1,Y,2,0,YN,Y,2,=,C,N,(5.6),其中,Y,=(,Y,1,Y,2,),当原问题的解为：,X,B,=,B,-1,b,时，其检验参数为,C,N,C,B,B,-1,N,与,C,B,B,-1,。,令,Y,=,C,B,B,-1,，将它代入,(5.5),和,(5.6),得,Y,1,=0,，,Y,2,=,C,N,C,B,B,-1,N,因此，结论成立。,24,4.3,对偶问题的基本性质,运筹学基础,8,单纯形乘子,Y,的定理：,若,B,是原问题的一最优可行基，则单纯形乘子,Y,=,C,B,B,-1,是对偶问题的一个最优解。,证：设,X,(0),是对应基,B,的原问题的最优解，则,显然，,Y A,C,。,所以,Y,是对偶问题的可行解。,又因,Yb,=,C,B,B,-1,b,=,CX,(0),由性质,4,可知,Y,是对偶问题的最优解。,因此，结论成立。,C,C,B,B,-1,A,0,，且,z,=,C X,(0),C,B,B,-1,b,。,根据本性质，可以从原问题最优解的单纯形表中直接得到对偶问题的最优解。,25,运筹学基础,9,最优对偶变量,(,影子价格,),的经济解释,从对偶定理可知,，当达到最优解时，原问题和对偶问题的目标函数值相等，即,z,=,CX,(0),=,Y,(0),b,=,C,B,B,-1,b,.,也即,z,=,CX,(0),=,Y,(0),b,=,C,B,B,-1,b,=,y,1,(0),b,1,+,y,2,(0),b,2,+ +,y,m,(0),b,m,其中,X,(0),Y,(0),分别是原问题和对偶问题的最优解。,现在考虑在最优解处,，常数项,b,i,的微小变动对目标函数值的影响,(,不改变原来的最优基,).,求,z,对,b,i,的偏导数，可得：,y,1,(0),z,b,1,y,2,(0),z,b,2,y,m,(0),z,b,m, ,这说明,，若原问题的某一约束条件的右端常数项,b,i,增加一个单位，则由此引起的最优目标函值的增加量，就等于该约束条件相对应的对偶变量的最优值。,最优变量,y,i,(0,的值,，就相当于对单位第,I,种资源在实现最大利润时的一种估价。这种估价是针对具体企业具体产品而存在的一种特殊价格，称它为“,影子价格,”。,“,影子价格,” 对市场有调节作用。,26,运筹学基础,例 已知线性规划问题,x,1,+,x,2,+2,x,3,+,x,4,+3,x,5,4,2,x,1,x,2,+3,x,3,+,x,4,+,x,5,3,min =2,x,1,+3,x,2,+5,x,3,+2,x,4,+3,x,5,x,1,x,2,x,3,x,4,x,5,0,其对偶问题的最优解为,y,1,*,=4/5, y,2,*,=3/5,；,z=5,。试用对偶理论找出原问题的最优解。,解：,对偶问题,max,z,4,y,1,+3,y,2,y,1,+ 2,y,2,2 ,y,1,y,2,3 ,2,y,1,+3,y,2,5 ,y,1,y,2,0,y,1,+,y,2,2 ,3,y,1,+,y,2,3 ,C,=(2,3, 5,2,3),b,=(4, 3),T,1 1 2 1 3,A,=,2 -1 3 1 1,Y A,C,确定约束条件,Y,=(,y,1,y,2,),原,对,min,变,0,0,无,max,约,约,变,0,0,无,关系表,形成,27,运筹学基础,原,对,min,变,0,0,无,max,约,约,变,0,0,无,解：,对偶问题,max,z,4,y,1,+3,y,2,y,1,+ 2,y,2,2 ,y,1,y,2,3 ,2,y,1,+3,y,2,5 ,y,1,y,2,0,y,1,+,y,2,2 ,3,y,1,+,y,2,3 ,C,=(2,3, 5,2,3),b,=(4, 3),T,1 1 2 1 3,A,=,2 -1 3 1 1,Y A,C,确定约束条件,Y,=(,y,1,y,2,),关系表,形成,设,X,=(,x,1,x,2,),T,，,Y,=(,y,1,y,2,y,3,y,4,y,5,),把,y,1,*,=4/5,y,2,*,=3/5,代入约束条件中可得,Y,=(0,14/5,8/5,2/5,0),据互补松弛性：,Y,X,*,=0,Y,X,*,=14/5,x,2,*,+8/5,x,3,*,+2/5,x,4,*,=0,所以,x,2,*,=,x,3,*,=,x,4,*,=0,又因,Y,*,X,=4/5,x,1,+3/5,x,2,=0,所以,x,1,=,x,2,=0,28,4.3,对偶问题的基本性质,运筹学基础,设,X,=(,x,1,x,2,),T,，,Y,=(,y,1,y,2,y,3,y,4,y,5,),把,y,1,*,=4/5,y,2,*,=3/5,代入约束条件中 可得,Y,=(0,14/5,8/5,2/5,0),据互补松弛性：,Y,X,*,=0,Y,X,*,=14/5,x,2,*,+8/5,x,3,*,+2/5,x,4,*,=0,所以,x,2,*,=,x,3,*,=,x,4,*,=0,又因,Y,*,X,=4/5,x,1,+3/5,x,2,=0,所以,x,1,=,x,2,=0,因为,所以,x,1,*,+,x,2,*,+2,x,3,*,+,x,4,*,+3,x,5,*,+,x,1,=4,2,x,1,*,x,2,*,+3,x,3,*,+,x,4,*,+,x,5,*,+,x,2,=3,x,1,*,+3,x,5,*,=4,2,x,1,*,+,x,5,*,=3,x,1,*,= 1,，,x,5,*,= 1,因此，原问题最优解为,X,*,=(1,，,0,，,0,，,0,，,1),T,，,*,=5,。,第二章 线性规划,对偶问题的提出,原问题与对偶问题的关系,对偶问题的基本性质,对偶单纯形法,灵敏度分析,29,30,4.4,对偶单纯形法,运筹学基础,1,对偶单纯形法与单纯形法的区别,1.1,对偶单纯形法的思路,原理：,由性质,7,可知：在单纯形表中进行迭代时，在,b,列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质,4,，,5,可知，已得到最优解。即原问题与对偶问题都是最优解。,思路：,在进行迭代时，保持对偶问题的解是基可行解，即,c,j,C,B,B,-1,p,j,0,，而原问题通过逐步迭代，达到基可行解，这样就得到最优解。,31,4.4,对偶单纯形法,运筹学基础,1.2,对偶单纯形法与单纯形法的区别,单纯形法：,在迭代中，保持,b,列中得到的是原问题的基可行解，逐步得到对偶问题的基可行解。,对偶单纯形法：,在逐步迭代中 ，保持检验数行,c,j,C,B,B,-1,p,j,0,，即保持对偶问题的解是基可行解。通过迭代得到原问题的基可行解。,说明：,对偶单纯法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯法。,2,对偶单纯形法求解步骤,2.1,对偶可行的基解：,设,X,(0),是原问题的基解，其对应的基为,B,，记,Y=C,B,B,-1,，若,Y,是对偶问题的基可行解。即,C,C,B,B,-1,A 0,，则称,X,(0),是原问题的对偶可行的基解。,32,运筹学基础,2.2,对偶单纯形法的计算步骤,列出初始单纯形表,最优性检验,根据线性规划问题，确定一个对偶可行的基解，列出初始单纯形表。,检查,b,列的数，若都为非负，则已得到最优解。停止计算。若,b,列的数中，还有分量为负数，则进行下一步计算。,确定换出变量,按,min (B,-1,b),i,| (B,-1,b),i,0,，则无可行解，停止计算。,如果 有,a,lj,0 (,j=1,2, n) ,则计算,c,k,z,k,min,c,j,z,j,a,lj,| a,lj, 0,时，, b,r, b,i,/ a,ir,当,a,ir,0 b,r, min b,i,/ a,ir,| a,ir, 0,时，, c,r, ,j,/ a,rj,当,a,rj,0 c,r, min,j,/ a,rj,| a,rj,0,，则原最优基不再是最优基，此时在原问题的最终表的基础上，换上改变后的第,j,列数据,B,-1,P,j,和,j,，把,x,j,作为换入变量，用单纯形法继续迭代。,基向量,P,j,变为,P,j,。此时原最优解的可行性和最优性都遭到破坏，一般不修改原来的最终表，而是重新计算。,