最優(yōu)化方法第二堂課

最優(yōu)化方法主講

王更生教授2.1回顧：一、最優(yōu)控制問題50年代前：古典化——工程試探法解析法使系統(tǒng)誤差平方和（ISE）最小提法A：

Min=

s.t

==c第二章線性規(guī)劃提法B：Min=Mins.t

=c

頻域基石：狀態(tài)空間可控、可觀（概念？）2.極小值原理動態(tài)規(guī)劃特點：適用于多變量、非線形、時變系統(tǒng)初始條件可變可滿足多個目標(biāo)函數(shù)要求，并可有多余約束可計算求解（數(shù)值法）可控性舉例：可控性舉例：二、一維搜索（一）．搜索算法概述1．問題：一般要求=0，判定②③無法寫出解析式因此，迭代算法——搜索算法①=0難求

難判別2．基本思想：通過逐次逼近，求最優(yōu)解或近似最優(yōu)解=+

步長

方向3．原則①下降性：f(x0)≥f(x1)≥┅f(xk)≥┅②收斂性：{xk}最終收斂到定義域內(nèi)某極限點（最優(yōu)解）（滿足精度）4．步驟①選定初始點xk，令k=0②如果已得xk，且xk不是最優(yōu)解，則選定搜索方向pk③從xk出發(fā)，沿pk求αk，以產(chǎn)生xk+1=xk+αkpk④新點是否極小？是，停止；否，令k=k+1，返回②。5．確定步長αk的方法①αk取常數(shù)（αk=1），簡單，不保證f(xk)下降②可接受點算法：只要使f(xk)下降，取αk任意步長③一維搜索：沿搜索方向使目標(biāo)函數(shù)值下降得最多，αk

：minf(xk+αkpk)即求一個以αk為變量的一元函數(shù)的極小值問題。6．一維搜索的判別準(zhǔn)則：充分小的正數(shù)例：（1）|f()-f（）|（2）|f()-f（）|<

=[f()+f（）]滿足（1）停；否，滿足（2）停；否，返回，繼續(xù)迭代。<7．原理設(shè)f（x）在[a，b]是下單峰函數(shù)，在[a，b]內(nèi)任取兩點、，且<若f()<f()，則[a，]，

若f()f()，則[，b]，

再從中取一個點，又將新區(qū)間再縮短一次，反復(fù)直到最終區(qū)間長度縮短到滿足預(yù)先給定的精確度在內(nèi)在內(nèi)二．Fibonacci法(書P14)[a，b]一定，計算n次，最多將多長（設(shè))的原始區(qū)間縮短為1？設(shè)<，[a，]，-a[，b]，b-=b-a=(b-)+(-a)++若=+,n2==1則為最大原始區(qū)間長度設(shè)=，若[a，b]，最終區(qū)間長度（>0），可確定n，，…，，，可得：=a+（b-a）（-a）=a+（b-a）（-a）+=1=1--a=b-=（b-a）)、f()得新區(qū)間[a，b]計算比較f(設(shè)已迭代i-1次，第i次，有n-i+1個試點令： =a+（b-a）=a+i=h-1時，==1，與重合。)、f(③區(qū)間縮水率不固定（b-a）注意：①先計算n②第一次計算f(),其余每次只計一個f(x)例題見書《最優(yōu)化方法》解可新編P172.2凸集、凸函數(shù)和凸規(guī)劃一、凸集1、凸集的概念：定義1：設(shè)集合SRn，若x(1),x(2)S,[0,1]，必有

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

是連接x(1)與x(2)的線段。凸集非凸集2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集1、凸集的概念：例:證明集合S={x∣Ax=b}是凸集。其中，A為mn矩陣，b為m維向量。證明：任取x(1),x(2)S,(0,1)

記x

=x(1)＋(1-)x(2)

有Ax

=A(x(1)＋(1-)x(2))

=Ax(1)＋(1-)Ax(2)

=b＋(1-)b

=b

2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))定義2：凸組合：設(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)成凸組合——凸集2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集1、凸集的概念：定理：S是凸集S中任意有限點的凸組合屬于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)。多胞形單純形單純形2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集

2、凸集的性質(zhì)：凸集的交集是凸集；（并？）凸集的內(nèi)點集是凸集；（逆命題是否成立？）凸集的閉包是凸集。（逆命題是否成立？）分離：定義1：設(shè)集合S1，S2

Rn，非空，若p

Rn，p≠0,使?jié)M足

pT

x≥α，xS1

pT

x≤α，xS2則稱超平面H={x∣pT

x=α}分離S1，S2

。H稱為分離超平面2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))如果S1∪S2H，則稱正常分離。如果等號去掉，則稱嚴(yán)格正常分離。如果進一步ε>0,使?jié)M足

pT

x≥α+ε，xS1

pT

x≤α，xS2則稱H強分離S1，S2

。強分離分離非正常分離2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))5）支撐：定義：設(shè)非空集合SRn，xS,p

Rn，p≠0,如果滿足pT(x-x)≥0，xS，則稱超平面H={x∣pT(x-x)=0}為S在x點的支撐超平面。又若SH，則稱正常支撐。支撐2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集3、凸錐：定義：C

Rn,若xC,>0

有xC,則稱

C是以0為頂點的錐。如果C還是凸集，則稱為凸錐。集合{0}、Rn

是凸錐。命題：C是凸錐C中任意有限點的半正組合屬于S02.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ù)。若進一步有上面不等式以嚴(yán)格不等式成立，則稱f(x)為凸集S上的嚴(yán)格凸函數(shù)。當(dāng)-f(x)為凸函數(shù)（嚴(yán)格凸函數(shù)）時，則稱f(x)為凹函數(shù)（嚴(yán)格凹函數(shù)）。嚴(yán)格凸函數(shù)凸函數(shù)嚴(yán)格凹函數(shù)2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)1、凸函數(shù)及水平集：定理：f(x)為凸集S上的凸函數(shù)S上任意有限點的凸組合的函數(shù)值不大于各點函數(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ù)？

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ù)非凸，但任意水平集是凸集。2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質(zhì)：方向?qū)?shù)：設(shè)S

Rn

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

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

>0

充分小時有x*+d

S,

如果

lim

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

存在（包括）

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

f`(x*;d)=lim

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

若f(x)在x*可導(dǎo)，則f`(x*;d)=[f(x*)]Td.2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)的性質(zhì)：以下設(shè)S

Rn

為非空凸集，函數(shù)f:SR2）若f凸，則f在S的內(nèi)點集上連續(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)格凸。2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))三、凸規(guī)劃：當(dāng)（fS）中，S為凸集，f是S上的凸函數(shù)（求min），稱（fS）為凸規(guī)劃；對于（fgh）,f,gi為凸函數(shù)，hj為線性函數(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。2.3多面體、極點、極方向1）多面體：有限個半閉空間的交例：S={xRnAx=b,x≥0}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

不能表示為兩個不同方向的組合(d=d(1)+d(2)).2.3多面體、極點、極方向多面體S={xRnAx=b,x≥0}的極點和極方向定理1（極點特征）設(shè)A

滿秩，x

是S極點的充分必要條件是:

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

這里xB=B-1b≥0,xN=0.S中必存在有限多個極點。(≤Cnm)2.3多面體、極點、極方向多面體

S={xRnAx=b,x≥0}的極點和極方向定理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中必存在有限多個極方向。(≤(n-m)Cnm)考慮多面體

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

3210065

A=21010b=400300175

即

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

例題

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]

例題

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

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

=0，解線性方程組：

3x1

+2x2

+0x5

=652x1

+x2

+0x5

=400x1

+3x2

+x5

=75

得到x1

=15，x2

=10，x5=45，對應(yīng)的極點：

x=(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T例題

類似可得到極點

x(2)=(5,25,0,5,0)T

（對應(yīng)B2）

x(7)=(20,0,5,0,75)T

（對應(yīng)B5）

x(8)=(0,25,15,15,0)T

（對應(yīng)B7）

x(9)=(0,0,65,40,75)T

（對應(yīng)B10）而x(3)=(0,32.5,0,7.5,-22.5)T（對應(yīng)B9）

x(4)=(65/3,0,0,-10/3,75)T

（對應(yīng)B6）

x(5)=(7.5,25,-7.5,0,0)T

（對應(yīng)B1）

x(6)=(0,40,-15,0,-45)T

（對應(yīng)B8）

不是極點例題2.3多面體、極點、極方向多面體S={xRnAx=b,x≥0}的極點和極方向定理3（表示定理）考慮上述多面體S，

設(shè)A滿秩，x(1),x(2),…,x(k)為所有極點，d(1),d(2),…,d(l)為所有極方向。那么，對于xS，λi≥0，且λ1+λ2+…+λk=1,j≥0,j=1,2,…,l,使

x=λ1x(1)+λ2x(2)+…+λkx(k)+1d(1)+2d(2)+…+ld(l).一線性規(guī)劃模型

例1:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示：

產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤（元/件）15002500

問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？解：設(shè)變量xi為第i種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（i＝1，2）。根據(jù)題意，我們知道兩種產(chǎn)品的生產(chǎn)受到設(shè)備能力（機時數(shù)）的限制。對設(shè)備A，兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)不能超過65，于是我們可以得到不等式：3x1

+2x2

≤65；對設(shè)備B，兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)不能超過40，于是我們可以得到不等式：2x1

+x2

≤40；一線性規(guī)劃模型

對設(shè)備C，兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)不能超過75，于是我們可以得到不等式：3x2

≤75；另外，產(chǎn)品數(shù)不可能為負(fù)，即x1,x2≥0。同時，我們有一個追求目標(biāo)，即獲取最大利潤。于是可寫出目標(biāo)函數(shù)z為相應(yīng)的生產(chǎn)計劃可以獲得的總利潤：z=1500x1+2500x2

。綜合上述討論，在加工時間以及利潤與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下，把目標(biāo)函數(shù)和約束條件放在一起，可以建立如下的線性規(guī)劃模型：一線性規(guī)劃模型目標(biāo)函數(shù)

Maxz=1500x1+2500x2

約束條件

s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1,x2≥0

一線性規(guī)劃模型這是一個典型的利潤最大化的生產(chǎn)計劃問題。其中，“Max”是英文單詞“Maximize”的縮寫，含義為“最大化”；“s.t.”是“subjectto”的縮寫，表示“滿足于……”。因此，上述模型的含義是：在給定條件限制下，求使目標(biāo)函數(shù)z達到最大的x1,x2

的取值。一線性規(guī)劃模型[例2]求線性電阻電橋中消耗的總功率最小時的最優(yōu)參數(shù)。設(shè)任意支路的電阻為Rk，其電流和電壓分別為Ik、Vk，已知Vk=IkRk

，Ikmin≤Ik≤Ikmax，k=1，2，…，5，Vk

、

Ikmin

、

Ikmax為已知常數(shù)。Minf(x)=s.t

Ikmin≤Ik≤Ikmax=+=+,0，計算=求一般形式

目標(biāo)函數(shù)：Max(Min)z=c1x1

+c2x2

+…+cnxn

約束條件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2

...am1x1+am2x2

+…+amnxn≤(=,≥)bm

x1，x2，…，xn≥0一線性規(guī)劃模型標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：Maxz=c1x1+c2x2+…+cnxn

約束條件：a11x1+a12x2+…+a1nxn

=

b1a21x1+a22x2+…+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn

≥0一線性規(guī)劃模型可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個特點：目標(biāo)最大化、約束為等式、決策變量均非負(fù)、右端項非負(fù)。對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:一線性規(guī)劃模型

1.極小化目標(biāo)函數(shù)的問題：設(shè)目標(biāo)函數(shù)為

Minf=c1x1

+c2x2

+…+cnxn

則可以令z

＝-f

，該極小化問題與下面的極大化問題有相同的最優(yōu)解，即

Maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即

Minf

＝-Maxz一線性規(guī)劃模型

2、約束條件不是等式的問題：設(shè)約束條件為

ai1x1+ai2x2+…+ain

xn

≤bi

可以引進一個新的變量s

，使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ain

xn

)

顯然，s

也具有非負(fù)約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ain

xn+s=bi一線性規(guī)劃模型當(dāng)約束條件為

ai1x1+ai2x2+…+ain

xn

≥bi

時，類似地令

s=(ai1x1+ai2x2+…+ain

xn)-bi

顯然，s

也具有非負(fù)約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ain

xn-s=bi

一線性規(guī)劃模型為了使約束由不等式成為等式而引進的變量s稱為“松弛變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進不同的松弛變量。

一線性規(guī)劃模型

例3：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

Minf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

一線性規(guī)劃模型

解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z=-f=-3.6x1+5.2x2-1.8x3

其次考慮約束，有2個不等式約束，引進松弛變量x4，x5

≥0。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：

Maxz=-3.6x1

+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9

x1+x2+x3=38

x1,x2,x3,x4,x5

≥0一線性規(guī)劃模型

3.變量無符號限制的問題：在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負(fù)約束。當(dāng)某一個變量xj沒有非負(fù)約束時，可以令

xj

=

xj’-

xj”其中

xj’≥0，xj”≥0即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然xj的符號取決于xj’和xj”的大小。一線性規(guī)劃模型

4.右端項有負(fù)值的問題：在標(biāo)準(zhǔn)形式中，要求右端項必須每一個分量非負(fù)。當(dāng)某一個右端項系數(shù)為負(fù)時，如bi<0，則把該等式約束兩端同時乘以-1，得到：-ai1x1-ai2x2-…-ain

xn

=-bi

。一線性規(guī)劃模型例4：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0一線性規(guī)劃模型解：首先，將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z=-f=3x1–5x2–8x3+7x4

；

其次考慮約束，有3個不等式約束，引進松弛變量x5,x6,x7

≥0；由于x2無非負(fù)限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；

由于第3個約束右端項系數(shù)為-58，于是把該式兩端乘以-1。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：一線性規(guī)劃模型Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

一線性規(guī)劃模型一線性規(guī)劃模型矩陣形式：線性規(guī)劃的標(biāo)準(zhǔn)形式：

MaxcTx(LP)s.t.Ax=b

x≥0其中,

c,x

Rn

b

Rm

Amn

矩陣一線性規(guī)劃模型線性規(guī)劃的規(guī)范形式：

MaxcTx(P)s.t.Ax≤b

x≥0其中,

c,x

Rn

b

Rm

Amn

矩陣二線性規(guī)劃的單純形法

線性規(guī)劃的理論：考慮(LP)的最優(yōu)性條件約束多面體S={xRnAx=b,x≥0}的極點和極方向定理1考慮(LP)及上述多面體S，設(shè)

A滿秩，x(1),x(2),…,x(k)為所有極點，d(1),d(2),…,d(l)為所有極方向。那么，

1)(LP)存在有限最優(yōu)解cTd(j)≤0,j.2)若(LP)存在有限最優(yōu)解,則最優(yōu)解可以在某個極點達到.二線性規(guī)劃的單純形法

線性規(guī)劃的理論定理2考慮(LP),條件同上，設(shè)x*為極點,存在分解A=[B,N]，其中B為m階非奇異矩陣，使x*T=[xB*T,xN*T],

這里xB*=B-1b≥0,xN*=0，相應(yīng)cT=[cBT,cNT]。那么，

1）若

cNT-cBT

B-1N≤0,則

x*--opt.2）若

cj-cBT

B-1aj>0,且B-1aj≤0,則(LP)無有界解.線形規(guī)劃的基本性質(zhì)(一)．線形規(guī)劃的可行域定理1：線形規(guī)劃的可行域是凸集定理2：線形規(guī)劃的可行域非空，若存在有限最優(yōu)解，則目標(biāo)函數(shù)的最優(yōu)值可在某個極點上達到。(二)．最優(yōu)基本可行解設(shè)矩陣A的秩為m，假設(shè)A=[B，N]，其中B為m維的可逆矩陣，相應(yīng)有x=Ax=[B，N]=B+N=b=b-N

可任意,取=0=基本解：B基矩陣，若b0，xx=為約束條件Ax=b，x0的基本可行解，B為可行基矩陣b>0非退化的b0退化的x=0定理3：令k={x|Ax=b，x0}，A是mn矩陣，A的秩為m，則k0的基本可行解等價。的極點集與Ax=b，x三．存在的問題定理4：如果Ax=b，x>0有可行解，則一定存在基本可行解，其中A為m四．基本性質(zhì)①可行解F={x|Ax=b，x②有可行解就一定有基本可行解③頂點與基本可行解一一對應(yīng)，最優(yōu)點一定可在基本可行解中找到④若有兩個或兩個以上的頂點是最優(yōu)解，則凸組合均為最優(yōu)解⑤基本可行解是有限的n矩陣，秩為m。0}為凸集1947年，丹茨格，研究出了單純形法線形規(guī)劃：目標(biāo)函數(shù)，約束方程均為線形的①線形規(guī)劃，合理的精度②高效的手段，方法③參數(shù)變化（靈敏度）易處理二線性規(guī)劃的單純形法表格單純形法1、原理

Maxf(x)=cTx(LP)s.t.Ax=b

x≥0其中,

c,xRn

b

Rm

A

mn

矩陣，秩（A）=m記A=[,,…，]===[]=設(shè)x=由Ax=b=-代入目標(biāo)函數(shù)可將A矩陣分解為[B，N]f=x=[]=+(-)+-(-)--若>0得到使目標(biāo)函數(shù)減小的新基本可行解。===-=在n-m

個非基變量中，使其中n-m-1個非基變量仍為零，而令一個非基變量不為零。如果Xk增大，取正值；如果-選擇，使=max假設(shè)-

>0，由零變?yōu)檎龜?shù)，得到Ax=b的解：=記=-

====-（3）越大，f減小的量越大；--=新的目標(biāo)值為：f=-(-)

(4)如何確定①由（4）式，越大，f下降越多的取值受到可行解的限制-

>0，由零變?yōu)檎龜?shù)？②由（3）式，假設(shè)二線性規(guī)劃的單純形法2、算法過程

MaxcTx(LP)s.t.Ax=b

x≥0其中,

c,xRn

b

Rm

A

mn

矩陣，秩（A）=m二線性規(guī)劃的單純形法

單純形法原理及算法過程算法過程(考慮一般步,k=0,1,2,…)設(shè)x(k)

為極點,對應(yīng)分解A=[B,N]，使

xT=[xBT,xNT],這里xB=B-1b>0,xN=0，

相應(yīng)cT=[cBT,cNT]。那么，

1）若

cNT-cBT

B-1N≤0,則x(k)–opt，停；

2）否則，存在

cj-cBT

B-1pj>0,a）若B-1pj≤0,則(LP)無有界解，停；

b）若存在

(B-1pj)i>0,

取α=min{(B-1b)i/(B-1pj)i

|(B-1pj)i

>0}=(B-1b)r/(B-1pj)r>0二線性規(guī)劃的單純形法

單純形法原理及算法過程(續(xù))

得到x(k+1)=x(k)+αd是極點其中,dT=[dBT,dNT

],這里j

dB=-B-1pj,dN=(0,...,1,…,0)T有,cTx(k+1)=cTx(k)+αcTd

=cTx(k)+α(cj

-cBTB-1pj)

>

cTx(k)

所以，x(k+1)

比

x(k)好重復(fù)這個過程，直到停機。二線性規(guī)劃的單純形法

表格單純形法2、單純形表：設(shè)x

為初始極點,相應(yīng)分解A=[B,N]fxBTxNTRHS目標(biāo)行1cBTcNT01行約束行0BNbM行1列m列n-m列1列作變換，使前m+1列對應(yīng)的m+1階矩陣變?yōu)閱挝痪仃?。相?dāng)于該表左乘

1cBT-11-cBT

B-1

0B

0B-1

=二線性規(guī)劃的單純形法

表格單純形法得到：檢驗數(shù)fxBTxNTRHS目標(biāo)行10TcNT-cBT

B-1cBTB-1

b1行

xB0IB-1NB-1bM行1列m列n-