線性規(guī)劃問題基本概念和基本理論

關(guān)于線性規(guī)劃問題基本概念和基本理論第一頁，共二十五頁，編輯于2023年，星期三第二章基本概念和理論基礎(chǔ)2.1數(shù)學(xué)規(guī)劃模型的一般形式

minf(x)

--------目標(biāo)函數(shù)

s.t.xS

--------約束集合，可行集其中，SRn，f:SR，xS稱（fS)的可行解最優(yōu)解:x*S，滿足f(x*)≤f(x),xS。則稱

x*為(fS)的全局最優(yōu)解(最優(yōu)解),

記g.opt.(globaloptimum),簡記opt.最優(yōu)值:x*為(fS)的最優(yōu)解,則稱f*=f(x*)

為

(fS)的最優(yōu)值(最優(yōu)目標(biāo)函數(shù)值)(fS)第二頁，共二十五頁，編輯于2023年，星期三2.1數(shù)學(xué)規(guī)劃模型的一般形式（續(xù)）局部最優(yōu)解:x*S，x*的鄰域N(x*)，使?jié)M足

f(x*)≤f(x),xSN(x*)

。則稱x*為(fS)的局部最優(yōu)解,記l.opt.(localoptimum)在上述定義中，當(dāng)xx*時(shí)有嚴(yán)格不等式成立，則分別稱x*

為(fS)的嚴(yán)格全局最優(yōu)解和嚴(yán)格局部最優(yōu)解。嚴(yán)格l.opt.嚴(yán)格g.opt.l.opt.第三頁，共二十五頁，編輯于2023年，星期三2.1數(shù)學(xué)規(guī)劃模型的一般形式（續(xù)）函數(shù)形式:

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)

:RnR(fgh)s.t.g(x)

≤0,g(x):RnRm

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

當(dāng)f(x),gi(x),hj(x)均為線性函數(shù)時(shí)，稱線性規(guī)劃；若其中有非線性函數(shù)時(shí)，稱非線性規(guī)劃。第四頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃一、凸集1、凸集的概念：定義：設(shè)集合SRn，若x(1),x(2)S,[0,1]，必有

x(1)＋(1-)x(2)S，則稱S為凸集。規(guī)定：單點(diǎn)集{x}為凸集，空集為凸集。注:x(1)＋(1-)x(2)=x(2)＋(x(1)-x(2))

是連接x(1)與x(2)的線段。凸集非凸集非凸集第五頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集1、凸集的概念：例:證明集合S={x∣Ax=b}是凸集。其中，A為mn矩陣，b為m維向量。凸組合：設(shè)

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=1jR

—構(gòu)成線性組合——線性子空間j≥0,

j>0—構(gòu)成半正組合——凸錐j≥0,

j=0—構(gòu)成凸組合——凸集第六頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集1、凸集的概念：定理：S是凸集S中任意有限點(diǎn)的凸組合屬于S多胞形H(x(1),x(2),…,x(m))：由x(1),x(2),…,x(m)的所有凸組合構(gòu)成。單純形：若多胞形H(x(1),x(2),…,x(m))滿足，

x(2)-x(1),x(3)-x(1),…,x(m)-

x(1)

線性無關(guān)。多胞形單純形單純形第七頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集

2、凸集的性質(zhì)：凸集的交集是凸集；（并？）凸集的內(nèi)點(diǎn)集是凸集；（逆命題是否成立？）凸集的閉包是凸集。（逆命題是否成立？）分離與支撐：凸集邊界上任意點(diǎn)存在支撐超平面兩個(gè)互相不交的凸集之間存在分離超平面支撐強(qiáng)分離分離非正常分離第八頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集3、凸錐：定義：C

Rn,若xC,>0

有xC,則稱C是以0為頂點(diǎn)的錐。如果C還是凸集，則稱為凸錐。集合{0}、Rn是凸錐。命題：C是凸錐C中任意有限點(diǎn)的半正組合屬于S0第九頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)

1、凸函數(shù)及水平集定義:設(shè)集合SRn為凸集，函數(shù)f:SR

若x(1),x(2)S,(0,1)，均有

f(x(1)＋(1-)x(2))≤f(x(1))+(1-)f(x(2))，則稱f(x)為凸集S上的凸函數(shù)。若進(jìn)一步有上面不等式以嚴(yán)格不等式成立，則稱f(x)為凸集S上的嚴(yán)格凸函數(shù)。當(dāng)-f(x)為凸函數(shù)（嚴(yán)格凸函數(shù)）時(shí)，則稱f(x)為凹函數(shù)（嚴(yán)格凹函數(shù)）。嚴(yán)格凸函數(shù)凸函數(shù)嚴(yán)格凹函數(shù)第十頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)1、凸函數(shù)及水平集：定理：f(x)為凸集S上的凸函數(shù)S上任意有限點(diǎn)的凸組合的函數(shù)值不大于各點(diǎn)函數(shù)值的凸組合。思考：設(shè)f1,f2是凸函數(shù)，設(shè)1,2>0,1f1+2f2,1f1-2f2是否凸函數(shù)？f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函數(shù)？

第十一頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)1、凸函數(shù)及水平集：定義：設(shè)集合SRn，函數(shù)f:SR，R

，稱S={xS∣f(x)≤

}為f(x)在S上的水平集。定理：設(shè)集合SRn是凸集，函數(shù)f:SR是凸函數(shù)，則對R

，S

是凸集。注：水平集的概念相當(dāng)于在地形圖中，海拔高度不高于某一數(shù)值的區(qū)域。上述定理的逆不真。考慮分段函數(shù)f(x)=1(x≥0)或0(x<0)，函數(shù)非凸，但任意水平集是凸集。第十二頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質(zhì)：方向?qū)?shù)：設(shè)S

Rn為非空凸集，函數(shù)f:SR，再設(shè)x*

S,d為方向，使當(dāng)

>0

充分小時(shí)有x*+d

S,

如果

lim

[f(x*+d)-f(x*)]/

存在（包括）

則稱f(x)為在點(diǎn)沿方向的方向?qū)?shù)存在，記

f`(x*;d)=lim

[f(x*+d)-f(x*)]/

若f(x)在x*可導(dǎo)，則f`(x*;d)=[f(x*)]Td.第十三頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質(zhì)：以下設(shè)S

Rn為非空凸集，函數(shù)f:SR2）若f凸，則f在S的內(nèi)點(diǎn)集上連續(xù)；注：f在S上不一定連續(xù)。

例:f(x)＝2(當(dāng)x=1)；f(x)＝x2(當(dāng)x<1).

3）設(shè)f凸，則對任意方向方向?qū)?shù)存在。4）設(shè)S是開集，f在S上可微，則

f凸x*S，有f(x)≥f(x*)+fT(x*)(x-x*),xS.5)設(shè)S是開集，f在S上二次可微，則

a)

f凸xS，2f(x)半正定；

b)若xS，2f(x)正定，則f嚴(yán)格凸。第十四頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質(zhì)：例：

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)；第十五頁，共二十五頁，編輯于2023年，星期三2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))三、凸規(guī)劃：當(dāng)（fS）中，S為凸集，f是S上的凸函數(shù)（求min），稱（fS）為凸規(guī)劃；對于（fgh）,f,gi為凸函數(shù)，hj為線性函數(shù)時(shí)，（fgh）為凸規(guī)劃。定理：設(shè)集合S

Rn為凸集，函數(shù)f:SRf(x)為凸集S上的凸函數(shù)。x*為問題（fs）的l.opt，則x*為g.opt；又如果f是嚴(yán)格凸函數(shù)，那么x*是（fs）的唯一g.opt。第十六頁，共二十五頁，編輯于2023年，星期三2.3多面體、極點(diǎn)、極方向1）多面體：有限個(gè)半閉空間的交例：S={xRnAx=b,x≥0}第十七頁，共二十五頁，編輯于2023年，星期三2.3多面體、極點(diǎn)、極方向2)多面體的極點(diǎn)（頂點(diǎn)）：

xS，不存在S

中的另外兩個(gè)點(diǎn)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)時(shí)，稱d(1)和d(2)同方向。4)極方向：方向d

不能表示為兩個(gè)不同方向的組合(d=d(1)+d(2)).第十八頁，共二十五頁，編輯于2023年，星期三2.3多面體、極點(diǎn)、極方向多面體S={xRnAx=b,x≥0}的極點(diǎn)和極方向定理1（極點(diǎn)特征）設(shè)A

滿秩，x

是S極點(diǎn)的充分必要條件是:

存在分解A=[B,N]，其中B為m階非奇異矩陣，使xT=[xBT,xNT],

這里xB=B-1b≥0,xN=0.S中必存在有限多個(gè)極點(diǎn)。(≤Cnm)第十九頁，共二十五頁，編輯于2023年，星期三2.3多面體、極點(diǎn)、極方向多面體

S={xRnAx=b,x≥0}的極點(diǎn)和極方向定理2（極方向特征）設(shè)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中必存在有限多個(gè)極方向。(≤(n-m)Cnm)第二十頁，共二十五頁，編輯于2023年，星期三考慮多面體

S={xRnAx=b,x≥0}，其中

3210065

A=21010b=400300175

即

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

例題第二十一頁，共二十五頁，編輯于2023年，星期三32100A=[P1,P2,P3,P4,P5]=2101003001

A矩陣包含以下10個(gè)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]

例題第二十二頁，共二十五頁，編輯于2023年，星期三

其中B4=0，因而B4不能構(gòu)成極點(diǎn)和極方向。其余均為非奇異方陣，因此該問題共有9個(gè)可構(gòu)成極點(diǎn)、極方向的子矩陣，我們稱之為基。對于基B3=[p1，p2，p5]，令x3

=0，x4