最優(yōu)化理論與方法

最優(yōu)化理論與方法課件制作：北方民族大學高岳林任子暉目錄第一章概論第二章線性規(guī)劃第三章無約束非線性規(guī)劃第四章約束非線性規(guī)劃第五章多目標規(guī)劃第六章整數(shù)規(guī)劃第七章動態(tài)規(guī)劃第一章概論

模型舉例最優(yōu)化問題的模型與分類第二章線性規(guī)劃

凸集與凸函數(shù)線性規(guī)劃的幾何特征線性規(guī)劃的標準型線性規(guī)劃的基本定理單純型法大M法第三章無約束非線性規(guī)劃

最優(yōu)性條件一維搜索最速下降法與共軛梯度法牛頓法與擬牛頓法第四章約束優(yōu)化方法

最優(yōu)性條件二次規(guī)劃可行方向法懲罰函數(shù)法復型法第五章多目標規(guī)劃

模型舉例向量集的優(yōu)化問題有效解和弱有效解評價函數(shù)法第六章整數(shù)規(guī)劃

整數(shù)規(guī)劃問題的基本概念線性整數(shù)規(guī)劃問題的分枝定界法

0—1的隱枚舉法第七節(jié)動態(tài)規(guī)劃

動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的最優(yōu)性與基本方程第一章概論

隨著生產(chǎn)、經(jīng)濟、技術(shù)的發(fā)展，工程技術(shù)、管理人員在實際工作中，肯定會面臨這樣的一類問題:工程設計中怎樣選擇參數(shù)，使得設計既滿足要求，又能降低成本；資源分配中，怎樣的分配方案既能滿足各方面的基本要求，又能獲得好的經(jīng)濟效益；生產(chǎn)計劃安排中，選擇怎樣的計劃方案才能提高產(chǎn)值和利潤；原料配比問題中，怎樣確定各種成分的比例才能提高質(zhì)量、降低成本；城建規(guī)劃中，怎樣安排工廠、機關、學校、商店、醫(yī)院、住宅和其他單位的合理布局，才能方便群眾，有利于城市各行各業(yè)的發(fā)展；農(nóng)田規(guī)劃中，怎樣安排農(nóng)作物的合理布局，才能保持高產(chǎn)穩(wěn)產(chǎn)，發(fā)揮地區(qū)優(yōu)勢；軍事指揮中，怎樣確定最佳作戰(zhàn)方案，才能有效地消滅敵人，保存自己，有利于戰(zhàn)爭的全局；在人類活動的各個領域，諸如此類問題，不勝枚舉。這一類問題的共同特點，就是要在所有可能的方案中，選出最合理的，達到事先規(guī)定的最優(yōu)目標的方案，這個方案可稱為最優(yōu)方案，尋求最優(yōu)方案的方法稱為最優(yōu)化方法，它是一門應用廣泛、實用性強的學科。定義1:尋找最優(yōu)方案的方法稱為最優(yōu)化方法。所謂的最優(yōu)方案就是要在所有可能的方案中，選出最合理的，達到事先規(guī)定的最優(yōu)目標的方案，最優(yōu)化結(jié)合管理，經(jīng)濟等一些領域，而最根本的要以我們的數(shù)學知識為基礎，現(xiàn)已被廣泛地應用于工程，國防，管理和經(jīng)濟等許多重要的領域。1.1模型舉例

當我們要量化一個問題時,首先需要將此問題轉(zhuǎn)化為一個數(shù)學問題,即建立數(shù)學模型。抓住其主要因素,理清其相互的聯(lián)系,然后綜合地運用有關學科的知識和數(shù)學知識才能完成。下面舉幾個例子。例1:配棉問題所謂的配棉問題就是要根據(jù)棉紗的質(zhì)量指標，采用各種價格不同的棉花，按一定的比例配制成紗，使其即達到質(zhì)量指標又使總成本最低。棉紗的質(zhì)量指標一般有棉結(jié)和品質(zhì)指標來決定，這兩項指標都可以用數(shù)量形式來表示，一般來說，棉結(jié)粒越少越好，品質(zhì)指標越大越好。個年紡能力為15000錠的小廠在采用最優(yōu)化方法配棉時，某一產(chǎn)品32D純棉紗的棉花配比質(zhì)量指標及單價如下:原料品名單價（元/t）混合比（%）

棉結(jié)

（粒）

品質(zhì)指標

混棉單價

（元/t）國棉131

8400

25

60

3800

2100國棉229

7500

35

65

3500

2625國棉327

6700

40

80

2500

2680平均合計

100

70

3175

7405有關部門對32D純棉紗規(guī)定的質(zhì)量指標為棉結(jié)不多于70粒，品質(zhì)指標不小于2900。下面我們建立數(shù)學模型:首先:根據(jù)問題需要設置變量:設分別為國棉131,229,327的棉花配比，然后用所設置的變量把所追求的目標及所受的約束，用數(shù)學語言表達出來，即得到該問題的數(shù)學模型。本例的目標是混棉單價最小，用即可表示為:

本例關于32D純棉紗的質(zhì)量指標作為約束條件表出，即有:

又因為的實際意義，它們應為百分數(shù)且和為100%，故又有:

故32D純棉紗配棉問題的數(shù)學模型為:

例2:資金使用問題設有400萬元資金，要求4年內(nèi)使用完，若在一年內(nèi)使用資金萬元，則可得到效益萬元，（效率不能再次使用），當年使用的資金可存入銀行，年利率為10%，試制定出資金的使用計劃，以使4年資金效益之和最大。很明顯，不同的使用方案，所取得的效益之和是不同的，如第一年就把400萬元全部用完，則效益總和為20萬元，若前三年均不使用而存入銀行，則第四年把本息和400=532.4萬元全部用完，則效益總和為萬元，比第一種方案效益大3萬多元。第一年

第二年

第三年

第四年現(xiàn)有資金

400

345.2

265.1

152.8

使用資金

86.2

104.2126.2

152.8效益總和為萬元，使第一種效益總和的兩倍多。注:此例反映出進行定量的優(yōu)化計算作用，故一些工業(yè)人士稱最優(yōu)化方法是不需要增加投入而增加產(chǎn)出的手段。為了將上述的問題轉(zhuǎn)化為最優(yōu)化問題，先建立數(shù)學模型，設變量分別表示第年所使用的資金數(shù)，于是所追求的目標----4年的效益總和最大，即可表示為:

所受的約束為每年的使用金額既不能為負數(shù)又不能超過當年資金擁有數(shù)，即:第一年:第二年:第三年:第四年:故資金使用問題的數(shù)學模型為:例3:汽輪機排序問題環(huán)形排序問題:由于考慮其共振的因素，一百多個葉片的質(zhì)量及幾何形狀各不相同。轉(zhuǎn)動時產(chǎn)生的慣性離心力也就存在差異，如何確定它們的安轉(zhuǎn)位置（排列順序），使諸離心力的合力最小。設有個葉片，第個葉片在轉(zhuǎn)動時產(chǎn)生的慣性離心的數(shù)值（模）為，轉(zhuǎn)子的一周被分為等份，安裝位置用輻角表示，如將第個葉片安裝在位置上，它產(chǎn)生的離心力（向量）可用復數(shù)表示:設葉片的排序方案用排列來表示，即葉片排在第位，那么合力就是:問題就是求排列使為最小。于是，設變量為，其意義為:這樣合力可表示為:而

于是問題的目標可以表示為:，而約束條件為每片葉子只能安裝在一個位置上，即:而且每個位置上只能安裝一片葉子，即:故汽輪機葉片排序問題的數(shù)學模型為:例4:投資的收益與風險市場上有種資產(chǎn)(如股票，債券等)共投資者選擇，某公司有一筆數(shù)額為的資產(chǎn)作為一個時期的投資，公司財務人員對幾種資產(chǎn)進行了評估，估算出在這一時期內(nèi)購買的平均收益率為，并預測購買的風險損失率為,考慮到投資越分散，總的風險越小，公司決定，當用這筆資金購買若干種資產(chǎn)時，總體風險可用所投資的中最大的一個風險來度量。購買要付交易費，費率為，并且當購買不超過給定值時，交易費按購買計算（不買無需付費），另外，假定同期存款利率且既無交易費又無風險。已知時的相關數(shù)據(jù)如下:

（%）

（%）

（%）(元)

28

2.5

1

103

21

1.5

2

198

23

5.5

4.5

52

25

2.6

6.5

40試給該公司設計一種投資組合方案,即用給定的資金,有選擇地購買若干種資產(chǎn)或銀行生息,使凈收益盡可能的大,總風險盡可能的小。設變量分別表示存入銀行和購買的金額，表示不購買，表示購買，目標有兩個:第一個目標:第二個目標:約束是總資金為，以及之間的關系。故投資的收益和風險的數(shù)學模型為:1.2最優(yōu)化問題的模型與分類數(shù)學規(guī)劃定義:在一些等式或不等式約束條件下，求一個目標函數(shù)的極大或極小的優(yōu)化模型稱為數(shù)學規(guī)劃。數(shù)學規(guī)劃分為:約束數(shù)學規(guī)劃和無約束數(shù)學規(guī)劃。約束數(shù)學規(guī)劃一般形式為:(P)其中稱為優(yōu)化向量或決策變量；稱為目標函數(shù)；約束函數(shù)分別稱為不等式約束和等式約束，等式約束和不等式約束統(tǒng)稱為約束條件。令:,我們稱D為（P）的約束集合（約束區(qū)域）或可行域。若，則稱為可行點或可行解，設若對任意的，都有，則稱為優(yōu)化問題（P）的全局最優(yōu)解（極小點或極大點）若存在的一個的領域:當時，有，稱為優(yōu)化問題（P）的局部最優(yōu)解，如時，有，稱為優(yōu)化問題（P）的嚴格局部最優(yōu)解。問題的分類1.無約束優(yōu)化問題當時，問題(P)稱為無約束優(yōu)化問題，無約束優(yōu)化問題是指在空間上尋求使目標函數(shù)達到極小或最小的點（解）。2.約束優(yōu)化問題若指標集I與E中至少有一個非空，則稱(P)為約束優(yōu)化問題，約束優(yōu)化問題是在約束集D上尋求使目標函數(shù)達到極小或最小的點（解）。若,即問題(P)只含有等式約束,此時稱問題(P)為等式約束優(yōu)化問題；若,即問題(P)只含不等式約束,此時稱問題(P)問不等式約束優(yōu)化問題；否則稱問題(P)為混合優(yōu)化問題。如果目標函數(shù)目標函數(shù)和約束函數(shù)都是線性,則稱問題為線性規(guī)劃,線性規(guī)劃常記為LP；如果目標函數(shù)和約束函數(shù)中至少有一個是非線性函數(shù),則稱問題為非線性規(guī)劃,常記為NP；在非線性規(guī)劃中,若約束函數(shù)均是線性函數(shù),則稱問題為線性約束非線性規(guī)劃問題,常記為NLP；目標函數(shù)為二次函數(shù)的線性約束問題稱為二次規(guī)劃問題,常記為QP。若變量限制取整數(shù),則稱為整數(shù)規(guī)劃；若變量限制取0或1,則稱為0—1規(guī)劃；若變量既可取整數(shù),又可取小數(shù),則成為混合整數(shù)規(guī)劃。若所研究的問題只含一個目標,則稱為單目標規(guī)劃；若所研究的問題需要同時考慮多個目標,則成為多目標規(guī)劃。組合優(yōu)化組合優(yōu)化為一個又有有限個元素組成的集合和定義在E的某些子集組成的集合上的實值函數(shù)。若E只有有限個元素,E的所有子集也只有有限個,故組合優(yōu)化問題的解必然存在,而且一定可以用原始的方法----逐個列舉法得到。圖論，網(wǎng)絡流定義：所謂的圖是由一組點和一組點與點之間的連線（邊）組成的總體組成的，圖論所研究的問題主要分為兩類：在給定的圖中具有某種性質(zhì)的點和邊是否存在，若存在，有多少？或至多（少）有多少？如何構(gòu)造具有某些給定性質(zhì)的圖或子圖？網(wǎng)絡：各邊賦有權(quán)值的圖：分為有向網(wǎng)絡和無向網(wǎng)絡。網(wǎng)絡流：路，流動態(tài)規(guī)劃定義:動態(tài)規(guī)劃方法將一個最優(yōu)化問題視為符合最優(yōu)性原理，無后效性的多階段決策過程，并進行求解的方法。注:最優(yōu)決策的任何截斷仍是最優(yōu)的。特點:將一個復雜的問題轉(zhuǎn)化為若干個較為簡單的問題。第二章線性規(guī)劃2.1凸集與凸函數(shù)1.凸集及基本性質(zhì)Def:設集合,若,有，則稱集合為凸集。由定義可直接驗證:設為凸集，，則

①是凸集。②是凸集。③是凸集。④是凸集。

[0,1],利用數(shù)學歸納法可證:設D是凸集，則任意和數(shù)，都有[0,1],其中,2.凸函數(shù)的定義及其基本性質(zhì)①Def:設f:,且D為非空凸集,若都有:(*)若

則稱f(x)是定義在凸集D上的凸函數(shù)。在式(*)中,若嚴格不等式成立時,則稱f(x)是凸集D上的嚴格凸函數(shù)。我們就不強調(diào)凸集D,而稱f(x)是凸函數(shù)或嚴格凸函數(shù)。凸函數(shù)的幾何意義:以n＝1來說明，當f(x)是凸函數(shù)時，其圖形f(x)上任意兩點之間的弧必在連接這兩點的弦的下方。

注:由定義1.5，我們不難用歸納法證明:若f(x)是凸集D上的凸函數(shù)，則任意和數(shù)，，有

定義:設D為凸集，,若D中不存在兩個相異的點y，z及某一實數(shù)使得,則稱x為D的極點。注:線性函數(shù)既是凸函數(shù)也是凹函數(shù)。證明:設

②凸函數(shù)的性質(zhì):i)設f(x)是凸集上的凸函數(shù)，實數(shù)，則kf(x)也是D上的凸函數(shù)。

ii)設是凸集上的凸函數(shù)，實數(shù)則也是D上的凸函數(shù)。iii）設f(x)是凸集上的凸函數(shù),為實數(shù),則水平集是凸集。iv)f(x)是凸集上的凹函數(shù)的充分必要條件是(-f(x))是凸集上的凸函數(shù)。證明:iii)設,于是且因為D是凸集，所以又因為f(x)是D上的凸函數(shù),所以有

即因此，是凸集。3．凸函數(shù)的判別條件

定理:設f(x)定義在凸集上，令則:i)f(x)是凸集D上的凸函數(shù)的充分必要條件為對任意單元函數(shù)在[0,1]上為凸函數(shù)。ii)設，若在[0,1]上為嚴格凸函數(shù)，則f(x)在D上為嚴格凸函數(shù)。證明:i)必要性:設f(x)在凸集D上為凸函數(shù)，

于是

故為[0,1]上的凸函數(shù)。充分性:設為[0,1]上的凸函數(shù)，對任意的則有

故f(x)是D上的凸函數(shù)。定理:(一階條件)設在凸集上可微，則f(x)在D上為凸函數(shù)的充分必要條件是對任意的，都有

證明:必要性:設f(x)是D上的凸函數(shù)，任取及有

即由Taylor公式有

代入上式得

上式兩端取極限，令有充分性:設，則令,有

用分別乘上面兩式再相加得

即

故f(x)在D上為凸函數(shù)。定理:設在凸集上f(x)可微，則f(x)為D上嚴格凸函數(shù)的充要條件為對,有定理:（二階條件）設在開凸集內(nèi)f(x)二階可微，則i)f(x)是D內(nèi)凸函數(shù)的充分必要條件為在D內(nèi)任一點x處，f(x)的海色(Hesse)矩陣G(x)半正定，其中

ii)若在D內(nèi)G(x)正定，則f(x)在D內(nèi)為嚴格凸函數(shù)。2.2線性規(guī)劃解的幾何特征例:下面考察僅含兩個決策變量的線性規(guī)劃:

我們在的坐標平面上畫出其可行域:為此，我們只需畫出K的邊界:

觀察目標函數(shù)，對于任一給定的實數(shù)z，方程表示一直線(稱為f的等值線)，變動z即得一族互相平行的直線，把f的等值線向z減小的方向移動，其和凸多邊形K的最后一個交點即為(2.1)的最優(yōu)解。而為K的一個頂點。結(jié)論:若兩個變量的線性規(guī)劃有最優(yōu)解，則必能在可行域凸多邊形的頂點中找到。由此:具有三個變量及一般具有幾個變量的情形，線性規(guī)劃的可行域K則是以一個平面(或超平面)為邊界的凸的多面體，而且目標函數(shù)等于常數(shù)的幾何圖形亦為平面(或超平面)即f的等值面，讓等值面往函數(shù)減小方向平行移動，其和凸多面體的最后一個交點之一比為凸多面體的頂點。線性規(guī)劃關于解的情形:①可行域是空集②有唯一最優(yōu)解（緊集上的連續(xù)函數(shù)）

③有無窮多最優(yōu)解（當f(x)分段且周期）④目標函數(shù)無界而無最優(yōu)解2.3線性規(guī)劃的標準型線性規(guī)劃的標準型:對目標函數(shù)求極小，決策變量一律為非負變量，約束條件除變量的非負條件外，一律為等式約束。各種形式的線性規(guī)劃模型一律為等式約束。①若目標函數(shù)為則可令f=-z,此問題轉(zhuǎn)化為求②若約束條件含則引進有

稱為松弛變量③若約束條件含,則引進新變量,有

稱為剩余變量。④若約束條件含則引進,于是

⑤若變量的符號不受限制,則可引進兩個新變量,并以代入目標函數(shù)及約束中消去,

而在約束條件中增加例2.1把線性規(guī)劃化為標準型.分析:①令，將maxz改為求minf②用代替，其中③對不等式約束分別引進松弛變量和剩余變量

于是，原問題化為標準型:

2.4線性規(guī)劃的基本定理

觀察線性規(guī)劃(2.1)及其相應的標準型(2.1)的可行域K共有四個頂點，這四個頂點在標準型的形式下所對應的變量值分別

可以發(fā)現(xiàn)這四個頂點的共同點為所對應的變量值中均有兩個坐標為0。作為平面上凸多邊形的頂點必然為兩條邊界直線之交點。若邊界直線為坐標軸，則相應的一個坐標為0。若非坐標軸，則化標準型時所引進的松弛變量或剩余變量就應為0。故在僅有兩個決策變量的線性規(guī)劃標準型的形式下，頂點所對應的變量(包括決策變量，松弛變量，剩余變量)值為0的個數(shù)不少于兩個。線性規(guī)劃的標準型用矩陣表示為:其中不妨設矩陣A的秩r(A)=m.這樣，線性規(guī)劃(2.3)的可行解等價于線性方程組Ax＝B的非負解。因線性方程組Ax＝B有n個變量和r(A)=m，故當Ax＝B的一個解中非零分量所對應A中的列為線性無關時，則非零分量的個數(shù)就不會超過r(A)(=m).也即零分量的個數(shù)不少于n-m.稱A中對應于非零分量的列是線性無關的Ax=B的解為線性規(guī)劃(2.3)的基本解，稱非負的基本解為基本可行解。線性規(guī)劃的基本定理:定理:對于線性規(guī)劃(2.3)①若有可行解，則一定有基本可行解。②若有最優(yōu)解，則一定有最優(yōu)基本可行解。

2.5單純形法由基本定理，求解線性規(guī)劃可采用如下步驟:①求得一個基本可行解②檢查該基本可行解是否為最優(yōu)解③若不是，設法再求一個沒有檢查過的基本可行解。

如此繼續(xù)，直至檢查出的基本可行解為最優(yōu)解為止。按照上面的思路，線性規(guī)劃的求解只需解決:①如何求出第一個基本可行解②如何判斷基本可行解為最優(yōu)解③如何由一個基本可行解過渡到另一個尚未檢查過的基本可行解。Ax=B中，A為m行n列矩陣，即Ax=B為有n個未知數(shù)，m個方程的線性方程組，又設A的秩為m，故由它可解出m個變量(稱為基本變量)，剩余的n－m個變量為自由取值的變量(稱為自由變量)。而所謂基本解即解中取零的變量個數(shù)不少于n－m個。于是，我們可令自由變量取值為零相應得到的解即為基本解。例:

把約束方程寫成表格形式：20－416(2.5)-11305從上述表格可以看出由第二、四列構(gòu)成一個單位子塊，因此將和解出，即和作為基本變量，余下的，作為自由變量，即令自由變量，則，即得一基本解,由此例可看出基本變量的取值即為(2.5)中右列的相應值。因此所得到的基本解是否為基本可行解，只需看當左邊有單位子快時，右列的元素是否均為非負？若是(即非負)，則所得到的基本解即為基本可行解。從n個變量中解出不同基本變量的組數(shù)不會超過組合數(shù)

因此線性規(guī)劃(2.3)的基本可行解(必為基本解)總數(shù)不會超過個。如何判斷所得到的基本可行解是否為最優(yōu)解呢？以(2.4)為例，我們把和(2.4)的約束方程等價的關系式(2.6)帶入目標函數(shù)以消去基本變量，而只剩下自由變量，即其實，這個過程也可以在表格上進行，即在表格(2.5)的基礎上加一底行，把目標函數(shù)的系數(shù)相應的寫在底行中，即20-416-113051-3240右下角的0為目標函數(shù)的變號值，因表格中的豎線可理解為一個等號，于是將目標函數(shù)中的常數(shù)項移至等號的另一邊而變號。為要在目標函數(shù)中消去變量，即把底行的系數(shù)變?yōu)榱?，可采取把底線以上的行倍加至底行的辦法，如第一行乘(-4)，第二行乘3均加至底行即得:20-416-11305(2.8)-100270-9目前的底行即為式(2.7)，無非是把常數(shù)項9移至等號另一邊變成(-9)，9即為相應基本可行解所對應的目標函數(shù)值。這樣，我們把線性規(guī)劃(2.4)化成與之等價的線性規(guī)劃:

由于(2.9)的目標函數(shù)中僅含，而要求非負，所以也只需判斷時是否在非負的范圍內(nèi)使目標函數(shù)取最小值，而這等價于(2.9)的目標函數(shù)中，的系數(shù)均為非負，如本例在表格(2.8)的形式下，由于底行中存在負系數(shù)(-10)，所以對應的基本可行解就不是最優(yōu)解，也即若取正值，可使目標函數(shù)值減小?？偨Y(jié):當把線性規(guī)劃(2.3)寫成表格形式AB0表格的四個部分分別稱為:中心部位右列底線底行右下端

求解線性規(guī)劃(2.3)，既可以用如下的計算:①底線以上的部分進行行交換②底線以上的某一行乘以非零常數(shù)③底線以上的行進行倍加運算④把地線以上行乘常數(shù)后加至底行(包括右下端)上當表格具有如下特點:①中心部位具有單位子塊②右列元素非負③底行相應于單位子塊的位置的元素為0④底行其它元素非負則從表格中立即可以讀出線性規(guī)劃(2.3)的最優(yōu)解和最優(yōu)值。讀法為:單位子塊中1所對應的變量去相應右列的值，不在單位子塊位置的變量取值為0，而右下端元素變號即為最優(yōu)值。

例：10-21/230111/28007521從形式上看，當表已經(jīng)具備了①②③三個特點，而第④個特點尚不具備時如何進行？單純形法的步驟：前提：設當前的表格已具備第①②③三個特點。設一般為：

具體的如表(2.8)20-416-11305(2.8)-100270-9①從底行負元素中任意選一個，設為(實質(zhì)上即為選該列所對應的變量取正值，因它取正值能使目標函數(shù)值下降，而變量要取正值必須作為基本變量，即必須將該列調(diào)至單位子塊中)，這一步稱為選擇進基變量。②從所選元素對應列(列)底線以上的正元素中按下列規(guī)則選定一元素:

=(2.11)我們即要使作為基本變量，則必須在原來的基本變量中選定一個退出改作自由變量，至于從正元素中選，以及若不止一個正元素時，采用(2.11)式所示的原則選，這一步稱為離基變量。10-21/230111/28007521③利用初等行變換及倍加至底行的運算把變?yōu)?，該列的其它元素(包括底行的相應元素)變?yōu)?，這一步稱為旋轉(zhuǎn)運算。④若底行元素均非負，則終止，否則回①。注:當最優(yōu)解存在和基變量的值都大于零時，經(jīng)有限步后一定能得到最優(yōu)解。定理2.2:在已知一個基本可行解的前提下，使用單純行法求解線性規(guī)劃時，若每次迭代得出的基本可行解的基變量均大于零(稱為非退化的)，則算法必有限步終止。例2.2:用單純形法求解:

解:先化為標準型:

列成表格:-11100212010103100115-2-30000可見此表已具備①②③三個特點，可采用單純形法。min{2/1,10/2,15/1}=2,選第一行第二列元素1，迭代依次得:-1110023^0-210640-10113-5*03006

-1/31100210-21064/30-101135/303006011/31/30410-2/31/302005/3^-4/31500-1/3*5/3016

0103/5-1/53100-1/52/54001-4/53/530007/51/517這時第④特點已具備，故終止。從表中讀出最優(yōu)解:

例:

解:20-416-11*3051-3*2402*0-416-11305-2*01141510-21/23-11305-2011415

10-21/230111/28007521

2.6大M法當初始基本可行解不知道時,即①②兩個特點不能兼得時,先利用容許的運算使右列為非負,然后在中心部位人工地添加一個單位子塊。

例:列成表格:32-36-12-1-4-3120

32-361-214-3120

32-31061-21014-3120上述第三張表格人工地增加了兩個變量(稱人工變量)，即把原約束條件修改為:2.13)和(2.12)的約束方程組并不同解，但(2.12)的解和(2.13)中的解是相對應的。因此只要找到以(2.13)為約束條件，且人工變量和均為自由變量的取值為零。現(xiàn)介紹的這個方法就是通過修改(2.12)的目標函數(shù)來實現(xiàn)這個目的。具體修改為:

其中，M為足夠大的正數(shù)，然后以(2.13)為約束條件，求(2.14)的最小值，這樣，只要不為0，則一定為正數(shù)，于是目標就會增加它們和的M倍，由于M足夠大，所以只要原問題有基本可行解，就不會讓，取正值而達到最小，于是本例的單純形表應改為:3*2-31061-21014-3*12MM0再通過運算使第③個特點具備，然后再嚴格地按照單純形法步驟執(zhí)行:3*2-31061-21014-3-4M*12+2M0010M

由于M為足夠大正數(shù)，所以-3-4M應視為負數(shù)，故選它，于是有12/3-11/3020-8/32-1/31203+8M/3-1-2M*1+4M/306-2M這時人工變量已經(jīng)成為自由變量，所以可立即將其略去，即可將第四列刪去:1-2/301/230-4/311/2105/301/2+M7這時表已具有四個特點且人工變量亦成為自由變量，故

如果表中已具備四個特點，而人工變量并沒有全都成為自由變量，則此題無最優(yōu)解。

第三章無約束非線性規(guī)劃本章討論如下的優(yōu)化模型:

（3.1）其中是的實值連續(xù)函數(shù),通常假定具有二階連續(xù)偏導數(shù).3.1最優(yōu)性條件由于可以等價地化為,所以下面僅討論極小化問題.無約束極小的最優(yōu)性條件現(xiàn)有多元函數(shù),若點存在一鄰域,使得對于均有:則稱為的局部極小點.

若為的局部極小點,顯然可以得出以下結(jié)論:為一元函數(shù)的局部極小點.由一元函數(shù)極值的必要條件有:(3.2)

因此有以下定理成立:

定理3.1(局部極小點的一階必要條件)設函數(shù)在點處可微,且為局部極小點,則必有梯度.

在一元函數(shù)的討論中,一已知滿足一階必要條件的(稱為駐點)未必是局部極小點,有可能是極大點或者鞍點.

利用局部極小點的一階必要條件求函數(shù)極值的問題往往化成求解

即求,使?jié)M足:

(3.3)

的問題,這是含有個未知量,個方程的方程組,并且一般是非線性的.對于一些特殊的情形,如當目標函數(shù)是二次函數(shù),因而此時方程組(3.3)是線性方程組時,有時可以解出,一般來說,非線性方程組的求解與無約束極值一樣也是一個困難的問題,甚至前者比后者更困難,一般是很難用解析方法求解的.這時必須用數(shù)值計算方法逐步求出非線性方程組的解.但是,與其用數(shù)值計算方法求解(3.3),倒不如用數(shù)值計算方法直接求極值.

迭代法數(shù)值解法中最為常見的是用迭代法,其基本思想是:

在給出的極小點位置的一個初始估計(稱為初始點)后,計算出一系列的迭代點,希望點列的極限就是的一個極小點.怎樣產(chǎn)生這樣的點列呢?也就是說,當有了迭代點后,怎樣求得新的迭代點呢?我們知道和之差是一個向量,而一個向量總是有其方向和長度所能確定.即總可以寫成

或

其中為一個向量,為一個實數(shù)(稱為常數(shù)).當和確定之后，由就可以唯一地確定，于是依次下去，從給定的便可以求出，由確定等等，從而也就確定了一個點列，如果這個點列逼近我們要求的極小點，我們便稱序列為極小化序列.所以對于每個迭代點，如果能設法給出和，則算法也就確定了.各種迭代法的區(qū)別就在于得出方向與步長的方式不同.特別是方向（我們稱為搜索方向）的產(chǎn)生在方法中起著關鍵的作用.我們要求:一.所構(gòu)造出來的極小化序列對應的函數(shù)值序列應該是逐次減小的,即

這種性質(zhì)的算法稱為下降算法.二.算法應該具有收斂性,即所產(chǎn)生的極小化序列具有這樣的性質(zhì):或者序列中的某一點,它本身就是極小點;或者序列有一個極限點,它是函數(shù)的極小點.但是這個要求卻是不容易做到的,例如:考慮函數(shù),顯然就是的極小點,即,我們按照下述的方式構(gòu)造極小化序列:已知后,令容易證明,這個算法是一個下降算法,即

若取初始點,則所有,因此序列不可能收斂到極小點(事實上,收斂到1),但若取初始點,則極小化序列收斂到極小點0.

注:當目標函數(shù)具有不止一個極小點時,則求得的往往是一個局部極小點,這時可以改變初始點的取值,更新計算,如果求得的仍然是同一個極小點,我們就可以認為它是總體極小點了.

綜上所述,最優(yōu)化算法中的迭代方法大致由下述步驟組成:1選擇初始點,要求越接近最優(yōu)解越好,2尋找可行下降方向,3選取步長,4迭代:,5終止條件:

須方能推出

(*)

我們稱為在處的下降方向.

設可行域為,若:

且滿足()式,則稱為在處的可行下降方向.

由出發(fā)沿方向求步長的過程叫一維搜索或線性搜索.

判斷算法好壞:一看是否收斂,二看收斂速度增:

定義:設序列收斂于,而且

若,則稱為線性收斂的,為收斂比;若,則稱為超線性收斂.

定義:設序列收斂于,若對于某個實數(shù)有

,

則稱序列為階收斂的.

3.2一維搜索上節(jié)提到,在大多數(shù)無約束極值的算法中,為了確定最優(yōu)解,一般用解析的方法是很難得到的,即精確解通常是計算不出來的,故我們常采用的是數(shù)值的方法來得到其近似解,上節(jié)我們提到,數(shù)值解法最常用的一種方法是迭代法.

為了確定極小化點列,要沿逐次確定的系列射線求極小點,即所謂的一維搜索.

一維搜索可歸結(jié)為單變量函數(shù)求極小的問題,設目標函數(shù)為,過點沿方向的直線可用點集表示為:

求在直線L上的極小點轉(zhuǎn)化為求一元函數(shù)

的極小點.如果的極小點為,通常稱為沿方向的步長因子或簡稱步長.函數(shù)在直線上的極小點就是

一維搜索的方法一般有以下幾類:1.數(shù)學分析中所講的方法，即解方程，此方法稱為精確線性搜索.2.試探法:按照某種方式試探點,通過一系列試探點的比較確定極小點.3.函數(shù)逼近法:用比較簡單的曲線近似代替原來的曲線,用近似曲線的極小點來估計原來的極小點.下面我們將分別具體介紹幾種方法:一.平分法根據(jù)以前我們所學習的知識,我們知道,在的極小點處有,并且當時,函數(shù)是遞減的,即;,而當時,函數(shù)遞增,即.注:因為為極小點,若:

此時為極大點.

我們找到了一個區(qū)間,具有性質(zhì)則在間必然有的極小點,且.為了找到,我們?nèi)?1.若,則在中有極小點,

2.若,則在中有極小點.y=f(x)00xy若情形1滿足時,此時以作為新的區(qū)間;若情形2滿足時,此時以作為新的區(qū)間.繼續(xù)上述過程,逐步將區(qū)間換小,當區(qū)間充分小時,或者當充分小時,即可將區(qū)間中點取做極小點的近似,此時有:0xy0xy注:也可以用以下的收斂準則:1.成立,

2.成立.但是我們?nèi)绾蝸泶_定初始區(qū)間呢?一般可以采取下述的方式:1.首先取一初始點,若,則在的右方取一點.其中為事先給定的一個步長;否則,在其左方取.2.若,則令.3.若,則在其右方取(或者將擴大一倍,再取4.若,則令.5.若轉(zhuǎn)步2.

如此繼續(xù)下去,對于的情況,做類似的情況討論.這一技巧不僅對平分法有用,對后面的方法也有用,例如,我們可以用類似的方法,找出,滿足,并且,便可一得到含極小點的區(qū)間

此時需要用數(shù)值的比較而不需要計算.

二.0.618法(黃金分割法)

該方法的使用范圍:單峰函數(shù),即在所討論的區(qū)間上函數(shù)只有一個極小點在極小點右邊,函數(shù)單調(diào)上升,如:對于單峰函數(shù),只需要選擇兩個試探點且.就可將極小點的區(qū)間縮短,事實上必有:(1)若,則

(2)若,則.0xy0xy0xy0xy0xy根據(jù)單峰函數(shù)的此性質(zhì),即可以不斷地縮小包含極小點的區(qū)間(可稱為搜索區(qū)間).若進行次迭代k以后,又有,此時取兩個試探點,,并規(guī)定<,計算函數(shù)值.1.若,即滿足(1)的情況,則令;2.若,即滿足(2)的情況,則令.如此繼續(xù)下去.但是我們怎么合理地選取,呢?1.因通過比較后,有可能去掉搜索中部分,也有可能去掉部分.因此,,取在中對稱的位置是合理的.2.將縮短為后,,必有一個仍然屬于.根據(jù)以上兩點有:

(3.4)(3.5)由前:1.若,有

上兩式推出此時有

2.若,有

上兩式推出(3.6)

注:

i)設在第k次迭代中得出:

于是有=,則由(3.7)有:

令,則為留在中已經(jīng)算出過函數(shù)值的試探點(令).

故有,算出

.

設在第k次迭代中得出:

于是有=,則有:

令,則根據(jù)前系數(shù)相等有:

所以有,

0.618法取試探點的規(guī)則為

計算步驟:1.給定一初始區(qū)間及精度要求,計算試探點:極其函數(shù)值,令;2.若,停止.中的任意點均可以作為所求極小點的近似,否則當時,轉(zhuǎn)步3,當時,轉(zhuǎn)步4;

3.置,,計算

及,轉(zhuǎn)步5;4.置,,計算及,轉(zhuǎn)步5;5.令,轉(zhuǎn)步2.參見46頁例3.1.注:在使用0.618法之前,務必確定目標函數(shù)為單峰函數(shù).三.牛頓法(函數(shù)逼近):基本思想:在迭代點附近用二階泰勒展開式近似目標,進而求極小點的估計值.

優(yōu)化模型:

（3.12）首先我們令

再令得到（3.13）用迭代公式（3.13）可得到一個點列,在一定條件下,這個

點列收斂于（3.12）的最優(yōu)解,且具有二階收斂速度.xy

3.3最速下降法與共軛梯度法在本章開始介紹了關于無約束極小問題普遍使用下降迭代算法,每一類算法中包含兩個關鍵步驟,得到一個迭代點后,如何選擇搜索方向以及在確定搜索方向上用什么方法進行一維搜索?而有關一維搜索的方法在上節(jié)已經(jīng)作了詳細的介紹,本章與下一章就介紹幾種常用的確定搜索方向的方法.一最速下降法考慮到函數(shù)在點處沿方向的方向?qū)?shù),其意義為:函數(shù)在點處沿方向的變化率.求解問題:

其中最速下降法的計算步驟

1選定初始點和給定精度,令

2若,則停止,;

否則令=－▽.3在點處沿方向作線性搜索,得到