運籌與優(yōu)化1-01概述

參考書

.陳寶林《最優(yōu)化理論與算法》.解可新等《最優(yōu)化方法》.薛嘉慶《最優(yōu)化原理與方法》.盛昭瀚等《最優(yōu)化方法基本教程》.部分英文教材1

ChapterOne

概述及預備知識2最優(yōu)化又稱數(shù)學規(guī)劃(Mathematical

Programming),大約在1947年誕生,是運籌學(OperationResearch)的一個分支.概括地說，最優(yōu)化就是從所有可能的方案中選取最合理的一種以達到最優(yōu)目標的學科。達取最優(yōu)化目標的方案就是最優(yōu)方案，搜尋最優(yōu)方案的方法就是最優(yōu)化方法，這種方法的數(shù)學理論就是最優(yōu)化理論。1.1最優(yōu)化定義（optimization）SectionOne最優(yōu)化問題的數(shù)學模型與基本概念31.2優(yōu)化分類優(yōu)化理論與算法線性規(guī)劃非線性規(guī)劃動態(tài)規(guī)劃整數(shù)規(guī)劃幾何規(guī)劃隨機規(guī)劃網(wǎng)絡規(guī)劃拓撲規(guī)劃……組合規(guī)劃4按照問題涉及到的變量是否是離散變量進行分類：具有連續(xù)變量的優(yōu)化問題（我們本學科的講授內(nèi)容，也即我們通常所講的優(yōu)化）具有離散變量的優(yōu)化問題（組合最優(yōu)化問題）

這兩類問題具有不同的特點，所以解決這兩類問題的方法也是完全不同的。由于現(xiàn)實世界的絕大多數(shù)問題都是處于離散狀態(tài)，所以目前組合優(yōu)化問題作為側(cè)重于應用的運籌技術之一，得到日益廣泛的應用。5附組合優(yōu)化問題技術及其應用簡介組合最優(yōu)化對于具有離散變量的問題，從有限個解中尋找最優(yōu)解的問題就是組合最優(yōu)化問題。簡單應用：古老的婚配問題一個遙遠的地方，一個酋長的三人女兒A，B，C準備嫁給三個求婚者D，E，F(xiàn)。按當?shù)亓曀?，求婚者必須向酋長交納一定數(shù)量的牛作為財禮。設已知求婚者愿意對酋長的每個女兒提供的牛的數(shù)量。假設酋長只以獲得盡可能多的牛為目的，試找出一種方案。6組合最優(yōu)化的應用舉例1．

最短路問題管道鋪設路線費用最少貨物運輸時間最短（費用最少）通訊路線最可靠2．

最小支撐樹問題電話通訊網(wǎng)的架設地區(qū)交通網(wǎng)絡的建設73.決策樹模型

.市場風險投資決策

.技術引進決策

.產(chǎn)品推銷策略4．

分配問題

.分房問題

.有限資源的最佳配置5．

網(wǎng)絡計劃技術

.有效組織實施工程86.網(wǎng)絡流問題

.交通流量最大

.物流運輸費用最少7．

網(wǎng)絡圖的其他一些應用問題

.歐拉圖

.機關設計問題

.汽車共用問題

.工廠選址問題9組合最優(yōu)化的應用成功應用領域舉例平板的最優(yōu)激光鉛化油田的最優(yōu)勘探血液銀行的管理考古發(fā)掘物的順序排列基因密碼計算機切割的最優(yōu)安排消防隊和災情點的調(diào)試計劃垃圾清除或街道清洗的調(diào)度計劃按訂貨以最小角邊料切割紙或鋼材等公交汽車線路的最優(yōu)安排或鏈接10最優(yōu)化理論與方法目前已滲透到生產(chǎn)、管理、商業(yè)、軍事和決策等各個方面。1.3優(yōu)化應用案例案例一生產(chǎn)活動安排問題案例二工廠（市場）選址問題11問題描述

設有m種資源B1,…,Bm,它們的可使用量分別為b1,…,bm,用于生產(chǎn)n種產(chǎn)品A1,…,An,設生產(chǎn)1個產(chǎn)品Aj需消耗資源Bi的單位數(shù)為aij，而產(chǎn)品Aj每單位的利潤為cj，問如何安排生產(chǎn)活動可使總利潤最大？案例一生產(chǎn)活動安排問題12題設:

為了使總利潤最大，要生產(chǎn)Aj的量為xj：c1c2c3……cnA1A2A3……Anx1x2x3……xn總利潤：生產(chǎn)條件約束：資源數(shù)量的限制，即用于生產(chǎn)的資源不能超過每種資源的總量…b1b2…bmB1B2…Bma11a21…am1a12a22…am2a13a23…am3a1na2n…amn.....A1A2A3……An13數(shù)學模型

s.t.¨¨max“s.t.”即subjectto,表示變量的約束條件“Max”即maximum,表示最大值，同樣，可用“min”表示極小值minimum14案例二工廠（市場）選址問題問題描述設有n個市場，第j個市場的位置為(aj,bj)，對某種貨物的需求量為qj

，j=1,2,…n?，F(xiàn)計劃建立m個貨棧，第i個貨棧的容量為ci

，i=1,2,…m。試確定貨棧的位置，使各貨棧到各市場的運輸量與路程的乘積最小。15引入數(shù)學符號：(xi,yi)

：第i個貨棧的位置，i=1,2,…m

Wij

：第i個貨棧供給第j個市場的貨物量

i=1,2,…m，j=1,2,…ndij：第i個貨棧到第j個市場的距離運輸量與路程的乘積和162。每個市場從各貨棧得到的貨物量等于它的需求量3。貨物的運輸量不能為負問題的條件約束：1。每個貨棧向各市場的貨物供應量不能超過它的容量17確立數(shù)學模型18最優(yōu)化問題的一般形式優(yōu)化問題就是求目標函數(shù)在約束條件下的極小點...m=l=0

稱為無約束問題,否則稱為約束最優(yōu)化問題..f,si,hj都為線性函數(shù)稱為線性規(guī)劃問題,..否則為非線性規(guī)劃問題f:RnR1目標函數(shù)x:n維的列向量Si

:RnR1等式約束Hj

:RnR1不等式約束19最優(yōu)化問題的向量形式minf(x)s.t.s(x)0

h(x)=0其中201.4基本概念可行解

若xRn滿足所有約束條件:即

xD={x|si(x)0,hj(x)=0,i=1:m,j=1:l},

則稱x為一個可行解(容許解、容許點)可行域

將可行解的集合D稱為可行域（容許集）全局最優(yōu)解

若有x*D,使對xD,有f(x)f(x*)局部最優(yōu)解

若有x*D，存在一個鄰域N(x*,)＝{x|||x*-x||<},使得：對xDN(x*,)，均有f(x)f(x*)

一般情況下我們往往只能求出問題的一個局部最優(yōu)解。課程所介紹的均是求解問題的一個局部最優(yōu)解的數(shù)值方法，所說的最優(yōu)解一般均指局部最優(yōu)解。21例1

min4x1+x2s.t.2x1+x2-402x1-x2+40x1,x20解作出4個約束函數(shù)圍起的可行域。(如圖示)1.5簡單的二維優(yōu)化問題的圖解法4x1+x2=c表示一族平行線，每條線上的點對應的目標函數(shù)值相等，此直線稱為目標函數(shù)值為c的等值線。22但因x受可行域約束！，不能無限往左下移動，因此當?shù)戎稻€往左下移動，直到移動至可行域的邊界時停止，此時的交點即為所求最優(yōu)解，本題即為點（0，4)T注意到等值線越往左下移動，對應的目標函數(shù)值越?。坏戎稻€越往右上移動，對應的目標函數(shù)值越大。23x1x2f·最優(yōu)解為（2，1)T到直線的垂足！由幾何知識，易求得為(3,2)T例2minf(x)=(x1-2)2+(x2-1)2

s.t.x1+x2-5=0目標函數(shù)f(x)在三維空間中代表一個曲面S對于三維及以上的問題因不好畫圖,圖解法失效242.1向量模（范數(shù)）SectionTwo

優(yōu)化學科的預備知識設x為n維列向量252.2函數(shù)的梯度、海色陣若f存在一階偏導數(shù)，則稱向量為f(x)在x處的梯度(一階導數(shù))若f存在二階連續(xù)偏導數(shù)，則稱矩陣為f(x)在x處的Hesse陣(對稱陣)f：RnR126例27特別地，對線性函數(shù)

f(x)=aTx+b=a1x1+a2x2+…+anxn28特別地，對二次函數(shù)將f(x)展開，含x1的項為：從而一般地

i=2:n29從而：繼續(xù)可求得：302.3多元函數(shù)的Taylor展開式設f:RnR1有連續(xù)二階偏導數(shù)，則31dRn,d≠0,這個向量也可被看作一個方向11.d(代表點也代表方向)2.x.x+2d這個向量可看作是x沿著方向d走了兩個單位！這時d，2d，1/2d,…,均表示的是同一個方向,只是它們的長度不同。比如n=2時，2.4方向向量32下降方向圖示f(x0+td)>f(x0),則稱d為f在x0處的上升方向f(x0+td)<f(x0),則稱d為f在x0處的下降方向f:RnR1,x0,dRn,d≠0,若存在>0,當t(0,)時：·xd·x+d33定理

梯度方向是函數(shù)值變化率最大的方向·由Taylor展開式，對任意方向d，有易見：當二者夾角為180度或0度(即P與梯度方向相反或相同)時，函數(shù)值變化(下降或上升)的最多分析梯度方向是函數(shù)值的最速上升方向，負梯度方向是函數(shù)值的最速下降方向。34同時可見f的值下降了，此時方向d是f在x點處的一個下降方向；若d與梯度夾角大于90度,即判斷一個方向是一點處的下降方向的方法反之，若d與梯度夾角大于90度即f的值上升了，方向d是f在x點處的一個上升方向。35SectionThree

凸分析初步凸集若對x,yC,[0,1],均有x+(1-)yC

則稱C是一個凸集。直觀上看，凸集的內(nèi)部必沒有“洞”，邊界也不會向內(nèi)凹，比如3.1凸集

36常見的凸集空集--(補充定義),整個歐式空間Rn,超平面--

H={x∈Rn|a1x1+a2x2+…anxn=b}半空間--

H+={x∈

Rn|a1x1+a2x2+…anxn≤b}證明

設x,y為超球中任意兩點,0≤a≤1,則有

||ax+(1-a)y||≤a||x||+(1-a)||y||≤ar+(1-a)r=r,即點ax+(1-a)y屬于超球,所以超球為凸集.例

超球||x||≤r為凸集37凸集的性質(zhì)(i)有限個(可以改成無限)凸集的交集為凸集.

即:若Cj(i∈J)是凸集,則它們的交集

C={x|x∈

Dj,i∈J}是凸集.(ii)設C是凸集,b是一實數(shù),則下面集合是凸集

bC={y|y=b

x,x

∈C}.(iii)設C1,C2是凸集,則C1與C2的和集

C1+C2={y|y=x+z,x∈C1,z∈C2}是凸集.

和集與并集有很大的區(qū)別,凸集的并集未必是凸集,而凸集的和集是凸集.38例

C1={(x,0)T|x∈R}表示x軸上的點,C2={(0,y)T|y∈R},表示y軸上的點.則

C1∩C2表示兩個軸的所有點,它不是凸集;C1+C2=R2是凸集39極點設C為凸集,x∈

C.若D中不存在兩個相異點y,z及某一實數(shù)a∈(0,1)使得

x=ay+(1-a)z

則稱x為C的極點.凸集凸集40例

D={x∈Rn|||x||≤a}(a>0),則||x||=a上的點均為極點證:設||x||=a,

若存在y,z∈D及a(0,1),使得x=ay+(1-a)z.

則a2=||x||2=<ay+(1-a)z,ay+(1-a)z>≤a2||y||2+(1-a)2||z||2

+2a(1-a)||y||.||z||≤a2不等式要取等號,必須

||y||=||z||=a,且<y,z>=||y||||z||,

容易證明y=z=x,根據(jù)定義可知,x為極點.41xyx+(1-)yf(x+(1-)y)··f(x)+(1-)f(y)定義在凸集C上的函數(shù)f：CRnR1，若對任意x、yC,[0,1],均有若當x≠y時上式總嚴格成立，則稱f為C上的嚴格凸函數(shù)。嚴格凸函數(shù)顯然是凸函數(shù)。3.2凸函數(shù)將上述定義中的不等式反向,可以得到凹函數(shù)和嚴格凹函數(shù)的定義.凸函數(shù)42設f:CRnR1,存在一階偏導,C為凸集,則Proof凸函數(shù)的判定定理143設f:CRnR1有二階連續(xù)偏導,C為凸集,則Proof凸函數(shù)的判定244(i)設f(x)是凸集C上的凸函數(shù),實數(shù)k0,則kf(x)也是C上的凸函數(shù).(ii)設f1(x),f2(x)是凸集C上的凸函數(shù),實數(shù)m,n≠0,則mf1(x)+nf2(x)也是C上的凸函數(shù).(iii)設f(x)是凸集C上的凸函數(shù),b為實數(shù),則水平集S(f,b)={x|x∈C,f(x)≤b}為凸集.凸函數(shù)的性質(zhì) 45凸函數(shù)的性質(zhì) (iv)設f(x)是定義在凸集C上的凸函數(shù)，則f的局部極小點也是其在C上的全局極小點?！·y·x*+(y-x*)即f(x*)≤f(y)于是f(x*)≤f(x*+(y-x*))≤(1-)f(x*)+f(y)可選擇一個(0，1)使得x*+(y-x*)C,且||x*+(y-x*)-x*||≤(即在x*的鄰域內(nèi))任意yC，要證f(x*)≤f(y)當||x-x*||≤時，f(x)≥f(x*),設x*是f的局部極小點，則由定義，存在>0，Proof46嚴格凸函數(shù)的性質(zhì)(v)設f(x)是定義在凸集C上的嚴格凸函數(shù)，則f的局部極小點也是其在C上的唯一全局極小點。即有x’C，x’≠x，但f(x’)=f(x*)反設x*不是唯一的，由前知x*是f的全局極小點Proof47SectionFour無約束最優(yōu)化的基本原理無約束問題的一階必要條件

若x*是無約束問題的一個局部極小點，在x*的鄰域內(nèi)f的一階偏導數(shù)存在，則▽f(x*)=0若▽f(x*)≠0,則取d=－▽f(x*)▽f(x*)Td=－▽f(x*)T▽f(x*)<0,即在x*處有下降方向d，這與x*是局部極小點矛盾。滿足▽f(x)=0的點x稱為駐點或平穩(wěn)點,但▽f(x*)=0的點未必就是f的極小點。Proof48設f有二階連續(xù)偏導數(shù)，在x*處▽f(x*)=0,▽2f(x*)正定,則x*是f的嚴格局部極小點。任意xN(x*,),由Taylor展開式

f(x)≈f(x*)+▽f(x*)T(x-x*)+1/2dT▽2f(x*)d,由條件知f(x)>f(x*)因充分條件涉及二階導數(shù)的求解與矩陣運算，許多算法往往只要求滿足一階必要條件即可，同時在算法中加上其它限制條件，以避免求得極大點等情況無約束問題的二階充分條件Proof49無約束問題的數(shù)值方法基本型求解最優(yōu)化問題的基本方法是迭代方法：為了排除局部極大點的可能性，在迭代算法中通?？傄骹(x(k))在迭代后減小，即f(x(k+1))<f(x(k))(2)按照某種規(guī)則生成x(1),…,由x(k)按照規(guī)則生成x(k+1),…,從而得到一個點的序列{x(k)}

(3)使得某個x(k)恰好是問題的最優(yōu)解(此時終止算法