运筹学全部课件.ppt

第1讲目录 课程简介CH0绪论CH1线性规划及单纯形法 1 1线性规划问题及其数学模型 1 2线性规划问题的解 1 3线性规划的单纯形法 1 4单纯形表 1 5单纯形法应用的几个问题 1 6线性规划建模举例 课程简介 课程性质 学科必修课先修课程 高等数学 线性代数 概率论与数理统计学分 4学时 64 1 16周 每周4学时 考核方式 闭卷考试成绩由三部分组成 理论考试成绩 80 平时成绩 含考勤 课堂纪律 课堂提问 平时作业 20 教材 胡运权主编 运筹学教程 第4版 北京 清华大学出版社 2012 11 课程简介 参考文献 1 运筹学 教材编写组编著 运筹学 北京 清华大学出版社 1990年9月 2 郭耀煌等编 运筹学原理与方法 成都 西南交通大学出版社 1994年9月 3 WAYNEL WINSTON OperationsResearch MathematicalProgramming 清华大学出版社 影印版 4 FredericS Hillier 运筹学导论 第8版 清华大学出版社 影印版 课程简介 教学目的1 使学生掌握若干运筹学的基本模型 为进一步学习IE的其它专业课程奠定基础 同时也为进一步研究IE方向之一的运筹学 OR 打下基础 2 使学生初步掌握将实际管理问题形成运筹学模型的方法与技巧 3 使学生初步具备运用软件求解重要的运筹学模型的能力 会使用所学软件解决实际的经济管理问题 4 注重理论与应用并重 兼顾以理论与方法为主的学生 以不低于研究生入学考试水平为要求 课程简介 教学要求 1 课前要预习 上课思路要跟上 课后认真完成作业 要求各位同学准备标准的作业本 认真完成案例及实验 2 基本思路 模型 算法及原理 必要时复习相关的数学知识 建模与求解 包括软件的应用 3 本课程将通过重点讲授原理方法 上机解题 个人研究与小组讨论相结合的案例分析等环节 培养学生全局优化的思想 使学生掌握若干类常用的运筹学模型 并能用其解决经济管理中的复杂问题 CH0绪论 0 1运筹学的定义 发展与应用简介 0 2运筹学与工业工程 0 3运筹学的主要分支及本课程的讲授内容 0 4运筹学研究的基本特征与基本方法 0 1运筹学的定义 发展与应用简介 1运筹学的定义 不唯一 运筹学 简称OR 美 OperationsResearch 英 OperationalResearch按照原意应译为运作研究或作战研究 运用科学的数量方法 主要是数学模型 研究对人力 物力进行合理筹划和运用 寻找管理及决策最优化的综合性学科 我国科学家把它译成 运筹学 运筹 一词出于 史记 汉高祖本纪 运筹策帷幄之中 决胜千里之外 关于OR的不同定义 它是一门基础性的应用学科 主要研究系统最优化的问题 通过对建立的模型求解 为管理人员作决策提供科学依据 运筹学是应用分析 试验 量化的方法 对经济管理系统中的人力 物力 财力等资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理 关于OR的不同定义 OperationsResearch or often managementscience meansascientificapproachtodecisionmaking whichseekstodeterminehowbesttodesignandoperateasystem usuallyunderconditionsrequiringtheallocationofscarceresources 2发展简史 运筹学思想的出现可以追溯到很早 田忌齐王赛马 对策论 孙子兵法等都体现了优化的思想 运筹学 这一名词最早出现在第二次世界大战期间 美 英等国家的作战研究小组为了解决作战中所遇到的许多错综复杂的战略 战术问题而提出的 战后这些研究成果被应用到生产 经济领域 并得到迅速发展 有关理论和方法的研究 实践不断深入 数学对运筹学的作用 是有关理论和方法的研究基础 是建立运筹学模型的工具 计算机的发展 促进运筹学的进一步发展 高速 可靠的计算是运筹学解决问题的基本保障 3应用领域 运筹学能够对经济管理系统中的人力 物力 财力等资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理 通常以最优 最佳等作为决策目标 避开最劣的方案 在军事 生产 决策 运输 存储 排队等经济管理领域有着广泛的应用 3应用领域 生产计划 生产作业的计划 日程表的编排 合理下料 配料问题 物料管理等 库存管理 多种物资库存量的管理 库存方式 库存量等 运输问题 确定最小成本的运输线路 物资的调拨 运输工具的调度以及建厂地址的选择等 3应用领域 人事管理 对人员的需求和使用的预测 确定人员编制 人员合理分配 建立人才评价体系等 市场营销 广告预算 媒介选择 定价 产品开发与销售计划制定等 3应用领域 财务和会计 包括预测 贷款 成本分析 定价 证券管理 现金管理等 其他 设备维修 更新 项目选择 评价 工程优化设计与管理等 OR应用的成功例子 0 2运筹学与工业工程 泰勒时代的IE叫传统IE或经典IE 工作研究等 现代工业工程以系统工程和运筹学为理论基础 以计算机为工具 20世纪40年代运筹学的发展丰富了工业工程的内涵 同时OR成为IE重要的研究领域 如国外大学和清华IE系 OR与IE OR IE 0 3运筹学的主要分支及本课程的讲授内容 运筹学是一门应用性学科 它主要是应用定性分析和定量分析相结合的方法 通过建立实际问题的数学模型 应用合适的优化算法对模型进行求解 从而解决实际问题 运筹学的内容很多 一般认为有以下分支 线性规划 整数规划 非线性规划 动态规划 图与网络分析 网络计划 存储论 排队论 目标规划 决策分析 对策 博弈论 等 线性规划 数学规划 非线性规划 整数规划 动态规划 学科内容 多目标规划 双层规划 组合优化 最优计数问题 网络优化 排序问题 统筹图 随机优化 对策论 排队论 库存论 决策分析 可靠性分析 运筹学的主要内容 讲授内容 教学内容CH0绪论CH1线性规划及单纯形法CH2线性规划的对偶理论与灵敏度分析CH3运输问题CH4整数规划CH5动态规划CH6图与网络方法CH7网络计划CH8目标规划CH9排队论CH10对策论CH11决策分析CH12存贮论 库存模型 0 4运筹学研究的基本特征与基本方法 1 运筹学研究的基本特点 系统的整体优化多学科的配合模型方法的应用 1 系统的整体观念系统是由相互关联 相互制约 相互作用的一些部分组成的具有某种功能的有机整体 2 多学科的综合系统常常涉及到很多领域 运筹学研究中需吸收来自不同领域 具有不同经验和技能的专家 3 模型方法的应用运筹学研究的系统往往不能搬到实验室来 代替的方法是建立这个问题的模型 运筹学解决问题的步骤1 问题的分析 2 模型的建立3 模型的求解 4 解的检验5 解的有效控制 6 方案的实施 真实系统 系统分析问题描述 模型建立与修改 模型求解与检验 结果分析与实施 数据准备 CH1线性规划及单纯形法 1 1线性规划问题及其数学模型 1 2线性规划问题的解 1 3线性规划的单纯形法 1 4单纯形表 1 5单纯形法应用的几个问题 1 6线性规划建模举例 1 1线性规划问题及其数学模型 一 线性规划问题在生产管理和经营活动中经常需要解决 如何合理地利用有限的资源 人力 物力 财力等 以得到最大的效益 生产计划问题如何合理使用有限的人力 物力和资金 使得收到最好的经济效益 如何合理使用有限的人力 物力和资金 以达到最经济的方式 完成生产计划的要求 1 1线性规划问题及其数学模型 例1 1某工厂生产A B两种产品 若生产A产品每吨需煤9吨 木材4立方米 人力3个劳动日 生产B产品每吨需煤4吨 木材5立方米 人力10个劳动日 已知A B两种产品每吨的价格分别为700元和1200元 并知该厂现有的资源为 煤360吨 木材200立方米 可提供人力300个劳动日 试问应生产A B产品各多少吨 能使该厂的产值最高 解先将题中有关数据列为下表 设计划生产A B产品分别为吨 产值为Z元 该问题的数学模型如下 称 1 1 为目标函数 1 2 1 5 为约束条件 其中s t是subjectto的缩写 可译为受约束于 这是一个典型的利润最大化的生产计划问题 其中 Max 是英文单词 Maximize 的缩写 含义为 最大化 s t 是 subjectto 的缩写 表示 满足于 因此 上述模型的含义是 在给定条件限制下 求使目标函数z达到最大的x1 x2的取值 例1 2 某工厂拥有A B C三种类型的设备 生产甲 乙两种产品 每件产品在生产中需要占用的设备机时数 每件产品可以获得的利润以及三种设备可利用的时数如下表所示 问题 工厂应如何安排生产可获得最大的总利润 目标函数Maxz 1500 x1 2500 x2约束条件s t 3x1 2x2 652x1 x2 403x2 75x1 x2 0 线性规划模型的三要素 3 约束条件 为实现优化目标需受到的限制 用决策变量的等式或不等式表示 1 决策变量 需决策的量 即待求的未知数 2 目标函数 需优化的量 即欲达的目标 用决策变量的表达式表示 例1 营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量 55克蛋白质和800毫克的钙 如果市场上只有四种食品可供选择 它们每千克所含的热量和营养成分和市场价格见下表 问如何选择才能在满足营养的前提下使购买食品的费用最小 各种食物的营养成分表 解 设xj为第j种食品每天的购入量 则配餐问题的线性规划模型为 minS 14x1 6x2 3x3 2x4s t 1000 x1 800 x2 900 x3 200 x4 300050 x1 60 x2 20 x3 10 x4 55400 x1 200 x2 300 x3 500 x4 800 x1 x2 x3 x4 0 以上例题的共同特征 每一个问题都用一组决策变量表示某一方案 这组决策变量的值就代表一个具体方案 一般这些变量取值是非负的 存在一定的约束条件 这些约束条件用一组线性等式或不等式来表示 都有一个要达到的目标 它可用决策变量的线性函数即目标函数来表示 按问题的不同 要求目标函数实现最大化或最小化 由于目标函数和约束条件都是自变量的线性函数 故称这各规划问题为线性规划问题 其他典型问题 合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题 二 线性规划的数学模型 Max Min z c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 s t 在线性规划的数学模型中有 目标函数 约束条件 决策变量的非负约束条件 线性规划问题隐含的假定 比例性假定 决策变量变化引起的目标函数的改变量和决策变量的改变量成比例 同样 每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例 可加性假定 每个决策变量对目标函数和约束方程的影响是独立于其他变量的 目标函数值是每个决策变量对目标函数贡献的总和 连续性假定 线性规划问题中的决策