最優(yōu)化理論與方法-電子科技大學(xué)

第三章最優(yōu)化理論與方法最優(yōu)化計(jì)算方法主要是研究在一定限制條件下，選取某種方案以達(dá)到最優(yōu)化目標(biāo)的一門(mén)學(xué)科。達(dá)到最優(yōu)目標(biāo)的方案，稱(chēng)為最優(yōu)方案，搜索最優(yōu)方案的方法，稱(chēng)為最優(yōu)化方法。這種方法的數(shù)學(xué)理論，稱(chēng)為最優(yōu)化理論。實(shí)際上最優(yōu)化方法已廣泛應(yīng)用于空間技術(shù)、軍事科學(xué)、電子工程、通訊工程、自動(dòng)控制、系統(tǒng)識(shí)別、資源分配、計(jì)算數(shù)學(xué)、經(jīng)濟(jì)管理等等領(lǐng)域。最優(yōu)化方法包括的內(nèi)容很廣泛，如線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、組合優(yōu)化等等。最優(yōu)化理論與方法3.1線性規(guī)劃問(wèn)題的數(shù)學(xué)模型3.2二維線性規(guī)劃的圖解法3.3二維線性規(guī)劃的基本概念及解的性質(zhì)

3.4單純形法3.7一維搜索法3.8無(wú)約束最優(yōu)化方法§3.1線性規(guī)劃問(wèn)題的數(shù)學(xué)模型一.最優(yōu)化問(wèn)題舉例

例1（運(yùn)輸問(wèn)題）設(shè)有位于不同城市的m個(gè)電視機(jī)廠A1，A2，…，Am，其產(chǎn)量分別為a1，a2，…，am（臺(tái)），其產(chǎn)品供應(yīng)n個(gè)城市B1，B2，…，Bn。每個(gè)城市的需要量分別為b1，b2，…，bn（臺(tái)）。假定產(chǎn)需平衡，即?=miia1?=niib1=已知從Ai到Bj的運(yùn)費(fèi)單價(jià)為cij（元/臺(tái)）（i=1,2,…,m；j=1,2,…,n）。問(wèn)由每個(gè)廠到每個(gè)城市的運(yùn)輸量各為多少時(shí)，既能保證需要量，又能使總運(yùn)費(fèi)最少？

解設(shè)由Ai到Bj的運(yùn)輸量為xij（臺(tái)）（i=1,2,…,m；j=1,2,…,n），則要求總運(yùn)費(fèi)

達(dá)到最小，其中要滿足的約束條件為：??==minjijijxc11綜上，可把所得到的線性規(guī)劃問(wèn)題記為:???????????íì==3====????====,,,2,1;,,2,1,0,,,2,1,,,2,1,..,min1,111mjnixnjbxmiaxtsxcijmijijnjiijminjijij…………?=njijx1?=miijx1=ai，i=1,2,…,m；=bj，j=1,2,…,n例2(系統(tǒng)可靠性問(wèn)題)在設(shè)計(jì)某些大型的系統(tǒng)工程時(shí),常常要考慮它們的可靠性。設(shè)一個(gè)系統(tǒng)是由n個(gè)部件串聯(lián)而成。為提高系統(tǒng)的可靠性，每個(gè)部件都裝有備用件，一旦原部件出現(xiàn)故障，備用件就自動(dòng)進(jìn)入系統(tǒng)。顯然,備用件越多系統(tǒng)可靠性越大，但費(fèi)用也越高，重量也越大，這在實(shí)際上是不行的。假定當(dāng)部件k配置uk個(gè)備用件時(shí)，這個(gè)部件正常工作的概率為pk

(uk)，而每個(gè)備用件k的費(fèi)用為ck,重量為ak。試在總費(fèi)用不超過(guò)C，總重量不超過(guò)A的條件下決定各部件的備用件的數(shù)量，使得系統(tǒng)正常工作的概率最大。解

因?yàn)橄到y(tǒng)正常工作的概率是各部件正常工作的概率的乘積，所以問(wèn)題歸納為uk

是正整數(shù)。?=nkkkup1)(max?=￡nkkkCucts1.?=￡nkkkAua1例3（非線性方程組的求解）解非線性方程組是相當(dāng)困難的一類(lèi)問(wèn)題，由于最優(yōu)化方法的發(fā)展，對(duì)解非線性方程組提供了一種有力的手段。解非線性方程組?????íì===0),,,(0),,,(0),,,(21212211nnnnxxxfxxxfxxxf…………………在方程組有解的情況下等價(jià)于下列函數(shù)的最小值點(diǎn)：),,,(),,,(min211221nniinxxxfxxxF?==……例4

合理下料問(wèn)題某車(chē)間有長(zhǎng)度為180cm的鋼管(數(shù)量充分多),今要將其截為三種不同長(zhǎng)度,長(zhǎng)度為70cm的管料100根,而52cm、35cm的管料分別不得少于150根和120根,問(wèn)應(yīng)采取怎樣的截法,才能完成任務(wù),同時(shí)使剩下的余料最少？解所有可能的截法共有8種,如下表所示：截法一二三四五六七八需要量長(zhǎng)度702111000010052021032101503510130235120余料56235246235選其中一種余料最少的截法,但不能完成任務(wù).所以我們必須同時(shí)采取若干種截法,配合起來(lái),在完成任務(wù)的條件下,使總的余料最少.設(shè)采用第i種截法的鋼管數(shù)目為xi

(i=1,…,8),那么截出70cm的管料數(shù)目應(yīng)為(2x1

+x2

+x3+x4

)根,其總數(shù)應(yīng)為100,即2x1

+x2

+x3+x4

=100同理可得2x2

+x3

+x4+3x5

+2x6

+x7

≥150x1

+x3

+3x4+2x6

+3x7

+5x8

≥120由題意可知

xi

≥0

(i=1,…,8)

余料的總長(zhǎng)度為于是上述下料問(wèn)題的數(shù)學(xué)模型為i

說(shuō)明：由于求變量x1，x2，…，xn使某函數(shù)f(x1，x2，…，xn)（也記為f(x))達(dá)到極大，等價(jià)于使-f(x)達(dá)到極小。所以上述例子均可歸結(jié)為函數(shù)的帶約束或不帶約束的極小化問(wèn)題，簡(jiǎn)稱(chēng)最優(yōu)化問(wèn)題，其中稱(chēng)f(x)為目標(biāo)函數(shù)。二．最優(yōu)化問(wèn)題的數(shù)學(xué)模型與分類(lèi)1.根據(jù)問(wèn)題不同特點(diǎn)分類(lèi)

(1)無(wú)約束極小化問(wèn)題求x=(x1，x2，…，xn)T

使函數(shù)f(x)

達(dá)到最小,記為)(minxfnRx?或min)(xf（2）約束極小化問(wèn)題記為=3migtsfi,,2,1,0)(..)(minxx…h(huán)j(x)=0,j=1,2,…,n說(shuō)明：若某些問(wèn)題的約束條件出現(xiàn)h(x)≤0，則可令g(x)=-h(x)而將此約束轉(zhuǎn)化為g(x)≥0,所以模型中的不等號(hào)均假定為≥.注:∵h(yuǎn)(x)=0

h(x)≥0-h(x)≥0其中S={x|gi(x)≥0,i=1,…,m}稱(chēng)為可行集或可行域，S中的點(diǎn)稱(chēng)為可行點(diǎn)。所以上述(2)約束極小化問(wèn)題也可表為：或)(minxfSx??íì=3migtsfi,…,2,1,0)(..)(minxx2.根據(jù)函數(shù)類(lèi)型分類(lèi)

根據(jù)目標(biāo)函數(shù)和約束函數(shù)是否是線性函數(shù)可分為三類(lèi)，具體見(jiàn)下表。類(lèi)目標(biāo)函數(shù)約束函數(shù)線性規(guī)劃線性線性二次規(guī)劃二次函數(shù)線性非線性規(guī)劃除上(1)

極大值問(wèn)題極小化對(duì)maxf(x),

只要令g(x)=-f(x)

,

則極大值問(wèn)題就轉(zhuǎn)化為求g(x)的極小值問(wèn)題.

4.將一般的線性規(guī)劃問(wèn)題轉(zhuǎn)化成標(biāo)準(zhǔn)形式的方法

3.線性規(guī)劃問(wèn)題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式稱(chēng)變量xn+p為松馳變量.

(3)

轉(zhuǎn)變“≥”約束為等式約束(2)

轉(zhuǎn)變“≤”約束為等式約束

引入xn+p

≥0

,使引入xn+q

≥0

,使稱(chēng)變量xn+q為剩余變量.

標(biāo)準(zhǔn)形式要求

xi

≥0,模型中如果出現(xiàn)xi可任取值,則稱(chēng)xi為自由變量,此時(shí)可作如下處理:

(4)消除自由變量

例5

將下面線性規(guī)劃化為標(biāo)準(zhǔn)形.

引入新變量,令即可.解極大問(wèn)題極小化:

引入松馳變量

x4≥0,使.引入剩余變量x5≥0,使消除自由變量x3,

令則原規(guī)劃的標(biāo)準(zhǔn)形式為注:

標(biāo)準(zhǔn)形中還可要求bi

≥0

(i=1,…,m),若某個(gè)bi

≤0,則可在所在等式兩端同乘以(

1)即可.

5.線性規(guī)劃的標(biāo)準(zhǔn)形還可以寫(xiě)成矩陣形式

令則線性規(guī)劃的標(biāo)準(zhǔn)形式又可寫(xiě)成矩陣形式:

的矩陣形式為:

如例5，即規(guī)化:其中§3.2二維線性規(guī)劃的圖解法當(dāng)x=(x1,x2)

(即二維線性規(guī)劃)時(shí),可行集R可用圖形表示出來(lái),因而可用圖解法來(lái)求該線性規(guī)劃的解.對(duì)線性規(guī)劃設(shè)其可行集為R.例1

用圖解法求解解先繪出可行集,由x1

≥0,x2

≥0,可知可行集在第一象限內(nèi);因–x1

+2x2

≤4,可知可行集在以直線–x1

+2x2

=4為分界線,且含原點(diǎn)的半平面內(nèi);而3x1

+2x2

≤12是包含坐標(biāo)原點(diǎn)的、以直線3x1

+2x2

=12為分界線的半平面.這兩個(gè)半平面在第一象限的交集就是可行集,如下圖所示的陰影部分.

再繪出目標(biāo)函數(shù)的等值線.當(dāng)目標(biāo)函數(shù)值為z0時(shí),其等值線為–x1

-2x2

=z0這是一條直線,當(dāng)

z0

取不同值時(shí),可得到其他等值線.因具有相同的斜率,所以等值線是彼此平行的直線.例如,當(dāng)z0=0時(shí),得一通過(guò)坐標(biāo)原點(diǎn)的等值線

–x1

-2x2

=0然后確定目標(biāo)函數(shù)的負(fù)梯度方向(這是函數(shù)值下降最快的方向):

如上圖中箭頭所指的方向.

最后沿(1,2)T方向,作目標(biāo)函數(shù)值的一系列等值線(一族平行線).由圖可知,沿目標(biāo)函數(shù)值下降方向的等值線在點(diǎn)x*=(2,3)與可行集R唯一相交;

若目標(biāo)函數(shù)值繼續(xù)下降,相應(yīng)的等值線與可行集將不再相交.故點(diǎn)x*=(2,3)為此線性規(guī)劃的唯一最小值點(diǎn),相應(yīng)的最小值為

8.

例中最優(yōu)解是R的一個(gè)“頂點(diǎn)”.一般地,可證:(1)

若可行集R=

,則線性規(guī)劃無(wú)最優(yōu)解;例2

解線性規(guī)劃(2)

若線性規(guī)劃的最優(yōu)解存在,則必可在R的某個(gè)“頂點(diǎn)”處取得.(3)

若R的某兩個(gè)頂點(diǎn)是最優(yōu)解,則這兩個(gè)頂點(diǎn)所連接的線段上任一點(diǎn)都是最優(yōu)解.

解可行集如下圖所示的陰影部分.

繪出過(guò)原點(diǎn)的等值線;求出目標(biāo)函數(shù)的負(fù)梯度方向:

沿(-2,-2)T的方向作目標(biāo)函數(shù)的等值線,也即2x1

+2x2

=0的平行線,易見(jiàn)x*=(1,0)是此規(guī)劃的唯一最小值點(diǎn),且最小值為2.說(shuō)明:

將例2的min改為max,即min(-2x1

-2x2).此目標(biāo)函數(shù)的下降方向與例2的相反,由圖可知此線性規(guī)劃沒(méi)有最優(yōu)解.

例3

將例1的目標(biāo)函數(shù)改為f(x)=-3x1

-2x2,而約束條件不變,

即求解可行集如圖:f(x)=-3x1

-2x2

可行集的4個(gè)頂點(diǎn)為:(0,2),(0,0),(4,0),(2,3)相應(yīng)的函數(shù)值依次為:-4,0,-12,-12所以,目標(biāo)函數(shù)的最小值為-12,且點(diǎn)(2,3)與(4,0)之間的所有點(diǎn)都是該規(guī)劃的最優(yōu)解,該規(guī)劃有無(wú)窮多個(gè)解.

§3.3線性規(guī)劃的基本概念及解的性質(zhì)

其中A為m

n矩陣,設(shè)秩R(A)=m,則m≤n,用Pj表示A的第j列,則Ax=b可記為基:

若可逆,則稱(chēng)B為該線性規(guī)劃的基.稱(chēng)為基向量.稱(chēng)

xji

為基變量.其余變量稱(chēng)為非基變量.考慮線性規(guī)劃:(3.3.1)基本解:

設(shè)是式(3.3.1)的一個(gè)基,相應(yīng)的基變量為

則方程組BxB=b有唯一解:可行解:

滿足Ax=b,x≥0

的向量x稱(chēng)為式(3.3.1)的可行解.

基本可行解:

若x既是可行解又是基本解,則稱(chēng)x為式(3.3.1)的基本可行解.此時(shí)的B稱(chēng)為可行基.因A為m

n矩陣，所以式(3.3.1)的不同基最多有Cnm個(gè).即基本可行解的個(gè)數(shù)有限.令非基變量全部為0,得Ax=b的一組解:

稱(chēng)此解為式(3.3.1)的基本解.(假定j1,…,jm=1,…,m)最優(yōu)解:

CTx取得的最小值的可行解x*,稱(chēng)為式(3.3.1)的最優(yōu)解.

例1

求下列約束的所有基本可行解.

即

均為基

解

由于x1=-2<0,故x不是可行解,從而不是基本可行解.(2)

取B2為基,則x2,x3

為基變量.(3)

取B3為基,則x1,x3

為基變量.所以所有基本可行解為:x2,x3

(1)

取B1為基,則定義1

設(shè),若對(duì),及,都有

,則稱(chēng)D為凸集.規(guī)定空集

與單元集也是凸集.

說(shuō)明:

(1)

凸集又等價(jià)為:若,且,都有,則D為凸集.(2)

從幾何來(lái)講,若集合D中任意兩點(diǎn)的連線仍屬于D,則D為凸集.定義2

設(shè)為一組非負(fù)實(shí)數(shù),且,則稱(chēng)為x1,x2,…,xm

的一個(gè)凸組合.定理

為凸集的充要條件是D中任意有限個(gè)點(diǎn)的凸組合仍在D中.

定義3

設(shè),D是凸集,若x0

不能表示為D中其他任意兩個(gè)不同點(diǎn)的凸組合,則稱(chēng)x0

是D的極點(diǎn).

例

(1)

右圖中,x1,x2,x3,x4為凸集D的極點(diǎn).(2)

下圖,圓周上每一點(diǎn)都是極點(diǎn).(3)

開(kāi)區(qū)間為凸集,其上任一點(diǎn)都可表示為兩個(gè)不同點(diǎn)的凸組合,故開(kāi)區(qū)間上沒(méi)有極點(diǎn).從以上理論可知:

求解線性規(guī)劃問(wèn)題,其本質(zhì)上是找出可行集的極點(diǎn).而極點(diǎn)與基本可行解一一對(duì)應(yīng),基本可行解最多Cnm個(gè).從理論上說(shuō)都可全部計(jì)算出來(lái),通過(guò)比較各極點(diǎn)處目標(biāo)函數(shù)值的大小就可以得到最優(yōu)解.

定理

若線性規(guī)劃有最優(yōu)解,則必可在其可行集的頂點(diǎn)處取得.

推論線性規(guī)劃可行集R的點(diǎn)x是R的極點(diǎn)的充要條件是x為此線性規(guī)劃的基本可行解.所以x1=(0,1,1)T

和-5是最優(yōu)解.

解由例1知此線性規(guī)劃有兩個(gè)基本可行解:

代入目標(biāo)函數(shù)得例4

求線性規(guī)劃的最優(yōu)解基本思想：

從可行集的一個(gè)頂點(diǎn)出發(fā),沿目標(biāo)函數(shù)值下降的方向?qū)ふ蚁乱粋€(gè)頂點(diǎn),而頂點(diǎn)的個(gè)數(shù)有限,所以若有解,則必可在有限步求得最優(yōu)解.§3.4單純形法一、對(duì)應(yīng)于B的單純形表設(shè)線性規(guī)劃問(wèn)題為:設(shè)系數(shù)矩陣A的秩為m,B為m

m的線性規(guī)劃問(wèn)題的一個(gè)基.不妨設(shè)相應(yīng)地其中,為對(duì)應(yīng)于B的基變量部分;為對(duì)應(yīng)于B的非基變量部分.此時(shí)判別定理對(duì)于基B,若,且則對(duì)應(yīng)于基B的基本解便是最優(yōu)解,稱(chēng)為基本最優(yōu)解;這時(shí)基B稱(chēng)為最優(yōu)基.注:

≤0與是等價(jià)的.此時(shí)目標(biāo)函數(shù)值為

cTx=

cBTxB=

cBTB-1b所以當(dāng)x為基本解時(shí)(有xN=0)有記:其中稱(chēng)為檢驗(yàn)數(shù).

對(duì)應(yīng)于基B的單純形表,記為T(mén)(B),

定義為說(shuō)明

(1)如果所有,這時(shí)對(duì)應(yīng)于基B的基本解為基本可行解,基B為可行基.(2)

若所有

而且所有

,這時(shí)對(duì)應(yīng)于基B的基本解為基本最優(yōu)解,基B為最優(yōu)基.相應(yīng)的目標(biāo)函數(shù)值為最優(yōu)值.例1

線性規(guī)劃有三個(gè)基:因此對(duì)于基B1的單純形表T(B1)如下:說(shuō)明:

(1)

因基變量值非負(fù),所以上述解是基本可行解.

(2)

由表可寫(xiě)出用非基變量x3表示S和用x3表示基變量.

對(duì)應(yīng)于B1的基本解及相應(yīng)的目標(biāo)函數(shù)值為:x1=1,x2=1,x3=0;S

=3.S表目標(biāo)函數(shù)

x1x2x3S3002x11101x21012S=3-2x3,x1=1-x3,x2=1-2x3類(lèi)似,得表T(B2):說(shuō)明:

因基變量值非負(fù),檢驗(yàn)數(shù)非正,所以上述解是最優(yōu)解(x1,x2,x3)=(1/2,0,1/2),S=2.

x1x2x3S20

10x11/21-1/20x31/201/21T(B3):x1x2x3S1

200x2

1

210x31101說(shuō)明:

因基變量有負(fù)值-1,所以上述基本解不是可行解.二、換基迭代所謂換基迭代就是從一個(gè)基本可行解迭代到一個(gè)新的基本可行解的方法.

第一行中的第二個(gè)數(shù)起是檢驗(yàn)數(shù),可用以判定基B對(duì)應(yīng)的基本可行解是否為最優(yōu)解.若

(1)所有檢驗(yàn)數(shù)皆非正,則判定基B是最優(yōu)基,取最優(yōu)解,求解終止.

(2)

有某些檢驗(yàn)數(shù)是正的,此時(shí)就要進(jìn)行換基迭代.

由運(yùn)算可知,如果已知線性規(guī)劃問(wèn)題的一個(gè)可行基B,我們可求得對(duì)應(yīng)于基B的單純形表,表中

第一列就是目標(biāo)函數(shù)值和基本解中基變量的值;一般地,如果對(duì)應(yīng)于可行基的單純形表(如下表)的檢驗(yàn)數(shù)出現(xiàn)正數(shù),這時(shí)就不能判定B是否為最優(yōu)基,因而要進(jìn)行換基迭代.

換基迭代的步驟:

(1)求軸心項(xiàng):

在所有的檢驗(yàn)數(shù)b0j>0中,選最左邊的一個(gè),設(shè)為b0s,其對(duì)應(yīng)的非基變量設(shè)為xs,對(duì)應(yīng)于向量用PS中正的各分量bis

分別去除對(duì)應(yīng)的bi0,取bi0/bis中最小者(若同時(shí)有幾個(gè)相同的最小者,則取其中對(duì)應(yīng)的基變量下標(biāo)最小者),設(shè)為br0/brs,則稱(chēng)brs為軸心項(xiàng),并將brs用□框住.

(2)

在基B中,調(diào)進(jìn)PS

(稱(chēng)為進(jìn)基列),換出Pr

(稱(chēng)為出基列),xs稱(chēng)為進(jìn)基變量,xr稱(chēng)為出基變量,得新基為使新表中brs=1,用原表中brs去除第r行各數(shù),得新表第r行的數(shù),即為使新表中bis=0（0≤i≠r≤m）,將在原表中第i行各數(shù)減去第r行相應(yīng)數(shù)的brj/brs,倍,得新表第i行的數(shù),即(3)

對(duì)基B的單純形表,進(jìn)行適當(dāng)?shù)淖儞Q,使PS各量變?yōu)閱挝幌蛄?分量brs取1,其他分量取0),便得新基的單純形表.

例如S表目標(biāo)函數(shù)

x1x2x3S3002x11101x21012

x1x2x3S3002x11101x31/201/21檢驗(yàn)數(shù)為正Min{1/1,1/2}=1/2軸心項(xiàng)變?yōu)?(該行每元同除以2)x1x2x3S20

10x11/21-1/20x31/201/21變?yōu)?三、由一可行基開(kāi)始,求解線性規(guī)劃的步驟1)作對(duì)應(yīng)于基B的單純形表T(B)

2)判別1.

如果所有檢驗(yàn)數(shù)都非正,則基B對(duì)應(yīng)的基本可行解為最優(yōu)解.

已知一可行基

2.如果檢驗(yàn)數(shù)中,有些為正數(shù),但其中某正數(shù)所對(duì)應(yīng)的列向量的所有分量都是非正數(shù),則問(wèn)題無(wú)最優(yōu)解.

3.如果檢驗(yàn)數(shù)中,有些為正數(shù),且這些正數(shù)的對(duì)應(yīng)的列向量中都有正分量,此時(shí)要進(jìn)行換基迭代.3)換基迭代注:

1.

若基B為單位矩陣I,則2.

若B=I,且cBT=0（如所有的基變量均為松馳變量），則

解引進(jìn)松馳變量,變化為標(biāo)準(zhǔn)形.

例2

用單純形法求解下列線性規(guī)劃此時(shí)-cT

=(2,5,0,0,0),bT

=(4,3,8)x1x2x3x4x5S

025000x3410100x4301010x5812001(1)

取基B為單位矩陣(P3,P4,P5

)得單純形表

(2)

判別數(shù)有正數(shù),正數(shù)中最左邊的為

2.(3)

因Min{4/1,8/1}=4,所以1為軸心項(xiàng)

.(4)

在基B1中調(diào)進(jìn)P1,換出P3,得新基(P1,P4,P5

)得單純形表

x1x2x3x4x5S

805

200x1410100x4301010x540

2

101(5)

判別數(shù)有正數(shù)5.(6)

因Min{3/1,4/2}=2,所以2為軸心項(xiàng)

.重復(fù)上面換基迭代步驟可得對(duì)應(yīng)于新基的單純形表

檢驗(yàn)數(shù)有正數(shù)1/2,作換基迭代步驟,得新的單純形表

x1x2x3x4x5S

18001/20-5/2x1410100x41001/21-1/2x2201-1/201/2x1x2x3x4x5S

19000

1

2x12100

21x320012

1x2301010檢驗(yàn)數(shù)全部小于等于零,得最優(yōu)解為去掉松馳變量的值,即得原問(wèn)題的最優(yōu)解為:x1=2,x2=3相應(yīng)的原問(wèn)題的目標(biāo)函數(shù)最大值為:

f(2,3)=19.例3

求解線性規(guī)劃解此時(shí)-cT

=(1,2,0,0,0),bT

=(4,3,8)(1)同上例一樣,取基B為單位矩陣(P3,P4,P5

)得單純形表:

換基迭代后,得新基(P1,P4,P5

)的單純形表:x1x2x3x4x5S

012000x34

1

0100x4301010x5812001x1x2x3x4x5S

402

100x1410000x4301010x540

2

101換基迭代后,得新基(P1,P4,P2

)的單純形表:x1x2x3x4x5S

80000

1x1410100x41011/21-1/2x2201-1/201/2

值得指出的是:

在上表中除基變量x1,x2,x4

對(duì)應(yīng)的檢驗(yàn)數(shù)為零外,非基變量x3對(duì)應(yīng)的檢驗(yàn)數(shù)也為零,可以把x3對(duì)應(yīng)列中b23=?作軸心項(xiàng).在最優(yōu)基(P1,P4,P2

)中調(diào)進(jìn)P3

,調(diào)出P4

進(jìn)行換基迭代,得新的最優(yōu)基(P1,P3,P2

)對(duì)應(yīng)的單純形表:檢驗(yàn)數(shù)全部小于等于零,得最優(yōu)解為:(x1,x2,x3,x4,x5)=(4,2,0,1,0),Smin

=-8因表中的檢驗(yàn)數(shù)全非負(fù),所以(P1,P3,P2

)也為最優(yōu)基,對(duì)應(yīng)的基本最優(yōu)解為:所以,原問(wèn)題的又一基本最優(yōu)解為:x1=2,x2=3;對(duì)應(yīng)的目標(biāo)函數(shù)最小值為:f(2,3)=-8.

x1x2x3x4x5S

80000

1x121-20

21x320212-1x230101

1綜上,得兩個(gè)最優(yōu)解:x1*=(4,2),x2*=(2,3).它們是可行集凸集的兩個(gè)頂點(diǎn),故這兩個(gè)頂點(diǎn)的連線上的所有點(diǎn)都是該線性規(guī)劃的最優(yōu)解—最優(yōu)解有無(wú)窮多個(gè),其表達(dá)式為

結(jié)論:

線性規(guī)劃問(wèn)題的最優(yōu)基對(duì)應(yīng)的單純形表中,若非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)都是負(fù)數(shù),其基本最優(yōu)解是唯一的;若非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)中有零,這一問(wèn)題的基本最優(yōu)解可能不止一個(gè),一旦求得另一個(gè)最優(yōu)解,就可得到無(wú)窮多個(gè)最優(yōu)解.解例4

求解取基B為單位矩陣(P3,P4,P5

)得單純形表:

x1x2x3x4x5S

025000x34

10100x4301010x58

10001因檢驗(yàn)數(shù)2>0,其對(duì)應(yīng)的列向量所以原規(guī)劃無(wú)最優(yōu)解.注:為避免迭代中的循環(huán),軸心基的選取應(yīng)遵循以下兩條原則:1)

對(duì)進(jìn)基列Ps在所有判別數(shù)為正的那些列中,以列標(biāo)最小,也就是最左邊的那一列作進(jìn)基列.2)

對(duì)軸心項(xiàng)若在進(jìn)基列Ps中有多個(gè)分量符合軸心項(xiàng)的條件,則取行標(biāo)最小的那一個(gè)作為軸心項(xiàng).§3.7一維搜索法一、下降迭代算法及終止準(zhǔn)則下降迭代算法的基本思想:

選擇一個(gè)初始點(diǎn)x0

，逐次產(chǎn)生一系列點(diǎn)列x0,x1,x2,…，使

f(x0)＞f(x1)＞…＞f(xk)＞…并希望點(diǎn)列{xk}的極限就是f(x)的極小點(diǎn)x*。即問(wèn)題為:基本步驟

(1)選初始點(diǎn)x0，令k=0。

(2)按某種規(guī)則確定一個(gè)方向pk，使f(x)

沿pk

方向函數(shù)值下降（稱(chēng)為搜索方向）。

（3）從xk

出發(fā)以pk

為方向作射線xk+

pk（

≥0），（參數(shù)

稱(chēng)為步長(zhǎng)因子）。在此射線上求f(x)

的最小值。即求min03f(xk+adk)=f(xk

+akdk)=f(xk+1

)

a其中xk+1=xk+

kdk

說(shuō)明：（*）式稱(chēng)為終止準(zhǔn)則，終止準(zhǔn)則也可用下式(4)判別xk+1

是否為最優(yōu)解；若則xk+1為近似最優(yōu)解，迭代停止；否則令k﹕=k+1，轉(zhuǎn)（2）。其中ε1為預(yù)先給定的一個(gè)很小的正數(shù),▽f(xk+1)

為函數(shù)在點(diǎn)xk+1

的梯度.?f(xk+1)f(xk+1)-f(xk)＜ε1

或

＜ε1（*）或二、黃金分割法（0.618法）0.618法是求單峰函數(shù)的一種試探法，也是廣泛使用的方法之一。1.單峰函數(shù)定義

設(shè)f(x)是定義在[a,b]上的函數(shù)，若（i）存在x*∈[a,b]使minf(x)=f(x*)x∈[a,b]（ii）對(duì)任意的a≤x1<x2≤b，當(dāng)x2<x*時(shí)，f(x1)>f(x2)當(dāng)x1>x*時(shí)f(x1)<f(x2)，則稱(chēng)f(x)為[a,b]上的單峰函數(shù)。例如：ax1x2

x*x1’x2’)(xf單峰函數(shù)ab)(xf不是單峰函數(shù)基本思想:

在搜索區(qū)間[a,b]內(nèi)適當(dāng)插入兩點(diǎn)t1和t2將其分成三段,通過(guò)比較這兩點(diǎn)的函數(shù)值后,由單峰函數(shù)的性質(zhì),可刪去最左或最右端的一段,這算一次迭代.然后在留下來(lái)的區(qū)間上再插入一點(diǎn),重復(fù)上述過(guò)程,如此下去,可將區(qū)間無(wú)限縮小.2.黃金分割法說(shuō)明:

(1)

黃金分割法中參數(shù)0.618是由對(duì)稱(chēng)原則和等比收縮原則導(dǎo)出的,其中對(duì)稱(chēng)原則是指選點(diǎn)x1和x2，使

[a,x1]的長(zhǎng)=[x2,b]的長(zhǎng)即使:x1-a=b-x2

x2=a+b-x1

（或x1=a+b-x2）即〝加兩頭減中間〞。等比收縮原則是指每次留下的區(qū)間長(zhǎng)是上次留下的ω倍（ω即為0.618）且x1或x2是下次搜索的一個(gè)分點(diǎn).

(2)

由等比收縮原則可得x1-a=l0(1-ω),l0為[a,b]的長(zhǎng).再由〝加兩頭減中間〞可得兩分點(diǎn)與端點(diǎn)間的關(guān)系式:x1=a+(1-ω)l0=a+(1-ω)(b-a)x2=a+

b-x1=a+ω(b-a)ω=0.618算法(0.618法

)

已知目標(biāo)函數(shù)f(x)，精度ε。(1)確定f(x)的搜索區(qū)間[a,b]—利用前一算法。(5)若y1≤y2，則置b:=x2，x2:=x1，y2:=y1

轉(zhuǎn)3）；否則置a:=x1，x1:=x2，計(jì)算x2=a+b-x1，y2=f(x2)，轉(zhuǎn)4）。(2)計(jì)算x2=a+0.618(b-a)，y2=

f(x2)。(3)計(jì)算x1=a+b-x2

，y1=f(x1)。(4)若|x1–x2|<ε，則停。取;否則轉(zhuǎn)5)。221*xxx+=§3.8無(wú)約束最優(yōu)化方法最速下降法1.最速下降方向

該方法在每次迭代中沿最速下降方向進(jìn)行搜索。那么什么方向是函數(shù),f(x)在點(diǎn)x∈Rn

處的最速下降方向呢？

分析：設(shè)f(x)在x處可微，由泰勒公式有)(δx+f=++)(xf)(xδgT)(δo其中g(shù)(x)=▽f(x)≠0，δ=(δ1,δ2,…,δn)T,,表示當(dāng)δ→0時(shí)，是比高階的無(wú)窮小。若忽略高階無(wú)窮小,上式等價(jià)于)(δo)(δo22221dd+…+dn

+=δδ再對(duì)上式右邊用Cauchy不等式可得)(δx+f)(xfδg(x)T-=δTg(x)≥-

)(xgδ)()(xxgg當(dāng)且僅當(dāng)δ=-時(shí)上式取等號(hào)。于是可見(jiàn)當(dāng)δ取負(fù)梯度方向時(shí)，f(x+δ)下降最快。這個(gè)方向稱(chēng)為最速下降方向。)()(xxgg當(dāng)且僅當(dāng)δ=-時(shí)上式取等號(hào)。)(δx+f)(xf-≥-)(xgδ2.最速下降法問(wèn)題：minf(x)，x∈Rn,本節(jié)的優(yōu)化問(wèn)題均作此假定。計(jì)算步驟1）取初始點(diǎn)x0∈Rn