管理运筹学教案

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管理运筹学教案,教 学 内 容,绪 论 运筹学概况,第一章 线性规划,第二章 运输问题,第三章 整数规划,综合建模练习（,1,）,-,（,10,）,绪论：运筹学概况,运筹学名称,运筹学的研究对象,运筹学的发展,运筹学在航空运输中的应用,课程设置情况,运筹学的名称,BK,：,Operational ResearchOR,US,：,Operations ResearchOR,台湾：作业研究,大陆：运筹学,运筹帷幄之中，决胜千里之外,运 筹 学 的 研 究 对 象,资源运用,运用分析理论,竞争现象,竞争理论,拥挤现象,随机服务理论,运 筹 学 的 发 展,http:/,WWW.IFORS.ORG,国际运筹学联盟（,International Federation 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.mathprog.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, Programming, Games - Dave,Rusin,; The Mathematical Atlas,提供一些简短的文章，介绍运筹学方面的文章，其用象征性的语言描述优化资源方面的研究。,Global Optimization,这个站点链接了全球的很多关于优化的站点,OR/MS Books,该站点收集了大量的运筹学和管理科学方面的书。,运 筹 学 的 发 展,http:/,/,中国运筹学会,http:/202.113.13.67/orgs/tdyc/index.php,天津运筹学会,http:/, 筹 学 的 发 展,http:/202.194.15.128/or/,山东大学全国精品课程,运筹学,2005, 线性规划,线性规划,(Linear programmingLP),线性规划的应用案例,线性规划的计算机求解,线性规划解的认识,影子价格,灵敏度分析,课程实验,LP,应用案例,生产计划的安排,某企业利用四种设备生产两种产品，单位产品占用各种设备的时间及有关数据如下表所示。该企业应如何安排生产，可使总利润最大？,目标函数,(objective function),、约束条件,(constraints),、非负约束,(,nonnegativity,constraints),、决策变量,(decision variables),LP,应用案例,铁皮的利用,用一块边长为,a,（,=100cm),的正方形铁皮折成盒子。如何折，可使盒子的容积最大？,（,x=16.67cm,V=74074cm,3,.),x,a,LP,应用案例,下料方式,用500,cm,长的条材截出长度为98,cm,和78,cm,的两种毛坯分别为10000根和20000根。如何截，所用条材根数最少？,(x,1,=1200,x,5,=4000,z=5200),LP,应用案例,人力资源分配问题,答案：时段,1-60,人、,2-10,人、,3-50,人、,5-30,人，总共,150,人。,LP,应用案例,人力资源分配问题,每周工作,5,天，连续休息,2,天。至少应该配备多少人员？,（答案：星期一,-8,人、三,-12,人、五,-11,人、六,-5,人；总共,36,人）,时间,所需人数,时间,所需人数,星期一,15,星期五,31,星期二,24,星期六,28,星期三,25,星期七,28,星期四,19,LP,应用案例,物资配运问题,答案：,A,1,-B,2,40000,、,-B,4,30000,，,A,2,-B,1,60000,、,-B,2,20000,，,A,3,-B,3,30000,；,总运费,890000,。,LP,应用案例,生产计划问题,甲、乙、丙三种产品皆需经铸造、机械加工和装配三道工序，其中甲、乙两种产品的铸造工序可以选择自行生产或者外包协作。如何安排生产能够获得最大利润？,（答案：甲,-,自,1600,件，甲,-,外,400,件；最大利润,33200,）,甲,乙,丙,可用工时,每件铸造工时,5,10,7,8000,每件机械工时,6,4,8,12000,每件装配工时,3,2,2,10000,自行生产铸件每件成本,3,5,4,外包协作铸件每件成本,5,6,机械加工每件成本,2,1,3,装配每件成本,3,2,2,每件产品售价,23,18,16,LP,应用案例,配料问题,使用三种原料,1,，,2,，,3,混合调配处三种不同产品甲、乙、丙，情况如下表所示。如何安排生产能够获得最大利润？,（答案：原料,1-,甲：,100,公斤，原料,2-,甲：,50,公斤，原料,2-,丙：,50,公斤，原料,3-,甲：,50,公斤；利润,=500,元）,产品,要求,单价,（元,/,公斤）,原料,可用量（公斤）,单价,（元,/,公斤）,甲,原料,1,不少于,50%,原料,2,不超过,25%,50,1,100,65,乙,原料,1,不少于,25%,原料,2,不超过,50%,35,2,100,25,丙,不限,25,3,60,35,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,万元）,项目,特点,A,第,1,5,年初都可投资，当年末收回本利,110%,B,第,1,4,年初都可投资，次年末收回本利,125%,，但每年投资额不能超过,30,万元,C,第,3,年初需要投资，第,5,年末收回本利,140%,，但投资额不能超过,80,万元,D,第,2,年初需要投资，第,5,年末收回本利,155%,，但投资额不能超过,100,万元,LP,应用案例,订货与库存问题,一粮库经营粮食批发业务。粮库的容量为5000担。1月1日，粮库内有粮食1000担，现金20000元。第一季度粮食的价格如下表。每月初卖出粮食,每月末买入粮食。希望季度末粮库余粮为2000担。如何安排可使该季度总的获利最大？,（答案：,1,月卖,1000,担、买,5000,担，,2,月卖,5000,担、买,0,担，,3,月卖,0,担、买,2000,担，总差价,-700,元）,线性规划的计算机求解,求解规划问题常用的计算机软件,Microsoft Excel,Lindo & Lingo,Matlab,ILOG,Excel,的“规划求解”简介,Excel,规划求解,目标函数设置,Excel,规划求解,目标函数设置,Excel,规划求解,约束条件设置,Excel,规划求解,参数设置,Excel,规划求解,最优解,线性规划解的认识,唯一最优解的认识,无穷多最优解的认识,无界解的认识,无可行解的认识,线性规划解的认识,唯一最优解的认识,x,1,2,4,6,8,2,4,6,8,x,2,0,唯一最优解的认识,x,1,2,4,6,8,2,4,6,8,x,2,0,10,无穷多解,(Multiple optimal solutions),的认识,x,1,-1,1,2,-1,1,2,x,2,0,-2,无界解,(Unbounded Solution),的认识,x,1,-12,-4,2,6,8,x,2,0,-16,4,-8,-18,Excel,规划求解,无界解,无可行解,(Infeasibility),的,认识,x,1,4,2,6,8,x,2,0,4,2,Excel,规划求解,无可行解,返回,线性规划解的基本性质,如果线性规划问题的可行域有界，则一定有最优解，且目标函数一定可以在可行域的顶点上达到最优,线性规划问题的最优解只可能在顶点或边界上得到，而不会在可行域内部得到。,线性规划的求解方法,单纯形法,(Simplex Method),该解为,最优解？,确定初始,基本可行解,已得到最优,解，停止,求出更佳的,基本可行解,是,否,影子价格,影子价格的含义,影子价格的意义,不同于市场价格，由资源的使用情况确定；,反映资源在生产中的使用情况；,为零时，说明该资源还有剩余或者刚好用尽；,为正值时，说明该资源已消耗完毕；,决定了对该种资源的处理方式；,可作为对紧缺资源的分配依据。,影子价格的应用,影子价格的含义,x,1,2,4,6,8,2,4,6,8,x,2,0,x,1,2,4,6,8,2,4,6,8,x,2,0,增加单位资源能使总利润增加的数量。,影子价格的意义,不同于市场价格，由资源的使用情况确定；,反映资源在生产中的使用情况；,为零时，说明该资源还有剩余或者刚好用尽；,为正值时，说明该资源已消耗完毕；,决定了对该种资源的处理方式；,可作为对紧缺资源的分配依据。,影子价格的应用,x,1,2,4,6,8,2,4,6,8,x,2,0,设,B,设备的市场价格为,1(,元,/,台时,),，应否增加该设备的使用时间？增加多少？,Excel,规划求解,运算结果报告,Excel,规划求解,敏感性报告,Excel,规划求解,极限值报告,灵敏度分析,线性规划的基本假设,确定性,c,j,、a,ij,、b,i,不随时间变化,等比性资源需要量与产品数量等比,可加性两种产品总利润等于各自利润之和(两种产品之间无替代性）,可分性决策变量可取小数值,灵敏度分析的内容和形式,灵敏度分析的内容,某参数的允许变化范围，使原最优方案不变；,某参数的变化超出允许范围时，如何求得新的最优方案。,灵敏度分析的形式,价值系数,c,j,发生变化,右端常数,b,i,发生变化,增加一个变量的情况,P,j,发生变化,增加一个约束条件的情况,价值系数,c,j,发生变化,确定产品的单位利润,c,2,的允许变动范围，使原最优生产方案不变。当,c,2,变为,5,时，求新的最优生产方案。,x,1,2,4,6,8,2,4,6,8,x,2,0,x,1,2,4,6,8,2,4,6,8,x,2,0,右端常数,b,i,发生变化,设,C,设备的可用台时,b,3,变为,20,时，求新的最优生产方案。,x,1,2,4,6,8,2,4,6,8,x,2,0,x,1,2,4,6,8,2,4,6,8,x,2,0,增加一个变量的情况,现有产品可供选择。生产每件产品耗用,A,B,C,D,设备的台时分别为3,2,6,3，单位利润为5元。是否应该生产产品？生产多少件？,P,j,发生变化的情况,由于工艺结构的改进，生产产品所耗,A,B,C,D,设备的时间变为3,2,5,2，单位利润也提高到4元。应如何安排生产？,x,1,2,4,6,8,2,4,6,8,x,2,0,x,1,2,4,6,8,2,4,6,8,x,2,0,增加一个约束条件,生产产品、产品时增加一道工序，在,E,设备上进行。产品、产品在,E,设备上加工的时间为2,2.4小时，,E,设备在计划期内的有效台时为12小时。应如何安排生产？,x,1,2,4,6,8,2,4,6,8,x,2,0,课程实验,:,LP,应用案例,(2)-(9),的,求解,随机抽签确定题目；,原则上力争每人,1,题，由于学生人数多而无法实现时，力争使每题分配的人数均等；,每次实验结果皆计入平时成绩。,第二章 运输问题,产销平衡运输问题的数学模型,产销不平衡运输问题的数学模型,需求有界运输问题的数学模型,转运问题的数学模型,课程实验,运输问题的数学模型,产地、销地、运价、运费,产销平衡问题的数学模型,产大于销问题的数学模型,销大于产问题的数学模型,有最低需求问题的数学模型,转运问题的数学模型,产地、销地、运价、运费,产销平衡问题的数学模型,产销平衡问题的数学模型,产大于销问题的数学模型,销大于产问题的数学模型,有最低需求问题的数学模型,转运问题,A,B,C,D,G,E,F,H,发量10,发量2,收量3,收量1,收量8,5,4,3,1,2,1,4,1,3,4,转运问题（续）,最优调运方案,A,B,C,D,G,E,F,H,发量10,发量2,收量3,收量1,收量8,5,4,3,1,2,1,4,1,3,4,10,3,7,8,6,1,8,课程实验,运输问题的计算机求解,产销平衡问题的求解,产大于销问题的求解,销大于产问题的求解,有最低需求问题的求解,转运问题的求解,有最低需求问题的计算机求解,“,=,”,时,有最低需求问题的计算机求解,“,=,”,时,有最低需求问题的计算机求解,“,”,时,有最低需求问题的计算机求解,“,”,时,第三章 整数规划,整数规划问题的数学模型,整数规划问题的求解方法,0-1型整数规划的应用,指派问题,整数规划应用案例,航班计划的制定,课程实验,整数规划的数学模型,整数规划的基本概念,整数线性规划,整数非线性规划,纯整数规划,混合整数规划,01规划,托运甲、乙两种货物分别采用两种不同规格的集装箱。每箱体积及重量等数据如下表所示。问两种货物各托运多少箱，可使所获利润最大,？,整数规划与松弛问题的关系,整数规划问题与其松弛问题的最优解对比,整数规划问题的目标函数值不超过其松弛问题的目标函数值,不能采用对松弛问题最优解取整方法得到整数规划最优解,整数规划问题的求解方法,分支定界法,X,1,4,X,1,5,整数规划问题的求解方法,分支定界法,X,2,2,X,2,3,X,2,1,X,2,2,0-1整数规划的应用案例,某公司拟在东、西、南三区建立门市部。共有七个地点,A,1,，,，A,7,可供选择。规定：在东区,A,1,A,2,A,3,中至多选两个；在西区，由,A,4,A,5,中至少选一个； 在南区，由,A,6,A,7,中至少选一个。选,A,i,点时，需投资,b,i,元，年获利,c,i,元。现有资金总额,B,元。问应选择哪些点，可使年获利润最大？,0-1整数规划的应用,0-1整数规划的应用,0-1整数规划的应用,要求：,从工程、中最多只能挑选一项；,如果选择工程或，就必须选择工程，反之亦然。,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,万元或为,6,万元或为,8,万元。,项目,D,：五年内每年初可购买公债，于当年末归还，并加利息,6%,，此项投资金额不限。,该部门现有资金,10,万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大,?,指派问题,平衡指派问题的数学模型,不平衡指派问题的数学模型,求极大的指派问题的数学模型,人员数多于工作数的指派问题的数学模型,工作数多于人员数的指派问题的数学模型,平衡指派问题的数学模型,平衡指派问题的数学模型,表中数据为完成工程所需时间,求极大指派问题的数学模型,表中数据为操作每台机器的产值,人员数多于工作数的指派问题,表中数据为承担每种工作的费用,人员数少于工作数的指派问题,表中数据为承担每种工作的费用，,且每人最多承担,1,项工作。,人员数少于工作数的指派问题,表中数据为承担每种工作的费用，,且每人最多可以承担,2,项工作。,整数规划应用案例,航班计划编制,某航空公司经营A,B,C三个城市之间的航线，这些航线每天航班起飞与到达时间如下表所示。设飞机在机场停留的损失费用大致与停留时间的平方成正比，而且从降落到起飞至少需2小时的准备时间。指定使停留费用损失最小的航班计划。,整数规划应用案例,航班计划编制,整数规划应用案例,航班计划编制,106,102,107,104,110,101,108,105,113,111,114,112,109,103,课程实验,(3),整数规划的计算机求解,0-1整数规划的应用,(4),、,(5),、,(11),平衡的指派问题,不平衡的指派问题,综合建模练习（,1,）,（参见教材,P20,）,Par,公司生产高尔夫袋，各道生产工序的可用时间、两种规格的高尔夫袋的单位加工时间以及利润情况如下表所示。两种袋各生产多少个，可使,Par,公司获得最大的利润？,工序,加工时间（小时）,可用时间,（小时）,标准袋,高级袋,切割与印染,7/10,1,630,缝合,1/2,5/6,600,成型,1,2/3,708,检查与包装,1/10,1/4,135,单位利润（美元）,10,9,综合建模练习（,2,）,背景：现将,20,吨货物从地点,依次经过地点,、,、,运至地点,，在地点,、,、,、,出发时都可以且只能选择铁路、公路和航空三种运输方式之一，相应的运输成本如表所示。并且如果在相邻两段改变了运输方式，还要发生额外的费用，具体数据亦如表所示。如何选择各段的运输方式，使总的运输成本最小？,1,2,3,4,5,第,1,段,第,2,段,第,3,段,第,4,段,综合建模练习（,3,）,（参见教材,P200,）某房产租赁公司现有,2000,千美元用于购置新的房产，别墅每套售价,282,千美元，最多可购买,5,套；每幢公寓楼售价,400,千美元。该公司每月最多可以花,140,小时管理新增房产，其中管理每套别墅每月要花,4,小时，管理每幢公寓楼每月要花,40,小时。出租后，每套别墅的年收益为,10,千美元，每种公寓楼的年收益为,15,千美元。别墅和公寓楼各购买多少套，可使全年总收益最大？,综合建模练习（,4-1,）,各进港航班中到各登机口转机的旅客人数,进港航班,衔接航班出港登机口,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,F1,5,5,10,8,15,8,2,10,8,20,5,4,0,9,3,4,1,2,1,F2,5,2,1,4,19,9,4,2,3,2,27,3,8,4,0,2,1,7,2,F3,10,0,4,9,13,4,4,4,3,5,5,8,4,9,11,7,9,4,4,F4,4,8,5,4,10,4,1,0,0,2,4,19,1,2,4,5,5,8,2,F5,4,11,9,9,6,3,1,4,4,2,1,0,3,5,1,2,2,3,4,F6,1,2,42,5,2,7,6,2,4,7,2,3,6,4,10,2,1,0,0,F7,3,3,2,5,9,13,11,2,2,3,7,22,4,0,1,1,2,2,9,综合建模练习（,4-2,）,各登机口之间的距离,进港航班登机口,出港航班登机口,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,3,10,40,-,30,10,40,20,50,30,60,40,70,50,80,60,90,70,90,80,4,40,10,30,-,40,10,50,20,60,30,70,40,80,50,90,60,90,70,80,10,70,40,60,30,50,20,40,10,30,-,40,10,50,40,60,30,70,40,50,11,50,80,40,70,30,60,20,50,10,40,-,30,10,40,20,50,30,50,40,14,90,60,80,50,70,40,60,30,50,20,40,10,30,-,40,10,50,20,30,15,70,100,60,90,50,80,40,70,30,60,20,50,10,40,-,30,10,30,20,17,80,100,70,90,60,80,50,70,40,60,30,50,20,40,10,30,-,20,10,综合建模练习（,5,）,背景：某航空公司以戴高乐机场作为中转枢纽。分别来自波尔多、克莱蒙,-,费朗、马赛、南特、尼斯、图卢兹的,6,架相同机型的飞机到达戴高乐机场之后，将分别执行去往柏林、波恩、布鲁塞尔、伦敦、罗马、维也纳的航班。某日的不同进港航班上去往各城市的旅客人数如下表所示。安排这,6,架飞机分别执行后续的哪些航班，才能使需要换飞机的旅客人数最少？,去往,来自,柏林,波恩,布鲁塞尔,伦敦,罗马,维也纳,波尔多,35,12,16,38,5,2,克莱蒙,-,费朗,25,8,9,24,6,8,马赛,12,8,11,27,3,2,南特,38,15,14,39,2,9,尼斯,9,8,25,10,5,图卢兹,14,6,7,综合建模练习（,6,）,背景：某省省会城市为,A,1,，另有,6,个旅游景点,A,2,A,7,。游客希望从,A,1,出发，乘机依次到达其他,6,个旅游景点游览，最后返回,A,1,。根据资料得知,A,1,A,7,城市之间的航程如表所示。沿着什么顺序依次到达,6,个城市，才能使游客花在飞行途中的时间最短？,去往,来自,A,1,A,2,A,3,A,4,A,5,A,6,A,7,A,1,0,786,549,657,331,559,250,A,2,786,0,668,979,593,224,905,A,3,549,668,0,316,607,472,467,A,4,657,979,316,0,890,769,499,A,5,331,593,607,890,0,386,559,A,6,559,224,472,769,386,0,681,A,7,250,905,467,499,559,681,0,综合建模练习（,7,）,某厂按合同规定须于当年每个季度末分别提供10,15,25,20台同一规格的设备。已知该厂各季度的生产能力及生产每台设备的成本如下表所示。如果生产出来的设备当季不交货，每台设备每积压一个季度需要储存、维护等费用0.15万元。问该厂应如何安排生产计划，使全年生产总成本为最小？,综合建模练习（,8,）,某食品公司经营两家制罐厂，从三个果品产地购进鲜果，有关情况如下表所示。水果罐头的批发价是500元/吨。该公司应如何组织两厂的生产，使获得的利润最大？,综合建模练习（,9,）,一超市为居住于四地的用户运送所购商品，每地必到一次且只到一次，最后仍回到超市（地点1）。已知各地之间的距离如下表所示，如何安排路线，使总的行程距离最短？,综合建模练习（,10,）,背景：现将,20,吨货物从地点,依次经过地点,、,、,运至地点,，在地点,、,、,、,出发时都可以且只能选择铁路、公路和航空三种运输方式之一，相应的运输成本如表所示。并且如果在相邻两段改变了运输方式，还要发生额外的费用，具体数据亦如表所示。如何选择各段的运输方式，使总的运输成本最小？,1,2,3,4,5,第,1,段,第,2,段,第,3,段,第,4,段,