《運(yùn)籌學(xué)與最優(yōu)化方法》課件

1、運(yùn)籌學(xué)與最優(yōu)化方法,吳祈宗 侯福均 編著,主要內(nèi)容,第1章 運(yùn)籌學(xué)思想與運(yùn)籌學(xué)建模第2章 基本概念和理論基礎(chǔ)第3章 線性規(guī)劃第4章 最優(yōu)化搜索算法的結(jié)構(gòu)與一維搜索第5章 無(wú)約束最優(yōu)化方法第6章 約束最優(yōu)化方法第7章 目標(biāo)規(guī)劃第8章 整數(shù)規(guī)劃第9章 網(wǎng)絡(luò)計(jì)劃第10章 層次分析法 第11章 智能優(yōu)化計(jì)算簡(jiǎn)介,第 1 章,運(yùn)籌學(xué)思想與運(yùn)籌學(xué)建模,第1章 運(yùn)籌學(xué)思想與運(yùn)籌學(xué)建模,運(yùn)籌學(xué)簡(jiǎn)稱(chēng) OR（美）Operat

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

3、一種給出問(wèn)題壞的答案的藝術(shù)，否則的話，問(wèn)題的結(jié)果會(huì)更壞。,1.2運(yùn)籌學(xué)的應(yīng)用原則,(1)合伙原則：應(yīng)善于同各有關(guān)人員合作。(2)催化原則：善于引導(dǎo)人們改變一些常規(guī)看法。(3)互相滲透原則：多部門(mén)彼此滲透地考慮。(4)獨(dú)立原則：不應(yīng)受某些特殊情況所左右。(5)寬容原則：思路寬、方法多，不局限在某一特定方法上。(6)平衡原則：考慮各種矛盾的平衡、關(guān)系的平衡。,1.3運(yùn)籌學(xué)解決問(wèn)題的工作步驟,(1)提出問(wèn)題：目標(biāo)、約束、決策變量、參

4、數(shù)。(2)建立模型：變量、參數(shù)、目標(biāo)之間的關(guān)系表 示。(3)模型求解：數(shù)學(xué)方法及其他方法。(4)解的檢驗(yàn)：制定檢驗(yàn)準(zhǔn)則、討論與現(xiàn)實(shí)的一致性。(5)靈敏性分析：參數(shù)擾動(dòng)對(duì)解的影響情況。(6)解的實(shí)施：回到實(shí)踐中。(7)后評(píng)估：考察問(wèn)題是否得到完滿解決。,1.4運(yùn)籌學(xué)模型的構(gòu)造思路及評(píng)價(jià),直 接 分 析 法類(lèi) 比 方 法模 擬 方 法數(shù) 據(jù) 分 析 法試 驗(yàn) 分 析 法構(gòu) 想 法模型評(píng)價(jià):易于理解、易于探查錯(cuò)

5、誤、易于計(jì)算等,,優(yōu)化模型的一般形式,opt. f ( xi , yj , ?k )s.t. gh ( xi , yj , ?k ) ≤? ?, ? ? 0 h = 1,2, …,m其中， xi 為決策變量（可控制） yj 為已知參數(shù) ?k 為隨機(jī)因素 f , gh 為（一般或廣義）函數(shù)建模舉例（略）——

6、自看,,,1.5基本概念和符號(hào),1.向量和子空間投影定理(1) n維歐氏空間：Rn 點(diǎn)（向量）：x ? Rn, x = (x1 ,x2 ,…,xn)T 分量 xi ? R (實(shí)數(shù)集) 方向（自由向量）：d ? Rn, d ? 0 d =(d1 ,d2 ,…,dn)T 表示從0指向d 的方向 實(shí)用中，常用 x + ?d 表示從x 點(diǎn)出發(fā)沿d 方向

7、移動(dòng)?d 長(zhǎng)度得到的點(diǎn)。,,,d,0,x,x+(1/2)d,1.5 基本概念和符號(hào),(2) 向量運(yùn)算：x , y ? Rn n x , y 的內(nèi)積：xTy = ? xi yi = x1y1+ x2y2+ …+ xn yn i =1 x , y 的距離： ‖x－y ‖= [(x － y)T(x － y)](1/2) x 的長(zhǎng)

8、度： ‖x‖= [ xTx ](1/2) 三角不等式： ‖x + y ‖≤‖x‖＋‖y‖ 點(diǎn)列的收斂：設(shè)點(diǎn)列｛x(k)｝? Rn , x ?Rn 點(diǎn)列｛x(k)｝收斂到 x ，記lim x(k) = x ? lim‖x(k) － x‖ = 0 ? lim xi(k) = xi ,?ik?? k??

9、 k??,,,,,,x+y,y,x,1.5基本概念和符號(hào),(3) 子空間：設(shè) d (1) , d (2) , … , d (m) ? Rn, d (k) ? 0，記 m L( d (1) , d (2) , … , d (m) )={ x = ? ?j d (j) ??j?R }

10、 j =1為由向量d (1) , d (2) , … , d (m) 生成的子空間，簡(jiǎn)記為L(zhǎng)。正交子空間：設(shè) L 為Rn的子空間，其正交子空間為 L?＝{ x ? Rn ?xTy=0 , ? y ?L }子空間投影定理：設(shè) L 為Rn的子空間，那么? z?Rn，? 唯一 x ?L , y ?L?, 使 z=x+y , 且 x 為問(wèn)題 min ‖z

11、－ u‖ s.t. u ? L 的唯一解，最優(yōu)值為‖y‖ 。特別地， L ＝Rn 時(shí)，正交子空間 L?＝{ 0 }（零空間）。,,1.5基本概念和符號(hào),規(guī)定：x , y ? Rn，x ≤ y ? xi ≤ yi ，?i ；類(lèi)似地規(guī)定 x ≥ y，x = y，x y 。一個(gè)有用的定理 設(shè) x?Rn，??R，L為Rn 的線性子空間。 若 xTy ≤ ? , ? y?Rn 且 y ≥

12、0， 則 x ≤ 0，? ≥ 0 若 xTy ≤ ? , ? y ? L ? Rn ， 則 x ? L?，? ≥ 0 (特別地, 當(dāng)L＝Rn時(shí),x =0) 定理的其他形式：若 xTy ≤ ? , ? y?Rn 且 y ≤ 0，則 x ≥ 0，? ≥ 0 。若 xTy ≥ ? , ? y?Rn 且 y ≥ 0，則 x ≥ 0，? ≤ 0 。若 xTy ≥ ?

13、, ? y?Rn 且 y ≤ 0，則 x ≤ 0，? ≤ 0 。若 xTy ≥ ? , ? y ? L ? Rn ， 則 x ? L?，? ≤ 0 。,1.5基本概念和符號(hào),2.多元函數(shù)及其導(dǎo)數(shù)(1) n元函數(shù)：f (x): Rn ? R 線性函數(shù)：f (x) = cTx + b = ? ci xi + b 二次函數(shù)：f (x) = (1/2) xTQx + cTx + b

14、 = (1/2)? ?aij xi xj + ? ci xi + b 向量值線性函數(shù)：F(x) = Ax + d ? Rm其中， A為 m?n矩陣，d為m維向量 F(x)=( f1(x), f2(x), … , fm(x) )T 記 aiT為A的第i行向量，f(x) = aiTx,1.5基本概念和符號(hào),(2) 梯度（一階偏導(dǎo)數(shù)向量）： ?f (x)＝(? f /? x1 ,

15、 ? 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 ? Rm ? F /

16、? x = AT,1.5基本概念和符號(hào),(3) Hesse 矩陣（二階偏導(dǎo)數(shù)矩陣）： ? 2f /?x1 2 ? 2f /?x2 ?x1 … ? 2f /?xn ?x1 ?2f (x)= ? 2f /?x1 ?x2 ? 2f /?x22 … ? 2f /?xn ?x2

17、 … … … ? 2f /?x1 ?xn ? 2f /?x2 ?xn … ? 2f /?xn2 線性函數(shù)：f (x) = cTx + b , ?2f (x) = 0 二次函數(shù)：f (x) = (1/2) xTQx + c

18、Tx + b, ?2f (x)=Q,,1.5基本概念和符號(hào),(4)n元函數(shù)的Taylor展開(kāi)式及中值公式 設(shè) f (x): Rn ? R ，二階可導(dǎo)。在x* 的鄰域內(nèi),有一階Taylor展開(kāi)式： f (x) = f (x*)+ ?f T(x*)(x－x*) + o‖x － x*‖二階Taylor展開(kāi)式： f (x) = f (x*)+ ?f T(x)(x － x*) + (1/2)(x － x*)T

19、 ?2f (x*)(x － x*) + o‖x － x*‖2一階中值公式：對(duì)x,? ? ? ?????, 使 f (x) = f (x*)+ ［?f (x*+?(x － x*))]T(x － x*)Lagrange余項(xiàng)：對(duì)x,? ? ? ?????, 記x??x*+ ?(x － x*) f (x) = f (x*)+ ?f T(x)(x － x*) + (1/2)(x － x*