资源描述
,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第一章 绪论,一、学科介绍,二、基本概念和基本理论,1,一、学科介绍,2,制定策略、策划,“,夫,运筹,帷幄之中，决胜于千里之外”,汉书,运筹学,管理科学,一、学科介绍,一、起源,Lanchester (1914),：人力与火力优势与胜利之间的关系。,Edison,：商船运行战略。,Erlang,（,1910,）：电话交换机排队系统。,运筹学小组（,1939,）：英国，美国。,运筹学的历史,应用科学管理方法管理盟国战事,一、学科介绍,4,二、创建阶段（,19451954,）,主要成果：,G.B.Dantzing,提出的线性规划单纯形法（,1947,年）。,英、美、法成立“,OR”,学会,MIT,（,1948,）：首开“运筹学”课。,“,里程碑”,三、成长阶段（,1955,现在）,特点：（,1,）理论发展迅速。,20,个分支。,（,2,）计算机发展的推动。,（,3,）在世界范围内的普及。,一、学科介绍,Operations Research (,美国,),简称,OR,Operational Research(,英国,),作业研究,(,港台,),运筹学,(,大陆,),管理科学,（,Management Science,，简称,MS,）,一、学科介绍,运筹学的定义,Morse,和,Kimball,的定义,为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。,其他定义,运筹学应用科学技术和数学方法，解决专门问题，为决策者选择最优决策提供定量依据。,一、学科介绍,7,OR/MS,的应用,生产管理,交通网络,存储管理,市场营销,项目评价,军事方面,等等,一、学科介绍,Many real world examples,许多实际问题举例,实际问题,Breakeven point Analysis,盈亏平衡分析,Resource-allocation,资源分配,New product pricing,新产品定价决策,Portfolio selection,投资组合,Sales forecasting,销售量预测,Supply chain network design,供应链网络设计,一、学科介绍,9,Breakeven point Analysis,盈亏平衡分析,实际问题,特殊产品公司生产在商店销售的昂贵而不常见的礼品，礼品是为那些已经几乎什么都有的富人生产的。公司研发部最新的产品计划是有限版,落地摆钟（,limited edition grandfather clock,）。,公司管理部门需要决定是否生产这个新产品，如果生产的话要生产多少。,我们需要知道些什么信息？,想想看！,一、学科介绍,10,Resource-allocation,资源分配,实际问题,潘得罗索工业公司生产胶合板，根据厚度和所用木材的质量而有所不同。因为产品在一个竞争的环境中进行销售，产品的价格由市场决定。所以每个月管理层面临的一个关键问题是选择产品组合以获取尽可能多的利润。需要考虑当前生产产品必须的各种资源的可得数量。六项最重要的资源为（,1,）四种类型的原木（根据原木的质量区分）和（,2,）生产胶合板的两项关键作业的生产能力（模压作业和刨光作业）。,你们公司有这样的经历吗？,一、学科介绍,11,New product pricing,新产品定价决策,实际问题,新产品定价的基本方法,成本加成法,竞争者定价,市场定价法,一、学科介绍,12,Portfolio selection,投资组合,实际问题,比尔是,Nesbit,投资公司的财务主管，他必须组合长期市场有价证券的业务量的每月支付计划。证券业务量的金额高达,$50,000,000,。组合此业务量的有价证券必须很快确定下来，在风险控制限度内，以使得一定时限内的收益最大。,我国证券市场什么时候需要呢？,一、学科介绍,13,Supply chain network design,供应链网络设计,实际问题,上海国美电器商场有限公司在上海的商场为什么圆形布点？围绕上海市外环线内部圆形均匀分布着,9,家商场，为什么只有一个配送中心，为什么要建在外环线的外面？,你对这个问题如何分析！,一、学科介绍,14,OR / MS,的本质,管理科学（,Management science,）是对与,定量因素（,quantitative factors,）,有关的管理问题通过应用,科学的方法（,scientific approach,）,进行,辅助管理决策制定（,aid managerial decision making,）,的一门,学科（,discipline,）,。,管理者,制定决策,管理科学,运用合理的分析来改善决策的制定,一、学科介绍,15,Systematic Steps,系统化步骤,定义问题和收集数据,构建模型,(,一般为数学模型,),从模型中形成求解的计算机的程序,测试模型并在必要时进行修正,应用模型分析问题以及提出管理建议,帮助实施被管理者采纳的小组建议,一、学科介绍,16,What is Data, Model and Decisions,数据模型与决策是什么,结论,决策,执行,结果,管理者,信息提供,模型,反馈,管理者在组织内制定决策，数据、模型与决策的目的,是在科学、符合逻辑和合理的基础上制定决策。内容,主要是管理科学和统计学。,一、学科介绍,17,Scientific Approach,科学的方法,问题的确定,分析问题,建立模型,软件求解,结果分析,确定解决方案,实施方案,控制,一、学科介绍,18,Impact of Management Science,管理科学的影响,改善全世界大量组织的效率,提高国家的经济生产力,促进商业运作的规范性,节约大量稀有的资源,为管理科学实践者颁发的最负盛名的奖项是,弗兰茨,厄德曼,(Franz Edelman),奖。这些奖项授予全世界年度,管理科学的最佳应用。,一、学科介绍,19,经典管理科学获奖应用,联合航空公司,（,1-2/1986,，,$600,万）,满足乘客需求以最低成本进行订票处和机场工作班次排程,Citgo,石油公司,（,1-2/1987,，,$7000,万）,优化炼油运作以及产品的供应、配送和营销,旧金山警署,（,1-2/1989,，,$1100,万）,用计算机系统最优排程和巡警设置,荷玛特发展公司,（,1-2/1987,，,$4000,万）,商业区和办公楼销售的最优化安排,AT&T,（,1-2/1990,，,$4.06,亿，更多的销售）,为公司商业用户的电话销售中心的优化选址,20,美国石油公司,（,12/1982,，,$1000,万）,确定和评价公司产品商业化的新战略,美国邮政服务公司,（,3-4/1987,1-2/1992,，,$2,亿）,邮件自动化方案的技术经济分析,标准品牌公司,（,12/1981,，,$380,万）,控制,100,种成品的库存（安全库存、再订购点和订购量）,IBM,（,1-2/1990,，,$2000,万,+$2.5,亿库存降低）,整合备件库存的全国网络以改进服务支持,Hydroelectrica Espanol,（,1-2/1990,，,$200,万）,应用统计预测管理水力发电的水库系统,施乐公司,（,11/1975,生产率提高,50%,以上）,缩短反应时间和改进维修人员生产率的维修战略修正,经典管理科学获奖应用,21,宝洁公司,（,1-2/1997,，,$2,亿）,重新设计生产和分销系统以降低成本和改进市场进入速度,南非国防部,（,1-2/1997,，,$11,亿）,国防设施和武器系统规模和状态的重新优化设计,数字设备公司,（,1-2/1995,，,$8,亿）,重构供应商、工厂、分销中心、潜在厂址和市场区域供应链,雷诺德金属制品公司,（,1-2/1991,，,$700,万）,自动化超过,200,个工厂、仓库和供应商的货物装载调度系统,中国政府,（,1-2/1995,，,$4.25,亿）,为满足国家未来能源需求的大型项目的优选和排程,Delta,航空公司,（,1-2/1994,，,$1,亿）,超过,2,，,500,个国内航线的飞机类型配置来最大化利润,管理科学获奖应用（,1990 ,）,22,美洲航空公司,（,1-2/1991,，,$2000,万）,为机组人员和服务人员优化配置航行支线的顺序,Merit,青铜制品公司,（,1-2/1993,，更佳的服务）,安装统计销售预测和成品库存管理系统来改进客户服务,美洲航空公司,（,1-2/1992,，,$5,亿，更多收入）,设计票价结构、订票和协调航班的系统来增加收入,L,L,Bean,公司,（,1-2/1991,，,$950,万）,为一个大型呼叫中心优化配置电话干线、接收台和电话代理,纽约市,（,1-2/1993,，,$950,万）,详细检查从传讯到被捕的程序以缩短等待时间,AT&T,（,1-2/1993,，,$7.5,亿）,为指导商业用户设计呼叫中心开发基于计算机的系统,管理科学获奖应用（,1990 ,）,23,课程体系内容,规划论,线性规划（较深入）,非线性规划,多目标规划,整数规划,动态规划,图与网络分析,排队论,存储论,对策论,决策论,系统仿真方法,智能优化算法,主要内容,第一章 绪论（学科简述）,第二章 基本概念和理论基础,第三章 线性规划深入与发展,第四章 非线性规划,第五章 多目标规划,第六章 动态规划与马氏决策规划,第七章 排队论,第八章 智能优化计算简介,25,主要教材和参考文献,:,1,、,运筹学, ,运筹学,教材编写组，清华大学出版社,2,、,Operations Research: Applications and Algoritions,. W. L. Winston,3,、,Introduction to Management Science Frederick S. Hillier, Gerald J. Lieberman,4,、,最优化理论与算法,陈宝林清华大学出版社,5,、,运筹学,（上册、下册）（,21,世纪普通高等学校管理科学与工程教材）徐渝、何正文编著，清华大学出版社,6,、,运筹学与最优化方法,（普通高等学校研究生教材）吴祈宗主编 机械工业出版社,7,、,运筹学,（吉林大学研究生立项教材）郭立夫主编，吉林大学出版社,26,理论与应用,深度与广度,+,相关论文讨论与应用案例分析,教学要求,:,考核方式：,作业、案例研究报告（,40%,）,考试（,60%,）,27,二、几个数学概念,和基本理论,28,1,、向量和子空间投影定理,(1),n,维欧氏空间：,R,n,点（向量）,：,x,R,n,x,= (,x,1,x,2,x,n,),T,分量,x,i,R,(,实数集,),方向（自由向量）,：,d,R,n,d, 0,d,=(,d,1,d,2,d,n,),T,表示从,0,指向,d,的方向,实用中，常用,x +,d,表示从,x,点出发沿,d,方向移动,d,长度得到的点,d,0,x,x+(1/2)d,29,1,、向量和子空间投影定理,(2),向量运算：,x , y,R,n,n,x , y,的内积：,x,T,y =,x,i,y,i,= x,1,y,1,+ x,2,y,2,+ + x,n,y,n,i =1,x , y,的距离：,x-y,= (,x-y,),T,(,x-y,),(1/2),x,的长度：,x,= ,x,T,x,(1/2),三角不等式,：,x + y,x,y,点列的收敛：,设点列,x,(,k,),R,n,x,R,n,点列,x,(,k,),收敛到,x,，,记,lim,x,(,k,),=,x,lim,x,(,k,),- x,= 0,lim,x,i,(,k,),=,x,i,i,k,k,k,x+y,y,x,30,1,、向量和子空间投影定理,(3),子空间：,设,d,(,1,), d,(,2,), , d,(,m,),R,n,d,(,k,),0,m,记,L,(,d,(,1,), d,(,2,), , d,(,m,),)=,x =,j,d,(,j,),j,R,j =1,为由向量,d,(,1,), d,(,2,), , d,(,m,),生成的子空间，简记为,L,。,正交子空间：设,L,为,R,n,的,子空间，其正交子空间为,L,x,R,n,x,T,y,=0 ,y,L,子空间投影定理：,设,L,为,R,n,的,子空间。那么,x,R,n,，, 唯一,x,L,y,L,使,z,=,x,+,y,且,x,为问题,min ,z - u,s.t.,u,L,的唯一解，最优值为,y,。,特别，,L,R,n,时，正交子空间,L,0,（,零空间,）,31,规定：,x , y,R,n,，,x,y,x,i,y,i,，,i,类似规定,x,y,，,x = y,，,x y .,一个有用的定理,设,x,R,n,，,R,，,L,为,R,n,的线性子空间，,(1),若,x,T,y,y,R,n,且,y,0,，,则,x, 0,，,0,.,(2),若,x,T,y,y,L,R,n,，,则,x,L,，,0,.,(,特别,L,R,n,时,x,=0,),定理的其他形式：,“,若,x,T,y,y,R,n,且,y,0,，,则,x, 0,，,0,.”,“,若,x,T,y,y,R,n,且,y,0,，,则,x, 0,，,0,.”,“,若,x,T,y,y,R,n,且,y,0,，,则,x, 0,，,0,.”,“,若,x,T,y,y,L,R,n,，,则,x,L,，,0,.”,32,2,、多元函数及其导数,(1),n,元函数：,f,(,x,):,R,n,R,线性函数,：,f (x) = c,T,x + b =, c,i,x,i,+,b,二次函数,：,f (x) = (1/2) x,T,Qx + c,T,x + b,= (1/2),i,j,a,ij,x,i,x,j,+, c,i,x,i,+,b,向量值线性函数：,F(x) = Ax + d,R,m,其中,A,为,m,n,矩阵，,d,为,m,维向量,F(x)=(,f,1,(x), f,2,(x), , f,m,(x),),T,记,a,i,T,为,A,的第,i,行向量，,f,i,(x) = a,i,T,x,33,2,、多元函数及其导数,(2),梯度（一阶偏导数向量）：,f,(,x,),(, f / x,1, f / x,2, , f / x,n,),T,R,n,.,线性函数,：,f (x) = c,T,x + b ,f (x) = c,二次函数,：,f (x) = (1/2) x,T,Qx + c,T,x + b,f (x) = Qx + c,向量值线性函数：,F(x) = Ax + d,R,m, F / x = A,T,34,2,、多元函数及其导数,(3) Hesse,阵（二阶偏导数矩阵）：,2,f /,x,1,2,2,f /,x,2,x,1, ,2,f /,x,n,x,1,2,f,(,x,)=,2,f /,x,1,x,2,2,f /,x,2,2, ,2,f /,x,n,x,2, ,2,f /,x,1,x,n,2,f /,x,2,x,n, ,2,f /,x,n,2,线性函数,：,f (x) = c,T,x + b ,2,f (x) =,0,二次函数,：,f (x) = (1/2) x,T,Qx + c,T,x + b,2,f (x)=Q,35,2,、多元函数及其导数,(4),n,元函数的,Taylor,展开式及中值公式：,设,f,(,x,):,R,n,R,，,二阶可导。在,x*,的邻域内,一阶,Taylor,展开式：,f (x) = f (x*)+,f,T,(x*)(x-x*) + o,x-x*,二阶,Taylor,展开式：,f (x) = f (x*)+,f,T,(x)(x-x*) + (,1/2,)(x-x*),T,2,f (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 (x*)+,f,T,(x)(x-x*) + (,1/2,)(x-x*),T,2,f (x,)(x-x*),36,三、凸集、凸函数和凸规划,37,一、凸集,1,、凸集的概念：,定义：设集合,S,R,n,，,若,x,(1),x,(2),S,0,1,，必有,x,(1),(1-,),x,(2),S,，则称,S,为凸集。,规定：单点集,x,为凸集，空集,为凸集。,注,:,x,(1),(1-,),x,(2),=,x,(2),(,x,(1),-,x,(2),),是连接,x,(1),与,x,(2),的线段,。,凸集,非凸集,非凸集,38,一、凸集,1,、凸集的概念：,例,:,证明集合,S,=,x,Ax = b,是凸集。其中，,A,为,m,n,矩阵，,b,为,m,维向量。,凸组合：,设,x,(,1,), x,(,2,), , x,(,m,),R,n,j,0,m,m,j,=,1,那么称,j,x,(,j,),为,x,(,1,), x,(,2,), , x,(,m,),的,j,=1 j = 1,凸组合。,m,比较,:,z =,j,x,(,j,),j =1,j,R,构成线性组合,线性子空间,j,0,j,0,构成半正组合,凸锥,j,0,j,=1,构成凸组合,凸集,定理：,S,是凸集,S,中任意有限点的凸组合属于,S,。,39,一、凸集,2,、凸集的性质：,凸集凸集的交集是凸集；,（并？）,的内点集是凸集；,（逆命题是否成立？）,凸集的闭包是凸集。,（逆命题是否成立？）,分离与支撑：,凸集边界上任意点存在支撑超平面,两个互相不交的凸集之间存在分离超平面,支撑,强分离,分离,非正常分离,40,一、,凸集,3,、凸锥：,定义：,C,R,n,若,x,C,0,有,x,C,则称,C,是以,0,为顶点的锥。如果,C,还是凸集，则称为凸锥。,集合, 0 ,、,R,n,是凸锥。,命题：,C,是凸锥,C,中任意有限点的半正组合属于,S,0,41,一、凸集,4,、多面体、极点、极方向,1,）多面集：有限个半闭空间的交,S,= ,x,R,n,Ax,b,x,0,称为多面集。有界的多面集称为多面体。,42,2),多面体的极点（顶点）：,x,S,，不存在,S,中的另外两个点,x,(1),和,x,(2),，及,(0,1),，使,x,=,x,(1),+(1-,),x,(2),.,3),方向：,x,S,d,R,n,d, 0,及, 0 ,总有,x,+,d,S,.,d,(1),=,d,(2),(,0),时，称,d,(1),和,d,(2),同方向。,4),极方向：方向,d,不能表示为两个不同方向的组合,(,d,=,d,(1),+,d,(2),) .,43,多面集,S,= ,x,R,n,Ax,b,x,0 ,的极点和极方向,定理,1,（表示定理）设,S,为非空,多面集，则有：,（,1,）极点集非空，且存在有限个极点,x,(1),x,(2), ,x,(k),。,（,2,）极方向集合为空集的充要条件是,S,有界。若,S,无界，则存在有限个极方向,d,(1),d,(2), ,d,(l),。,（,3,）对于,x,S,，,i,0,，且,1,+,2,+,k,=,1,j,0, j = 1,2,l,使,x =,1,x,(1),+,2,x,(2),+ + ,k,x,(k),+,1,d,(1),+,2,d,(2),+, +,l,d,(l),.,44,二、凸函数,1,、凸函数及水平集,定义,:,设集合,S,R,n,为凸集，函数,f,:,S,R,若 ,x,(1),x,(2),S, ( 0 , 1 ),，均有,f(x,(1),(1-,),x,(2),),f(,x,(1),)+(1-,),f(x,(2),),，,则称,f(x),为凸集,S,上的凸函数。,若进一步有上面不等式以严格不等式成立，则称,f(x),为凸集,S,上的严格凸函数。,当,-,f(x),为凸函数（严格凸函数）时，则称,f(x),为凹函数（严格凹函数）。,严格凸函数,凸函数,严格凹函数,45,二、凸函数,1,、凸函数及水平集：,定理：,f(x),为凸集,S,上的凸函数,S,上任意有限点的凸组合的函数值不大于各点函数值的凸组合。,思考：设,f,1,f,2,是凸函数，,设,1,2, 0,1,f,1,+,2,f,2,1,f,1,-,2,f,2,是否凸函数？,f(x)= max,f,1,(,x,) ,f,2,(,x,) ,g(x)= min,f,1,(,x,) ,f,2,(,x,) ,是否凸函数？,46,二、凸函数,1,、凸函数及水平集：,定义：,设集合,S,R,n,，函数,f,:,S,R,，,R,，,称,S,=,x,S,f(x),为,f(x),在,S,上,的,水平集,。,定理：,设集合,S,R,n,是凸集，函数,f,:,S,R,是凸函数，则对 ,R,，,S,是凸集,。,注：,水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。,上述定理的逆不真。,考虑分段函数,f(x)=,1,(x,0),或,0(x,0,充分小时有,x*,+,d,S,如果,lim,f(x*+,d )-f(x*),/,存在（包括, ,）, ,则称,f(x),为在点沿方向的方向导数存在，记,f (x*;d) =,lim,f(x*+,d )-f(x*),/, ,若,f(x),在,x*,可导，则,f (x*;d) =,f (x*),T,d .,48,二、凸函数,2,、凸函数的性质：,以下设,S,R,n,为非空凸集，函数,f,:,S,R,2,）若,f,凸，则,f,在,S,的内点集上连续；,注：,f,在,S,上不一定连续。,例,:,f(x),2(,当,x,=1),；,f(x),x,2,(,当,x,1) .,3,）设,f,凸，则对任意方向方向导数存在。,4,）设,S,是开集，,f,在,S,上可微，则,f,凸,x*,S,，有,f (x),f (x*)+,f,T,(x*)(x-x*),x,S .,5),设,S,是开集，,f,在,S,上二次可微，则,a),f,凸, ,x,S,，,2,f (x),半正定；,b),若,x,S,，,2,f (x),正定，则,f,严格凸。,49,二、凸函数,2,、凸函数的性质：,例：,f(x),x,1,2,+2x,1,x,2,+2x,2,2,+10x,1,- 4,；,f(x),-3,x,1,2,+x,1,x,2,-x,2,2,-2x,3,2,-2x,2,x,3,+26,;,f(x),3,x,1,2,+ax,1,x,2,+2x,2,2,-4x,1,+6 ( a=5, 4.5 ),；,50,三、凸规划,1,、数学规划模型的一般形式,min,f(x),-,目标函数,s.t.,x,S,-,约束集合，可行集,其中，,S,R,n,，,f,:,S,R,，,x,S,称（,f S,),的可行解,最优解,:,x*,S,，,满足,f (x*),f (x), ,x,S,。,则称,x*,为,(,f S,),的全局最优解,(,最优解,),记,g.opt.,(,global optimum,),简记,opt.,最优值,:,x*,为,(,f S,),的最优解,则称,f * = f (x*),为,(,f S,),的最优值,(,最优目标函数值,),( f S ),51,1,、数学规划模型的一般形式（续）,局部最优解,:,x*,S,，,x*,的邻域,N,(,x*,),，使满足,f (x*),f (x), ,x,S,N,(,x*,),。,则称,x*,为,(,f S,),的局部最优解,记,l .opt.,(,local optimum,),在上述定义中，当,x,x*,时有严格不等式成立，,则分别称,x*,为,(,f S,),的严格全局最优解和严格局部最优解。,严格,l .opt .,严格,g .opt .,l .opt .,52,函数形式,:,f(x), g,i,(x),h,j,(x),:,R,n,R,min,f(x),(,fgh,) s.t.,g,i,(x), 0 ,i = 1,2,m,h,j,(x),= 0 ,j = 1,2,l,矩阵形式,:,min,f(x),，,f(x),:,R,n,R,(,fgh,) s.t.,g(x), 0 ,g(x),:,R,n,R,m,h(x),= 0 ,h(x),:,R,n,R,l,当,f(x), g,i,(x),h,j,(x),均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。,1,、数学规划模型的一般形式（续）,53,2,、凸规划：,当（,f S,）中，,S,为凸集，,f,是,S,上的凸函数（求,min,），称（,f S,）为凸规划；,对于（,fgh,）,f,g,i,为凸函数，,h,j,为线性函数时，（,fgh,）为凸规划。,定理：,设集合,S,R,n,为凸集，函数,f,:,S,R,f(x),为凸集,S,上的凸函数。,X,*,为问题（,fs,）,的,l.opt,，则,X,*,为,g.opt,；又如果,f,是,严格凸函数，那么,X,*,是（,fs,）的唯一,g.opt,。,54,
展开阅读全文