第2章 运筹学基本概念和理论基础

《第2章 运筹学基本概念和理论基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章基本概念和基本理论第二章基本概念和理论基础2.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*的邻域N(x*)

2、，使满足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):RnR(fgh)s.t.g(x)≤0,g(x)

3、:RnRmh(x)=0,h(x):RnRl当f(x),gi(x),hj(x)均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。2.2凸集、凸函数和凸规划一、凸集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)的线段。凸集非凸集非凸集2.2凸集、凸函数和凸规划(续)一、凸集1、凸集的概念：例:证明集合

4、S={x∣Ax=b}是凸集。其中，A为mn矩阵，b为m维向量。凸组合：设x(1),x(2),…,x(m)Rn,j≥0mm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=0—构成凸组合——凸集2.2凸集、凸函数和凸规划(续)一、凸集1、凸集的概念：定理：S是凸集S中任意有限点的凸组合属于S多胞形H(x(1),x(2),…,x(m))：由x(1),x(2),…,x(

5、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Rn,若xC,>0有xC,则称C是以0

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

7、严格凹函数2.2凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集：定理：f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。思考：设f1,f2是凸函数，设1,2>0,1f1+2f2,1f1-2f2是否凸函数？f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函数？2.2凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集：定义：设集合SRn，函数f:SR，R，称S={xS∣f(x)≤}为f(x)在S上的水平集。定理：设集合S

8、Rn是凸集，函数f:SR是凸函数，则对R，S是凸集。注：水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。上述定理的逆不真。考虑分段函数f(x)=1(x≥0)或0(x<0)，函数非凸，但任意水平集是凸