资源描述
第一章 绪论一、学科介绍一、学科介绍二、基本概念和基本理论二、基本概念和基本理论1一、学科介绍一、学科介绍2制定策略、策划制定策略、策划“夫夫运筹运筹帷幄之中，决胜于千里之外帷幄之中，决胜于千里之外”汉书汉书运筹学运筹学管理科学管理科学一、学科介绍一、学科介绍一、起源Lanchester(1914)：人力与火力优势与胜利之间的关系。Edison：商船运行战略。Erlang（1910）：电话交换机排队系统。运筹学小组（1939）：英国，美国。运筹学的历史运筹学的历史应用科学管理方法管理盟国战事应用科学管理方法管理盟国战事一、学科介绍一、学科介绍4二、创建阶段（19451954）主要成果：G.B.Dantzing提出的线性规划单纯形法（1947年）。英、美、法成立“OR”学会MIT（1948）：首开“运筹学”课。“里程碑里程碑”三、成长阶段（三、成长阶段（1955现在）现在）特点：（特点：（1）理论发展迅速。）理论发展迅速。20个分支。个分支。（2）计算机发展的推动。）计算机发展的推动。（3）在世界范围内的普及。）在世界范围内的普及。一、学科介绍一、学科介绍lOperations Research(美国美国)简称简称ORlOperational Research(英国英国)l作业研究作业研究(港台港台)l运筹学运筹学(大陆大陆)l管理科学管理科学 （Management Science，简称，简称MS）一、学科介绍一、学科介绍 运筹学的定义Morse 和 Kimball 的定义为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。其他定义运筹学应用科学技术和数学方法，解决专门问题，为决策者选择最优决策提供定量依据。一、学科介绍一、学科介绍7OR/MS 的应用一、学科介绍一、学科介绍Many real world examples许多实际问题举例许多实际问题举例实际问题实际问题 Breakeven point Analysis 盈亏平衡分析盈亏平衡分析 Resource-allocation 资源分配资源分配 New product pricing 新产品定价决策新产品定价决策 Portfolio selection 投资组合投资组合 Sales forecasting 销售量预测销售量预测 Supply chain network design 供应链网络设计供应链网络设计一、学科介绍一、学科介绍9Breakeven point Analysis盈亏平衡分析盈亏平衡分析 实际问题实际问题特殊产品公司生产在商店销售的昂贵而不常见的特殊产品公司生产在商店销售的昂贵而不常见的礼品，礼品是为那些已经几乎什么都有的富人生礼品，礼品是为那些已经几乎什么都有的富人生产的。公司研发部最新的产品计划是有限版产的。公司研发部最新的产品计划是有限版落地落地摆钟（摆钟（limited edition grandfather clock）。）。公司公司管理部门需要决定是否生产这个新产品，如果生管理部门需要决定是否生产这个新产品，如果生产的话要生产多少。产的话要生产多少。我们需要知道些什么信息？我们需要知道些什么信息？想想看！想想看！一、学科介绍一、学科介绍10Resource-allocation资源分配资源分配实际问题实际问题潘得罗索工业公司生产胶合板，根据厚度和所用木潘得罗索工业公司生产胶合板，根据厚度和所用木材的质量而有所不同。因为产品在一个竞争的环境材的质量而有所不同。因为产品在一个竞争的环境中进行销售，产品的价格由市场决定。所以每个月中进行销售，产品的价格由市场决定。所以每个月管理层面临的一个关键问题是选择产品组合以获取管理层面临的一个关键问题是选择产品组合以获取尽可能多的利润。需要考虑当前生产产品必须的各尽可能多的利润。需要考虑当前生产产品必须的各种资源的可得数量。六项最重要的资源为（种资源的可得数量。六项最重要的资源为（1）四）四种类型的原木（根据原木的质量区分）和（种类型的原木（根据原木的质量区分）和（2）生）生产胶合板的两项关键作业的生产能力（模压作业和产胶合板的两项关键作业的生产能力（模压作业和刨光作业）。刨光作业）。你们公司有这样的经历吗？你们公司有这样的经历吗？一、学科介绍一、学科介绍11New product pricing新产品定价决策新产品定价决策实际问题实际问题 新产品定价的基本方法新产品定价的基本方法 v 成本加成法成本加成法 v 竞争者定价竞争者定价 v 市场定价法市场定价法一、学科介绍一、学科介绍12Portfolio selection投资组合投资组合实际问题实际问题比尔是比尔是Nesbit投资公司的财务主管，他必须组合投资公司的财务主管，他必须组合长期市场有价证券的业务量的每月支付计划。证长期市场有价证券的业务量的每月支付计划。证券业务量的金额高达券业务量的金额高达$50,000,000。组合此业务量。组合此业务量的有价证券必须很快确定下来，在风险控制限度的有价证券必须很快确定下来，在风险控制限度内，以使得一定时限内的收益最大。内，以使得一定时限内的收益最大。我国证券市场什么时候需要呢？我国证券市场什么时候需要呢？一、学科介绍一、学科介绍13Supply chain network design 供应链网络设计供应链网络设计实际问题实际问题上海国美电器商场有限公司在上海的商场为什么上海国美电器商场有限公司在上海的商场为什么圆形布点？围绕上海市外环线内部圆形均匀分布圆形布点？围绕上海市外环线内部圆形均匀分布着着9家商场，为什么只有一个配送中心，为什么家商场，为什么只有一个配送中心，为什么要建在外环线的外面？要建在外环线的外面？你对这个问题如何分析！你对这个问题如何分析！一、学科介绍一、学科介绍14OR/MS的本质的本质管理科学（管理科学（Management science）是对与）是对与定量定量因素（因素（quantitative factors）有关的管理问题通有关的管理问题通过应用过应用科学的方法（科学的方法（scientific approach）进行进行辅助管理决策制定（辅助管理决策制定（aid managerial decision making）的一门的一门学科（学科（discipline）。管理者管理者管理者管理者 制定决策制定决策制定决策制定决策管理科学管理科学管理科学管理科学 运用合理的分析来改善决策的制定运用合理的分析来改善决策的制定运用合理的分析来改善决策的制定运用合理的分析来改善决策的制定一、学科介绍一、学科介绍15Systematic Steps系统化步骤系统化步骤 定义问题和收集数据定义问题和收集数据 构建模型构建模型(一般为数学模型一般为数学模型)从模型中形成求解的计算机的程序从模型中形成求解的计算机的程序 测试模型并在必要时进行修正测试模型并在必要时进行修正 应用模型分析问题以及提出管理建议应用模型分析问题以及提出管理建议 帮助实施被管理者采纳的小组建议帮助实施被管理者采纳的小组建议 一、学科介绍一、学科介绍16What is Data,Model and Decisions 数据模型与决策是什么数据模型与决策是什么结论结论决策决策执行执行结果结果管理者管理者信息提供信息提供模型模型反馈反馈管理者在组织内制定决策，数据、模型与决策的目的管理者在组织内制定决策，数据、模型与决策的目的是在科学、符合逻辑和合理的基础上制定决策。内容是在科学、符合逻辑和合理的基础上制定决策。内容主要是管理科学和统计学。主要是管理科学和统计学。一、学科介绍一、学科介绍17Scientific Approach科学的方法科学的方法问题的确定问题的确定分析问题分析问题建立模型建立模型软件求解软件求解结果分析结果分析确定解决方案确定解决方案实施方案实施方案控制控制一、学科介绍一、学科介绍18Impact 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亿，更多收入）亿，更多收入）设计票价结构、订票和协调航班的系统来增加收入设计票价结构、订票和协调航班的系统来增加收入 LLBean公司公司（1-2/1991，$950万）万）为一个大型呼叫中心优化配置电话干线、接收台和电话代理为一个大型呼叫中心优化配置电话干线、接收台和电话代理 纽约市纽约市（1-2/1993，$950万）万）详细检查从传讯到被捕的程序以缩短等待时间详细检查从传讯到被捕的程序以缩短等待时间 AT&T（1-2/1993，$7.5亿）亿）为指导商业用户设计呼叫中心开发基于计算机的系统为指导商业用户设计呼叫中心开发基于计算机的系统管理科学获奖应用（管理科学获奖应用（1990 ）23课程体系内容规划论规划论 线性规划线性规划线性规划线性规划（较深入）（较深入）（较深入）（较深入）非线性规划非线性规划非线性规划非线性规划 多目标规划多目标规划多目标规划多目标规划整数规划整数规划 动态规划动态规划动态规划动态规划图与网络分析图与网络分析排队论排队论排队论排队论存储论存储论存储论存储论对策论对策论对策论对策论决策论决策论决策论决策论系统仿真方法系统仿真方法智能优化算法智能优化算法智能优化算法智能优化算法主要内容l第一章第一章 绪论（学科简述）绪论（学科简述）l第二章第二章 基本概念和理论基础基本概念和理论基础l第三章第三章 线性规划深入与发展线性规划深入与发展l第四章第四章 非线性规划非线性规划l第五章第五章 多目标规划多目标规划l第六章第六章 动态规划与马氏决策规划动态规划与马氏决策规划l第七章第七章 排队论排队论l第八章第八章 智能优化计算简介智能优化计算简介25主要教材和参考文献:1、运筹学运筹学 运筹学运筹学教材编写组，清华大学出版社教材编写组，清华大学出版社2 2、Operations Research:Applications and AlgoritionsOperations Research:Applications and Algoritions.W.L.W.L.Winston,Winston,3 3、Introduction to Management Science Frederick S.Hillier,Introduction to Management Science Frederick S.Hillier,Gerald J.LiebermanGerald J.Lieberman4 4、最优化理论与算法最优化理论与算法陈宝林清华大学出版社陈宝林清华大学出版社5 5、运筹学运筹学（上册、下册）（上册、下册）（2121世纪普通高等学校管理科学与世纪普通高等学校管理科学与工程教材）徐渝、何正文编著，清华大学出版社工程教材）徐渝、何正文编著，清华大学出版社6 6、运筹学与最优化方法运筹学与最优化方法（普通高等学校研究生教材）吴祈宗（普通高等学校研究生教材）吴祈宗主编主编 机械工业出版社机械工业出版社7 7、运筹学运筹学（吉林大学研究生立项教材）郭立夫主编，吉林大（吉林大学研究生立项教材）郭立夫主编，吉林大学出版社学出版社26理论与应用深度与广度深度与广度+相关论文讨论与应用案例分析相关论文讨论与应用案例分析教学要求教学要求:考核方式：考核方式：作业、案例研究报告（作业、案例研究报告（作业、案例研究报告（作业、案例研究报告（40%40%40%40%）考试（考试（考试（考试（60%60%60%60%）27二、几个数学概念二、几个数学概念和基本理论和基本理论281 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)d291 1、向量和子空间投影定理、向量和子空间投影定理(2)(2)向量运算：向量运算：x,y R Rn n n x,y 的内积：的内积：xTy=xiyi=x1y1+x2y2+xnyn i=1 x,y 的距离：的距离：xy=(xy)T(xy)(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+yyx301 1、向量和子空间投影定理、向量和子空间投影定理(3)(3)子空间：子空间：设设 d(1),d(2),d(m)R Rn n,d(k)0 m 记记 L L(d(1),d(2),d(m)=)=x=j d(j)j R j=1为由向量为由向量d(1),d(2),d(m)生成的子空间，简记为生成的子空间，简记为L L。l正交子空间：设正交子空间：设 L 为为R Rn n的的子空间，其正交子空间为子空间，其正交子空间为 L x R Rn n xTy=0,y L l子空间投影定理：子空间投影定理：设设 L 为为R Rn n的的子空间。那么子空间。那么 x R Rn n，唯一唯一 x L,y L,使使 z=x+y,且且 x 为问题为问题 min z u s.t.u L 的唯一解，最优值为的唯一解，最优值为y。l特别，特别，L R Rn n 时，正交子空间时，正交子空间 L 0（零空间零空间）31l规定：规定：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.”322 2、多元函数及其导数、多元函数及其导数(1)(1)n n元函数：元函数：f(x):):R Rn n 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 向量值线性函数：向量值线性函数：F(x)=Ax+d R Rm m其中其中 A为为 m n矩阵，矩阵，d为为m维向量维向量 F(x)=(f1(x),f2(x),fm(x)T 记记 aiT为为A的第的第i行向量，行向量，fi(x)=aiTx332 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=AT342 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)=Q352 2、多元函数及其导数、多元函数及其导数(4)(4)n n元函数的元函数的TaylorTaylor展开式及中值公式：展开式及中值公式：设设 f(x):):R Rn n R R ，二阶可导。在二阶可导。在x*的邻域内的邻域内l一阶一阶TaylorTaylor展开式：展开式：f(x)=f(x*)+f T(x*)(xx*)+oxx*l二阶二阶TaylorTaylor展开式：展开式：f(x)=f(x*)+f T(x)(xx*)+(1/2)(xx*)T 2f(x*)(xx*)+oxx*2l一阶中值公式：对一阶中值公式：对x,使使 f(x)=f(x*)+f(x*+(xx*)T(xx*)lLagrange余项：余项：对对x,记记x x*+(xx*)f(x)=f(x*)+f T(x)(xx*)+(1/2)(xx*)T 2f(x )(xx*)36三、凸集、凸函数三、凸集、凸函数和凸规划和凸规划37一、凸集一、凸集1、凸集的概念：、凸集的概念：定义：设集合定义：设集合 S Rn，若若 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、凸集的概念：、凸集的概念：l例例:证明集合证明集合 S=x Ax=b 是凸集。其中，是凸集。其中，A为为 m n矩阵，矩阵，b为为m维向量。维向量。l凸组合：凸组合：设设 x(1),x(2),x(m)R Rn n,j 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 构成线性组合构成线性组合 线性子空间线性子空间 j0,j 0 构成半正组合构成半正组合 凸锥凸锥 j0,j=1 构成凸组合构成凸组合 凸集凸集定理：定理：S是凸集是凸集S中任意有限点的凸组合属于中任意有限点的凸组合属于S。39一、凸集一、凸集 2、凸集的性质：、凸集的性质：1)凸集凸集的交集是凸集；凸集凸集的交集是凸集；（并？）（并？）2)的内点集是凸集；的内点集是凸集；（逆命题是否成立？）（逆命题是否成立？）3)凸集的闭包是凸集。凸集的闭包是凸集。（逆命题是否成立？）（逆命题是否成立？）4)分离与支撑：分离与支撑：凸集边界上任意点存在支撑超平面凸集边界上任意点存在支撑超平面 两个互相不交的凸集之间存在分离超平面两个互相不交的凸集之间存在分离超平面支撑支撑强分离强分离分离分离非正常非正常分离分离40一、一、凸集凸集 3、凸锥：、凸锥：l定义：定义：C Rn,若若 x C,0 有有 x C,则称则称 C 是以是以 0 为顶点的锥。如果为顶点的锥。如果 C 还是凸集，则还是凸集，则称为凸锥。称为凸锥。l集合集合 0、Rn 是凸锥。是凸锥。l命题：命题：C是凸锥是凸锥C中任意有限点的半正组合属于中任意有限点的半正组合属于S041一、凸集一、凸集一、凸集一、凸集 4、多面体、极点、极方向、多面体、极点、极方向1）多面集：有限个半闭空间的交）多面集：有限个半闭空间的交 S=x Rn Ax b,x0 称为多面集。有界的多面集称为多面体。称为多面集。有界的多面集称为多面体。422)多面体的极点（顶点）：多面体的极点（顶点）：x S，不存在，不存在 S 中的另外两个点中的另外两个点x(1)和和x(2)，及及 (0,1)，使，使 x=x(1)+(1-)x(2).3)方向：方向：x S,d Rn,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 Rn Ax b,x0 的极点和极方向的极点和极方向定理定理1（表示定理）设（表示定理）设S为非空为非空多面集，则有：多面集，则有：（1）极点集非空，且存在有限个极点）极点集非空，且存在有限个极点 x(1),x(2),x(k)。（2）极方向集合为空集的充要条件是）极方向集合为空集的充要条件是S有界。若有界。若S无界，无界，则存在有限个极方向则存在有限个极方向d(1),d(2),d(l)。（3）对于）对于 x S，i0，且，且1+2+k=1,j0,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 Rn 为凸集，函数为凸集，函数 f:SR 若若 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 上的严格凸函数。上的严格凸函数。l当当-f(x)为凸函数（严格凸函数）时，则称为凸函数（严格凸函数）时，则称 f(x)为为凹函数（严格凹函数）。凹函数（严格凹函数）。严格凸函数严格凸函数凸函数凸函数严格凹函数严格凹函数45二、凸函数二、凸函数 1、凸函数及水平集：、凸函数及水平集：l定理：定理：f(x)为凸集为凸集 S 上的凸函数上的凸函数 S 上任上任意有限点的凸组合的函数值不大于各点函意有限点的凸组合的函数值不大于各点函数值的凸组合。数值的凸组合。l思考：设思考：设f1,f2是凸函数，是凸函数，1)设设 1,2 0,1f1+2f2,1f1-2f2是否凸函是否凸函数？数？2)f(x)=max f1(x),f2(x),g(x)=min f1(x),f2(x)是否凸函数？是否凸函数？46二、凸函数二、凸函数 1、凸函数及水平集：、凸函数及水平集：l定义：定义：设集合设集合 S Rn，函数，函数 f:SR，R，称称 S =x S f(x)为为 f(x)在在 S 上上 的的 水平集水平集。l定理：定理：设集合设集合 S Rn 是凸集，函数是凸集，函数 f:SR是是凸函数，则对凸函数，则对 R，S 是凸集是凸集。l注：注：1)水平集的概念相当于在地形图中，海拔高度不高于某一水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。数值的区域。2)上述定理的逆不真。上述定理的逆不真。考虑分段函数考虑分段函数f(x)=1(x0)或或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*)Td .48二、凸函数二、凸函数 2、凸函数的性质：、凸函数的性质：以下设以下设 S Rn 为非空凸集，函数为非空凸集，函数 f:SR2）若）若f 凸，则凸，则 f 在在 S 的内点集上连续；的内点集上连续；注：注：f 在在 S 上不一定连续。上不一定连续。例例:f(x)2(当当 x=1)；f(x)x2(当当 x 1).3）设）设f 凸，则对任意方向方向导数存在。凸，则对任意方向方向导数存在。4）设）设 S 是开集，是开集，f 在在 S 上可微，则上可微，则 f凸凸 x*S，有，有f(x)f(x*)+f T(x*)(xx*),x S.5)设设 S 是开集，是开集，f 在在 S 上二次可微，则上二次可微，则 a)f 凸凸 x S，2f(x)半正定；半正定；b)若若 x S，2f(x)正定，则正定，则f f严格凸。严格凸。49二、凸函数二、凸函数 2、凸函数的性质：、凸函数的性质：l例：例：1)f(x)x12+2x1x2+2x22+10 x1 4；2)f(x)-3x12+x1x2x222x322x2x3+26;3)f(x)3x12+ax1x2+2x224x1+6 (a=5,4.5)；50三、凸规划三、凸规划1 1、数学规划模型的一般形式、数学规划模型的一般形式 min min f(x)-目标函数目标函数 s.t.s.t.x S-约束集合，可行集约束集合，可行集其中，其中，S R Rn n，f:S R R，x S称（称（f S)的可行解的可行解l最优解最优解:x*S，满足满足f(x*)f(x),x S。则称则称 x*为为(f S)的全局最优解的全局最优解(最优解最优解),),记记 g.opt.(global optimum),),简记简记 opt.l最优值最优值:x*为为(f S)的最优解的最优解,则称则称 f*=f(x*)为为 (f S)的最优值的最优值(最优目标函数值最优目标函数值)(f S)511 1、数学规划模型的一般形式（续）、数学规划模型的一般形式（续）l局部最优解局部最优解:x*S，x*的邻域的邻域 N(x*)，使满足，使满足 f(x*)f(x),x S N(x*)。则称则称 x*为为(f S)的局的局部最优解部最优解,记记 l.opt.(local optimum)l在上述定义中，当在上述定义中，当x x*时有严格不等式成立，时有严格不等式成立，则则分别称分别称 x*为为(f S)的严格全局最优解和严格局部最的严格全局最优解和严格局部最优解。优解。严格严格l.opt.严格严格g.opt.l.opt.52l函数形式函数形式:f(x),gi(x),hj(x):RnR min f(x)(fgh)s.t.gi(x)0 ,i=1,2,m hj(x)=0 ,j=1,2,ll矩阵形式矩阵形式:min f(x)，f(x):RnR(fgh)s.t.g(x)0 ,g(x):RnRm h(x)=0 ,h(x):RnRl 当当 f(x),gi(x),hj(x)均为线性函数时，称线性均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。规划；若其中有非线性函数时，称非线性规划。1 1、数学规划模型的一般形式（续）、数学规划模型的一般形式（续）532 2、凸规划：、凸规划：l当（当（f S）中，）中，S为凸集，为凸集，f是是S上的凸函数上的凸函数（求（求minmin），称（），称（f S）为凸规划；）为凸规划；l对于（对于（fgh）,f,gf,gi i为凸函数，为凸函数，h hj j为线性函为线性函数时，（数时，（fghfgh）为凸规划。）为凸规划。l定理：定理：设集合设集合 S Rn 为凸集，函数为凸集，函数 f:SRf(x)为凸集为凸集 S 上的凸函数。上的凸函数。X*为问题（为问题（fs）的的l.opt，则，则X*为为g.opt；又如果；又如果f是是严格凸函数，严格凸函数，那么那么X*是（是（fs）的唯一）的唯一g.opt。54
展开阅读全文