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

運(yùn)籌學(xué) 與最優(yōu)化方法,吳祈宗等編制,主要內(nèi)容,第一章 運(yùn)籌學(xué)思想與運(yùn)籌學(xué)建模 第二章 基本概念和理論基礎(chǔ) 第三章 線性規(guī)劃 第四章 最優(yōu)化搜索算法的結(jié)構(gòu)與一維搜索 第五章 無約束最優(yōu)化方法 第六章 約束最優(yōu)化方法 第七章 目標(biāo)規(guī)劃 第八章 整數(shù)規(guī)劃 第九章 層次分析法 第十章 智能優(yōu)化計算簡介,第 一 章,運(yùn)籌學(xué)思想 與 運(yùn)籌學(xué)建模,第一章 運(yùn)籌學(xué)思想與運(yùn)籌學(xué)建模,運(yùn)籌學(xué)簡稱 OR （美）Operations Research （英）Operational Research “運(yùn)籌于帷幄之中，決勝于千里之外” 三個來源：軍事、管理、經(jīng)濟(jì) 三個組成部分： 運(yùn)用分析理論、競爭理論、隨機(jī)服務(wù)理論,一、什么是運(yùn)籌學(xué),為決策機(jī)構(gòu)在對其控制下的業(yè)務(wù)活動進(jìn)行決策時，提供一門量化為基礎(chǔ)的科學(xué)方法。 或是一門應(yīng)用科學(xué)，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法，解決實際中提出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)。 運(yùn)籌學(xué)是一種給出問題壞的答案的藝術(shù)，否則的話，問題的結(jié)果會更壞。,二、運(yùn)籌學(xué)的應(yīng)用原則,合伙原則：應(yīng)善于同各有關(guān)人員合作 催化原則：善于引導(dǎo)人們改變一些常規(guī)看法 互相滲透原則：多部門彼此滲透地考慮 獨立原則：不應(yīng)受某些特殊情況所左右 寬容原則：思路寬、方法多，不局限在某一特定方法上 平衡原則：考慮各種矛盾的平衡、關(guān)系的平衡,三、運(yùn)籌學(xué)解決問題的工作步驟,1 ）提出問題：目標(biāo)、約束、決策變量、參數(shù) 2 ）建立模型：變量、參數(shù)、目標(biāo)之間的關(guān)系表示 3 ）模型求解：數(shù)學(xué)方法及其他方法 4 ）解的檢驗：制定檢驗準(zhǔn)則、討論與現(xiàn)實的一致性 5 ）靈敏性分析：參數(shù)擾動對解的影響情況 6 ）解的實施：回到實踐中 7 ）后評估：考察問題是否得到完滿解決,四、運(yùn)籌學(xué)模型的構(gòu)造思路及評價,直 接 分 析 法 類 比 方 法 模 擬 方 法 數(shù) 據(jù) 分 析 法 試 驗 分 析 法 構(gòu) 想 法 模型評價: 易于理解、易于探查錯誤、易于計算等,優(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ù) 建模舉例（略） 自看,五、基本概念和符號,1、向量和子空間投影定理 (1) n維歐氏空間：Rn 點（向量）：x Rn, x = (x1 ,x2 ,xn)T 分量 xi R (實數(shù)集) 方向（自由向量）：d Rn, d 0 d =(d1 ,d2 ,dn)T 表示從0指向d 的方向 實用中，常用 x + d 表示從x 點出發(fā)沿d 方向移動d 長度得到的點,d,0,x,x+(1/2)d,五、基本概念和符號（續(xù)）,1、向量和子空間投影定理 (2) 向量運(yùn)算：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 xy 點列的收斂：設(shè)點列x(k) Rn , x Rn 點列x(k)收斂到 x ，記 lim x(k) = x limx(k)- x = 0 lim xi(k) = xi ,i k k k,x+y,y,x,五、基本概念和符號（續(xù)）,1、向量和子空間投影定理 (3) 子空間：設(shè) d (1) , d (2) , , d (m) Rn, d (k) 0 m 記 L( d (1) , d (2) , , d (m) )= x = j d (j) jR j =1 為由向量d (1) , d (2) , , d (m) 生成的子空間，簡記為L。 正交子空間：設(shè) L 為Rn的子空間，其正交子空間為 L x Rn xTy=0 , y L 子空間投影定理：設(shè) 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ù)）,規(guī)定：x , y Rn，x y xi yi ，i 類似規(guī)定 x y，x = y，x y . 一個有用的定理 設(shè) xRn，R，L為Rn 的線性子空間， (1)若 xTy , yRn 且 y 0， 則 x 0， 0 . (2)若 xTy , y L Rn ， 則 x L， 0 .(特別, LRn時,x =0) 定理的其他形式： “若 xTy , yRn 且 y 0，則 x 0， 0 .” “若 xTy , yRn 且 y 0，則 x 0， 0 .” “若 xTy , yRn 且 y 0，則 x 0， 0 .” “若 xTy , y L Rn ， 則 x L， 0 .”,五、基本概念和符號（續(xù)）,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 = (1/2)i j aij xi xj + ci xi + b 向量值線性函數(shù)：F(x) = Ax + d Rm 其中 A為 mn矩陣，d為m維向量 F(x)=( f1(x), f2(x), , fm(x) )T 記 aiT為A的第i行向量，fi (x) = aiTx,五、基本概念和符號（續(xù)）,2、多元函數(shù)及其導(dǎo)數(shù) (2) 梯度（一階偏導(dǎo)數(shù)向量）： f (x)( f / x1 , f / x2 , , f / xn )TRn . 線性函數(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 / x = AT,五、基本概念和符號（續(xù)）,2、多元函數(shù)及其導(dǎo)數(shù) (3) Hesse 陣（二階偏導(dǎo)數(shù)矩陣）： 2f /x1 2 2f /x2 x1 2f /xn x1 2f (x)= 2f /x1 x2 2f /x22 2f /xn x2 2f /x1 xn 2f /x2 xn 2f /xn2 線性函數(shù)：f (x) = cTx + b , 2f (x) = 0 二次函數(shù)：f (x) = (1/2) xTQx + cTx + b, 2f (x)=Q,五、基本概念和符號（續(xù)）,2、多元函數(shù)及其導(dǎo)數(shù) (4)n元函數(shù)的Taylor展開式及中值公式： 設(shè) f (x): Rn R ，二階可導(dǎo)。在x* 的鄰域內(nèi) 一階Taylor展開式： f (x) = f (x*)+ f T(x*)(x-x*) + ox-x* 二階Taylor展開式： f (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x*)(x-x*) + ox-x*2 一階中值公式：對x, , 使 f (x) = f (x*)+ f (x*+(x-x*)T(x-x*) Lagrange余項：對x, , 記xx*+ (x-x*) f