管理运筹学：管理科学方法讲义课件

管理运筹学管理运筹学-管理科学方法管理科学方法1 1管理运筹学管理运筹学-管理科学方法管理科学方法1OR:SM2教材与参考书籍教材与参考书籍教材：教材：教材：教材：谢家平编著谢家平编著.管理运筹学：管理科学方法，管理运筹学：管理科学方法，中国人民大学出版社，中国人民大学出版社，20102010参考书：参考书：参考书：参考书：费雷德里克费雷德里克.数据、模型与决策，中国财政经济出版社，数据、模型与决策，中国财政经济出版社，20012教材与参考书籍教材：教材与参考书籍教材：OR:SM3讲授提纲讲授提纲绪绪 论论第一章第一章 线性规划线性规划第二章第二章 线性规划讨论线性规划讨论第三章第三章 对偶规划对偶规划 静态规划静态规划第四章第四章 整数规划整数规划第五章第五章 目标规划目标规划第六章第六章 动态规划动态规划 动态优化动态优化第七章第七章 网络分析网络分析第八章第八章 网络计划网络计划第九章第九章 决策分析决策分析第十章第十章 方案排序方案排序第十一章第十一章 库存控制库存控制第十二章第十二章 排队理论排队理论离散优化离散优化随机优化随机优化淡化数学算法淡化数学算法计算机求解计算机求解3讲授提纲绪讲授提纲绪 论离散优化随机优化淡化数学算法论离散优化随机优化淡化数学算法OR:SM4考核方式考核方式结课考试：结课考试：笔试笔试 每章一题每章一题 70%案例研究：案例研究：选择合适方法结合企业实际进行应用选择合适方法结合企业实际进行应用 20%平时成绩：平时成绩：上课情况上课情况 10%4考核方式结课考试：考核方式结课考试：OR:SM5管理运筹学的称谓管理运筹学的称谓管理运筹学是一门研究如何最优安排的学科。管理运筹学是一门研究如何最优安排的学科。Operations Research日本译作日本译作“运用学运用学”香港、台湾译为香港、台湾译为“作业研究作业研究”我国译作我国译作“运筹学运筹学”源于古语“运筹帷幄之中，决胜千里之外”取“运筹”二字，体现运心筹谋、策略取胜Management Science 管理科学管理科学运运用用数数学学、统统计计学学和和运运筹筹学学中中的的量量化化分分析析原原理理和和方方法法，建建立数学模型立数学模型/计算机仿真，给管理决策提供科学依据。计算机仿真，给管理决策提供科学依据。5管理运筹学的称谓管理运筹学是一门研究如何最优安排的学科。管理运筹学的称谓管理运筹学是一门研究如何最优安排的学科。OR:SM6绪绪 论论6绪绪 论一、发展历史论一、发展历史OR:SM7一、发展历史一、发展历史1.1.早期的运筹思想早期的运筹思想早期的运筹思想早期的运筹思想 齐王赛马齐王赛马 渭修皇宫渭修皇宫沈括运军粮沈括运军粮 科学管理科学管理 2.2.军事运筹学阶段军事运筹学阶段军事运筹学阶段军事运筹学阶段 20世纪世纪40年代诞生于英美年代诞生于英美1940年，英国为对付德国空军的空袭，使用了雷达，但没有科学布年，英国为对付德国空军的空袭，使用了雷达，但没有科学布局，效果不好。为解决这个问题，成立运筹学小组，称局，效果不好。为解决这个问题，成立运筹学小组，称Operational Operational ResearchResearch，意为，意为作战研究作战研究作战研究作战研究。美国和加拿大也在军队设立运筹学小组，称美国和加拿大也在军队设立运筹学小组，称Operations ResearchOperations Research，协助指挥官研究战略及战术问题。协助指挥官研究战略及战术问题。3.3.管理运筹学阶段管理运筹学阶段管理运筹学阶段管理运筹学阶段战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹学在企业管理方面的应用得到了长足进展。学在企业管理方面的应用得到了长足进展。7一、发展历史一、发展历史1.早期的运筹思想早期的运筹思想 OR:SM8企业的成功要素中：企业的成功要素中：观念意识更新观念意识更新 47人文文化人文文化 35技术优势技术优势 18决策意识的科学性决策意识的科学性成功决策成功决策正确决策正确决策二、学科作用二、学科作用 理念的重要性理念的重要性8企业的成功要素中：二、学科作用企业的成功要素中：二、学科作用 理念的重要性理念的重要性OR:SM9二、学科作用二、学科作用1.1.量化管理的重要性量化管理的重要性量化管理的重要性量化管理的重要性 管理科学是对与管理科学是对与定量因素定量因素定量因素定量因素有关的管理问题通过有关的管理问题通过应用科学应用科学应用科学应用科学的方法的方法的方法的方法进行进行辅助管理决策辅助管理决策辅助管理决策辅助管理决策的一门学科。的一门学科。目的：用科学方法分析管理问题，为管理者决策提供依据目的：用科学方法分析管理问题，为管理者决策提供依据目标：在企业经营内外环境的限制下，实现资源效用最大目标：在企业经营内外环境的限制下，实现资源效用最大组织中存在的问题定量分析定性分析评价与评估决策量化管理是第一步,它导致控制,并最终实现改进如果不能量化某些事情，那么就不能理解它如果不能理解它，那么就不能控制它如果不能控制它，那么就不能改进它 H.James Harrington定性到定量分析，数量界限的重要性：量变引起质变定性到定量分析，数量界限的重要性：量变引起质变9二、学科作用二、学科作用1.量化管理的重要性量化管理的重要性 组织中存定量分析定性分组织中存定量分析定性分OR:SM10听一场音乐会：听一场音乐会：网络订票的票价网络订票的票价500500元，不去可退票元，不去可退票情况情况1 1：在你马上要出发的时候，发现你把最近的价值：在你马上要出发的时候，发现你把最近的价值500500元的电话卡弄丢了。你是否还会去听这场音乐会？元的电话卡弄丢了。你是否还会去听这场音乐会？情况情况2 2：假设昨天花：假设昨天花500500元钱买一张今晚的音乐会取票单。元钱买一张今晚的音乐会取票单。在你出发时，发现把票单丢了。如果去听音乐会，就必在你出发时，发现把票单丢了。如果去听音乐会，就必须再花须再花500500元钱买张票，去还会不去？元钱买张票，去还会不去？二、学科作用二、学科作用 2.2.量化思考使人理性量化思考使人理性量化思考使人理性量化思考使人理性 冰淇淋实验：冰淇淋实验：一杯一杯A有有70克克，装在，装在50克克的杯子里，看上去要溢出了的杯子里，看上去要溢出了一杯一杯B是是80克克，装在，装在100克克的杯子里，看上去还没装满的杯子里，看上去还没装满 单独凭经验判断时，在相同的价格上，人们普遍选择单独凭经验判断时，在相同的价格上，人们普遍选择A 实验表明，大部分的回答者仍旧会去听实验表明，大部分的回答者仍旧会去听结果却是，大部分人回答说不去了结果却是，大部分人回答说不去了10听一场音乐会：网络订票的票价听一场音乐会：网络订票的票价500元，不去可退票二、学科元，不去可退票二、学科OR:SM11二、学科作用二、学科作用3.3.量化分析辅助决策量化分析辅助决策量化分析辅助决策量化分析辅助决策 盈亏平衡分析盈亏平衡分析40,00080,000120,000160,00004080120160200Revenue=900 xFixed costLossProfitCost=50,000+400 xxBreak-even point=100 units利润：利润：I =(P Cm Ch)Q -F策略策略1 差异化，领先者战略差异化，领先者战略策略策略2 规模化，大规模市场规模化，大规模市场策略策略3 机械化，第一利润源机械化，第一利润源策略策略4 技能化，第二利润源技能化，第二利润源策略策略5 信息化，第三利润源信息化，第三利润源11二、学科作用二、学科作用3.量化分析辅助决策量化分析辅助决策 盈亏平盈亏平OR:SM12二、学科作用二、学科作用量化辅助决策案例：盈亏平衡分析量化辅助决策案例：盈亏平衡分析例：某企业例：某企业 总销售额 1100万元 物料成本 700万元 员工工资 200万元 管理费用 100万元现在利润现在利润=100万元，目标利润万元，目标利润150万元万元利润实现的方法有：利润实现的方法有：将销售收入增加100%将员工工资减少 25%将管理费用减少 50%将物料成本减少 7.1%12二、学科作用量化辅助决策案例：盈亏平衡分析利润实现的方法二、学科作用量化辅助决策案例：盈亏平衡分析利润实现的方法OR:SM13二、学科作用二、学科作用4.4.决策意识的重要性决策意识的重要性决策意识的重要性决策意识的重要性 生产计划决策生产计划决策u一星期工作5天,每天正常工作8小时u一周作业费用：11000 (直接人工成本与间接费用)u直接人工成本：10/1h (一台机器需一位作业人员)u间接费用：人工成本2.5倍甲甲乙乙丙丙原料原料659565直直接接工时工时65分分95分分65分分直直接人工接人工121410间间接費用接費用303525总总成本成本107144100售售价价173233170利利润润668970H 18H 6H 10甲甲设备数设备数EGHFHGG20H 13E 6F 10裝配裝配E 24E 15G 7DG 14G10H 7F 10G 7G 4CBA裝配裝配H 14乙乙丙丙13二、学科作用二、学科作用4.决策意识的重要性决策意识的重要性 生产计划决策一星生产计划决策一星OR:SM14二、学科作用二、学科作用甲产品产量甲产品产量40,乙产品乙产品 80,丙产品丙产品 40利润利润=4066+8089+4070=12560 人员有限如何实现人员有限如何实现?采取什么薪酬制度采取什么薪酬制度?计件工资制，让员工自愿加班计件工资制，让员工自愿加班甲甲乙乙丙丙单位产品总单位产品总成本成本107144100单位产品单位产品售售价价173233170单位产品单位产品利利润润668970市场每周需求市场每周需求408040决策的科学性？决策的科学性？决策的科学性？决策的科学性？方方方方案案案案 一一一一14二、学科作用甲产品产量二、学科作用甲产品产量40,乙产品乙产品 80,丙产品丙产品 4OR:SM15二、学科作用二、学科作用甲产品产量甲产品产量 40,乙产品乙产品 80,丙产品丙产品 40总收入总收入=40173+80233+40170=32360原料成本原料成本=4065+8095+4065=12800营运费用营运费用=11000总利润总利润=32360-12800-11000=8560人员有限如何实现人员有限如何实现?采取什么薪酬制度采取什么薪酬制度?岗位工资制（定岗定员），让员工自觉加班岗位工资制（定岗定员），让员工自觉加班甲甲乙乙丙丙原料原料659565运营费用运营费用11000售售价价173233170市场每周需求市场每周需求408040决策的科学性？决策的科学性？决策的科学性？决策的科学性？方方方方案案案案 二二二二15二、学科作用甲产品产量二、学科作用甲产品产量 40,乙产品乙产品 80,丙产品丙产品 OR:SM16二、学科作用二、学科作用 决策的科学性？产能符合计算决策的科学性？产能符合计算决策的科学性？产能符合计算决策的科学性？产能符合计算甲甲乙乙丙丙总总成本成本107144100售售价价173233170利利润润668970乙与丙哪一个产品比较赚钱乙与丙哪一个产品比较赚钱?产品产品市场需求市场需求单位产品设备工时消耗单位产品设备工时消耗EFGH甲甲400103131乙乙8030202113丙丙401502124需求产能需求产能3000200037603240可用产能可用产能2400240048004800E是是瓶颈瓶颈16二、学科作用二、学科作用 决策的科学性？产能符合计算甲乙丙总成本决策的科学性？产能符合计算甲乙丙总成本10OR:SM17二、学科作用二、学科作用 方方方方案案案案 三三三三：计时工资，且以单位利润率高低为决策意识。：计时工资，且以单位利润率高低为决策意识。：计时工资，且以单位利润率高低为决策意识。：计时工资，且以单位利润率高低为决策意识。乙比较赚钱乙比较赚钱,假如假如80个全部生产个全部生产需用E产能2400分钟，但是E只有2400分钟可用因此只能生产80个乙(2400/30)，而丙无法生产方案：方案：甲产品甲产品 40个，乙产品个，乙产品80个，丙产品个，丙产品0个个总收入总收入=40173+80233+0170=25560 原料原料=4065+8095+065=10200，营运费用，营运费用=11000利润利润=25560-10200-11000=4360 方方方方案案案案 四四四四：计时工资，但以占用瓶颈资源大小为决策意识。：计时工资，但以占用瓶颈资源大小为决策意识。：计时工资，但以占用瓶颈资源大小为决策意识。：计时工资，但以占用瓶颈资源大小为决策意识。丙比较赚钱丙比较赚钱,优先生产优先生产40个个需用E产能600(4015)分钟剩下1800分钟,可生产60个乙(1800/30)方案：方案：甲产品甲产品 40个，乙产品个，乙产品 60个，丙产品个，丙产品 40个个总收入总收入=40173+60233+40170=27700原材料原材料=4065+6095+406540=10900，营运费用，营运费用=11000利润利润=27700-10900-11000=580017二、学科作用方案二、学科作用方案 三：计时工资，且以单位利润率高低为决策三：计时工资，且以单位利润率高低为决策OR:SM18三、学科性质三、学科性质 1.1.研究对象研究对象研究对象研究对象经济和管理活动中能用经济和管理活动中能用“数量关系数量关系”描述的描述的如运营、规划与组织管理问题如运营、规划与组织管理问题解决的理论模型和优化方法实践解决的理论模型和优化方法实践 2.2.学科特点学科特点学科特点学科特点强调科学性和定量分析强调科学性和定量分析强调应用性和实践性强调应用性和实践性强调从整体上进行把握强调从整体上进行把握 18三、学科性质三、学科性质 1.研究对象研究对象OR:SM19四、工作程序四、工作程序管理者制定决策：管理运筹学的步骤：明确问题环境分析确定目标制定准则收集资料数量关系结构分析数学模型制定决策方案选择算法求解方案优选否是方案实施持续改进识别问题识别问题量化分析量化分析建立模型建立模型软件求解软件求解结果分析结果分析确定方案确定方案实施方案实施方案控制管理者解的分析19四、工作程序管理者制定决策：管理运筹学的步骤：明确问题环四、工作程序管理者制定决策：管理运筹学的步骤：明确问题环OR:SM20五、学科体系五、学科体系 1.1.管理问题管理问题管理问题管理问题 需求预测产品的市场需求量有多大，需求类别如何，对企业盈利有何影响?生产计划在有限资源约束下，生产什么，生产多少，获利最大？资源配置需要哪些资源，如何进行最优配置，资源紧缺性如何，以什么代价获取?作业排序作业的重要次序如何，作业的顺序安排如何?市场营销广告预算、媒介选择、产品定价、销售计划等如何安排？运输问题最佳运输线路是哪条？物流配送集载如何优化？物流设施布局如何设置？设施选址运营点如何选择，需要哪些运作设施，设施如何布局?库存控制应保持多大库存量，何时应进行订货，订货批量多少为宜?项目规划项目完工工期多长为宜，哪些作业起关键性作用，资源如何分配?设备更新设备运转状况如何演进，运行可靠性如何，何时和如何更新或改造?人力资源人员需求预测，技能要求，编制与任务指派，绩效测评，留用多长时间?财务资金资金投放的数量，从何处进行融资，资金成本是多少?排队问题队列多长，有无容量限制，多少服务台为宜，能提供什么水平的服务?20五、学科体系五、学科体系 1.管理问题管理问题 需求预测产品的市场需求量有需求预测产品的市场需求量有OR:SM21五、学科体系五、学科体系2.2.学科内容学科内容学科内容学科内容 模型类型解决的典型办法线性规划在线性目标和约束条件间取得最优化结果整数规划在线性目标和约束条件间寻求整数决策最优目标规划在相对立的目标间寻得多目标妥协的满意解动态规划寻求多阶段动态系统的整体决策优化问题网络分析寻求网络路径、流量分布、网络瓶颈及其改进网络计划用各种作业和结点的网络排列来说明项目实施计划管理决策依据决策准则权衡比较备选方案的决策结果方案排序综合各方案的优势与不足寻求多指标排名次序库存模型寻求订货、存储和缺货等库存成本降至最低的经济批量统计方法从一个抽样得到普遍结果的推论和曲线拟合排队理论分析正在等待的队列特点及其运行指标仿真模拟动态观察复杂的管理问题的行为，模拟管理系统的结构关系21五、学科体系五、学科体系2.学科内容学科内容 模型类型解决的典型办法线性规模型类型解决的典型办法线性规OR:SM22五、学科体系五、学科体系3.3.学科应用学科应用学科应用学科应用管理既是科学又是艺术管理既是科学又是艺术低层管理的科学成分较多，高层管理的艺术成分较多低层管理的科学成分较多，高层管理的艺术成分较多运营管理需较多管理科学，人力资源管理需较多管理艺术运营管理需较多管理科学，人力资源管理需较多管理艺术例行管理需要较多管理科学，例外管理需要较多管理艺术例行管理需要较多管理科学，例外管理需要较多管理艺术M:管理决策问题管理决策问题MC:定量解决方法定量解决方法方案选择依据方案选择依据问题导向问题导向技术支持技术支持战略决策营销决策生产安排财务分析人力资源方案优选应用统计线性规划整数规划目标规划网络计划网络分析 决策分析动态规划管理科学管理科学：运用合理的运用合理的分析来改善分析来改善决策的制定决策的制定管理者管理者:制定决策制定决策22五、学科体系五、学科体系3.学科应用学科应用M:管理决策问题管理决策问题MC:定量定量OR:SM23六、学习要求六、学习要求 1.1.学科地位学科地位学科地位学科地位 数学技术科学管理学科基础管理运筹学管理专业课高等数学、概率统计、线性代数加工技术、工程技术、信息技术经济学原理、管理学、行为科学离散、连续，静态、动态的方法战略、运营、营销、财务、人力23六、学习要求六、学习要求 1.学科地位学科地位 数学技术科学管理学科基础管数学技术科学管理学科基础管OR:SM24六、学习要求六、学习要求经济学企业战略、公司治理会计学财务管理人力资源管理组织行为学管理科学方法支持企业B行业企业C企业A商务2商务3商务1职能b职能c职能a小组ii小组iii小组i运营管理市场营销质量管理项目管理信息管理流程管理物流管理供应链管理24六、学习要求经济学企业战略、公司治理会计学人力资源管理组六、学习要求经济学企业战略、公司治理会计学人力资源管理组OR:SM25六、学习要求六、学习要求2.如何学习如何学习重点在结合实际的应用重点在结合实际的应用发挥自己管理实践经验丰富和理论联系实际的能力发挥自己管理实践经验丰富和理论联系实际的能力强化结合实际问题建立管理优化模型的能力强化结合实际问题建立管理优化模型的能力强化解决问题的方案或模型的解的分析与应用能力强化解决问题的方案或模型的解的分析与应用能力充分借用管理运筹学教学软件充分借用管理运筹学教学软件25六、学习要求六、学习要求2.如何学习重点在结合实际的应用如何学习重点在结合实际的应用OR:SM26第第1 章章 线性规划线性规划Sub titleSub title内容提要26第第1 章章 线性规划线性规划Sub title内容提要第一节内容提要第一节 OR:SM27一、线性规划的三个要素一、线性规划的三个要素 第一节第一节 线性规划的一般模型线性规划的一般模型 决策变量决策变量决策问题待定的量值决策问题待定的量值取值要求非负取值要求非负约束条件约束条件任何管理决策问题都是限定在一定的条件下求解任何管理决策问题都是限定在一定的条件下求解把各种限制条件表示为一组等式或不等式称约束条件把各种限制条件表示为一组等式或不等式称约束条件约束条件是决策方案可行的保障约束条件是决策方案可行的保障约束条件是决策变量的线性函数约束条件是决策变量的线性函数目标函数目标函数衡量决策优劣的准则，如时间最省、利润最大、成本最低衡量决策优劣的准则，如时间最省、利润最大、成本最低目标函数是决策变量的线性函数目标函数是决策变量的线性函数有的目标要实现极大，有的则要求极小有的目标要实现极大，有的则要求极小27一、线性规划的三个要素一、线性规划的三个要素 第一节第一节 线性规划的一般模型线性规划的一般模型 决策决策OR:SM28二、线性规划模型的举例二、线性规划模型的举例 第一节第一节 线性规划的一般模型线性规划的一般模型 1 1、生产计划问题、生产计划问题例例例例.某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备备A A、B B加工，最后都需在设备加工，最后都需在设备C C上装配。经测算得到相关数据如表所上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。示。应如何制定生产计划，使总利润为最大。据市场分析，单位甲乙产品的销售价格分别为据市场分析，单位甲乙产品的销售价格分别为7373和和7575元，试确定元，试确定获利最大的产品生产计划。获利最大的产品生产计划。产品产品设备设备工时消耗工时消耗甲甲 乙乙工时成本工时成本元元/h生产能力生产能力hABC 2 0 0 2 3 420151016103228二、线性规划模型的举例二、线性规划模型的举例 第一节第一节 线性规划的一般模型线性规划的一般模型 1、OR:SM29第一节第一节 线性规划的一般模型线性规划的一般模型 (1)(1)决策变量决策变量决策变量决策变量：设设x1为甲产品的产量，为甲产品的产量，x2为乙产品的产量。为乙产品的产量。(2(2)约束条件约束条件约束条件约束条件：生产受设备能力制约，能力需求不能突破有效供给量。生产受设备能力制约，能力需求不能突破有效供给量。设备A的约束条件表达为 2 x1 16同理，设备B的加工能力约束条件表达为 2x2 10设备C的装配能力也有限，其约束条件为 3x1+4x2 32(3)(3)目标函数：目标函数：目标函数：目标函数：目标是企业利润最大化目标是企业利润最大化 max Z=3x1+5x2(4)(4)非负约束：非负约束：非负约束：非负约束：甲乙产品的产量为非负甲乙产品的产量为非负 x1 0，x2 0综上的综上的综上的综上的LPLPLPLP模型：模型：模型：模型：29第一节第一节 线性规划的一般模型线性规划的一般模型(1)决策变量：设决策变量：设x1为甲产为甲产OR:SM30二、线性规划模型的举例二、线性规划模型的举例 第一节第一节 线性规划的一般模型线性规划的一般模型 2 2、物资运输问题、物资运输问题例：例：例：例：某产品商有三个供货源某产品商有三个供货源A1、A2、A3，其经销商有，其经销商有4个（需求个（需求市场）市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及从。已知各厂的产量、各经销商的销售量及从Ai 到到Bj 的单位运费为的单位运费为Cij。为发挥集团优势，公司要统一筹划运销。为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。问题，求运费最小的调运方案。销地销地产地产地B1B2B3B4产量产量A1632550A2758420A3329730销量销量2030104030二、线性规划模型的举例二、线性规划模型的举例 第一节第一节 线性规划的一般模型线性规划的一般模型 2、OR:SM31第一节第一节 线性规划的一般模型线性规划的一般模型 (1)(1)(1)(1)决策变量：决策变量：决策变量：决策变量：设从设从Ai到到Bj的运输量为的运输量为xij，(2)(2)(2)(2)目标函数：目标函数：目标函数：目标函数：运费最小的目标函数为运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)(3)(3)(3)约束条件约束条件约束条件约束条件：产量之和等于销量之和产量之和等于销量之和,故要满足：故要满足：供应平衡条件供应平衡条件x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34=30销售平衡条件销售平衡条件x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40非负性约束非负性约束 xij0 (i=1,2,3；j=1,2,3,4)31第一节第一节 线性规划的一般模型线性规划的一般模型(1)决策变量：设从决策变量：设从Ai到到BOR:SM32二、线性规划模型的举例二、线性规划模型的举例 第一节第一节 线性规划的一般模型线性规划的一般模型 3 3、产品配比问题、产品配比问题例：例：例：例：用浓度用浓度45%和和92%的硫酸配置的硫酸配置100吨浓度吨浓度80%的硫酸。的硫酸。决策变量决策变量决策变量决策变量：取取取取45%45%和和和和92%92%的硫酸分别为的硫酸分别为的硫酸分别为的硫酸分别为 x x1 1 和和和和 x x2 2 吨吨吨吨 约束条件约束条件约束条件约束条件：求解二元一次方程组得解求解二元一次方程组得解求解二元一次方程组得解求解二元一次方程组得解 非负约束非负约束非负约束非负约束：x1 0，x2 032二、线性规划模型的举例二、线性规划模型的举例 第一节第一节 线性规划的一般模型线性规划的一般模型 3、OR:SM33第一节第一节 线性规划的一般模型线性规划的一般模型 若有若有5种不同浓度的硫酸可选种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢？会如何呢？取这取这5种硫酸分别为种硫酸分别为 x1 1、x2 2、x3 3、x4 4、x5 5 ，有，有有多少种配比方案？有多少种配比方案？何为最好？何为最好？若若5种硫酸价格分别为种硫酸价格分别为400,700,1400,1900,2500元元/t，则：，则：33第一节第一节 线性规划的一般模型线性规划的一般模型 若有若有5种不同浓度的种不同浓度的OR:SM34三、线性规划模型的特征三、线性规划模型的特征 第一节第一节 线性规划的一般模型线性规划的一般模型 1 1、模型隐含假定、模型隐含假定（1）线性化假定 函数关系式函数关系式f(x)=c1x1+c2x2+cnxn，称线性函数。，称线性函数。建模技巧：将非线性的函数进行分段线性化。建模技巧：将非线性的函数进行分段线性化。（2）同比例假定决策变量变化引起目标函数和约束方程的改变量比例。决策变量变化引起目标函数和约束方程的改变量比例。（3）可加性假定 决策变量对目标函数和约束方程的影响是独立于其他变量的。决策变量对目标函数和约束方程的影响是独立于其他变量的。目标函数值是决策变量对目标函数贡献的总和。目标函数值是决策变量对目标函数贡献的总和。（4）连续性假定 决策变量取值连续。决策变量取值连续。（5）确定性假定 所有参数都是确定的，不包含随机因素。所有参数都是确定的，不包含随机因素。34三、线性规划模型的特征三、线性规划模型的特征 第一节第一节 线性规划的一般模型线性规划的一般模型 1、OR:SM35三、线性规划模型的特征三、线性规划模型的特征 第一节第一节 线性规划的一般模型线性规划的一般模型 2 2、一般数学模型、一般数学模型 用一组非负决策变量表示的一个决策问题；用一组非负决策变量表示的一个决策问题；存在一组等式或不等式的线性约束条件；存在一组等式或不等式的线性约束条件；有一个希望达到的目标，可表示成决策变量的极值线性函数。有一个希望达到的目标，可表示成决策变量的极值线性函数。35三、线性规划模型的特征三、线性规划模型的特征 第一节第一节 线性规划的一般模型线性规划的一般模型 2、OR:SM36四、线性规划的图解方法四、线性规划的图解方法 第一节第一节 线性规划的一般模型线性规划的一般模型 1 1、线性规划的可行域、线性规划的可行域可行域：可行域：满足所有约束条件的解的集合，满足所有约束条件的解的集合，即所有约束条件共同围城的区域。即所有约束条件共同围城的区域。maxZ=3x1+5 x2 2 x1 16 2x2 10 3x1+4 x2 32 x1 0,x2 0S.t.2x1=162x2=103x1+4 x2=32x1x248103590ABCD36四、线性规划的图解方法四、线性规划的图解方法 第一节第一节 线性规划的一般模型线性规划的一般模型 1、OR:SM372x1=162x2=10 x1x248103583x1+4 x2=320ABCD四、线性规划的图解方法四、线性规划的图解方法 第一节第一节 线性规划的一般模型线性规划的一般模型 2 2、线性规划的最优解、线性规划的最优解目标函数目标函数 Z=3x1+5 x2 代表以代表以 Z 为参数的一族平行线。为参数的一族平行线。Z=30Z=37Z=15372x1=162x2=10 x1x248103583x1OR:SM38四、线性规划的图解方法四、线性规划的图解方法 第一节第一节 线性规划的一般模型线性规划的一般模型 3 3、线性规划解的特性、线性规划解的特性abcd由线性不等式组成的可行域是凸多边形由线性不等式组成的可行域是凸多边形(凸多边形是凸集凸多边形是凸集)凸集定义：集合内部任意两点连线上的点都属于这个集合凸集定义：集合内部任意两点连线上的点都属于这个集合可行域有有限个顶点。可行域有有限个顶点。目标函数最优值一定在可行域的边界达到，而不可能在目标函数最优值一定在可行域的边界达到，而不可能在其区域的内部。其区域的内部。38四、线性规划的图解方法四、线性规划的图解方法 第一节第一节 线性规划的一般模型线性规划的一般模型 3、OR:SM39五、线性规划解的可能性五、线性规划解的可能性第一节第一节 线性规划的一般模型线性规划的一般模型 1、唯一最优解：只有一个最优点、唯一最优解：只有一个最优点2、多重最优解：无穷多个最优解、多重最优解：无穷多个最优解当市场价格下降到当市场价格下降到7474元，其数学模型变为元，其数学模型变为 2x1=162x2=103x1+4 x2=32x1x248102580 0A AB BC CD DZ=24Z=32Z=1239五、线性规划解的可能性第一节五、线性规划解的可能性第一节 线性规划的一般模型线性规划的一般模型 1、唯、唯OR:SM40五、线性规划解的可能性五、线性规划解的可能性第一节第一节 线性规划的一般模型线性规划的一般模型 3、无界解：可行域无界，目标值无限增大、无界解：可行域无界，目标值无限增大 (缺乏必要约束缺乏必要约束)40五、线性规划解的可能性第一节五、线性规划解的可能性第一节 线性规划的一般模型线性规划的一般模型 3、无、无OR:SM41五、线性规划解的可能性五、线性规划解的可能性第一节第一节 线性规划的一般模型线性规划的一般模型 4、没有可行解：线性规划问题的可行域是空集、没有可行解：线性规划问题的可行域是空集 (约束条件相互矛盾约束条件相互矛盾)目标冲突目标冲突利害冲突利害冲突目标强冲突目标强冲突利害弱冲突利害弱冲突41五、线性规划解的可能性第一节五、线性规划解的可能性第一节 线性规划的一般模型线性规划的一般模型 4、没、没OR:SM42一、线性规划的标准型式一、线性规划的标准型式 第二节第二节 线性规划的一般模型线性规划的一般模型 1 1、标准型表达方式、标准型表达方式(1)(1)代数式代数式 (2)(2)向量式向量式 (3)(3)矩阵式矩阵式 A：技术系数矩阵，简称系数矩阵；：技术系数矩阵，简称系数矩阵；B：可用的资源量，称资源向量；：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；：决策变量对目标的贡献，称价值向量；X：决策向量。：决策向量。42一、线性规划的标准型式一、线性规划的标准型式 第二节第二节 线性规划的一般模型线性规划的一般模型 1、OR:SM43一、线性规划的标准型式一、线性规划的标准型式 第二节第二节 线性规划的一般模型线性规划的一般模型 2 2、标准型转换方法、标准型转换方法(1)如果极小化原问题如果极小化原问题minZ=CX，则令，则令 Z=-Z，转为求，转为求 maxZ=-CX (2)若某个若某个bi Pk+1。u同一优先等级下目标的相对重要性赋以不同权数同一优先等级下目标的相对重要性赋以不同权数w。108第二节第二节 目标规划的数学模型三、目标达成函数目标达成函数目标规划的数学模型三、目标达成函数目标达成函数OR:SM109第二节第二节 目标规划的数学模型目标规划的数学模型例如例如P1 级目标实现利润至少30元；P2级目标是甲乙产品的产量 假设：乙产品产量不少于4件比甲产品产量不少于6件更重要，取其权重为2 minG=P1 d1-+P2(2d2-+d3+)3x1+5x2+d1-d1+=30 x2 +d2-d2+=4 x1+d3-d3+=6 x1,x2,dk-,dk+0(k=1,2,3)109第二节第二节 目标规划的数学模型例如目标规划的数学模型例如OR:SM110第三节第三节 目标规划的图解法目标规划的图解法目标规划的图解法目标规划的图解法n首先，按照绝对约束画出可行域，首先，按照绝对约束画出可行域，n其次，不考虑正负偏差变量，画出目标约束的边界线，其次，不考虑正负偏差变量，画出目标约束的边界线，n最后。按优先级别和权重依次分析各级目标。最后。按优先级别和权重依次分析各级目标。F2x1=162x2=10BCx14A103x1+4 x2=326x20D2642EGHx1=5,x2=4110第三节第三节 目标规划的图解法目标规划的图解法目标规划的图解法目标规划的图解法F2x1=1OR:SM111软件求解软件求解111软件求解软件求解OR:SM112运算结果运算结果step 1 目标函数值为目标函数值为 :0 变量变量 解解 相差值相差值 -x1 1.667 0 x2 5 0 d1-0 1 d1+0 0 d2-0 0 d2+1 0 d3-4.333 0 d3+0 0step 2 目标函数值为目标函数值为 :.667 变量变量 解解 相差值相差值 -x1 5.333 0 x2 4 0 d1-0 0 d1+6 0 d2-0 .667 d2+0 1.333 d3-.667 0 d3+0 1112运算结果运算结果step 1step OR:SM113第四节第四节 目标规划的应用案例目标规划的应用案例一、无穷多满意解一、无穷多满意解解：设解：设x1,x2表示表示A、B产品的产量。两个等级的目标：产品的产量。两个等级的目标：P1：充分利用电量限额，正负偏差之和为最小 目标达成函数目标达成函数 目标约束条件目标约束条件 P2：利润额希望不能低于100元，负偏差最小 目标达成函数目标达成函数 目标约束条件目标约束条件 计划生产两种产品，计划生产两种产品，首先要充分利用设备工时而不加班；然首先要充分利用设备工时而不加班；然后考虑利润不低于后考虑利润不低于100元。问应如何制定产品元。问应如何制定产品A、B的产量。的产量。113第四节第四节 目标规划的应用案例一、无穷多满意解解：设目标规划的应用案例一、无穷多满意解解：设x1,OR:SM1142A24BDx26810 x1第四节第四节 目标规划的应用案例目标规划的应用案例一、无穷多满意解一、无穷多满意解由于材料供应限量为由于材料供应限量为8单位，所以有系统约束条件，如下单位，所以有系统约束条件，如下该问题的目标规划模型如下，图解法求解如图该问题的目标规划模型如下，图解法求解如图CG1142A24BDx26810 x1第四节第四节 目标规划的应用案例目标规划的应用案例OR:SM115115OR:SM116运算结果运算结果step 1 目标函数值为目标函数值为 :0 变量变量 解解 相差值相差值 -x1 1.5 0 x2 4.25 0 d1-0 1 d1+0 1 d2-0 0 d2+0 0step 2 目标函数值为目标函数值为 :0 变量变量 解解 相差值相差值 -x1 1.5 0 x2 4.25 0 d1-0 1 d1+0 1 d2-0 0 d2+0 0116运算结果运算结果step 1OR:SM117第第四四节节 目标规划的应用案例目标规划的应用案例二、加班时间问题二、加班时间问题例：例：某音像店有某音像店有5名全职售货员和名全职售货员和4名兼职售货员，全职名兼职售货员，全职售货员每月工作售货员每月工作160小时，兼职售货员每月工作小时，兼职售货员每月工作80小时。根小时。根据记录，全职每小时销售据记录，全职每小时销售CD25张，平均每小时工资张，平均每小时工资15元，元，加班工资每小时加班工资每小时22.5元。兼职售货员每小时销售元。兼职售货员每小时销售CD10张，张，平均工资每小时平均工资每小时10元，加班工资每小时元，加班工资每小时10元。现在预测下元。现在预测下月月CD销售量为销售量为27500张，商店每周开门营业张，商店每周开门营业6天，所以可能天，所以可能要加班。每出售一张要加班。每出售一张CD盈利盈利1.5元。元。商店经理认为，保持稳定的就业水平加上必要的加班，商店经理认为，保持稳定的就业水平加上必要的加班，比不加班就业水平要好，但全职销售员如果加班过多，就比不加班就业水平要好，但全职销售员如果加班过多，就会因为疲劳过度而造成效率下降，因此不允许每月加班超会因为疲劳过度而造成效率下降，因此不允许每月加班超过过100小时，建立相应的目标规划模型。小时，建立相应的目标规划模型。117第四节第四节 目标规划的应用案例二、加班时间问题例：某音像店目标规划的应用案例二、加班时间问题例：某音像店OR:SM118第第四四节节 目标规划的应用案例目标规划的应用案例二、加班时间问题二、加班时间问题首先，确定目标约束的优先级。首先，确定目标约束的优先级。如下：如下：P1：下月的：下月的CD销售量达到销售量达到27500张；张；P2：全职售货员加班时间不超过：全职售货员加班时间不超过100小时；小时；P3：保持全体售货员充分就业，对全职的要比兼职的加：保持全体售货员充分就业，对全职的要比兼职的加倍优先考虑；倍优先考虑；P4：尽量减少加班时间，对两种售货员区别对待，权重：尽量减少加班时间，对两种售货员区别对待，权重由他们对利润的贡献而定。由他们对利润的贡献而定。其次，建立目标约束函数其次，建立目标约束函数（1）销售目标约束销售目标约束，设全体全职售货员下月的工作时，设全体全职售货员下月的工作时间间x1，全体兼职售货员下月的工作时间，全体兼职售货员下月的工作时间 x2；达不到销售目；达不到销售目标的偏差标的偏差d1-，超过销售目标的偏差，超过销售目标的偏差 d1+。118第四节第四节 目标规划的应用案例二、加班时间问题首先，确定目目标规划的应用案例二、加班时间问题首先，确定目OR:SM119第第四四节节 目标规划的应用案例目标规划的应用案例二、加班时间问题二、加班时间问题（2）正常工作时间约束正常工作时间约束。设全体全职售货员下月的停工时间。设全体全职售货员下月的停工时间d2-，加班时间加班时间d2+；全体兼职售货员下月的停工时间；全体兼职售货员下月的停工时间d3-，加班时间，加班时间d3+。（3）加班时间的限制。加班时间的限制。设全体全职售货员下月的加班不足设全体全职售货员下月的加班不足100小时小时的偏差的偏差d4-，加班超过，加班超过100小时的偏差小时的偏差 d4+。两类售货员区别对待，权重比两类售货员区别对待，权重比d2+:d3+=1:3，另一加班目标约束为，另一加班目标约束为119第四节第四节 目标规划的应用案例二、加班时间问题目标规划的应用案例二、加班时间问题（2）正常）正常OR:SM120第第四四节节 目标规划的应用案例目标规划的应用案例二、加班时间问题二、加班时间问题 第三，按目标的优先级，写出相应的目标规划模型：第三，按目标的优先级，写出相应的目标规划模型：运用运用LINGO软件求解得软件求解得 x1=900,x2=500，下月共销售，下月共销售CD盘盘27500张，获利张，获利275001.5-80015-10022.5-50010=22000。120第四节第四节 目标规划的应用案例二、加班时间问题目标规划的应用案例二、加班时间问题 第三，按目第三，按目OR:SM121第四节第四节 目标规划的应用案例目标规划的应用案例三、目标管理方案三、目标管理方案 例：例：某公司准备生产甲、乙产品，据市场调查：甲产品的最大某公司准备生产甲、乙产品，据市场调查：甲产品的最大市场需求市场需求3台，乙产品的最大市场需求台，乙产品的最大市场需求2台。台。在满足现有电力资源严格供给约束的前提下，该厂长考虑两在满足现有电力资源严格供给约束的前提下，该厂长考虑两个目标：个目标：一是总利润不低于一是总利润不低于36003600元；二是充分利用设备台时，元；二是充分利用设备台时，但尽量少加班。但尽量少加班。问应如何制定产品甲、乙的产量，试建立其目问应如何制定产品甲、乙的产量，试建立其目标规划的数学模型。标规划的数学模型。121第四节第四节 目标规划的应用案例三、目标管理方案目标规划的应用案例三、目标管理方案 例：某公司例：某公司OR:SM122第四节第四节 目标规划的应用案例目标规划的应用案例三、目标管理方案三、目标管理方案 1.利润期望优先利润期望优先目标规划数学模型：目标规划数学模型：运用图解法进行求解运用图解法进行求解 FECx1=8x2=65x1+5x2=600 x12410126ABx20842D10Gx1=8,x2=3122第四节第四节 目标规划的应用案例三、目标管理方案目标规划的应用案例三、目标管理方案 1.利润利润OR:SM123第四节第四节 目标规划的应用案例目标规划的应用案例1.利润期望优先利润期望优先 总利润总利润：3600单位甲单位甲：300单位乙单位乙：400生产部目标生产部目标甲产品的产量：甲产品的产量：8，成本：，成本：900乙产品的产量：乙产品的产量：3，成本：，成本：1400技术部目标技术部目标甲的设备单耗甲的设备单耗25，需降低，需降低5工时工时 乙的设备单耗乙的设备单耗50，需降低，需降低10工时工时 销售部目标销售部目标甲产品的销量：甲产品的销量：8，单价：，单价：1200乙产品的销量：乙产品的销量：3，单价：，单价：1800满意解：满意解：x1=8,x2=3设备能力：需求：设备能力：需求：30 8+60 3=420，实际：，实际：360实现实现目标目标P1和和P2，降低甲乙产品的设备消耗，降低甲乙产品的设备消耗:降低率降低率(420-360)/360=17%，甲产品的设备消耗降为甲产品的设备消耗降为30 (1-17%)=25,乙产品的设备消耗降为乙产品的设备消耗降为60 (1-17%)=50。123第四节第四节 目标规划的应用案例目标规划的应用案例1.利润期望优先利润期望优先 总利润总利润OR:SM124第四节第四节 目标规划的应用案例目标规划的应用案例三、目标管理方案三、目标管理方案 2.设备工时优先设备工时优先目标规划数学模型：目标规划数学模型：运用图解法进行求解运用图解法进行求解 FECx1=8x2=65x1+5x2=600 x12410126ABx20842D10Gx1=8,x2=2124第四节第四节 目标规划的应用案例三、目标管理方案目标规划的应用案例三、目标管理方案 2.设备设备OR:SM125第四节第四节 目标规划的应用案例目标规划的应用案例2.设备工时优先设备工时优先 总利润总利润：3600单位甲单位甲：337.5单位乙单位乙：450 生产部目标生产部目标甲产品的产量：甲产品的产量：8，成本：，成本：862.5 乙产品的产量：乙产品的产量：2，成本：，成本：1350 技术部目标技术部目标保证设备的正常运行保证设备的正常运行甲的设备单耗甲的设备单耗30，乙的单耗，乙的单耗60 销售部目标销售部目标甲产品的销量：甲产品的销量：8，单价：，单价：1200乙产品的销量：乙产品的销量：2，单价：，单价：1800满意解：满意解：x1=8,x2=2利润总额利润总额300 8+400 2=3200，目标：，目标：3600不能提价，就必须降低成本以增加利润，利润增长率为不能提价，就必须降低成本以增加利润，利润增长率为12.5%甲产品的甲产品的成本需要降为成本需要降为1200-300(1+12.5%)=862.5元元/台，降低幅度台，降低幅度4.2%乙产品的乙产品的成本需要降为成本需要降为1800-400(1+12.5%)=1350元元/台，降低幅度台，降低幅度3.6%125第四节第四节 目标规划的应用案例目标规划的应用案例2.设备工时优先设备工时优先 总利润：总利润：OR:SM126第第7 章章 网络分析网络分析Sub titleSub title内容提要126第第7 章章 网络分析网络分析Sub title内容提要第一节内容提要第一节 OR:SM1271818世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？第第7 章章 网络分析网络分析陆地A陆地B岛D岛CAD B C 17361736年年瑞瑞士士数数学学家家欧欧拉拉将将两两岸岸和和小小岛岛抽抽象象为为四四个个点点，将将桥桥抽抽象为七条边，此问题归结为一笔画问题。象为七条边，此问题归结为一笔画问题。12718世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将OR:SM128第一节第一节 图论的概念图论的概念一、图的内涵一、图的内涵 1 1、图的定义、图的定义 v1 v4v2 v3e1e2e3e4e5e6 v1 v4v2v3 e1e2e3e4e5e6 v1 v2 v3 v4e1e2e3e4e5e6图论的图与一般几何图形或代数函数图形是完全不同的图论的图与一般几何图形或代数函数图形是完全不同的图论中的图图论中的图:由一些点和连接点的线所组成的由一些点和连接点的线所组成的“图形图形”点和线的位置是任意的点和线的位置是任意的线的曲直、长短与实际无关，代表的只是点与点之间的相互关系线的曲直、长短与实际无关，代表的只是点与点之间的相互关系例：例：表示表示苏州苏州v1、杭州、杭州v2、上海、上海v3、南京、南京v4仓储网点之间的物流运输线路关系仓储网点之间的物流运输线路关系 128第一节第一节 图论的概念一、图的内涵图论的概念一、图的内涵 1、图的定义、图的定义 OR:SM129第一节第一节 图论的概念图论的概念一、图的内涵一、图的内涵 2 2、图的分类、图的分类 l 不带箭头的连线称为不带箭头的连线称为“边边”，如公路运输线路；，如公路运输线路；l 带箭头的连线称为带箭头的连线称为“弧弧”，如供排水的管道运输线路，如供排水的管道运输线路。1 1、无向图、无向图 由点和边的集合所构成由点和边的集合所构成由点和弧的集合所构成由点和弧的集合所构成 2 2、有向图、有向图 链：链：无向网络中，前后相继点和边无向网络中，前后相继点和边的交替序列称为一条链。的交替序列称为一条链。圈：圈：闭合的链称为一个圈。闭合的链称为一个圈。路径：路径：有向网络图中，前后相继并且有向网络图中，前后相继并且方向一致的点弧序列称为一条路径。方向一致的点弧序列称为一条路径。回路：回路：闭合的路径称为一个回路。闭合的路径称为一个回路。129第一节第一节 图论的概念一、图的内涵图论的概念一、图的内涵 2、图的分类、图的分类 不带不带OR:SM130第二节第二节 最小树问题最小树问题例：一家企业分别要在例：一家企业分别要在6 6间办公室铺设网线接入口，网线的可行间办公室铺设网线接入口，