《运筹学基本概念和理论基础.ppt》由会员分享，可在线阅读，更多相关《运筹学基本概念和理论基础.ppt（25页珍藏版）》请在三一办公上搜索。
1、第 二 章,基本概念和基本理论,第二章 基本概念和理论基础,2.1 数学规划模型的一般形式 min f(x)-目标函数 s.t.xS-约束集合，可行集其中，S R n，f:S R，xS称（f S)的可行解最优解:x*S，满足f(x*)f(x),xS。则称 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*)。则
2、称 x*为(f S)的局部最优解,记 l.opt.(local optimum)在上述定义中，当x x*时有严格不等式成立，则分别称 x*为(f S)的严格全局最优解和严格局部最优解。,严格l.opt.,严格g.opt.,l.opt.,2.1 数学规划模型的一般形式（续）,函数形式:f(x),gi(x),hj(x):RnR min f(x)(fgh)s.t.gi(x)0,i=1,2,m hj(x)=0,j=1,2,l矩阵形式:min f(x)，f(x):RnR(fgh)s.t.g(x)0,g(x):RnRm h(x)=0,h(x):RnRl 当 f(x),gi(x),hj(x)均为线性函数时，
3、称线性规划；若其中有非线性函数时，称非线性规划。,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、凸集的概念：例:证明集合 S=xAx=b 是凸集。其中，A为 mn矩阵，b为m维向量。凸组合：设 x(1),x(2),x(m)Rn,j 0 m m j=1,那么称 j x(j)为x(1
4、),x(2),x(m)的 j=1 j=1凸组合。m比较:z=j x(j)j=1jR 构成线性组合 线性子空间j0,j 0 构成半正组合 凸锥j0,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、凸集的性质：凸集的交集是凸集；（
5、并？）凸集的内点集是凸集；（逆命题是否成立？）凸集的闭包是凸集。（逆命题是否成立？）分离与支撑：凸集边界上任意点存在支撑超平面 两个互相不交的凸集之间存在分离超平面,支撑,强分离,分离,非正常分离,2.2 凸集、凸函数和凸规划(续),一、凸集 3、凸锥：定义：C Rn,若 x C,0 有 x C,则称 C 是以 0 为顶点的锥。如果 C 还是凸集，则称为凸锥。集合 0、Rn 是凸锥。命题：C是凸锥C中任意有限点的半正组合属于S,0,2.2 凸集、凸函数和凸规划(续),二、凸函数 1、凸函数及水平集定义:设集合 S Rn 为凸集，函数 f:SR 若 x(1),x(2)S,(0,1)，均有 f(x
6、(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 上任意有限点的凸组合的函数值不大于各点函数值的凸组合。思考：设f1,f2是凸函数，设1,2 0,1f1+2f2,1f1-2f2是否凸函数？f(x)=max f1(x),f2(x),g(x)=min f1(
7、x),f2(x)是否凸函数？,2.2 凸集、凸函数和凸规划(续),二、凸函数 1、凸函数及水平集：定义：设集合 S Rn，函数 f:SR，R，称 S=x Sf(x)为 f(x)在 S 上 的 水平集。定理：设集合 S Rn 是凸集，函数 f:SR是凸函数，则对 R，S 是凸集。注：水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。上述定理的逆不真。考虑分段函数f(x)=1(x0)或0(x0)，函数非凸，但任意水平集是凸集。,2.2 凸集、凸函数和凸规划(续),二、凸函数 2、凸函数的性质：方向导数：设 S Rn 为非空凸集，函数 f:SR，再设 x*S,d 为方向，使当 0 充分小时
8、有 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*)Td.,2.2 凸集、凸函数和凸规划(续),二、凸函数 2、凸函数的性质：以下设 S Rn 为非空凸集，函数 f:SR2）若f 凸，则 f 在 S 的内点集上连续；注：f 在 S 上不一定连续。例:f(x)2(当x=1)；f(x)x2(当x1).3）设f 凸，则对任意方向方向导数存在。4）设 S 是开集，f 在 S 上可微，则 f凸 x*S，有f(x)f(x*)+f T(
9、x*)(x-x*),x S.5)设 S 是开集，f 在 S 上二次可微，则 a)f 凸 xS，2f(x)半正定；b)若 xS，2f(x)正定，则f严格凸。,2.2 凸集、凸函数和凸规划(续),二、凸函数 2、凸函数的性质：例：f(x)x12+2x1x2+2x22+10 x1-4；f(x)-3x12+x1x2-x22-2x32-2x2x3+26;f(x)3x12+ax1x2+2x22-4x1+6(a=5,4.5)；,2.2 凸集、凸函数和凸规划(续),三、凸规划：当（f S）中，S为凸集，f是S上的凸函数（求min），称（f S）为凸规划；对于（fgh）,f,gi为凸函数，hj为线性函数时，（f
10、gh）为凸规划。定理：设集合 S Rn 为凸集，函数 f:SRf(x)为凸集 S 上的凸函数。x*为问题（fs）的l.opt，则x*为g.opt；又如果f是严格凸函数，那么x*是（fs）的唯一g.opt。,2.3 多面体、极点、极方向,1）多面体：有限个半闭空间的交 例：S=xRnAx=b,x0,2.3 多面体、极点、极方向,2)多面体的极点（顶点）：xS，不存在 S 中的另外两个点x(1)和x(2)，及(0,1)，使 x=x(1)+(1-)x(2).3)方向：xS,dRn,d 0 及 0,总有 x+d S.d(1)=d(2)(0)时，称 d(1)和d(2)同方向。4)极方向：方向 d 不能表
11、示为两个不同方向的组合(d=d(1)+d(2).,2.3 多面体、极点、极方向,多面体 S=xRnAx=b,x0 的极点和极方向定理1（极点特征）设 A 满秩，x 是 S 极点的充分必要条件是:存在分解 A=B,N，其中B为m阶非奇异矩阵，使 xT=xBT,xNT,这里 xB=B-1b0,xN=0.S中必存在有限多个极点。(Cnm),2.3 多面体、极点、极方向,多面体 S=xRnAx=b,x0 的极点和极方向定理2（极方向特征）设 A=p1,p2,pn满秩，d 是 S 极方向的充分必要条件是:存在分解 A=B,N，其中B为m阶非奇异矩阵，对于N中的列向量 pj 使 B-1pj0,dT=dBT
12、,dNT,这里 j dB=-B-1pj,dN=(0,.,1,0)TS中必存在有限多个极方向。(n-m)Cnm),考虑多面体 S=xRnAx=b,x0，其中 3 2 1 0 0 65 A=2 1 0 1 0 b=40 0 3 0 0 1 75 即 3 x1+2 x2+x3=65 2 x1+x2+x4=40 3 x2+x5=75 x1,x2,x3,x4,x5 0,例题,3 2 1 0 0A=P1,P2,P3,P4,P5=2 1 0 1 0 0 3 0 0 1 A矩阵包含以下10个33的子矩阵：B1=p1，p2，p3 B2=p1，p2，p4 B3=p1，p2，p5 B4=p1，p3，p4 B5=p1
13、，p3，p5 B6=p1，p4，p5 B7=p2，p3，p4 B8=p2，p3，p5 B9=p2，p4，p5 B10=p3，p4，p5,例题,其中B4=0，因而B4不能构成极点和极方向。其余均为非奇异方阵，因此该问题共有9个可构成极点、极方向的子矩阵，我们称之为基。对于基B3=p1，p2，p5，令x3=0，x4=0，在等式约束中令x3=0，x4=0，解线性方程组：3 x1+2 x2+0 x5=65 2 x1+x2+0 x5=40 0 x1+3 x2+x5=75 得到x1=15，x2=10，x5=45，对应的极点：x=(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T,例题,类似
14、可得到极点 x(2)=(5,25,0,5,0)T（对应B2）x(7)=(20,0,5,0,75)T（对应B5）x(8)=(0,25,15,15,0)T（对应B7）x(9)=(0,0,65,40,75)T（对应B10）而 x(3)=(0,32.5,0,7.5,-22.5)T（对应B9）x(4)=(65/3,0,0,-10/3,75)T（对应B6）x(5)=(7.5,25,-7.5,0,0)T（对应B1）x(6)=(0,40,-15,0,-45)T（对应B8）不是极点,例题,2.3 多面体、极点、极方向,多面体 S=xRnAx=b,x0 的极点和极方向定理3（表示定理）考虑上述多面体S，设A满秩，x(1),x(2),x(k)为所有极点，d(1),d(2),d(l)为所有极方向。那么，对于 xS，i0，且1+2+k=1,j0,j=1,2,l,使 x=1 x(1)+2 x(2)+k x(k)+1 d(1)+2 d(2)+l d(l).,
