运筹学课件第2章.ppt

《运筹学课件第2章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章基本概念和理论基础第2章基本概念和理论基础1.1数学规划模型的一般形式Minf(x)——目标函数s.t.xS——约束集合，可行集其中，SRn，f:SR，xS称（fS)的可行解最优解:x*S，满足f(x*)≤f(x),xS，则称x*为(fS)的全局最优解(最优解),记为g.opt.(globaloptimum),简记为opt.。最优值:x*为(fS)的最优解,则称f*=f(x*)为(fS)的最优值(最优目标函数值)。(fS)2.1数学规划模型的一般形式局部最优解:x*S，x*的

2、邻域N(x*)，使满足f(x*)≤f(x),xSN(x*),则称x*为(fS)的局部最优解,记为l.opt.(localoptimum)。在上述定义中，当xx*时有严格不等式成立，则分别称x*为(fS)的严格全局最优解和严格局部最优解。严格l.opt.严格g.opt.l.opt.2.1数学规划模型的一般形式函数形式:f(x),gi(x),hj(x):RnRMinf(x)(fgh)s.t.gi(x)≤0,i=1,2,…,mhj(x)=0,j=1,2,…,l矩阵形式:Minf(x)，f(x):

3、RnR(fgh)s.t.g(x)≤0,g(x):RnRmh(x)=0,h(x):RnRl当f(x),gi(x),hj(x)均为线性函数时，称其为线性规划；若其中有非线性函数时，称其为非线性规划。2.2凸集、凸函数和凸规划1.凸集（1）凸集的概念定义1设集合SRn，若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)

4、的线段。凸集非凸集非凸集2.2凸集、凸函数和凸规划例1证明集合S={x∣Ax=b}是凸集。其中，A为mn矩阵，b为m维向量。凸组合：设x(1),x(2),…,x(m)Rn,j≥0，mmj=1,那么称jx(j)为x(1),x(2),…,x(m)的j=1j=1凸组合。m比较:z=jx(j)j=1jR——构成线性组合——线性子空间j≥0,j>0——构成半正组合——凸锥j≥0,j=1——构成凸组合——凸集2.2凸集、凸函数和凸规划定理1S是凸集S中任意有限点的凸组合属于S

5、。多胞形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

6、.2凸集、凸函数和凸规划（3）凸锥定义2CRn,若xC,>0，有xC,则称C是以0为顶点的锥。如果C还是凸集，则称为凸锥。集合{0}、Rn是凸锥。命题：C是凸锥C中任意有限点的半正组合属于S。02.2凸集、凸函数和凸规划2.凸函数（1）凸函数及水平集定义3设集合SRn为凸集，函数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上的凸函数。若进一步有上面不等式以严格不等式成立，

7、则称f(x)为凸集S上的严格凸函数。(几何意义见P27)当－f(x)为凸函数（严格凸函数）时，则称f(x)为凹函数（严格凹函数）。严格凸函数凸函数严格凹函数2.2凸集、凸函数和凸规划定理2f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。思考：设f1,f2是凸函数。设1,2>0,1f1+2f2,1f1－2f2是否凸函数？(都是)2）f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函数？（不一定）2.2凸集、凸函

8、数和凸规划定义4设集合SRn，函数f:SR，R，称S={xS∣f(x)≤}为f(x)在S上的水平集。定理3设集合SRn是凸集，函数f:SR是凸函数，则对R，S是凸集。注：水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。上述定理的逆不真。考虑分段函数f(x)=1(x≥0)或0(x<0)，函数非凸，但任意水平集是凸集。2.2凸集、凸函数和凸规划（2）凸函数的性质方向导数：设SRn为非空凸集，函数f:SR，再设x*S,d为方向，