运筹学思想与运筹学建模(运筹学与最优化方法-吴祈宗).ppt

运筹学与最优化方法 吴祈宗等编制 主要内容 第一章运筹学思想与运筹学建模第二章基本概念和理论基础第三章线性规划第四章最优化搜索算法的结构与一维搜索第五章无约束最优化方法第六章约束最优化方法第七章目标规划第八章整数规划第九章层次分析法第十章智能优化计算简介 第一章 运筹学思想与运筹学建模 第一章运筹学思想与运筹学建模 运筹学 简称OR 美 Operation sResearch 英 OperationalResearch 运筹于帷幄之中 决胜于千里之外 三个来源 军事 管理 经济三个组成部分 运用分析理论 竞争理论 随机服务理论 一 什么是运筹学 为决策机构在对其控制下的业务活动进行决策时 提供一门量化为基础的科学方法 或是一门应用科学 它广泛应用现有的科学技术知识和数学方法 解决实际中提出的专门问题 为决策者选择最优决策提供定量依据 运筹学是一种给出问题坏的答案的艺术 否则的话 问题的结果会更坏 二 运筹学的应用原则 合伙原则 应善于同各有关人员合作催化原则 善于引导人们改变一些常规看法互相渗透原则 多部门彼此渗透地考虑独立原则 不应受某些特殊情况所左右宽容原则 思路宽 方法多 不局限在某一特定方法上平衡原则 考虑各种矛盾的平衡 关系的平衡 三 运筹学解决问题的工作步骤 1 提出问题 目标 约束 决策变量 参数2 建立模型 变量 参数 目标之间的关系表示3 模型求解 数学方法及其他方法4 解的检验 制定检验准则 讨论与现实的一致性5 灵敏性分析 参数扰动对解的影响情况6 解的实施 回到实践中7 后评估 考察问题是否得到完满解决 四 运筹学模型的构造思路及评价 直接分析法类比方法模拟方法数据分析法试验分析法构想法模型评价 易于理解 易于探查错误 易于计算等 优化模型的一般形式 Opt f xi yj k s t gh xi yj k 0h 1 2 m其中 xi为决策变量 可控制 yj为已知参数 k为随机因素f gh为 一般或广义 函数建模举例 略 自看 五 基本概念和符号 1 向量和子空间投影定理 1 n维欧氏空间 Rn点 向量 x Rn x x1 x2 xn T分量xi R 实数集 方向 自由向量 d Rn d 0d d1 d2 dn T表示从0指向d的方向实用中 常用x d表示从x点出发沿d方向移动 d长度得到的点 d 0 x x 1 2 d 五 基本概念和符号 续 1 向量和子空间投影定理 2 向量运算 x y Rnnx y的内积 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 点列的收敛 设点列 x k Rn x Rn点列 x k 收敛到x 记limx k x lim x k x 0 limxi k xi ik k k x y y x 五 基本概念和符号 续 1 向量和子空间投影定理 3 子空间 设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 正交子空间 设L为Rn的子空间 其正交子空间为L x Rn xTy 0 y L 子空间投影定理 设L为Rn的子空间 那么 x Rn 唯一x L y L 使z x y 且x为问题min z u s t u L的唯一解 最优值为 y 特别 L Rn时 正交子空间L 0 零空间 五 基本概念和符号 续 规定 x y Rn x y xi yi i类似规定x y x y xy 一个有用的定理设x Rn R L为Rn的线性子空间 1 若xTy y Rn且y 0 则x 0 0 2 若xTy y L Rn 则x L 0 特别 L Rn时 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 五 基本概念和符号 续 2 多元函数及其导数 1 n元函数 f x Rn R线性函数 f x cTx b cixi b二次函数 f x 1 2 xTQx cTx b 1 2 i jaijxixj cixi b向量值线性函数 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 五 基本概念和符号 续 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 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线性函数 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 的邻域内一阶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余项 对x 记x x x x f x f