運籌學(xué)與最優(yōu)化方法

1、運籌學(xué)與最優(yōu)化方法l第一章第一章 運籌學(xué)思想與運籌學(xué)建模運籌學(xué)思想與運籌學(xué)建模l第二章第二章 基本概念和理論基礎(chǔ)基本概念和理論基礎(chǔ)l第三章第三章 線性規(guī)劃線性規(guī)劃l第四章第四章 最優(yōu)化搜索算法的結(jié)構(gòu)與一維搜索最優(yōu)化搜索算法的結(jié)構(gòu)與一維搜索l第五章第五章 無約束最優(yōu)化方法無約束最優(yōu)化方法l第六章第六章 約束最優(yōu)化方法約束最優(yōu)化方法l第七章第七章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃l第八章第八章 整數(shù)規(guī)劃整數(shù)規(guī)劃l第九章第九章 層次分析法層次分析法l第十章第十章 智能優(yōu)化計算簡介智能優(yōu)化計算簡介運籌學(xué)運籌學(xué)簡稱簡稱 OR（美）（美）Operations Research（英）（英）Operational Resea

2、rch“運籌于帷幄之中，決勝于千里之外運籌于帷幄之中，決勝于千里之外”l三個來源：軍事、管理、經(jīng)濟(jì)三個來源：軍事、管理、經(jīng)濟(jì)l三個組成部分：三個組成部分：運用分析理論、競爭理論、隨機(jī)服務(wù)理論運用分析理論、競爭理論、隨機(jī)服務(wù)理論l為決策機(jī)構(gòu)在對其控制下的業(yè)務(wù)活動進(jìn)為決策機(jī)構(gòu)在對其控制下的業(yè)務(wù)活動進(jìn)行決策時，提供一門量化為基礎(chǔ)的科學(xué)行決策時，提供一門量化為基礎(chǔ)的科學(xué)方法。方法。l或是一門應(yīng)用科學(xué)，它廣泛應(yīng)用現(xiàn)有的或是一門應(yīng)用科學(xué)，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法，解決實際中科學(xué)技術(shù)知識和數(shù)學(xué)方法，解決實際中提出的專門問題，為決策者選擇最優(yōu)決提出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)。策

3、提供定量依據(jù)。l運籌學(xué)是一種給出問題壞的答案的藝術(shù)，運籌學(xué)是一種給出問題壞的答案的藝術(shù)，否則的話，問題的結(jié)果會更壞。否則的話，問題的結(jié)果會更壞。l合伙原則：應(yīng)善于同各有關(guān)人員合作合伙原則：應(yīng)善于同各有關(guān)人員合作l催化原則：善于引導(dǎo)人們改變一些常規(guī)看催化原則：善于引導(dǎo)人們改變一些常規(guī)看法法l互相滲透原則：多部門彼此滲透地考慮互相滲透原則：多部門彼此滲透地考慮l獨立原則：不應(yīng)受某些特殊情況所左右獨立原則：不應(yīng)受某些特殊情況所左右l寬容原則：思路寬、方法多，不局限在某一特定寬容原則：思路寬、方法多，不局限在某一特定方法上方法上l平衡原則：考慮各種矛盾的平衡、關(guān)系的平衡原則：考慮各種矛盾的平衡、關(guān)系的

4、平衡平衡1 1 ）提出問題：目標(biāo)、約束、決策變量、參數(shù)）提出問題：目標(biāo)、約束、決策變量、參數(shù)2 2 ）建立模型：變量、參數(shù)、目標(biāo)之間的關(guān)系）建立模型：變量、參數(shù)、目標(biāo)之間的關(guān)系表示表示3 3 ）模型求解：數(shù)學(xué)方法及其他方法）模型求解：數(shù)學(xué)方法及其他方法4 4 ）解的檢驗：制定檢驗準(zhǔn)則、討論與現(xiàn)實的）解的檢驗：制定檢驗準(zhǔn)則、討論與現(xiàn)實的一致性一致性5 5 ）靈敏性分析：參數(shù)擾動對解的影響情況）靈敏性分析：參數(shù)擾動對解的影響情況6 6 ）解的實施：回到實踐中）解的實施：回到實踐中7 7 ）后評估：考察問題是否得到完滿解決）后評估：考察問題是否得到完滿解決l直直 接接 分分 析析 法法l類類 比比

5、方方 法法l模模 擬擬 方方 法法l數(shù)數(shù) 據(jù)據(jù) 分分 析析 法法l試試 驗驗 分分 析析 法法l構(gòu)構(gòu) 想想 法法模型評價模型評價:易于理解、易于探查錯誤、易于計算等易于理解、易于探查錯誤、易于計算等Opt. f ( xi, yj, k )s.t. gh ( xi, yj, k ) , 0 h = 1,2, ,m其中：其中： xi 為決策變量（可控制）為決策變量（可控制） yj 為已知參數(shù)為已知參數(shù) k 為隨機(jī)因素為隨機(jī)因素 f , gh 為（一般或廣義）函數(shù)為（一般或廣義）函數(shù)建模舉例（略）建模舉例（略） 自看自看1 1、向量和子空間投影定理、向量和子空間投影定理(1) (1) n n維歐氏空

6、間：維歐氏空間：R Rn n 點（向量）點（向量）：x R Rn n, , x = ( = (x1 , ,x2 , , ,xn) )T T 分量分量 xi R R ( (實數(shù)集實數(shù)集) ) 方向（自由向量）方向（自由向量）：d R Rn n, , d 0 d =(=(d1 , ,d2 , , ,dn) )T T 表示從表示從0 0指向指向d 的方向的方向 實用中，常用實用中，常用 x + d 表示從表示從x 點出發(fā)沿點出發(fā)沿d 方向方向移動移動 d 長度得到的點長度得到的點d0 xx+(1/2)d1 1、向量和子空間投影定理、向量和子空間投影定理(2) (2) 向量運算：向量運算：x , y

7、R Rn n n x , y 的內(nèi)積：的內(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 xy 點列的收斂：設(shè)點列點列的收斂：設(shè)點列x(k) R Rn n , , x R Rn n 點列點列x(k)收斂到收斂到 x ，記記lim x(k) = x limx(k)- x = 0 lim xi(k) = xi , ik k kx+yyx1 1、向量和子空間投影定理、向量和子空間投影定理(3) (3) 子空間：設(shè)

8、子空間：設(shè) d (1) , d (2) , , d (m) R Rn n, , d (k) 0 m 記記 L L( ( d (1) , d (2) , , d (m) )=)= x = j d (j) j R j =1為由向量為由向量d (1) , d (2) , , d (m) 生成的子空間，簡記為生成的子空間，簡記為L L。l正交子空間：設(shè)正交子空間：設(shè) L 為為R Rn n的的子空間，其正交子空間為子空間，其正交子空間為 L x R Rn n xTy=0 , y L l子空間投影定理：設(shè)子空間投影定理：設(shè) L 為為R Rn n的的子空間。那么子空間。那么 x R Rn n， 唯一唯一 x

9、 L , y L , 使使 z=x+y , 且且 x 為問題為問題 min z - u s.t. u L 的唯一解，最優(yōu)值為的唯一解，最優(yōu)值為y。l特別，特別， L R Rn n 時，正交子空間時，正交子空間 L 0 （零空間）（零空間）l規(guī)定：規(guī)定：x , y R Rn n，x y xi yi ， i 類類似規(guī)定似規(guī)定 x y，x = y，x y .l一個有用的定理一個有用的定理 設(shè)設(shè) x R Rn n， R R，L L為為R Rn n 的線性子空間，的線性子空間， (1)(1)若若 xTy , y R Rn n 且且 y 0， 則則 x 0， 0 . (2) (2)若若 xTy , y L

10、 L R Rn n ， 則則 x L L ， 0 .(特別特別, L LR Rn n時時, ,x =0=0)l定理的其他形式：定理的其他形式：“若若 xTy , y R Rn n 且且 y 0，則，則 x 0， 0 .”“若若 xTy , y R Rn n 且且 y 0，則，則 x 0， 0 .”“若若 xTy , y R Rn n 且且 y 0，則，則 x 0， 0 .”“若若 xTy , y L L R Rn n ， 則則 x L L ， 0 .”2 2、多元函數(shù)及其導(dǎo)數(shù)、多元函數(shù)及其導(dǎo)數(shù)(1) (1) n n元函數(shù)：元函數(shù)：f ( (x): ): R Rn n R R 線性函數(shù)線性函數(shù)：

11、f (x) = cTx + b = ci xi + b 二次函數(shù)二次函數(shù)：f (x) = (1/2) xTQx + cTx + b = (1/2) i j aij xi xj + ci xi + b 向量值線性函數(shù)：向量值線性函數(shù)：F(x) = Ax + d R Rm m其中其中 A為為 m n矩陣，矩陣，d為為m維向量維向量 F(x)=( f1(x), f2(x), , fm(x) )T 記記 aiT為為A的第的第i行向量，行向量，fi (x) = aiTx2 2、多元函數(shù)及其導(dǎo)數(shù)、多元函數(shù)及其導(dǎo)數(shù)(2) (2) 梯度（一階偏導(dǎo)數(shù)向量）：梯度（一階偏導(dǎo)數(shù)向量）： f ( (x) )( ( f

12、 / x1 , f / x2 , , f / xn ) )T T R Rn n . . 線性函數(shù)線性函數(shù)：f (x) = cTx + b , f (x) = c 二次函數(shù)二次函數(shù)：f (x) = (1/2) xTQx + cTx + b f (x) = Qx + c 向量值線性函數(shù)：向量值線性函數(shù)：F(x) = Ax + d R Rm m F / x = AT2 2、多元函數(shù)及其導(dǎo)數(shù)、多元函數(shù)及其導(dǎo)數(shù)(3) Hesse (3) Hesse 陣（二階偏導(dǎo)數(shù)矩陣）：陣（二階偏導(dǎo)數(shù)矩陣）： 2f / x1 2 2f / x2 x1 2f / xn x1 2f ( (x)= )= 2f / x1 x2

13、 2f / x22 2f / xn x2 2f / x1 xn 2f / x2 xn 2f / xn2 線性函數(shù)線性函數(shù)：f (x) = cTx + b , 2f (x) = 0 二次函數(shù)二次函數(shù)：f (x) = (1/2) xTQx + cTx + b, 2f (x)=Q2 2、多元函數(shù)及其導(dǎo)數(shù)、多元函數(shù)及其導(dǎo)數(shù)(4)(4)n n元函數(shù)的元函數(shù)的TaylorTaylor展開式及中值公式：展開式及中值公式： 設(shè)設(shè) f ( (x): ): R Rn n R R ，二階可導(dǎo)。在二階可導(dǎo)。在x* 的鄰域內(nèi)的鄰域內(nèi)l一階一階TaylorTaylor展開式：展開式： f (x) = f (x*)+ f T(x*)(x-x*) + ox-x*l二階二階TaylorTaylor展開式：展開式： f (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x*)(x-x*) + ox-x*2l一階中值公式：對一階中值公式：對x, , , 使使 f (x) = f (x*)+ f (x*+ (x-x*)T(x-x*)lLagrange余項：余項：對對x, , , 記記x x*+ (x-x*) f (x) = f (x*)+