《运筹学思想与运筹学建模(运筹学与最优化方法-吴祈宗)》由会员分享,可在线阅读,更多相关《运筹学思想与运筹学建模(运筹学与最优化方法-吴祈宗)(18页珍藏版)》请在金锄头文库上搜索。
1、运筹学 与最优化方法吴祈宗等编制主 要 内 容l第一章 运筹学思想与运筹学建模l第二章 基本概念和理论基础l第三章 线性规划l第四章 最优化搜索算法的结构与一维搜索l第五章 无约束最优化方法l第六章 约束最优化方法l第七章 目标规划l第八章 整数规划l第九章 层次分析法l第十章 智能优化计算简介第 一 章 运筹学思想运筹学思想 与与 运筹学建模运筹学建模第一章 运筹学思想与运筹学建模运筹学简称 OR (美)Operations Research (英)Operational Research“运筹于帷幄之中,决胜于千里之外”l三个来源:军事、管理、经济l三个组成部分: 运用分析理论、竞争理论、
2、随机服务理论一、什么是运筹学l为决策机构在对其控制下的业务活动 进行决策时,提供一门量化为基础的 科学方法。l或是一门应用科学,它广泛应用现有 的科学技术知识和数学方法,解决实 际中提出的专门问题,为决策者选择 最优决策提供定量依据。l运筹学是一种给出问题坏的答案的艺 术,否则的话,问题的结果会更坏。二、运筹学的应用原则l合伙原则:应善于同各有关人员合作l催化原则:善于引导人们改变一些常规看 法l互相渗透原则:多部门彼此渗透地考虑l独立原则:不应受某些特殊情况所左右l宽容原则:思路宽、方法多,不局限在某一特定 方法上l平衡原则:考虑各种矛盾的平衡、关系的 平衡三、运筹学解决问题的工作步骤1 )
3、提出问题:目标、约束、决策变量、参数 2 )建立模型:变量、参数、目标之间的关系 表示 3 )模型求解:数学方法及其他方法 4 )解的检验:制定检验准则、讨论与现实的 一致性 5 )灵敏性分析:参数扰动对解的影响情况 6 )解的实施:回到实践中 7 )后评估:考察问题是否得到完满解决四、运筹学模型的构造思路及评价l直 接 分 析 法l类 比 方 法l模 拟 方 法l数 据 分 析 法l试 验 分 析 法l构 想 法 模型评价:易于理解、易于探查错误、易于计算等优化模型的一般形式Opt. f ( xi, yj, k ) s.t. gh ( xi, yj, k ) , 0h = 1,2, ,m 其
4、中: xi 为决策变量(可控制)yj 为已知参数k 为随机因素f , gh 为(一般或广义)函数 建模举例(略) 自看五、基本概念和符号1、向量和子空间投影定理 (1) n维欧氏空间:Rn点(向量):x Rn, x = (x 1 ,x2 ,xn)T分量 xi R (实数集)方向(自由向量):d Rn, d 0d =(d1 ,d2 ,dn)T 表示从0指向d 的方向实用中,常用 x + d 表示从x 点出发沿d 方 向移动d 长度得到的点 d0xx+(1/2)d五、基本概念和符号(续 ) 1、向量和子空间投影定理 (2) 向量运算:x , y Rnnx , y 的内积:xTy = xiyi =
5、x1y1+ x2y2+ + xnyni =1x , 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 kx+yyx五、基本概念和符号(续 ) 1、向量和子空间投影定理 (3) 子空间:设 d (1) , d (2) , , d (m) Rn, d (k) 0m记 L( d (1) , d (2) , , d (m) )= x = j d (j) j
6、R j =1 为由向量d (1) , d (2) , , d (m) 生成的子空间,简记为L 。l正交子空间:设 L 为Rn的子空间,其正交子空间为L x Rn xTy=0 , y L l子空间投影定理:设 L 为Rn的子空间。那么 x Rn, 唯一 x L , y L, 使 z=x+y , 且 x 为问题min z - us.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
7、)若 xTy , yRn 且 y 0,则 x 0, 0 .(2)若 xTy , y L Rn ,则 x L, 0 .(特别, LRn时,x =0)l定理的其他形式: “若 xTy , yRn 且 y 0,则 x 0, 0 .” “若 xTy , yRn 且 y 0,则 x 0, 0 .” “若 xTy , yRn 且 y 0,则 x 0, 0 .” “若 xTy , y L Rn , 则 x L, 0 .”五、基本概念和符号(续 ) 2、多元函数及其导数 (1) n元函数:f (x): Rn R线性函数:f (x) = cTx + b = c i xi + b二次函数:f (x) = (1/2
8、) xTQx + cTx + b= (1/2)i j aij xi xj + ci xi + b向量值线性函数:F(x) = Ax + d Rm 其中 A为 mn矩阵,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 )TRn .线性函数:f (x) = cTx + b , f (x) = c 二次函数:f (x) = (1/2) xTQx + cTx + b f (x)
9、= 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展开式
10、及中值公式:设 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*2 l一阶中值公式:对x, , 使f (x) = f (x*)+ f (x*+(x-x*)T(x-x*) lLagrange余项:对x, , 记xx*+ (x-x*)f (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x )(x-x*) 第一章 其它基础知识l复习下列知识:线性代数的有关概念:向量与 矩阵的运算、向量的线性相关 和线性无关,矩阵的秩,正定 、半正定矩阵,线性空间等;集合的有关概念:开集、闭集 ,集合运算,内点、边界点等 。