线性规划问题基本概念和基本理论

关于线性规划问题基本概念和基本理论第二章基本概念和理论基础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页,共25页，2024年2月25日，星期天2.1数学规划模型的一般形式（续）局部最优解:x*

S，

x*的邻域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.第3页,共25页，2024年2月25日，星期天2.1数学规划模型的一般形式（续）函数形式:

f(x),gi(x),hj(x):RnRminf(x)(fgh)s.t.gi(x)

≤0,i=1,2,…,m

hj(x)=0,j=1,2,…,l矩阵形式:minf(x)，f(x)

:Rn

R(fgh)s.t.g(x)

≤0,g(x):Rn

Rm

h(x)=0,h(x):Rn

Rl

当f(x),gi(x),hj(x)均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。第4页,共25页，2024年2月25日，星期天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)的线段。凸集非凸集非凸集第5页,共25页，2024年2月25日，星期天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=0—构成凸组合——凸集第6页,共25页，2024年2月25日，星期天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)

线性无关。多胞形单纯形单纯形第7页,共25页，2024年2月25日，星期天2.2凸集、凸函数和凸规划(续)一、凸集

2、凸集的性质：凸集的交集是凸集；（并？）凸集的内点集是凸集；（逆命题是否成立？）凸集的闭包是凸集。（逆命题是否成立？）分离与支撑：凸集边界上任意点存在支撑超平面两个互相不交的凸集之间存在分离超平面支撑强分离分离非正常分离第8页,共25页，2024年2月25日，星期天2.2凸集、凸函数和凸规划(续)一、凸集3、凸锥：定义：C

Rn,若x

C,

>0

有

x

C,则称C是以0为顶点的锥。如果C还是凸集，则称为凸锥。集合{0}、Rn是凸锥。命题：C是凸锥

C中任意有限点的半正组合属于S0第9页,共25页，2024年2月25日，星期天2.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)为凹函数（严格凹函数）。严格凸函数凸函数严格凹函数第10页,共25页，2024年2月25日，星期天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)}是否凸函数？

第11页,共25页，2024年2月25日，星期天2.2凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集：定义：设集合S

Rn，函数f:S

R，

R

，称S

={x

S∣f(x)≤

}为f(x)在S上的

水平集。定理：设集合S

Rn是凸集，函数f:S

R是凸函数，则对

R

，S

是凸集。注：水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。上述定理的逆不真。考虑分段函数f(x)=1(x≥0)或0(x<0)，函数非凸，但任意水平集是凸集。第12页,共25页，2024年2月25日，星期天2.2凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：方向导数：设S

Rn为非空凸集，函数f:S

R，再设x*

S,d为方向，使当

>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*)]Td.第13页,共25页，2024年2月25日，星期天2.2凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：以下设S

Rn为非空凸集，函数f:S

R2）若f凸，则f在S的内点集上连续；注：f在S上不一定连续。

例:f(x)＝2(当

x

=1)；f(x)＝x2(当

x<1).

3）设f凸，则对任意方向方向导数存在。4）设S是开集，f在S上可微，则

f凸

x*

S，有f(x)≥f(x*)+

fT(x*)(x-x*),

x

S.5)设S是开集，f在S上二次可微，则

a)

f凸

x

S，2f(x)半正定；

b)若

x

S，2f(x)正定，则f严格凸。第14页,共25页，2024年2月25日，星期天2.2凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：例：

f(x)＝x12+2x1x2+2x22+10x1-4；

f(x)＝-3x12+x1x2-x22-2x32-2x2x3+26;

f(x)＝3x12+ax1x2+2x22-4x1+6(a=5,4.5)；第15页,共25页，2024年2月25日，星期天2.2凸集、凸函数和凸规划(续)三、凸规划：当（fS）中，S为凸集，f是S上的凸函数（求min），称（fS）为凸规划；对于（fgh）,f,gi为凸函数，hj为线性函数时，（fgh）为凸规划。定理：设集合S

Rn为凸集，函数f:S

Rf(x)为凸集S上的凸函数。x*为问题（fs）的l.opt，则x*为g.opt；又如果f是严格凸函数，那么x*是（fs）的唯一g.opt。第16页,共25页，2024年2月25日，星期天2.3多面体、极点、极方向1）多面体：有限个半闭空间的交例：S={x

Rn

Ax=b,x≥0}第17页,共25页，2024年2月25日，星期天2.3多面体、极点、极方向2)多面体的极点（顶点）：

x

S，不存在S

中的另外两个点x(1)和x(2)，及λ(0,1)，使x=λx(1)+(1-λ)x(2).3)方向：x

S,d

Rn,d

0及λ>0,总有x+λd

S.

d(1)=λd(2)(λ>0)时，称d(1)和d(2)同方向。4)极方向：方向d

不能表示为两个不同方向的组合(d=d(1)+d(2)).第18页,共25页，2024年2月25日，星期天2.3多面体、极点、极方向多面体S={x

Rn

Ax=b,x≥0}的极点和极方向定理1（极点特征）设A

满秩，x

是S极点的充分必要条件是:

存在分解A=[B,N]，其中B为m阶非奇异矩阵，使xT=[xBT,xNT],

这里xB=B-1b≥0,xN=0.S中必存在有限多个极点。(≤Cnm)第19页,共25页，2024年2月25日，星期天2.3多面体、极点、极方向多面体

S={x

Rn

Ax=b,x≥0}的极点和极方向定理2（极方向特征）设A=[p1,p2,…,pn]满秩，d

是S

极方向的充分必要条件是:存在分解A=[B,N]，其中B为m阶非奇异矩阵，对于N中的列向量pj

使B-1pj≤0,

dT=[dBT,dNT],这里j

dB=-B-1pj

,dN=(0,...,1,…,0)TS中必存在有限多个极方向。(≤(n-m)Cnm)第20页,共25页，2024年2月25日，星期天考虑多面体

S={x

Rn

Ax=b,x≥0}，其中

3210065

A=21010b=400300175

即

3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x5≥0

例题第21页,共25页，2024年2月25日，星期天32100A=[P1,P2,P3,P4,P5]=2101003001

A矩阵包含以下10个3×3的子矩阵：

B1=[p1，p2，p3]B2=[p1，p2，p4]

B3=[p1，p2，p5]B4=[p1，p3，p4]

B5=[p1，p3，p5]B6=[p1，p4，p5]

B7=[p2，p3，p4]B8=[p2，p3，p5]

B9=[p2，p4，p5]B10=[p3，p4，p5]

例题第22页,共25页，2024年2月25日，星期天

其中

B4

=0，因而B4不能构成极点和极方向。其余均为非奇异方阵，因此该问题共有9个可构成极点、极方向的子矩阵，我们称之为基。对于基B3=[p1，p2，p5]，令x3

=0，x4=0，在等式约束中令x3=0