管理运筹学教案.ppt

《管理运筹学教案.ppt》由会员分享，可在线阅读，更多相关《管理运筹学教案.ppt（108页珍藏版）》请在三一办公上搜索。

1、管理运筹学教案,教 学 内 容,绪 论 运筹学概况第一章 线性规划 第二章 运输问题第三章 整数规划综合建模练习（1）-（10）,绪论：运筹学概况,运筹学名称运筹学的研究对象运筹学的发展运筹学在航空运输中的应用课程设置情况,运筹学的名称,BK：Operational ResearchORUS：Operations ResearchOR台湾：作业研究大陆：运筹学运筹帷幄之中，决胜千里之外,运 筹 学 的 研 究 对 象,资源运用运用分析理论竞争现象竞争理论拥挤现象随机服务理论,运 筹 学 的 发 展,http:/WWW.IFORS.ORG 国际运筹学联盟（International Federa

2、tion of Operational Research Societies-IFORS,于1959年建立）。http:/www.agifors.org/index.jsp国际运筹学联盟航空运输组(The Airline Group of the International Federation of Operational Research Societies-AGIFORS)http:/www.euro-online.org/欧洲运筹学协会(Association of European Operational Research Societies-EURO).http:/www.math

3、prog.org/数学规划学会（Mathematical Programming Society）是一个国际性的组织，致力于计算数学、应用学、数学规划的理论研究。,运 筹 学 的 发 展,http:/www.ams.org/home/page美国数学会（American Mathematical Society-AMS）http:/www.orsoc.org.uk/orshop/(cojjpu553n0cnealhpkk4jzl)/orhomepage2.aspx运筹学研究社团（Operational Research Society）Economics,Operations Research

4、,Programming,Games-Dave Rusin;The Mathematical Atlas 提供一些简短的文章，介绍运筹学方面的文章，其用象征性的语言描述优化资源方面的研究。Global Optimization 这个站点链接了全球的很多关于优化的站点OR/MS Books 该站点收集了大量的运筹学和管理科学方面的书。,运 筹 学 的 发 展,http:/,运 筹 学 的 发 展,http:/202.194.15.128/or/山东大学全国精品课程运筹学2005http:/,运筹学在航空运输中的应用,航班计划问题机队规划问题飞机选型问题机场选址问题引进飞机决策问题紧缺资源排班问题

5、机组、地面服务人员、装卸工、操纵设备者,飞机维修计划问题航线网络布局问题停机位分配问题机坪作业优化问题收益管理问题空中流量控制问题航材优化问题,课程设置情况,2012培养方案之管理运筹学,课程设置情况,使用教材,课程设置情况,考核方式,第一章 线性规划,线性规划(Linear programmingLP)线性规划的应用案例线性规划的计算机求解线性规划解的认识影子价格灵敏度分析课程实验,LP应用案例生产计划的安排,某企业利用四种设备生产两种产品，单位产品占用各种设备的时间及有关数据如下表所示。该企业应如何安排生产，可使总利润最大？,目标函数(objective function)、约束条件(co

6、nstraints)、非负约束(nonnegativity constraints)、决策变量(decision variables),LP应用案例铁皮的利用,用一块边长为a（=100cm)的正方形铁皮折成盒子。如何折，可使盒子的容积最大？（x=16.67cm,V=74074cm3.),LP应用案例下料方式,用500cm长的条材截出长度为98cm和78cm的两种毛坯分别为10000根和20000根。如何截，所用条材根数最少？(x1=1200,x5=4000,z=5200),LP应用案例人力资源分配问题,答案：时段1-60人、2-10人、3-50人、5-30人，总共150人。,LP应用案例人力资

7、源分配问题,每周工作5天，连续休息2天。至少应该配备多少人员？（答案：星期一-8人、三-12人、五-11人、六-5人；总共36人）,LP应用案例物资配运问题,答案：A1-B240000、-B430000，A2-B160000、-B220000，A3-B330000；总运费890000。,LP应用案例生产计划问题,甲、乙、丙三种产品皆需经铸造、机械加工和装配三道工序，其中甲、乙两种产品的铸造工序可以选择自行生产或者外包协作。如何安排生产能够获得最大利润？（答案：甲-自1600件，甲-外400件；最大利润33200）,LP应用案例配料问题,使用三种原料1，2，3混合调配处三种不同产品甲、乙、丙，情

8、况如下表所示。如何安排生产能够获得最大利润？（答案：原料1-甲：100公斤，原料2-甲：50公斤，原料2-丙：50公斤，原料3-甲：50公斤；利润=500元）,LP应用案例投资问题,现有资金200万元，今后5年内可投资项目如下。如何确定各项目每年的投资额，使得第5年末的资金总额最大？（答案：A项目1-170、2-62.2、5-31.4，B项目1-30、2-24.8、3-25.92、4-30，C项目3-80，D项目2-100；第5年末资金总额339.04万元）,LP应用案例订货与库存问题,一粮库经营粮食批发业务。粮库的容量为5000担。1月1日，粮库内有粮食1000担，现金20000元。第一季度

9、粮食的价格如下表。每月初卖出粮食,每月末买入粮食。希望季度末粮库余粮为2000担。如何安排可使该季度总的获利最大？（答案：1月卖1000担、买5000担，2月卖5000担、买0担，3月卖0担、买2000担，总差价-700元）,线性规划的计算机求解,求解规划问题常用的计算机软件Microsoft ExcelLindo&LMatlabILOGExcel的“规划求解”简介,Excel规划求解目标函数设置,Excel规划求解目标函数设置,Excel规划求解约束条件设置,Excel规划求解参数设置,Excel规划求解最优解,线性规划解的认识,唯一最优解的认识无穷多最优解的认识无界解的认识无可行解的认识线

10、性规划解的认识,唯一最优解的认识,唯一最优解的认识,无穷多解(Multiple optimal solutions)的认识,无界解(Unbounded Solution)的认识,Excel规划求解无界解,无可行解(Infeasibility)的认识,Excel规划求解无可行解,返回,线性规划解的基本性质,如果线性规划问题的可行域有界，则一定有最优解，且目标函数一定可以在可行域的顶点上达到最优线性规划问题的最优解只可能在顶点或边界上得到，而不会在可行域内部得到。,线性规划的求解方法单纯形法(Simplex Method),影子价格,影子价格的含义影子价格的意义 不同于市场价格，由资源的使用情况确

11、定；反映资源在生产中的使用情况；为零时，说明该资源还有剩余或者刚好用尽；为正值时，说明该资源已消耗完毕；决定了对该种资源的处理方式；可作为对紧缺资源的分配依据。影子价格的应用,影子价格的含义,增加单位资源能使总利润增加的数量。,影子价格的意义,不同于市场价格，由资源的使用情况确定；反映资源在生产中的使用情况；为零时，说明该资源还有剩余或者刚好用尽；为正值时，说明该资源已消耗完毕；决定了对该种资源的处理方式；可作为对紧缺资源的分配依据。,影子价格的应用,设B设备的市场价格为1(元/台时)，应否增加该设备的使用时间？增加多少？,Excel规划求解运算结果报告,Excel规划求解敏感性报告,Exce

12、l规划求解极限值报告,灵敏度分析线性规划的基本假设,确定性cj、aij、bi不随时间变化等比性资源需要量与产品数量等比可加性两种产品总利润等于各自利润之和(两种产品之间无替代性）可分性决策变量可取小数值,灵敏度分析的内容和形式,灵敏度分析的内容某参数的允许变化范围，使原最优方案不变；某参数的变化超出允许范围时，如何求得新的最优方案。灵敏度分析的形式 价值系数cj发生变化 右端常数bi发生变化 增加一个变量的情况 Pj发生变化 增加一个约束条件的情况,价值系数cj发生变化,确定产品的单位利润c2 的允许变动范围，使原最优生产方案不变。当c2变为5时，求新的最优生产方案。,右端常数bi发生变化,设

13、C设备的可用台时b3变为20时，求新的最优生产方案。,增加一个变量的情况,现有产品可供选择。生产每件产品耗用A,B,C,D设备的台时分别为3,2,6,3，单位利润为5元。是否应该生产产品？生产多少件？,Pj发生变化的情况,由于工艺结构的改进，生产产品所耗A,B,C,D设备的时间变为3,2,5,2，单位利润也提高到4元。应如何安排生产？,增加一个约束条件,生产产品、产品时增加一道工序，在E设备上进行。产品、产品在E设备上加工的时间为2,2.4小时，E设备在计划期内的有效台时为12小时。应如何安排生产？,课程实验:LP应用案例(2)-(9)的求解,随机抽签确定题目；原则上力争每人1题，由于学生人数

14、多而无法实现时，力争使每题分配的人数均等；每次实验结果皆计入平时成绩。,第二章 运输问题,产销平衡运输问题的数学模型产销不平衡运输问题的数学模型需求有界运输问题的数学模型转运问题的数学模型课程实验,运输问题的数学模型,产地、销地、运价、运费产销平衡问题的数学模型 产大于销问题的数学模型销大于产问题的数学模型有最低需求问题的数学模型转运问题的数学模型,产地、销地、运价、运费,产销平衡问题的数学模型,产销平衡问题的数学模型,产大于销问题的数学模型,销大于产问题的数学模型,有最低需求问题的数学模型,转运问题,转运问题（续）最优调运方案,课程实验运输问题的计算机求解,产销平衡问题的求解 产大于销问题的

15、求解销大于产问题的求解有最低需求问题的求解转运问题的求解,有最低需求问题的计算机求解“=”时,有最低需求问题的计算机求解“=”时,有最低需求问题的计算机求解“”时,有最低需求问题的计算机求解“”时,第三章 整数规划,整数规划问题的数学模型整数规划问题的求解方法0-1型整数规划的应用指派问题整数规划应用案例航班计划的制定课程实验,整数规划的数学模型,整数规划的基本概念整数线性规划整数非线性规划纯整数规划混合整数规划01规划,托运甲、乙两种货物分别采用两种不同规格的集装箱。每箱体积及重量等数据如下表所示。问两种货物各托运多少箱，可使所获利润最大？,整数规划与松弛问题的关系,整数规划问题与其松弛问题

16、的最优解对比整数规划问题的目标函数值不超过其松弛问题的目标函数值 不能采用对松弛问题最优解取整方法得到整数规划最优解,整数规划问题的求解方法分支定界法,X14,X15,整数规划问题的求解方法分支定界法,X22,X23,X21,X22,0-1整数规划的应用案例,某公司拟在东、西、南三区建立门市部。共有七个地点A1，A7可供选择。规定：在东区A1,A2,A3中至多选两个；在西区，由A4,A5中至少选一个；在南区，由A6,A7中至少选一个。选Ai点时，需投资bi元，年获利ci元。现有资金总额B元。问应选择哪些点，可使年获利润最大？,0-1整数规划的应用,0-1整数规划的应用,0-1整数规划的应用,要

17、求：从工程、中最多只能挑选一项；如果选择工程或，就必须选择工程，反之亦然。,0-1整数规划的应用,0-1整数规划的应用,0-1整数规划的应用,0-1整数规划的应用*,0-1整数规划的应用*,0-1整数规划的应用*,0-1整数规划的应用*,某公司在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年末能回收本利128，但规定最低投资金额为3万元，最高金额为5万元；项目C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或

18、为6万元或为8万元。项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?,指派问题,平衡指派问题的数学模型不平衡指派问题的数学模型 求极大的指派问题的数学模型 人员数多于工作数的指派问题的数学模型 工作数多于人员数的指派问题的数学模型,平衡指派问题的数学模型,平衡指派问题的数学模型,表中数据为完成工程所需时间,求极大指派问题的数学模型,表中数据为操作每台机器的产值,人员数多于工作数的指派问题,表中数据为承担每种工作的费用,人员数少于工作数的指派问题,表中数据为承担每种工

19、作的费用，且每人最多承担1项工作。,人员数少于工作数的指派问题,表中数据为承担每种工作的费用，且每人最多可以承担2项工作。,整数规划应用案例航班计划编制,某航空公司经营A,B,C三个城市之间的航线，这些航线每天航班起飞与到达时间如下表所示。设飞机在机场停留的损失费用大致与停留时间的平方成正比，而且从降落到起飞至少需2小时的准备时间。指定使停留费用损失最小的航班计划。,整数规划应用案例航班计划编制,整数规划应用案例航班计划编制,课程实验(3)整数规划的计算机求解,0-1整数规划的应用(4)、(5)、(11)平衡的指派问题不平衡的指派问题,综合建模练习（1）,（参见教材P20）Par公司生产高尔夫

20、袋，各道生产工序的可用时间、两种规格的高尔夫袋的单位加工时间以及利润情况如下表所示。两种袋各生产多少个，可使Par公司获得最大的利润？,综合建模练习（2）,背景：现将20吨货物从地点依次经过地点、运至地点，在地点、出发时都可以且只能选择铁路、公路和航空三种运输方式之一，相应的运输成本如表所示。并且如果在相邻两段改变了运输方式，还要发生额外的费用，具体数据亦如表所示。如何选择各段的运输方式，使总的运输成本最小？,综合建模练习（3）,（参见教材P200）某房产租赁公司现有2000千美元用于购置新的房产，别墅每套售价282千美元，最多可购买5套；每幢公寓楼售价400千美元。该公司每月最多可以花140

21、小时管理新增房产，其中管理每套别墅每月要花4小时，管理每幢公寓楼每月要花40小时。出租后，每套别墅的年收益为10千美元，每种公寓楼的年收益为15千美元。别墅和公寓楼各购买多少套，可使全年总收益最大？,综合建模练习（4-1）,综合建模练习（4-2）,综合建模练习（5）,背景：某航空公司以戴高乐机场作为中转枢纽。分别来自波尔多、克莱蒙-费朗、马赛、南特、尼斯、图卢兹的6架相同机型的飞机到达戴高乐机场之后，将分别执行去往柏林、波恩、布鲁塞尔、伦敦、罗马、维也纳的航班。某日的不同进港航班上去往各城市的旅客人数如下表所示。安排这6架飞机分别执行后续的哪些航班，才能使需要换飞机的旅客人数最少？,综合建模练

22、习（6）,背景：某省省会城市为A1，另有6个旅游景点A2A7。游客希望从A1出发，乘机依次到达其他6个旅游景点游览，最后返回A1。根据资料得知A1A7城市之间的航程如表所示。沿着什么顺序依次到达6个城市，才能使游客花在飞行途中的时间最短？,综合建模练习（7）,某厂按合同规定须于当年每个季度末分别提供10,15,25,20台同一规格的设备。已知该厂各季度的生产能力及生产每台设备的成本如下表所示。如果生产出来的设备当季不交货，每台设备每积压一个季度需要储存、维护等费用0.15万元。问该厂应如何安排生产计划，使全年生产总成本为最小？,综合建模练习（8）,某食品公司经营两家制罐厂，从三个果品产地购进鲜果，有关情况如下表所示。水果罐头的批发价是500元/吨。该公司应如何组织两厂的生产，使获得的利润最大？,综合建模练习（9）,一超市为居住于四地的用户运送所购商品，每地必到一次且只到一次，最后仍回到超市（地点1）。已知各地之间的距离如下表所示，如何安排路线，使总的行程距离最短？,综合建模练习（10）,背景：现将20吨货物从地点依次经过地点、运至地点，在地点、出发时都可以且只能选择铁路、公路和航空三种运输方式之一，相应的运输成本如表所示。并且如果在相邻两段改变了运输方式，还要发生额外的费用，具体数据亦如表所示。如何选择各段的运输方式，使总的运输成本最小？,