运筹学第一章-引言PPT课件

第一章绪论 一 学科介绍二 基本概念和基本理论 一 学科介绍 夫运筹帷幄之中 决胜于千里之外 汉书 运筹学 管理科学 一 学科介绍 一 起源Lanchester 1914 人力与火力优势与胜利之间的关系 Edison 商船运行战略 Erlang 1910 电话交换机排队系统 运筹学小组 1939 英国 美国 运筹学的历史 应用科学管理方法管理盟国战事 一 学科介绍 二 创建阶段 1945 1954 主要成果 G B Dantzing提出的线性规划单纯形法 1947年 英 美 法成立 OR 学会MIT 1948 首开 运筹学 课 里程碑 三 成长阶段 1955 现在 特点 1 理论发展迅速 20个分支 2 计算机发展的推动 3 在世界范围内的普及 一 学科介绍 OperationsResearch 美国 简称OROperationalResearch 英国 作业研究 港台 运筹学 大陆 管理科学 ManagementScience 简称MS 一 学科介绍 运筹学的定义 Morse和Kimball的定义为决策机构在对其控制下业务活动进行决策时 提供以数量化为基础的科学方法 其他定义运筹学应用科学技术和数学方法 解决专门问题 为决策者选择最优决策提供定量依据 一 学科介绍 OR MS的应用 生产管理交通网络存储管理市场营销项目评价军事方面等等 一 学科介绍 Manyrealworldexamples许多实际问题举例 实际问题 BreakevenpointAnalysis盈亏平衡分析Resource allocation资源分配Newproductpricing新产品定价决策Portfolioselection投资组合Salesforecasting销售量预测Supplychainnetworkdesign供应链网络设计 一 学科介绍 BreakevenpointAnalysis盈亏平衡分析 实际问题 特殊产品公司生产在商店销售的昂贵而不常见的礼品 礼品是为那些已经几乎什么都有的富人生产的 公司研发部最新的产品计划是有限版落地摆钟 limitededitiongrand fatherclock 公司管理部门需要决定是否生产这个新产品 如果生产的话要生产多少 我们需要知道些什么信息 一 学科介绍 Resource allocation资源分配 实际问题 潘得罗索工业公司生产胶合板 根据厚度和所用木材的质量而有所不同 因为产品在一个竞争的环境中进行销售 产品的价格由市场决定 所以每个月管理层面临的一个关键问题是选择产品组合以获取尽可能多的利润 需要考虑当前生产产品必须的各种资源的可得数量 六项最重要的资源为 1 四种类型的原木 根据原木的质量区分 和 2 生产胶合板的两项关键作业的生产能力 模压作业和刨光作业 你们公司有这样的经历吗 一 学科介绍 Newproductpricing新产品定价决策 实际问题 新产品定价的基本方法 成本加成法 竞争者定价 市场定价法 一 学科介绍 Portfolioselection投资组合 实际问题 比尔是Nesbit投资公司的财务主管 他必须组合长期市场有价证券的业务量的每月支付计划 证券业务量的金额高达 50 000 000 组合此业务量的有价证券必须很快确定下来 在风险控制限度内 以使得一定时限内的收益最大 我国证券市场什么时候需要呢 一 学科介绍 Supplychainnetworkdesign供应链网络设计 实际问题 上海国美电器商场有限公司在上海的商场为什么圆形布点 围绕上海市外环线内部圆形均匀分布着9家商场 为什么只有一个配送中心 为什么要建在外环线的外面 你对这个问题如何分析 一 学科介绍 OR MS的本质 管理科学 Managementscience 是对与定量因素 quantitativefactors 有关的管理问题通过应用科学的方法 scientificapproach 进行辅助管理决策制定 aidmanagerialdecisionmaking 的一门学科 discipline 管理者制定决策管理科学运用合理的分析来改善决策的制定 一 学科介绍 SystematicSteps系统化步骤 定义问题和收集数据构建模型 一般为数学模型 从模型中形成求解的计算机的程序测试模型并在必要时进行修正应用模型分析问题以及提出管理建议帮助实施被管理者采纳的小组建议 一 学科介绍 WhatisData ModelandDecisions数据模型与决策是什么 管理者在组织内制定决策 数据 模型与决策的目的是在科学 符合逻辑和合理的基础上制定决策 内容主要是管理科学和统计学 一 学科介绍 ScientificApproach科学的方法 一 学科介绍 ImpactofManagementScience管理科学的影响 改善全世界大量组织的效率提高国家的经济生产力促进商业运作的规范性节约大量稀有的资源 为管理科学实践者颁发的最负盛名的奖项是弗兰茨 厄德曼 FranzEdelman 奖 这些奖项授予全世界年度管理科学的最佳应用 一 学科介绍 经典管理科学获奖应用 联合航空公司 1 2 1986 600万 满足乘客需求以最低成本进行订票处和机场工作班次排程Citgo石油公司 1 2 1987 7000万 优化炼油运作以及产品的供应 配送和营销旧金山警署 1 2 1989 1100万 用计算机系统最优排程和巡警设置荷玛特发展公司 1 2 1987 4000万 商业区和办公楼销售的最优化安排AT T 1 2 1990 4 06亿 更多的销售 为公司商业用户的电话销售中心的优化选址 美国石油公司 12 1982 1000万 确定和评价公司产品商业化的新战略美国邮政服务公司 3 4 1987 1 2 1992 2亿 邮件自动化方案的技术经济分析标准品牌公司 12 1981 380万 控制100种成品的库存 安全库存 再订购点和订购量 IBM 1 2 1990 2000万 2 5亿库存降低 整合备件库存的全国网络以改进服务支持HydroelectricaEspanol 1 2 1990 200万 应用统计预测管理水力发电的水库系统施乐公司 11 1975 生产率提高50 以上 缩短反应时间和改进维修人员生产率的维修战略修正 经典管理科学获奖应用 宝洁公司 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 美洲航空公司 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 课程体系内容 规划论线性规划 较深入 非线性规划多目标规划整数规划动态规划图与网络分析 排队论存储论对策论决策论系统仿真方法智能优化算法 主要内容 第一章绪论 学科简述 第二章基本概念和理论基础第三章线性规划深入与发展第四章非线性规划第五章多目标规划第六章动态规划与马氏决策规划第七章排队论第八章智能优化计算简介 主要教材和参考文献 1 运筹学 运筹学 教材编写组 清华大学出版社2 OperationsResearch ApplicationsandAlgoritions W L Winston 3 IntroductiontoManagementScience FrederickS Hillier GeraldJ Lieberman4 最优化理论与算法 陈宝林清华大学出版社5 运筹学 上册 下册 21世纪普通高等学校管理科学与工程教材 徐渝 何正文编著 清华大学出版社6 运筹学与最优化方法 普通高等学校研究生教材 吴祈宗主编机械工业出版社7 运筹学 吉林大学研究生立项教材 郭立夫主编 吉林大学出版社 理论与应用 深度与广度 相关论文讨论与应用案例分析 教学要求 考核方式 作业 案例研究报告 40 考试 60 二 几个数学概念和基本理论 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行向量 fi 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 x fT x x x 1 2 x x T 2f x x x 三 凸集 凸函数和凸规划 一 凸集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 的线段 凸集 非凸集 非凸集 一 凸集1 凸集的概念 例 证明集合S x Ax b 是凸集 其中 A为m n矩阵 b为m维向量 凸组合 设x 1 x 2 x m Rn j 0mm j 1 那么称 jx j 为x 1 x 2 x m 的j 1j 1凸组合 m比较 z jx j j 1 j R 构成线性组合 线性子空间 j 0 j 0 构成半正组合 凸锥 j 0 j 1 构成凸组合 凸集 定理 S是凸集 S中任意有限点的凸组合属于S 一 凸集2 凸集的性质 凸集凸集的交集是凸集 并 的内点集是凸集 逆命题是否成立 凸集的闭包是凸集 逆命题是否成立 分离与支撑 凸集边界上任意点存在支撑超平面两个互相不交的凸集之间存在分离超平面 支撑 强分离 分离 非正常分离 一 凸集3 凸锥 定义 C Rn 若x C 0有 x C 则称C是以0为顶点的锥 如果C还是凸集 则称为凸锥 集合 0 Rn是凸锥 命题 C是凸锥 C中任意有限点的半正组合属于S 0 一 凸集4 多面体 极点 极方向 1 多面集 有限个半闭空间的交S x Rn Ax b x 0 称为多面集 有界的多面集称为多面体 2 多面体的极点 顶点 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 多面集S x Rn 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 1x 1 2x 2 kx k 1d 1 2d 2 ld l 二 凸函数1 凸函数及水平集定义 设集合S Rn为凸集 函数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 为凹函数 严格凹函数 严格凸函数 凸函数 严格凹函数 二 凸函数1 凸函数及水平集 定理 f x 为凸集S上的凸函数 S上任意有限点的凸组合的函数值不大于各点函数值的凸组合 思考 设f1 f2是凸函数 设 1 2 0 1f1 2f2 1f1 2f2是否凸函数 f x max f1 x f2 x g x min f1 x f2 x 是否凸函数 二 凸函数1 凸函数及水平集 定义 设集合S Rn 函数f S R R 称S x S f x 为f x 在S上的 水平集 定理 设集合S Rn是凸集 函数f S R是凸函数 则对 R S 是凸集 注 水平集的概念相当于在地形图中 海拔高度不高于某一数值的区域 上述定理的逆不真 考虑分段函数f x 1 x 0 或0 x 0 函数非凸 但任意水平集是凸集 二 凸函数2 凸函数的性质 方向导数 设S Rn为非空凸集 函数f S R 再设x S d为方向 使当 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 二 凸函数2 凸函数的性质 以下设S Rn为非空凸集 函数f S R2 若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 fT x x x x S 5 设S是开集 f在S上二次可微 则a f凸 x S 2f x 半正定 b 若 x S 2f x 正定 则f严格凸 二 凸函数2 凸函数的性质 例 f x x12 2x1