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

參考書

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

ChapterOne

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

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

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

最短路問題管道鋪設(shè)路線費(fèi)用最少貨物運(yùn)輸時(shí)間最短（費(fèi)用最少）通訊路線最可靠2．

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

.市場風(fēng)險(xiǎn)投資決策

.技術(shù)引進(jìn)決策

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

分配問題

.分房問題

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

網(wǎng)絡(luò)計(jì)劃技術(shù)

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

.交通流量最大

.物流運(yùn)輸費(fèi)用最少7．

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

.歐拉圖

.機(jī)關(guān)設(shè)計(jì)問題

.汽車共用問題

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

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

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

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

，j=1,2,…n。現(xiàn)計(jì)劃建立m個(gè)貨棧，第i個(gè)貨棧的容量為ci

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

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

Wij

：第i個(gè)貨棧供給第j個(gè)市場的貨物量

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

稱為無約束問題,否則稱為約束最優(yōu)化問題..f,si,hj都為線性函數(shù)稱為線性規(guī)劃問題,..否則為非線性規(guī)劃問題f:RnR1目標(biāo)函數(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為一個(gè)可行解(容許解、容許點(diǎn))可行域

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

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

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

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

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

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

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

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

i=2:n29從而：繼續(xù)可求得：302.3多元函數(shù)的Taylor展開式設(shè)f:RnR1有連續(xù)二階偏導(dǎo)數(shù)，則31dRn,d≠0,這個(gè)向量也可被看作一個(gè)方向11.d(代表點(diǎn)也代表方向)2.x.x+2d這個(gè)向量可看作是x沿著方向d走了兩個(gè)單位！這時(shí)d，2d，1/2d,…,均表示的是同一個(gè)方向,只是它們的長度不同。比如n=2時(shí)，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,當(dāng)t(0,)時(shí)：·xd·x+d33定理

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

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

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

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

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

H+={x∈

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

設(shè)x,y為超球中任意兩點(diǎn),0≤a≤1,則有

||ax+(1-a)y||≤a||x||+(1-a)||y||≤ar+(1-a)r=r,即點(diǎn)ax+(1-a)y屬于超球,所以超球?yàn)橥辜?例

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

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

C={x|x∈

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

bC={y|y=b

x,x

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

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

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

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

C1∩C2表示兩個(gè)軸的所有點(diǎn),它不是凸集;C1+C2=R2是凸集39極點(diǎn)設(shè)C為凸集,x∈

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

x=ay+(1-a)z

則稱x為C的極點(diǎn).凸集凸集40例

D={x∈Rn|||x||≤a}(a>0),則||x||=a上的點(diǎn)均為極點(diǎn)證:設(shè)||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不等式要取等號(hào),必須

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

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

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

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

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