运筹学思想与运筹学建模.ppt
运筹学与最优化方法吴祈宗等编制主要内容l第一章 运筹学思想与运筹学建模l第二章 基本概念和理论基础l第三章 线性规划l第四章 最优化搜索算法的结构与一维搜索l第五章 无约束最优化方法l第六章 约束最优化方法l第七章 目标规划l第八章 整数规划l第九章 层次分析法l第十章 智能优化计算简介第 一 章 运筹学思想与运筹学建模第一章 运筹学思想与运筹学建模运筹学简称 OR（美）Operations Research（英）Operational Research“运筹于帷幄之中，决胜于千里之外”l三个来源：军事、管理、经济l三个组成部分：运用分析理论、竞争理论、随机服务理论一、什么是运筹学l为决策机构在对其控制下的业务活动进行决策时，提供一门量化为基础的科学方法。l或是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。l运筹学是一种给出问题坏的答案的艺术，否则的话，问题的结果会更坏。二、运筹学的应用原则1)合伙原则：应善于同各有关人员合作2)催化原则：善于引导人们改变一些常规看法3)互相渗透原则：多部门彼此渗透地考虑4)独立原则：不应受某些特殊情况所左右5)宽容原则：思路宽、方法多，不局限在某一特定方法上6)平衡原则：考虑各种矛盾的平衡、关系的平衡三、运筹学解决问题的工作步骤1）提出问题：目标、约束、决策变量、参数2）建立模型：变量、参数、目标之间的关系表示3）模型求解：数学方法及其他方法4）解的检验：制定检验准则、讨论与现实的一致性5）灵敏性分析：参数扰动对解的影响情况6）解的实施：回到实践中7）后评估：考察问题是否得到完满解决四、运筹学模型的构造思路及评价1.直 接 分 析 法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)n维欧氏空间：Rn 点（向量）：x Rn,x=(x1,x2,xn)T 分量 xi R(实数集)方向（自由向量）：d Rn,d 0 d=(d1,d2,dn)T 表示从0指向d 的方向 实用中，常用 x+d 表示从x 点出发沿d 方向移动d 长度得到的点d0 xx+(1/2)d五、基本概念和符号（续）五、基本概念和符号（续）1、向量和子空间投影定理(2)向量运算：x,y Rn 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)Rn,x Rn 点列x(k)收敛到 x，记lim x(k)=x limx(k)-x=0 lim xi(k)=xi,ik k k x+yyx五、基本概念和符号（续）五、基本概念和符号（续）1、向量和子空间投影定理(3)子空间：设 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。l 正交子空间：设 L 为Rn的子空间，其正交子空间为 L x Rn xTy=0,y L l 子空间投影定理：设 L 为Rn的子空间。那么 z Rn，唯一 x L,y L,使 z=x+y,且 x 为问题 min z-u s.t.u L 的唯一解，最优值为y。l 特别，L Rn 时，正交子空间 L 0（零空间）五、基本概念和符号（续）五、基本概念和符号（续）l规定：x,y Rn，x y xi yi，i 类似规定 x y，x=y，x y.l一个有用的定理 设 xRn，R，L为Rn 的线性子空间，(1)若 xTy,y Rn 且 y 0，则 x 0，0.(2)若 xTy,y L Rn，则 x L，0.(特别,LRn时,x=0)l定理的其他形式：“若 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.”五、基本概念和符号（续）五、基本概念和符号（续）2、多元函数及其导数(1)n元函数：f(x):Rn 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 Rm其中 A为 m n矩阵，d为m维向量 F(x)=(f1(x),f2(x),fm(x)T 记 aiT为A的第i行向量，fi(x)=aiTx+di五、基本概念和符号（续）五、基本概念和符号（续）2、多元函数及其导数(2)梯度（一阶偏导数向量）：f(x)(f/x1,f/x2,f/xn)T Rn.线性函数：f(x)=cTx+b,f(x)=c 二次函数：f(x)=(1/2)xTQx+cTx+b f(x)=Qx+c 向量值线性函数：F(x)=Ax+d Rm F/x=AT五、基本概念和符号（续）五、基本概念和符号（续）2、多元函数及其导数(3)Hesse 阵（二阶偏导数矩阵）：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 线性函数：f(x)=cTx+b,2f(x)=0 二次函数：f(x)=(1/2)xTQx+cTx+b,2f(x)=Q五、基本概念和符号（续）五、基本概念和符号（续）2、多元函数及其导数(4)n元函数的Taylor展开式及中值公式：设 f(x):Rn R，二阶可导。在x*的邻域内l一阶Taylor展开式：f(x)=f(x*)+f T(x*)(x-x*)+ox-x*l二阶Taylor展开式：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*)l Lagrange余项：对x,记xx*+(x-x*)f(x)=f(x*)+f T(x*)(x-x*)+(1/2)(x-x*)T 2f(x)(x-x*)第一章 其它基础知识l复习下列知识：线性代数的有关概念：向量与矩阵的运算、向量的线性相关和线性无关，矩阵的秩，正定、半正定矩阵，线性空间等；集合的有关概念：开集、闭集，集合运算，内点、边界点等。
