運籌學與最優(yōu)化方法課件

運籌學

與最優(yōu)化方法吳祈宗等編制運籌學

與最優(yōu)化方法吳祈宗等編制主要內(nèi)容第一章運籌學思想與運籌學建模第二章基本概念和理論基礎第三章線性規(guī)劃第四章最優(yōu)化搜索算法的結構與一維搜索第五章無約束最優(yōu)化方法第六章約束最優(yōu)化方法第七章目標規(guī)劃第八章整數(shù)規(guī)劃第九章層次分析法第十章智能優(yōu)化計算簡介主要內(nèi)容第一章運籌學思想與運籌學建模第一章

運籌學思想與運籌學建模第一章運籌學思想第一章運籌學思想與運籌學建模運籌學—簡稱OR（美）Operation`sResearch（英）OperationalResearch“運籌于帷幄之中，決勝于千里之外”三個來源：軍事、管理、經(jīng)濟三個組成部分：運用分析理論、競爭理論、隨機服務理論第一章運籌學思想與運籌學建模運籌學—簡稱OR一、什么是運籌學為決策機構在對其控制下的業(yè)務活動進行決策時，提供一門量化為基礎的科學方法?；蚴且婚T應用科學，它廣泛應用現(xiàn)有的科學技術知識和數(shù)學方法，解決實際中提出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)。運籌學是一種給出問題壞的答案的藝術，否則的話，問題的結果會更壞。一、什么是運籌學為決策機構在對其控制下的業(yè)務活動進行決策時，二、運籌學的應用原則合伙原則：應善于同各有關人員合作催化原則：善于引導人們改變一些常規(guī)看法互相滲透原則：多部門彼此滲透地考慮獨立原則：不應受某些特殊情況所左右寬容原則：思路寬、方法多，不局限在某一特定方法上平衡原則：考慮各種矛盾的平衡、關系的平衡二、運籌學的應用原則合伙原則：應善于同各有關人員合作三、運籌學解決問題的工作步驟1）提出問題：目標、約束、決策變量、參數(shù)2）建立模型：變量、參數(shù)、目標之間的關系表示3）模型求解：數(shù)學方法及其他方法4）解的檢驗：制定檢驗準則、討論與現(xiàn)實的一致性5）靈敏性分析：參數(shù)擾動對解的影響情況6）解的實施：回到實踐中7）后評估：考察問題是否得到完滿解決三、運籌學解決問題的工作步驟1）提出問題：目標、約束、決策四、運籌學模型的構造思路及評價直接分析法類比方法模擬方法數(shù)據(jù)分析法試驗分析法構想法模型評價:易于理解、易于探查錯誤、易于計算等四、運籌學模型的構造思路及評價直接分析法優(yōu)化模型的一般形式Opt.f(xi,yj,

k)s.t.gh

(xi,yj,

k),0

h=1,2,…,m其中：

xi為決策變量（可控制）

yj

為已知參數(shù)

k

為隨機因素

f,gh

為（一般或廣義）函數(shù)建模舉例（略）——自看優(yōu)化模型的一般形式Opt.f(xi,yj,五、基本概念和符號1、向量和子空間投影定理(1)n維歐氏空間：Rn

點（向量）：x

Rn,x=(x1,x2,…,xn)T

分量xi

R(實數(shù)集)

方向（自由向量）：d

Rn,d0d=(d1,d2,…,dn)T

表示從0指向d的方向?qū)嵱弥校Ｓ脁+d表示從x點出發(fā)沿d方向移動

d長度得到的點d0xx+(1/2)d五、基本概念和符號1、向量和子空間投影定理d0xx+(1/2五、基本概念和符號（續(xù)）1、向量和子空間投影定理(2)向量運算：x,y

Rn

n

x,y的內(nèi)積：xTy=

xiyi=x1y1+x2y2+…+xnyn

i=1

x,y的距離：

‖x-y‖=[(x-y)T(x-y)](1/2)

x的長度：

‖x‖=[xTx](1/2)

三角不等式：

‖x+y‖≤‖x‖＋‖y‖

點列的收斂：設點列｛x(k)｝

Rn

,x

Rn

點列｛x(k)｝收斂到x，記limx(k)=x

lim‖x(k)-x‖=0

limxi(k)=xi,ik

k

k

x+yyx五、基本概念和符號（續(xù)）1、向量和子空間投影定理x+yyx五、基本概念和符號（續(xù)）1、向量和子空間投影定理(3)子空間：設

d(1),d(2),…,d(m)

Rn,d(k)

0

m

記L(d(1),d(2),…,d(m))={x=

jd(j)

j

R

}

j=1為由向量d(1),d(2),…,d(m)

生成的子空間，簡記為L。正交子空間：設L

為Rn的子空間，其正交子空間為

L

＝{x

Rn

xTy=0,

y

L

}子空間投影定理：設L為Rn的子空間。那么

x

Rn，唯一x

L,y

L

,使z=x+y,且x

為問題

min‖z-u‖

s.t.u

L

的唯一解，最優(yōu)值為‖y‖。特別，

L

＝Rn時，正交子空間L

＝{0}（零空間）五、基本概念和符號（續(xù)）1、向量和子空間投影定理五、基本概念和符號（續(xù)）規(guī)定：x,y

Rn，x≤y

xi≤

yi，

i

類似規(guī)定x≥y，x=y，x<y,x>y.一個有用的定理設x

Rn，

R，L為Rn

的線性子空間，

(1)若xTy≤

,

y

Rn

且y≥

0，

則x≤0，

≥

0.(2)若xTy≤

,

y

L

Rn

，

則x

L

，

≥

0.(特別,

L＝Rn時,x=0)定理的其他形式：“若xTy≤

,

y

Rn

且y≤

0，則x≥0，

≥

0.”“若xTy≥

,

y

Rn

且y≥

0，則x≥0，

≤

0.”“若xTy≥

,

y

Rn

且y≤

0，則x≤0，

≤

0.”“若xTy≥

,

y

L

Rn

，則x

L

，

≤

0.”五、基本概念和符號（續(xù)）規(guī)定：x,yRn，x≤五、基本概念和符號（續(xù)）2、多元函數(shù)及其導數(shù)(1)n元函數(shù)：f(x):Rn

R

線性函數(shù)：f(x)=cTx+b=cixi

+b

二次函數(shù)：f(x)=(1/2)xTQx+cTx+b=(1/2)

i

jaijxixj

+cixi

+b

向量值線性函數(shù)：F(x)=Ax+d

Rm其中A為m

n矩陣，d為m維向量

F(x)=(f1(x),f2(x),…,fm(x))T記aiT為A的第i行向量，fi(x)=aiTx五、基本概念和符號（續(xù)）2、多元函數(shù)及其導數(shù)五、基本概念和符號（續(xù)）2、多元函數(shù)及其導數(shù)(2)梯度（一階偏導數(shù)向量）：

f(x)＝(f/x1,f/x2,…,f/xn)T

Rn

.

線性函數(shù)：f(x)=cTx+b,

f(x)=c

二次函數(shù)：f(x)=(1/2)xTQx+cTx+b

f(x)=Qx+c

向量值線性函數(shù)：F(x)=Ax+d

RmF/x=AT五、基本概念和符號（續(xù)）2、多元函數(shù)及其導數(shù)五、基本概念和符號（續(xù)）2、多元函數(shù)及其導數(shù)(3)Hesse陣（二階偏導數(shù)矩陣）：

2f/x12

2f/x2x1

…2f/xnx1

2f(x)=

2f/

x1

x2

2f/x22

…2f/xnx2

…

…

……

2f/

x1

xn

2f/x2xn

…2f/xn2

線性函數(shù)：f(x)=cTx+b,

2f(x)=0

二次函數(shù)：f(x)=(1/2)xTQx+cTx+b,

2f(x)=Q五、基本概念和符號（續(xù)）2、多元函數(shù)及其導數(shù)五、基本概念和符號（續(xù)）2、多元函數(shù)及其導數(shù)(4)n元函數(shù)的Taylor展開式及中值公式：

設f(x):Rn

R

，二階可導。在x*的鄰域內(nèi)一階Taylor展開式：

f(x)=f(x*)+

fT(x*)(x-x*)+o‖x-x*‖二階Taylor展開式：

f(x)=f(x*)+

fT(x)(x-x*)+(1/2)(x-x*)T

2f(x*)(x-x*)+o‖x-x*‖2一階中值公式：對x,

,使

f(x)=f(x*)+［

f(x*+

(x-x*))]T