运筹学与最优化方法课件.ppt

1、吴祈宗等编制吴祈宗等编制l第一章第一章 运筹学思想与运筹学建模运筹学思想与运筹学建模l第二章第二章 基本概念和理论基础基本概念和理论基础l第三章第三章 线性规划线性规划l第四章第四章 最优化搜索算法的结构与一维搜索最优化搜索算法的结构与一维搜索l第五章第五章 无约束最优化方法无约束最优化方法l第六章第六章 约束最优化方法约束最优化方法l第七章第七章 目标规划目标规划l第八章第八章 整数规划整数规划l第九章第九章 层次分析法层次分析法l第十章第十章 智能优化计算简介智能优化计算简介第第 一一 章章运筹学运筹学简称简称 OR（美）（美）Operations Research（英）（英）Operat

2、ional Research“运筹于帷幄之中，决胜于千里之外运筹于帷幄之中，决胜于千里之外”l三个来源：军事、管理、经济三个来源：军事、管理、经济l三个组成部分：三个组成部分：运用分析理论、竞争理论、随机服务理论运用分析理论、竞争理论、随机服务理论l为决策机构在对其控制下的业务活动进为决策机构在对其控制下的业务活动进行决策时，提供一门量化为基础的科学行决策时，提供一门量化为基础的科学方法。方法。l或是一门应用科学，它广泛应用现有的或是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决提出的专门问题，为决策者选择最

3、优决策提供定量依据。策提供定量依据。l运筹学是一种给出问题坏的答案的艺术，运筹学是一种给出问题坏的答案的艺术，否则的话，问题的结果会更坏。否则的话，问题的结果会更坏。1)合伙原则：应善于同各有关人员合作合伙原则：应善于同各有关人员合作2)催化原则：善于引导人们改变一些常规看催化原则：善于引导人们改变一些常规看法法3)互相渗透原则：多部门彼此渗透地考虑互相渗透原则：多部门彼此渗透地考虑4)独立原则：不应受某些特殊情况所左右独立原则：不应受某些特殊情况所左右5)宽容原则：思路宽、方法多，不局限在某一特定宽容原则：思路宽、方法多，不局限在某一特定方法上方法上6)平衡原则：考虑各种矛盾的平衡、关系的平

4、衡原则：考虑各种矛盾的平衡、关系的平衡平衡1 1 ）提出问题：目标、约束、决策变量、参数）提出问题：目标、约束、决策变量、参数2 2 ）建立模型：变量、参数、目标之间的关系）建立模型：变量、参数、目标之间的关系表示表示3 3 ）模型求解：数学方法及其他方法）模型求解：数学方法及其他方法4 4 ）解的检验：制定检验准则、讨论与现实的）解的检验：制定检验准则、讨论与现实的一致性一致性5 5 ）灵敏性分析：参数扰动对解的影响情况）灵敏性分析：参数扰动对解的影响情况6 6 ）解的实施：回到实践中）解的实施：回到实践中7 7 ）后评估：考察问题是否得到完满解决）后评估：考察问题是否得到完满解决1.直直

5、接接 分分 析析 法法2.类类 比比 方方 法法3.模模 拟拟 方方 法法4.数数 据据 分分 析析 法法5.试试 验验 分分 析析 法法6.构构 想想 法法模型评价模型评价:易于理解、易于探查错误、易于计算等易于理解、易于探查错误、易于计算等Opt. f ( xi, yj, k )s.t. gh ( xi, yj, k ) , 0 h = 1,2, ,m其中：其中： xi 为决策变量（可控制）为决策变量（可控制） yj 为已知参数为已知参数 k 为随机因素为随机因素 f , gh 为（一般或广义）函数为（一般或广义）函数建模举例（略）建模举例（略） 自看自看1 1、向量和子空间投影定理、向量

6、和子空间投影定理(1) (1) n n维欧氏空间：维欧氏空间：R Rn n 点（向量）点（向量）：x R Rn n, , x = ( = (x1 , ,x2 , , ,xn) )T T 分量分量 xi R R ( (实数集实数集) ) 方向（自由向量）方向（自由向量）：d R Rn n, , d 0 d =(=(d1 , ,d2 , , ,dn) )T T 表示从表示从0 0指向指向d 的方向的方向 实用中，常用实用中，常用 x + d 表示从表示从x 点出发沿点出发沿d 方向方向移动移动 d 长度得到的点长度得到的点d0 xx+(1/2)d1 1、向量和子空间投影定理、向量和子空间投影定理(

7、2) (2) 向量运算：向量运算：x , y R Rn n n x , y 的内积：的内积：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 点列的收敛：点列的收敛：设点列设点列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、向量和子空间投影定理、

8、向量和子空间投影定理(3) (3) 子空间：子空间：设设 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正交子空间：设正交子空间：设 L 为为R Rn n的的子空间，其正交子空间为子空间，其正交子空间为 L x R Rn n xTy=0 , y L l子空间投影定理：子空间投影定理：设设 L 为为R Rn n的的子空间。那么

9、子空间。那么 x R Rn n， 唯一唯一 x L , y L , 使使 z=x+y , 且且 x 为问题为问题 min z - u s.t. u L 的唯一解，最优值为的唯一解，最优值为y。l特别，特别， L R Rn n 时，正交子空间时，正交子空间 L 0 （零空间零空间）l规定：规定：x , y R Rn n，x y xi yi ， i 类类似规定似规定 x y，x = y，x y .l一个有用的定理一个有用的定理 设设 x R Rn n， R R，L L为为R Rn n 的线性子空间，的线性子空间， (1)(1)若若 xTy , y R Rn n 且且 y 0， 则则 x 0， 0

10、. (2) (2)若若 xTy , y L 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、多元函数及其导数、多元函数及其导数(1) (1) n n元函数：元函数：f ( (x): ): R

11、Rn n R R 线性函数线性函数：f (x) = cTx + b = ci xi + b 二次函数二次函数：f (x) = (1/2) xTQx + cTx + b = (1/2) i j aij xi xj + ci xi + b 向量值线性函数：向量值线性函数：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、多元函数及其导数、多元函数及其导数(2) (2) 梯度（一阶偏导数向量）：梯度（一阶偏导数向

12、量）： f ( (x) )( ( f / x1 , f / x2 , , f / xn ) )T T R Rn n . . 线性函数线性函数：f (x) = cTx + b , f (x) = c 二次函数二次函数：f (x) = (1/2) xTQx + cTx + b f (x) = Qx + c 向量值线性函数：向量值线性函数：F(x) = Ax + d R Rm m F / x = AT2 2、多元函数及其导数、多元函数及其导数(3) Hesse (3) Hesse 阵（二阶偏导数矩阵）：阵（二阶偏导数矩阵）： 2f / x1 2 2f / x2 x1 2f / xn x1 2f (

13、(x)= )= 2f / x1 x2 2f / x22 2f / xn x2 2f / x1 xn 2f / x2 xn 2f / xn2 线性函数线性函数：f (x) = cTx + b , 2f (x) = 0 二次函数二次函数：f (x) = (1/2) xTQx + cTx + b, 2f (x)=Q2 2、多元函数及其导数、多元函数及其导数(4)(4)n n元函数的元函数的TaylorTaylor展开式及中值公式：展开式及中值公式： 设设 f ( (x): ): R Rn n R R ，二阶可导。在二阶可导。在x* 的邻域内的邻域内l一阶一阶TaylorTaylor展开式：展开式：

14、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*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x )(x-x*) l复习下列知识：复习下列知识：线性代数的有关概念：向量与矩线性代数的有关概念：向量与矩阵的运算、向量的线性相关和线阵的运算、向量的线性相关和线性无关，矩阵的秩，正定、半正性无关，矩阵的秩，正定、半正定矩阵，线性空间等；定矩阵，线性空间等；集合的有关概念：开集、闭集，集合的有关概念：开集、闭集，集合运算，内点、边界点等。集合运算，内点、边界点等。