- 1、下载文档前请自行甄别文档内容的完整性,平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益,请联系客服反馈,我们会尽快为您处理(人工客服工作时间:9:00-18:30)。
一、什么是运筹学
为决策机构在对其控制下的业务活动进
行决策时,提供一门量化为基础的科学 方法。 或是一门应用科学,它广泛应用现有的 科学技术知识和数学方法,解决实际中 提出的专门问题,为决策者选择最优决 策提供定量依据。 运筹学是一种给出问题坏的答案的艺术, 否则的话,问题的结果会更坏。
复习下列知识:
线性代数的有关概念:向量与矩 阵的运算、向量的线性相关和线 性无关,矩阵的秩,正定、半正 定矩阵,线性空间等; 集合的有关概念:开集、闭集, 集合运算,内点、边界点等。
n
五、基本概念和符号(续)
2、多元函数及其导数
(1) n元函数:f (x): 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 m 向量值线性函数:F(x) = Ax + d R 其中 A为 mn矩阵,d为m维向量 T F(x)=( f1(x), f2(x), … , fm(x) ) 记 aiT为A的第i行向量,f(x) = aiTx
二、运筹学的应用原则
1)
2)
3) 4)
5)
合伙原则:应善于同各有关人员合作 催化原则:善于引导人们改变一些常规看 法 互相渗透原则:多部门彼此渗透地考虑 独立原则:不应受某些特殊情况所左右
宽容原则:思路宽、方法多,不局限在某一特定 方法上
6)
平衡原则:考虑各种矛盾的平衡、关系的 平衡
三、运筹学解决问题的工作步骤
n
五、基本概念和符号(续)
2、多元函数及其导数
(2) 梯度(一阶偏导数向量): T n f (x)=( f / x1 , f / x2 , … , f / xn ) R . 线性函数:f (x) = cTx + b , f (x) = c 二次函数:f (x) = (1/2) xTQx + cTx + b f (x) = Qx + c m 向量值线性函数:F(x) = Ax + d R F / x = AT
k 为随机因素
f , gh 为(一般或广义)函数 建模举例(略)—— 自看
五、基本概念和符号
1、向量和子空间投影定理
(1) n维欧氏空间:R n T 点(向量):x R , x = (x1 ,x2 ,…,xn) 分量 xi R (实数集) n 方向(自由向量):d R , d 0 T d =(d1 ,d2 ,…,dn) 表示从0指向d 的方向 实用中,常用 x + d 表示从x 点出发沿d 方向 移动d 长度得到的点
f (x) = f (x*)+ [f (x*+(x-x*))]T(x-x*)
Lagrange余项:对x, , 记xx*+ (x-x*)
T T 2
f (x) = f (x*)+ f (x)(x-x*) + (1/2)(x-x*) f (x )(x-x*)
第一章 其它基础知识
“若 xTy ≤ , yRn 且 y ≤ 0,则 x ≥ 0, ≥ 0 .” “若 xTy ≥ , yRn 且 y ≥ 0,则 x ≥ 0, ≤ 0 .” n “若 xTy ≥ , yR 且 y ≤ 0,则 x ≤ 0, ≤ 0 .” “若 xTy ≥ , y L Rn , 则 x L, ≤ 0 .”
(1)
(2)
(m)
五、基本概念和符号(续)
规定:x , y R ,x ≤ y xi ≤ yi ,i 类 似规定 x ≥ y,x = y,x < y , x > y . 一个有用的定理 n n 设 xR ,R,L为R 的线性子空间, Ty ≤ , yRn 且 y ≥ 0, (1)若 x 则 x ≤ 0, ≥ 0 . Ty ≤ , y L R n , (2)若 x n 则 x L , ≥ 0 .(特别, L=R 时,x =0) 定理的其他形式:
d x+(1/2)d 0 x
n
五、基本概念和符号(续)
1、向量和子空间投影定理
(2) 向量运算:x , y R
n
x,y
的内积:xTy
= i =1 xiyi = x1y1+ x2y2+ …+ xnyn
(1/2)
n
x , y 的距离: ‖x-y ‖= [(x-y)T(x-y)] (1/2) x 的长度: ‖x‖= [ xTx ] 三角不等式: ‖x + y ‖≤‖x‖+‖y‖
1)提出问题:目标、约束、决策变量、参数 2)建立模型:变量、参数、目标之间的关系表示 3)模型求解:数学方法及其他方法 4)解的检验:制定检验准则、讨论与现实的一致性 5)灵敏性分析:参数扰动对解的影响情况 6)解的实施:回到实践中 7)后评估:考察问题是否得到完满解决
四、运筹学模型的构造思路及评价
第
一
章
运筹学思想 与 运筹学建模
第一章 运筹学思想与运筹学建模
运筹学—简称 OR (美)Operation`s Research (英)Operational Research “运筹于帷幄之中,决胜于千里之外” 三个来源:军事、管理、经济 三个组成部分: 运用分析理论、竞争理论、随机服务理论
五、基本概念和符号(续)
2、多元函数及其导数
(3) Hesse 阵(二阶偏导数矩阵): f (x)=
2
2f /x1 2 2f /x1 x2
… 2f /x1 xn
2f /x2 x1 … 2f /xn x1 2f /x22
… 2f /x2 xn
… 2f /xn x2 … … … 2f /xn2
最优化理论与学思想与运筹学建模 第二章 基本概念和理论基础 第三章 线性规划 第四章 最优化搜索算法的结构与一维搜索 第五章 无约束最优化方法 第六章 约束最优化方法 第七章 目标规划 第八章 整数规划 第九章 层次分析法 第十章 智能优化计算简介
2
线性函数:f (x) = +b, f (x) = 0 TQx + cTx + b, 2f (x)=Q 二次函数:f (x) = (1/2) x c Tx
五、基本概念和符号(续)
2、多元函数及其导数
(4)n元函数的Taylor展开式及中值公式:
n
设 f (x): R R ,二阶可导。在x* 的邻域内
直接分析法 2. 类 比 方 法 3. 模 拟 方 法 4. 数 据 分 析 法 5. 试 验 分 析 法 6. 构 想 法 模型评价:
1.
易于理解、易于探查错误、易于计算等
优化模型的一般形式
Opt. f ( xi, yj, k ) s.t. gh ( xi, yj, k ) , 0 h = 1,2, … ,m 其中: xi 为决策变量(可控制) yj 为已知参数
(1)
,d
(2)
,…,d
(m) m
R, d
(j)
n
(k)
0
记 L( d
(1)
,d
(2)
,…,d
(m)
)={ x = =1 j d j
jR }
为由向量d , d , … , d 生成的子空间,简记为L。 n 正交子空间:设 L 为R 的子空间,其正交子空间为 n L ={ x R xTy=0 , y L } n n 子空间投影定理:设 L 为R 的子空间。那么 x R , 唯一 x L , y L , 使 z=x+y , 且 x 为问题 min ‖z - u‖ s.t. u L 的唯一解,最优值为‖y‖。 n 特别, L =R 时,正交子空间 L ={ 0 }(零空间)
一阶Taylor展开式:
f (x) = f (x*)+ f T(x*)(x-x*) + o‖x-x*‖
二阶Taylor展开式: 一阶中值公式:对x, , 使
f (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x*)(x-x*) + o‖x-x*‖2
x x+y
点列的收敛:设点列{x(k)} R , x R 点列{x(k)}收敛到 x ,记 lim x(k) = x k lim‖x(k)- x‖ = 0 lim xi(k) = xi ,i k k
y
n
n
五、基本概念和符号(续)
1、向量和子空间投影定理
(3) 子空间:设 d