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

參考書

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

ChapterOne

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

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

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

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

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

.市場風險投資決策

.技術引進決策

.產品推銷策略4．

分配問題

.分房問題

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

網絡計劃技術

.有效組織實施工程86.網絡流問題

.交通流量最大

.物流運輸費用最少7．

網絡圖的其他一些應用問題

.歐拉圖

.機關設計問題

.汽車共用問題

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

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

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

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

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

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

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

Wij

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

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

稱為無約束問題,否則稱為約束最優(yōu)化問題..f,si,hj都為線性函數稱為線性規(guī)劃問題,..否則為非線性規(guī)劃問題f:RnR1目標函數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)解的數值方法，所說的最優(yōu)解一般均指局部最優(yōu)解。21例1

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

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

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

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

i=2:n29從而：繼續(xù)可求得：302.3多元函數的Taylor展開式設f:RnR1有連續(xù)二階偏導數，則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定理

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

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

則稱C是一個凸集。直觀上看，凸集的內部必沒有“洞”，邊界也不會向內凹，比如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凸集的性質(i)有限個(可以改成無限)凸集的交集為凸集.

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

C={x|x∈

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

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

若x*是無約束問題的一個局部極小點，在x*的鄰域內f的一階偏導數存在，則▽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ù)偏導數，在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*)因充分條件涉及二階導數的求解與矩陣運算，許多算法往往只要求滿足一階必要條件即可，同時在算法中加上其它限制條件，以避免求得極大點等情況無約束問題的二階充分條件Proof49無約束問題的數值方法基本型求解最優(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)解(此時終止算法