運(yùn)籌學(xué)與最優(yōu)化方法第1章.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)化計(jì)算簡介 第一章 運(yùn)籌學(xué)思想與運(yùn)籌學(xué)建模 第一章運(yùn)籌學(xué)思想與運(yùn)籌學(xué)建模 運(yùn)籌學(xué) 簡稱OR 美 Operation sResearch 英 OperationalResearch 運(yùn)籌于帷幄之中 決勝于千里之外 三個(gè)來源 軍事 管理 經(jīng)濟(jì)三個(gè)組成部分 運(yùn)用分析理論 競爭理論 隨機(jī)服務(wù)理論 一 什么是運(yùn)籌學(xué) 為決策機(jī)構(gòu)在對其控制下的業(yè)務(wù)活動進(jìn)行決策時(shí) 提供一門量化為基礎(chǔ)的科學(xué)方法 或是一門應(yīng)用科學(xué) 它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法 解決實(shí)際中提出的專門問題 為決策者選擇最優(yōu)決策提供定量依據(jù) 運(yùn)籌學(xué)是一種給出問題壞的答案的藝術(shù) 否則的話 問題的結(jié)果會更壞 二 運(yùn)籌學(xué)的應(yīng)用原則 合伙原則 應(yīng)善于同各有關(guān)人員合作催化原則 善于引導(dǎo)人們改變一些常規(guī)看法互相滲透原則 多部門彼此滲透地考慮獨(dú)立原則 不應(yīng)受某些特殊情況所左右寬容原則 思路寬 方法多 不局限在某一特定方法上平衡原則 考慮各種矛盾的平衡 關(guān)系的平衡 三 運(yùn)籌學(xué)解決問題的工作步驟 1 提出問題 目標(biāo) 約束 決策變量 參數(shù)2 建立模型 變量 參數(shù) 目標(biāo)之間的關(guān)系表示3 模型求解 數(shù)學(xué)方法及其他方法4 解的檢驗(yàn) 制定檢驗(yàn)準(zhǔn)則 討論與現(xiàn)實(shí)的一致性5 靈敏性分析 參數(shù)擾動對解的影響情況6 解的實(shí)施 回到實(shí)踐中7 后評估 考察問題是否得到完滿解決 四 運(yùn)籌學(xué)模型的構(gòu)造思路及評價(jià) 直接分析法類比方法模擬方法數(shù)據(jù)分析法試驗(yàn)分析法構(gòu)想法模型評價(jià) 易于理解 易于探查錯(cuò)誤 易于計(jì)算等 優(yōu)化模型的一般形式 Opt f xi yj k s t gh xi yj k 0h 1 2 m其中 xi為決策變量 可控制 yj為已知參數(shù) k為隨機(jī)因素f gh為 一般或廣義 函數(shù)建模舉例 略 自看 五 基本概念和符號 1 向量和子空間投影定理 1 n維歐氏空間 Rn點(diǎn) 向量 x Rn x x1 x2 xn T分量xi R 實(shí)數(shù)集 方向 自由向量 d Rn d 0d d1 d2 dn T表示從0指向d的方向?qū)嵱弥?常用x d表示從x點(diǎn)出發(fā)沿d方向移動 d長度得到的點(diǎn) d 0 x x 1 2 d 五 基本概念和符號 續(xù) 1 向量和子空間投影定理 2 向量運(yùn)算 x y Rnnx y的內(nèi)積 xTy xiyi x1y1 x2y2 xnyni 1x y的距離 x y x y T x y 1 2 x的長度 x xTx 1 2 三角不等式 x y x y 點(diǎn)列的收斂 設(shè)點(diǎn)列 x k Rn x Rn點(diǎn)列 x k 收斂到x 記limx k x lim x k x 0 limxi k xi ik k k x y y x 五 基本概念和符號 續(xù) 1 向量和子空間投影定理 3 子空間 設(shè)d 1 d 2 d m Rn d k 0m記L d 1 d 2 d m x jd j j R 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時(shí) 正交子空間L 0 零空間 五 基本概念和符號 續(xù) 規(guī)定 x y Rn x y xi yi i類似規(guī)定x y x y xy 一個(gè)有用的定理設(shè)x Rn R L為Rn的線性子空間 1 若xTy y Rn且y 0 則x 0 0 2 若xTy y L Rn 則x L 0 特別 L Rn時(shí) 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ù) 2 多元函數(shù)及其導(dǎo)數(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行向量 f x aiTx 五 基本概念和符號 續(xù) 2 多元函數(shù)及其導(dǎo)數(shù) 2 梯度 一階偏導(dǎo)數(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 Rm F x AT 五 基本概念和符號 續(xù) 2 多元函數(shù)及其導(dǎo)數(shù) 3 Hesse陣 二階偏導(dǎo)數(shù)矩陣 2f x12 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 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 x x Lagrange余項(xiàng) 對x 記x x x x f x f