运筹学基本概念和理论基础

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第 二 章,基本概念,和,基本理论,第二章 基本概念和理论基础,2.1 数学规划模型的一般形式,min,f(x),-目标函数,s.t.,x,S,-约束集合，可行集,其中，,S,R,n,，,f,:,S,R,，,x,S,称（,f S,)的可行解,最优解:,x*,S，,满足,f(x*),f(x),x,S。,则称,x*,为(,f S,)的全局最优解(最优解),记,g.opt.,(,global optimum,),简记,opt.,最优值:,x*,为(,f S,)的最优解,则称,f*=f(x*),为,(,f S,)的最优值(最优目标函数值),(f S),2.1 数学规划模型的一般形式（续）,局部最优解:,x*,S，,x*,的邻域,N,(,x*,)，使满足,f(x*),f(x),x,S,N,(,x*,),。,则称,x*,为(,f S,)的局部最优解,记,l.opt.,(,local optimum,),在上述定义中，当,x,x*,时有严格不等式成立，,则分别称,x*,为(,f S,)的严格全局最优解和严格局部最优解。,严格,l.opt.,严格,g.opt.,l.opt.,2.1 数学规划模型的一般形式（续）,函数形式:,f(x),g,i,(x),h,j,(x),:,R,n,R,min,f(x),(,fgh,)s.t.,g,i,(x),0 ,i=1,2,m,h,j,(x),=0 ,j=1,2,l,矩阵形式:,min,f(x)，,f(x),:,R,n,R,(,fgh,)s.t.,g(x),0 ,g(x),:,R,n,R,m,h(x),=0 ,h(x),:,R,n,R,l,当,f(x),g,i,(x),h,j,(x),均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。,2.2 凸集、凸函数和凸规划,一、凸集,1、凸集的概念：,定义：设集合,S,R,n,，,若,x,(1),x,(2),S,0,1，必有,x,(1),(1-,),x,(2),S,，则称,S,为凸集。,规定：单点集,x,为凸集，空集,为凸集。,注:,x,(1),(1-,),x,(2),=,x,(2),(,x,(1),-,x,(2),),是连接,x,(1),与,x,(2),的线段,。,凸集,非凸集,非凸集,2.2 凸集、凸函数和凸规划(续),一、凸集 1、凸集的概念：,例:证明集合,S,=,x,Ax=b,是凸集。其中，,A,为,m,n,矩阵，,b,为,m,维向量。,凸组合：,设,x,(,1,),x,(,2,),x,(,m,),R,n,j,0,m,m,j,=,1,那么称,j,x,(,j,),为,x,(,1,),x,(,2,),x,(,m,),的,j,=1 j=1,凸组合。,m,比较:,z=,j,x,(,j,),j=1,j,R,构成线性组合 线性子空间,j,0,j,0,构成半正组合 凸锥,j,0,j,=0,构成凸组合 凸集,2.2 凸集、凸函数和凸规划(续),一、凸集 1、凸集的概念：,定理：,S,是凸集,S,中任意有限点的凸组合属于,S,多胞形,H,(,x,(,1,),x,(,2,),x,(,m,),)：,由,x,(,1,),x,(,2,),x,(,m,),的所有凸组合构成。,单纯形：若,多胞形,H,(,x,(,1,),x,(,2,),x,(,m,),)满足，,x,(,2,),-x,(,1,),x,(3),-,x,(,1,),x,(,m,),-,x,(,1,),线性无关。,多胞形,单纯形,单纯形,2.2 凸集、凸函数和凸规划(续),一、凸集,2、凸集的性质：,凸集的交集是凸集；,（并？）,凸集的内点集是凸集；,（逆命题是否成立？）,凸集的闭包是凸集。,（逆命题是否成立？）,分离与支撑：,凸集边界上任意点存在支撑超平面,两个互相不交的凸集之间存在分离超平面,支撑,强分离,分离,非正常分离,2.2 凸集、凸函数和凸规划(续),一、凸集,3、凸锥：,定义：,C,R,n,若,x,C,0,有,x,C,则称,C,是以 0 为顶点的锥。如果,C,还是凸集，则称为凸锥。,集合 0、,R,n,是凸锥。,命题：,C,是凸锥,C,中任意有限点的半正组合属于,S,0,2.2 凸集、凸函数和凸规划(续),二、凸函数,1、凸函数及水平集,定义:设集合,S,R,n,为凸集，函数,f,:,S,R,若,x,(1),x,(2),S,(0,1)，均有,f(,x,(1),(1-,),x,(2),),f(,x,(1),)+(1-,),f(x,(2),),，,则称,f(x),为凸集,S,上的凸函数。,若进一步有上面不等式以严格不等式成立，则称,f(x),为凸集,S,上的严格凸函数。,当-,f(x),为凸函数（严格凸函数）时，则称,f(x),为凹函数（严格凹函数）。,严格凸函数,凸函数,严格凹函数,2.2 凸集、凸函数和凸规划(续),二、凸函数 1、凸函数及水平集：,定理：,f(x),为凸集,S,上的凸函数,S,上任意有限点的凸组合的函数值不大于各点函数值的凸组合。,思考：设,f,1,f,2,是凸函数，,设,1,2,0,1,f,1,+,2,f,2,1,f,1,-,2,f,2,是否凸函数？,f(x)=max,f,1,(,x,),f,2,(,x,),g(x)=min,f,1,(,x,),f,2,(,x,),是否凸函数？,2.2 凸集、凸函数和凸规划(续),二、凸函数 1、凸函数及水平集：,定义：,设集合,S,R,n,，函数,f,:,S,R，,R,，,称,S,=,x,S,f(x),为,f(x),在,S,上,的,水平集,。,定理：,设集合,S,R,n,是凸集，函数,f,:,S,R,是凸函数，则对 ,R,，,S,是凸集,。,注：,水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。,上述定理的逆不真。,考虑分段函数,f(x)=,1,(x,0),或0(,x,0,充分小时有,x*,+,d,S,如果,lim,f(x*+,d)-f(x*),/,存在（包括,）,则称,f(x),为在点沿方向的方向导数存在，记,f(x*;d)=,lim,f(x*+,d)-f(x*),/,若,f(x),在,x*,可导，则,f(x*;d)=,f(x*),T,d .,2.2 凸集、凸函数和凸规划(续),二、凸函数 2、凸函数的性质：,以下设,S,R,n,为非空凸集，函数,f,:,S,R,2）若,f,凸，则,f,在,S,的内点集上连续；,注：,f,在,S,上不一定连续。,例:,f(x),2(当,x,=1)；,f(x),x,2,(当,x,0,总有,x,+,d,S,.,d,(1),=,d,(2),(,0)时，称,d,(1),和,d,(2),同方向。,4)极方向：方向,d,不能表示为两个不同方向的组合(,d,=,d,(1),+,d,(2),).,2.3 多面体、极点、极方向,多面体,S,=,x,R,n,Ax,=,b,x,0 的极点和极方向,定理1（极点特征）设,A,满秩，,x,是,S,极点的充分必要条件是:,存在分解,A,=,B,N,，其中,B,为,m,阶非奇异矩阵，使,x,T,=,x,B,T,x,N,T,这里,x,B,=,B,-1,b,0,x,N,=0.,S,中必存在有限多个极点。(,C,n,m,),2.3 多面体、极点、极方向,多面体,S,=,x,R,n,Ax,=,b,x,0 的极点和极方向,定理2（极方向特征）,设,A,=,p,1,p,2,p,n,满秩，,d,是,S,极方向的充分必要条件是:,存在分解,A,=,B,N,，其中,B,为,m,阶非奇异矩阵，对于,N,中的列向量,p,j,使,B,-1,p,j,0,d,T,=,d,B,T,d,N,T,这里,j,d,B,=-,B,-1,p,j,d,N,=(0,.,1,0),T,S,中必存在有限多个极方向。(,n,-,m,),C,n,m,),考虑多面体,S,=,x,R,n,Ax,=,b,x,0,，其中,3 2 1 0 0 65,A,=2 1 0 1 0,b,=40,0 3 0 0 1 75,即,3 x,1,+2 x,2,+x,3,=65,2 x,1,+x,2,+x,4,=40,3 x,2,+x,5,=75,x,1,x,2,x,3,x,4,x,5,0,例题,3 2 1 0 0,A,=,P,1,P,2,P,3,P,4,P,5,=,2 1 0 1 0,0 3 0 0 1,A,矩阵包含以下10个33的子矩阵：,B,1,=,p,1,，p,2,，p,3,B,2,=,p,1,，p,2,，p,4,B,3,=,p,1,，p,2,，p,5,B,4,=,p,1,，p,3,，p,4,B,5,=,p,1,，p,3,，p,5,B,6,=,p,1,，p,4,，p,5,B,7,=,p,2,，p,3,，p,4,B,8,=,p,2,，p,3,，p,5,B,9,=,p,2,，p,4,，p,5,B,10,=,p,3,，p,4,，p,5,例题,其中,B,4,=0，因而,B,4,不能构成极点和极方向。其余均为非奇异方阵，因此该问题共有9个可构成极点、极方向的子矩阵，我们称之为基。,对于基,B,3,=,p,1,，p,2,，p,5,，令,x,3,=0，x,4,=0，在等式约束中令,x,3,=0，,x,4,=0，解线性方程组：,3,x,1,+2,x,2,+0,x,5,=65,2,x,1,+,x,2,+0,x,5,=40,0,x,1,+3,x,2,+,x,5,=75,得到,x,1,=15，,x,2,=10，,x,5,=45，对应的极点：,x,=(,x,1,，x,2,，x,3,，x,4,，x,5,),T,=(15，10，0，0，45),T,例题,类似可得到极点,x,(2),=(5,25,0,5,0),T,（对应B,2,）,x,(7),=(20,0,5,0,75),T,（对应B,5,）,x,(8),=(0,25,15,15,0),T,（对应B,7,）,x,(9),=(0,0,65,40,75),T,（对应B,10,）,而,x,(3),=(0,32.5,0,7.5,-22.5),T,（对应B,9,）,x,(4),=(65/3,0,0,-10/3,75),T,（对应B,6,）,x,(5),=(7.5,25,-7.5,0,0),T,（对应B,1,）,x,(6),=(0,40,-15,0,-45),T,（对应B,8,）,不是极点,例题,2.3 多面体、极点、极方向,多面体,S,=,x,R,n,Ax,=,b,x,0 的极点和极方向,定理3（表示定理）考虑上述多面体,S,，,设,A,满秩，,x,(1),x,(2),x,(k),为所有极点，,d,(1),d,(2),d,(l),为所有极方向。那么，对于,x,S,，,i,0,，且,1,+,2,+,k,=,1,j,0,j=1,2,l,使,x=,1,x,(1),+,2,x,(2),+,k,x,(k),+,1,d,(1),+,2,d,(2),+,+,l,d,(l),.,