第1章-运筹学思想与运筹学建模-筹学与最优化方法-课件.ppt
运筹学运筹学与最优化方法与最优化方法吴祈宗等编制吴祈宗等编制主主要要内内容容l第一章第一章 运筹学思想与运筹学建模运筹学思想与运筹学建模l第二章第二章 基本概念和理论基础基本概念和理论基础l第三章第三章 线性规划线性规划l第四章第四章 最优化搜索算法的结构与一维搜索最优化搜索算法的结构与一维搜索l第五章第五章 无约束最优化方法无约束最优化方法l第六章第六章 约束最优化方法约束最优化方法l第七章第七章 目标规划目标规划l第八章第八章 整数规划整数规划l第九章第九章 层次分析法层次分析法l第十章第十章 智能优化计算简介智能优化计算简介第第 一一 章章 运筹学思想运筹学思想与与运筹学建模运筹学建模第一章第一章 运筹学思想与运筹学建模运筹学思想与运筹学建模运筹学运筹学简称简称 OR（美）（美）Operations Research（英）（英）Operational Research“运筹于帷幄之中，决胜于千里之外运筹于帷幄之中，决胜于千里之外”l三个来源：军事、管理、经济三个来源：军事、管理、经济l三个组成部分：三个组成部分：运用分析理论、竞争理论、随机服务理论运用分析理论、竞争理论、随机服务理论二、运筹学的应用原则二、运筹学的应用原则1)合伙原则：应善于同各有关人员合作合伙原则：应善于同各有关人员合作2)催化原则：善于引导人们改变一些常规看催化原则：善于引导人们改变一些常规看法法3)互相渗透原则：多部门彼此渗透地考虑互相渗透原则：多部门彼此渗透地考虑4)独立原则：不应受某些特殊情况所左右独立原则：不应受某些特殊情况所左右5)宽容原则：思路宽、方法多，不局限在某一特定宽容原则：思路宽、方法多，不局限在某一特定方法上方法上6)平衡原则：考虑各种矛盾的平衡、关系的平衡原则：考虑各种矛盾的平衡、关系的平衡平衡三、运筹学解决问题的工作步骤三、运筹学解决问题的工作步骤1 1）提出问题：目标、约束、决策变量、参数）提出问题：目标、约束、决策变量、参数2 2）建立模型：变量、参数、目标之间的关系）建立模型：变量、参数、目标之间的关系表示表示3 3）模型求解：数学方法及其他方法）模型求解：数学方法及其他方法4 4）解的检验：制定检验准则、讨论与现实的）解的检验：制定检验准则、讨论与现实的一致性一致性5 5）灵敏性分析：参数扰动对解的影响情况）灵敏性分析：参数扰动对解的影响情况6 6）解的实施：回到实践中）解的实施：回到实践中7 7）后评估：考察问题是否得到完满解决）后评估：考察问题是否得到完满解决四、运筹学模型的构造思路及评价四、运筹学模型的构造思路及评价1.直直 接接 分分 析析 法法2.类类 比比 方方 法法3.模模 拟拟 方方 法法4.数数 据据 分分 析析 法法5.试试 验验 分分 析析 法法6.构构 想想 法法模型评价模型评价:易于理解、易于探查错误、易于计算等易于理解、易于探查错误、易于计算等五、基本概念和符号五、基本概念和符号1 1、向量和子空间投影定理、向量和子空间投影定理(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)d五、基本概念和符号（续）五、基本概念和符号（续）五、基本概念和符号（续）五、基本概念和符号（续）1 1、向量和子空间投影定理、向量和子空间投影定理(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+yyx五、基本概念和符号（续）五、基本概念和符号（续）五、基本概念和符号（续）五、基本概念和符号（续）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.(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、多元函数及其导数、多元函数及其导数(2)(2)梯度（一阶偏导数向量）：梯度（一阶偏导数向量）：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=AT五、基本概念和符号（续）五、基本概念和符号（续）五、基本概念和符号（续）五、基本概念和符号（续）2 2、多元函数及其导数、多元函数及其导数(3)Hesse(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第一章第一章 其它基础知识其它基础知识l复习下列知识：复习下列知识：线性代数的有关概念：向量与矩线性代数的有关概念：向量与矩阵的运算、向量的线性相关和线阵的运算、向量的线性相关和线性无关，矩阵的秩，正定、半正性无关，矩阵的秩，正定、半正定矩阵，线性空间等；定矩阵，线性空间等；集合的有关概念：开集、闭集，集合的有关概念：开集、闭集，集合运算，内点、边界点等。集合运算，内点、边界点等。
