运筹学(课件)

1、运运 筹筹 学学范秋芳范秋芳教材与参考书教材与参考书 胡运权主编胡运权主编运筹学教程运筹学教程 清华大学出版社清华大学出版社 谢家平编著谢家平编著. .管理运筹学：管理科学方法，管理运筹学：管理科学方法， 中国人民大学出版社，中国人民大学出版社，20102010运筹学主要内容（分支）运筹学主要内容（分支） 绪绪 论论 第一章第一章 线性规划线性规划 第二章第二章 整数规划整数规划 静态优化静态优化 第三章第三章 目标规划目标规划 第四章第四章 非线性规划非线性规划 第五章第五章 动态规划动态规划 动态优化动态优化 第六章第六章 网络分析网络分析 第七章第七章 网络计划网络计划 第八章第八章 决

2、策分析决策分析 第九章第九章 对策论（博弈论）对策论（博弈论） 第十章第十章 库存控制库存控制 第十一章第十一章 排队理论排队理论离散优化离散优化随机优化随机优化 第一部分、绪论第一部分、绪论 第二部分、主要分支简介第二部分、主要分支简介 第三部分、线性规划第三部分、线性规划 第四部分、网络计划技术第四部分、网络计划技术 第五部分、决策分析（决策论）第五部分、决策分析（决策论） 第六部分、对策论（博弈论）第六部分、对策论（博弈论）讲课提纲讲课提纲第一部分第一部分 绪论绪论 一、运筹学释义与发展简史一、运筹学释义与发展简史 二、学科性质二、学科性质 三、工作程序三、工作程序 四、学科体系四、学科

3、体系 五、学课地位五、学课地位 六、学习要求六、学习要求一、运筹学释义与发展简史一、运筹学释义与发展简史 运筹学一词起源于运筹学一词起源于2020世纪世纪3030年代年代u大英百科全书大英百科全书：“运筹学是一门应用于管理有组运筹学是一门应用于管理有组织系统的科学织系统的科学”，“运筹学为掌管这类系统的人提供运筹学为掌管这类系统的人提供决策目标和数量分析决策目标和数量分析的工具的工具”。u中国大百科全书中国大百科全书：“用用数学方法数学方法研究经济、民政研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效

4、运行的技术科学，物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行它可以用来预测发展趋势，制定行动规划或优选可行方案方案”u辞海辞海：“主要研究经济活动与军事活动中能用主要研究经济活动与军事活动中能用数数量量来表达有关运用、筹划与管理方面的问题，它根据来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过问题的要求，通过数学的分析与运算数学的分析与运算，作出综合性的，作出综合性的合理安排，以达到合理安排，以达到较经济较有效地使用人力物力较经济较有效地使用人力物力”。u中国企业管理百科全书中国企业管理百科全书)(1984)(1984年版年版) )

5、：“应用分析、应用分析、试验、量化的方法试验、量化的方法，对经济管理系统中人、财、物等，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理方案，以实现最有效的管理”。 英国称为英国称为 operational research 美国称为美国称为 operations research ( (缩写为缩写为OR) )可直译为可直译为“运用研究运用研究”或或“作业研作业研究究”运筹学：运筹学：是一门研究如何最优安排的学科。是一门研究如何最优安排的学科。l 日本译作：日本译作：“运用学运用学”l 香港、台湾译

6、为：香港、台湾译为：“作业研究作业研究”l 我国译作：我国译作：“运筹学运筹学” 源于古语源于古语“运筹帷幄之中，决胜千里之外运筹帷幄之中，决胜千里之外” 取取“运筹运筹”二字，体现运心筹谋、策略取二字，体现运心筹谋、策略取胜胜 由于运筹学涉及的主要领域是由于运筹学涉及的主要领域是管理问题，管理问题，研究研究的基本手段是的基本手段是建立数学模型建立数学模型，并比较多地运用，并比较多地运用各种数学工具从这点出发，有人将运筹学称各种数学工具从这点出发，有人将运筹学称做做“管理数学管理数学” ” 发展历史 齐王赛马 渭修皇宫 沈括运军粮 科学管理 20世纪40年代诞生于英美 1940年，英国为对付德

7、国空军的空袭，使用了雷达，但没有科学布局，效果不好。为解决这个问题，成立运筹学小组，称，意为。 美国和加拿大也在军队设立运筹学小组，称，协助指挥官研究战略及战术问题。 战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹学在管理方面的应用得到了长足进展。 运筹学这个名词的正式使用是在运筹学这个名词的正式使用是在19381938年，当时年，当时英国为解决空袭英国为解决空袭的早期预警的早期预警，积极进行，积极进行“雷达雷达”的研究。但随着雷达性能的改的研究。但随着雷达性能的改善和配置数量的增多，出现了来自不同雷达站的信息以及雷达善和配置数量的增多，出现了来自不同雷达站的信息以及雷达站同整个防

8、空作战系统的协调配合问题。站同整个防空作战系统的协调配合问题。 19381938年年7 7月月，波得塞，波得塞(Bawdsey(Bawdsey) )雷达站的负责人罗伊雷达站的负责人罗伊(Rowe)(Rowe)提出提出立即进行整个防空作战系统运行的研究，并用立即进行整个防空作战系统运行的研究，并用operational research一词作为这方面研究的描述，这就是一词作为这方面研究的描述，这就是O OR R( (运筹学运筹学) )这个名词的起源。这个名词的起源。 19401940年年9 9月月英国成立了由物理学家布莱克特领导的第一个运筹英国成立了由物理学家布莱克特领导的第一个运筹学小组，后来

9、发展到每一个英军指挥部都成立运筹学小组。学小组，后来发展到每一个英军指挥部都成立运筹学小组。 1942年美国和加拿大也都相继成立运筹学小组年美国和加拿大也都相继成立运筹学小组，这些小组在，这些小组在确定扩建舰队规模、开展反潜艇战的侦察和组织有效的对敌确定扩建舰队规模、开展反潜艇战的侦察和组织有效的对敌轰炸等方面作了大量研究，为取得反法西斯战争的胜利及运轰炸等方面作了大量研究，为取得反法西斯战争的胜利及运筹学有关分支的建立作出了贡献。筹学有关分支的建立作出了贡献。 1939年前苏联学者摩托洛维奇年前苏联学者摩托洛维奇出版了出版了生产组织与计划中的生产组织与计划中的数学方法数学方法一书，对列宁格勒

10、胶合板厂的计划任务建立了一一书，对列宁格勒胶合板厂的计划任务建立了一个线性规划的模型，并提出了个线性规划的模型，并提出了“解乘数法解乘数法”的求解方法，为的求解方法，为数学与管理科学的结合做了开创性的工作。数学与管理科学的结合做了开创性的工作。 大致可分三个阶段：大致可分三个阶段：1 1从从19451945年到年到5050年代初，被称为创建时期。年代初，被称为创建时期。此阶段的特点是从此阶段的特点是从事运筹学研究的人数不多，范围较小，运筹学的出版物、学会事运筹学研究的人数不多，范围较小，运筹学的出版物、学会等寥寥无几积极探讨从军队到民用的应用，等寥寥无几积极探讨从军队到民用的应用，线性规划出现

11、。线性规划出现。2 2从从5050年代初期到年代初期到5050年代末期，被认为是运筹学的成长时期。年代末期，被认为是运筹学的成长时期。此阶段的一个特点是电子计算机技术的迅速发展，使得运筹学此阶段的一个特点是电子计算机技术的迅速发展，使得运筹学中一些方法如中一些方法如单纯形法、动态规划方法等，单纯形法、动态规划方法等，得以用来解决实际得以用来解决实际管理系统中的优化问题，促进了运筹学的推广应用管理系统中的优化问题，促进了运筹学的推广应用物资储备、物资储备、资源分配、设备更新中应用运筹学；更多刊物、学会出现。资源分配、设备更新中应用运筹学；更多刊物、学会出现。3 3自自6060年代以来，被认为是运

12、筹学开始普及和迅速发展的时期。年代以来，被认为是运筹学开始普及和迅速发展的时期。此阶段的特点是运筹学进一步细分为各个分支，专业学术团体此阶段的特点是运筹学进一步细分为各个分支，专业学术团体的迅速增多，更多期刊的创办，运筹学书籍的大量出版，以及的迅速增多，更多期刊的创办，运筹学书籍的大量出版，以及更多学校将运筹学课程纳入教学计划之中更多学校将运筹学课程纳入教学计划之中 我国第一个运筹学小组于我国第一个运筹学小组于19561956年在中国科学院力学研究年在中国科学院力学研究所成立，所成立，19581958年建立了运筹学研究室。年建立了运筹学研究室。19601960年在山东济南召年在山东济南召开全国

13、应用运筹学的经验交流和推广会议，开全国应用运筹学的经验交流和推广会议，19621962年和年和19781978年年先后在北京和成都召开了全国运筹学专业学术会议，先后在北京和成都召开了全国运筹学专业学术会议，19801980年年4 4月成立中国运筹学学会。在农林、交通运输、建筑、机械、月成立中国运筹学学会。在农林、交通运输、建筑、机械、冶金、石油化工、水利、邮电、纺织等部门，运筹学的方法冶金、石油化工、水利、邮电、纺织等部门，运筹学的方法已开始得到应用推广。除中国运筹学学会外，中国系统工程已开始得到应用推广。除中国运筹学学会外，中国系统工程学学会以及与国民经济各部门有关的专业学会，也都把运筹学学

14、会以及与国民经济各部门有关的专业学会，也都把运筹学应用作为重要的研究领域。我国各高等院校，特别是各经学应用作为重要的研究领域。我国各高等院校，特别是各经济管理类专业中已普遍把运筹学作为一门专业的主干课程列济管理类专业中已普遍把运筹学作为一门专业的主干课程列入教学计划之中入教学计划之中。二、学科性质二、学科性质 经济和管理活动中能用经济和管理活动中能用“数量关系数量关系”描述描述的如运营、规划与组织管理问题解决的的如运营、规划与组织管理问题解决的理理论模型和优化方法实践论模型和优化方法实践 强调科学性和定量分析强调科学性和定量分析 强调应用性和实践性强调应用性和实践性 强调从整体上进行把握强调从

15、整体上进行把握 三、工作程序三、工作程序管理者制定决策：管理者制定决策：运筹学的步骤：运筹学的步骤：明确问题环境分析明确问题环境分析确定目标制定准则确定目标制定准则收集资料数量关系收集资料数量关系结构分析数学模型结构分析数学模型制定决策方案选择制定决策方案选择算法求解方案优选算法求解方案优选否否是是方案实施持续改进方案实施持续改进识别问题识别问题量化分析量化分析建立模型建立模型软件求解软件求解结果分析结果分析确定方案确定方案实施方案实施方案控制控制管理者管理者解的分析解的分析四、学科体系四、学科体系 需求预测需求预测产品的市场需求量有多大，需求类别如何，对企业盈利有何影响产品的市场需求量有多大

16、，需求类别如何，对企业盈利有何影响?生产计划生产计划在有限资源约束下，生产什么，生产多少，获利最大？在有限资源约束下，生产什么，生产多少，获利最大？资源配置资源配置需要哪些资源，如何进行最优配置，资源紧缺性如何，以什么代价获取需要哪些资源，如何进行最优配置，资源紧缺性如何，以什么代价获取?作业排序作业排序作业的重要次序如何，作业的顺序安排如何作业的重要次序如何，作业的顺序安排如何?市场营销市场营销广告预算、媒介选择、产品定价、销售计划等如何安排？广告预算、媒介选择、产品定价、销售计划等如何安排？运输问题运输问题最佳运输线路是哪条？物流配送集载如何优化？物流设施布局如何设置？最佳运输线路是哪条？

17、物流配送集载如何优化？物流设施布局如何设置？设施选址设施选址运营点如何选择，需要哪些运作设施，设施如何布局运营点如何选择，需要哪些运作设施，设施如何布局?库存控制库存控制应保持多大库存量，何时应进行订货，订货批量多少为宜应保持多大库存量，何时应进行订货，订货批量多少为宜?项目规划项目规划项目完工工期多长为宜，哪些作业起关键性作用，资源如何分配项目完工工期多长为宜，哪些作业起关键性作用，资源如何分配?设备更新设备更新设备运转状况如何演进，运行可靠性如何，何时和如何更新或改造设备运转状况如何演进，运行可靠性如何，何时和如何更新或改造?人力资源人力资源人员需求预测，技能要求，编制与任务指派，绩效测评

18、，留用多长时间人员需求预测，技能要求，编制与任务指派，绩效测评，留用多长时间?财务资金财务资金资金投放的数量，从何处进行融资，资金成本是多少资金投放的数量，从何处进行融资，资金成本是多少?排队问题排队问题队列多长，有无容量限制，多少服务台为宜，能提供什么水平的服务队列多长，有无容量限制，多少服务台为宜，能提供什么水平的服务? 模型类型模型类型解决的典型办法解决的典型办法线性规划线性规划在线性目标和约束条件间取得最优化结果在线性目标和约束条件间取得最优化结果整数规划整数规划在线性目标和约束条件间寻求整数决策最优在线性目标和约束条件间寻求整数决策最优目标规划目标规划在相对立的目标间寻得多目标妥协的

19、满意解在相对立的目标间寻得多目标妥协的满意解动态规划动态规划寻求多阶段动态系统的整体决策优化问题寻求多阶段动态系统的整体决策优化问题网络分析网络分析寻求网络路径、流量分布、网络瓶颈及其改进寻求网络路径、流量分布、网络瓶颈及其改进网络计划网络计划用各种作业和结点的网络排列来说明项目实施计划用各种作业和结点的网络排列来说明项目实施计划管理决策管理决策依据决策准则权衡比较备选方案的决策结果依据决策准则权衡比较备选方案的决策结果方案排序方案排序综合各方案的优势与不足寻求多指标排名次序综合各方案的优势与不足寻求多指标排名次序库存模型库存模型寻求订货、存储和缺货等库存成本降至最低的经济批量寻求订货、存储和

20、缺货等库存成本降至最低的经济批量统计方法统计方法从一个抽样得到普遍结果的推论和曲线拟合从一个抽样得到普遍结果的推论和曲线拟合排队理论排队理论分析正在等待的队列特点及其运行指标分析正在等待的队列特点及其运行指标仿真模拟仿真模拟动态观察复杂的管理问题的行为，模拟管理系统的结构关系动态观察复杂的管理问题的行为，模拟管理系统的结构关系 管理既是科学又是艺术低层管理的科学成分较多，高层管理的艺术成分较多低层管理的科学成分较多，高层管理的艺术成分较多运营管理需较多管理科学，人力资源管理需较多管理艺术运营管理需较多管理科学，人力资源管理需较多管理艺术例行管理需要较多管理科学，例外管理需要较多管理艺术例行管理

21、需要较多管理科学，例外管理需要较多管理艺术M: 管理决策问题管理决策问题MC: 定量解决方法定量解决方法方案选择依据方案选择依据问题导向问题导向技术支持技术支持战略决策营销决策生产安排财务分析人力资源方案优选应用统计线性规划整数规划目标规划网络计划网络分析 决策分析动态规划管理科学管理科学：运用合理的运用合理的分析来改善分析来改善决策的制定决策的制定管理者管理者:制定决策制定决策五、学科地位五、学科地位 数学技术科学管理学科基础运筹学运筹学管理专业课高等数学、概率统计、线性代数加工技术、工程技术、信息技术经济学原理、管理学、行为科学离散、连续，静态、动态的方法离散、连续，静态、动态的方法战略、

22、运营、营销、财务、人力经济学企业战略、公司治理会计学财务管理人力资源管理组织行为学管理管理科学科学方法方法支持支持企业B行业企业C企业A商务2商务3商务1职能b职能c职能a小组ii小组iii小组i运营管理市场营销质量管理项目管理信息管理流程管理物流管理供应链管理六、学习要求六、学习要求 重点在结合实际的应用重点在结合实际的应用 发挥自己管理实践经验丰富和理论联系实际的能力发挥自己管理实践经验丰富和理论联系实际的能力 强化结合实际问题建立管理优化模型的能力强化结合实际问题建立管理优化模型的能力 强化解决问题的方案或模型的解的分析与应用能力强化解决问题的方案或模型的解的分析与应用能力 充分借用管理

23、运筹学教学软件充分借用管理运筹学教学软件第二部分、运筹学主要分支简介第二部分、运筹学主要分支简介（一）、规划论（一）、规划论（二）、决策论（二）、决策论（三）、图论与网络计划技术（三）、图论与网络计划技术（四）、对策论（博弈论、竞赛论）（四）、对策论（博弈论、竞赛论）（五）、存贮论（五）、存贮论（六）、排队论（六）、排队论（一）、规划论（一）、规划论 线性规划线性规划 目标规划目标规划 整数规划整数规划 非线性规划非线性规划 动态规划动态规划 线性规划线性规划(1inear programming)p 这类统筹规划问题用数学语言表达，先根据问题要达到的目这类统筹规划问题用数学语言表达，先根据问

24、题要达到的目标标选取适当的变量，选取适当的变量，p 问题的目标通过用变量的函数形式表示问题的目标通过用变量的函数形式表示( (称为称为目标函数目标函数) )，p 对问题的限制条件用有关变量的等式或不等式表达对问题的限制条件用有关变量的等式或不等式表达( (称为称为约约束条件束条件) )。p 当变量连续取值，且目标函数和约束条件均为线性时，称这当变量连续取值，且目标函数和约束条件均为线性时，称这类模型为线性规划的模型。类模型为线性规划的模型。p 是运筹学中应用最为广泛的一个分支是运筹学中应用最为广泛的一个分支 用线性规划求解的典型问题有：用线性规划求解的典型问题有： 运输问题、生产计划问题、下料

25、问题、运输问题、生产计划问题、下料问题、混合配料问题等混合配料问题等 有些规划问题的目标函数是非线性的，但往有些规划问题的目标函数是非线性的，但往往可以采用分段线性化等方法，转化为线性规往可以采用分段线性化等方法，转化为线性规划问题划问题（二）、决策论（二）、决策论 决策是指为最优地达到目标，依据一定准则，对若干备选行决策是指为最优地达到目标，依据一定准则，对若干备选行动的方案进行的抉择动的方案进行的抉择 决策过程一般是指：决策过程一般是指：形成决策问题，包括提出方案，确定目形成决策问题，包括提出方案，确定目标及效果的度量；确定各方案对应的结局及出现的概率、确标及效果的度量；确定各方案对应的结

26、局及出现的概率、确定决策者对不同结局的效用值，综合评价，决定方案的取舍定决策者对不同结局的效用值，综合评价，决定方案的取舍。决策论是对整个决策过程中涉及方案目标选取、度量、概率决策论是对整个决策过程中涉及方案目标选取、度量、概率值确定、效用值计算，一直到最优方案和策略选取的有关科值确定、效用值计算，一直到最优方案和策略选取的有关科学理论学理论（三）、图论与网络计划技术（三）、图论与网络计划技术p生产管理中经常遇到工序间的合理衔接搭配问题，生产管理中经常遇到工序间的合理衔接搭配问题， 设计中设计中经常遇到研究各种管道、线路的通过能力，以及仓库、附属经常遇到研究各种管道、线路的通过能力，以及仓库、

27、附属设施的布局等问题。设施的布局等问题。p运筹学中把一些研究的对象用节点表示，对象之间的联系用运筹学中把一些研究的对象用节点表示，对象之间的联系用连线连线( (边边) )表示，用表示，用点、边的集合构成图点、边的集合构成图。图论是研究由节点图论是研究由节点和边所组成图形的数学理论和方法。和边所组成图形的数学理论和方法。p图是网络分析的基础图是网络分析的基础，根据研究的具体网络对象，根据研究的具体网络对象( (如铁路网、如铁路网、电力网、通信网等电力网、通信网等) )，赋予图中各边某个具体的参数，如时，赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图中各节点代表具体网络中间、流量、

28、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点、中转点或终点，然后利用图论方法来任何一种流动的起点、中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。研究各类网络结构和流量的优化分析。 网络计划技术的基本思路网络计划技术的基本思路 运运用用网络图网络图的形式表达一个计划项目中各种活动的形式表达一个计划项目中各种活动（作业、工序）之间的先后次序和相互关系，在此基（作业、工序）之间的先后次序和相互关系，在此基础上进行网络分析，计算础上进行网络分析，计算网络时间，确定关键活动和网络时间，确定关键活动和关键路线；然后利用时差，对网络进行工期、资源和关键路线；然后利用时差，

29、对网络进行工期、资源和成本的优化；成本的优化；在实施过程中，通过信息反馈进行监督在实施过程中，通过信息反馈进行监督和控制，以确定计划目标的实现。和控制，以确定计划目标的实现。例：例：某飞机发动机维修项目，包括以下作业某飞机发动机维修项目，包括以下作业 A. 拆卸，拆卸，5天；天； B. 电子器件检查，电子器件检查，8天；天； C. 机械零件检查，机械零件检查，10天；天； D. 机械零件更换，机械零件更换，6天；天； E. 机械零件维修，机械零件维修，15天；天； F. 电子器件更换，电子器件更换，9天；天； G. 组装，组装，6天；天； H. 试车，试车，3天。天。 4 46 65 53 3

30、7 78 8DEFGH1 12 2ABC5108159663（四）、对策论（博弈论、竞赛论）（四）、对策论（博弈论、竞赛论）u 用于研究具有对抗局势的模型。在这类模型中，参与对抗的各方称为用于研究具有对抗局势的模型。在这类模型中，参与对抗的各方称为局中局中人人，每个局中人均有，每个局中人均有一组策略一组策略可供选择，当各局中人分别采取不同策略时，可供选择，当各局中人分别采取不同策略时，对应一个对应一个收益或需要支付的函数。收益或需要支付的函数。u 在社会、经济、管理等与人类活动有关的系统中，各局中人都按各自的利在社会、经济、管理等与人类活动有关的系统中，各局中人都按各自的利益和知识进行对策，每

31、个人都力求扩大自己的利益，但又无法精确预测其益和知识进行对策，每个人都力求扩大自己的利益，但又无法精确预测其他局中人的行为，无法取得必要的信息，他们之间还可能玩弄花招，制造他局中人的行为，无法取得必要的信息，他们之间还可能玩弄花招，制造假象。对策论为局中人在这种高度不确定和充满竞争的环境中，提供一套假象。对策论为局中人在这种高度不确定和充满竞争的环境中，提供一套完楚的、定量化和程序化的选择策略的理论和方法。完楚的、定量化和程序化的选择策略的理论和方法。u 对策论已应用于商品、消费者、生产者之间的供求平衡分析，利益集团间对策论已应用于商品、消费者、生产者之间的供求平衡分析，利益集团间的协商和谈判

32、，以及军事上各种作战模型的研究等。的协商和谈判，以及军事上各种作战模型的研究等。 囚犯困境囚犯困境-8，-8 0，-10-10，0 -1，-1囚徒囚徒A 坦白坦白抵赖抵赖坦白坦白抵赖抵赖囚徒囚徒B （五）、存贮论（五）、存贮论p 一种研究最优存贮策略的理论和方法如为了保证企业生产一种研究最优存贮策略的理论和方法如为了保证企业生产的正常进行，需要有一定数量原材料和零部件的储备，以调节的正常进行，需要有一定数量原材料和零部件的储备，以调节供需之间的不平衡供需之间的不平衡p 实际问题中，需求量可以是常数，也可以是服从某一分布的随实际问题中，需求量可以是常数，也可以是服从某一分布的随机变量每次订货需一

33、定费用，提出订货后，货物可以一次到机变量每次订货需一定费用，提出订货后，货物可以一次到达，也可能分批到达。从提出订货到货物的到达可能是即时的，达，也可能分批到达。从提出订货到货物的到达可能是即时的，也可能需要一个周期也可能需要一个周期( (订货提前期订货提前期) )。某些情况下允许缺货，有。某些情况下允许缺货，有些情况不允许缺货。些情况不允许缺货。p 存贮策略研究在不同需求、供货及到达方式等情况下，确定在存贮策略研究在不同需求、供货及到达方式等情况下，确定在什么时间点及一次提出多大批量的订货，使用于订购、贮存和什么时间点及一次提出多大批量的订货，使用于订购、贮存和可能发生短缺的费用的总和为最少

34、。可能发生短缺的费用的总和为最少。 （六）、排队论（六）、排队论p 生产和生活中存在大量有形和无形的拥挤和排队现象。生产和生活中存在大量有形和无形的拥挤和排队现象。p 排队系统由服务机构排队系统由服务机构( (服务员服务员) )及被服务的对象及被服务的对象( (顾客顾客) )组成。组成。一般顾客的到达及服务员用于对每名顾客的服务时间是随机一般顾客的到达及服务员用于对每名顾客的服务时间是随机的，服务员可以是一个或多个，多个情况下又分平行或串联的，服务员可以是一个或多个，多个情况下又分平行或串联排列。排列。p 排队按一定规则进行，如分为等待制、损失制、混合制等。排队按一定规则进行，如分为等待制、损

35、失制、混合制等。p 排队论研究顾客不同输入、各类服务时间的分布、不同服务排队论研究顾客不同输入、各类服务时间的分布、不同服务员数及不同排队规则情况下，排队系统的工作性能和状态，员数及不同排队规则情况下，排队系统的工作性能和状态，为设计新的排队系统及改进现有系统的性能提供数量依据。为设计新的排队系统及改进现有系统的性能提供数量依据。 服务台服务台服务台服务台1服务台服务台2服务台服务台n 服务台服务台1服务台服务台2服务台服务台n服务台服务台1服务台服务台2单服务台排队系统单服务台排队系统n个服务台一个队列个服务台一个队列n个服务台个服务台n个队列个队列多个服务台的串联排队系统多个服务台的串联排

36、队系统第三部分、线性规划第三部分、线性规划 在现有各项资源条件的限制下，如何确定方案，在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优。使预期目标达到最优。 步骤：步骤：第一、确定决策变量第一、确定决策变量(x(xi i) ) 第二、确定目标函数第二、确定目标函数(Z)(Z)第三、确定约束条件第三、确定约束条件第四、找出目标函数达到最优的可行解第四、找出目标函数达到最优的可行解一、线性规划的三个要素一、线性规划的三个要素 决策变量决策变量 决策问题待定的量值决策问题待定的量值 取值要求非负取值要求非负 约束条件约束条件 任何管理决策问题都是限定在一定的条件下求解任何管理决策问题都是

37、限定在一定的条件下求解 把各种限制条件表示为一组等式或不等式称约束条件把各种限制条件表示为一组等式或不等式称约束条件 约束条件是决策方案可行的保障约束条件是决策方案可行的保障 约束条件是决策变量的线性函数约束条件是决策变量的线性函数 目标函数目标函数 衡量决策优劣的准则，如时间最省、利润最大、成本衡量决策优劣的准则，如时间最省、利润最大、成本最低最低 目标函数是决策变量的线性函数目标函数是决策变量的线性函数 有的目标要实现极大，有的则要求极小有的目标要实现极大，有的则要求极小二、一般数学模型二、一般数学模型 用一组非负决策变量表示的一个决策问题；用一组非负决策变量表示的一个决策问题； 存在一组

38、等式或不等式的线性约束条件；存在一组等式或不等式的线性约束条件； 有一个希望达到的目标，可表示成决策变量的极值线性函数。有一个希望达到的目标，可表示成决策变量的极值线性函数。11221111221121122222112212max(min) Z( , )( , )s.t. ( , ),0nnnnnnmmmnnmnc xc xc xa xa xa xba xaxaxbaxaxaxbxxx 三、线性规划模型的举例三、线性规划模型的举例 1 1、生产计划问题、生产计划问题某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如

39、何制定生产计划，使总利润为最大。 据市场分析，单位甲乙产品的销售价格分别为据市场分析，单位甲乙产品的销售价格分别为7373和和7575元，试确定获利最大的产品生产计划。元，试确定获利最大的产品生产计划。 产品设备工时消耗甲 乙工时成本元/h生产能力hABC 2 0 0 2 3 4201510161032：设x1为甲产品的产量，x2为乙产品的产量。：生产受设备能力制约，能力需求不能突破有效供给量。 设备设备A的约束条件表达为的约束条件表达为 2 x1 16 同理，设备同理，设备B的加工能力约束条件表达为的加工能力约束条件表达为 2x2 10 设备设备C的装配能力也有限，其约束条件为的装配能力也有

40、限，其约束条件为 3x1+ 4x2 32目标是企业利润最大化 max Z= 3x1 +5x2 甲乙产品的产量为非负 x1 0， x2 012121212max35216210s.t.3432,0Zxxxxxxx x2 2、物资运输问题、物资运输问题某产品商有三个供货源某产品商有三个供货源A1、A2、A3，其经销商有，其经销商有4个（需求个（需求市场）市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及。已知各厂的产量、各经销商的销售量及从从Ai 到到Bj 的单位运费为的单位运费为Cij。为发挥集团优势，公司要统一筹划运。为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。

41、销问题，求运费最小的调运方案。 销地产地B1B2B3B4产量A1632550A2758420A3329730销量20301040设从设从Ai到到Bj的运输量为的运输量为xij，运费最小的目标函数为运费最小的目标函数为 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 ：产量之和等于销量之和产量之和等于销量之和,故要满足：故要满足： 供应平衡条件供应平衡条件x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34 =30 销售平衡条件销售平衡条件x11+x21+x31

42、=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40 非负性约束非负性约束 xij0 (i=1,2,3；j=1,2,3,4) 3 3、产品配比问题、产品配比问题用浓度用浓度45%45%和和92%92%的硫酸配置的硫酸配置100100吨浓度吨浓度80%80%的的硫酸。硫酸。：1008 . 092. 045. 01002121xxxx： x1 0， x2 0 若有若有5 5种不同浓度的硫酸可选种不同浓度的硫酸可选(30%,45%,73%,85%,92%)(30%,45%,73%,85%,92%)会如何呢？会如何呢？1008 . 092. 085. 073

43、. 045. 03 . 01005432154321xxxxxxxxxx 取这取这5种硫酸分别为种硫酸分别为 xxxxx ，有，有 有多少种配比方案？有多少种配比方案？ 何为最好？何为最好？若若5种硫酸价格分别为种硫酸价格分别为400, 700, 1400, 1900, 2500元元/t，则：，则：123451234512345min400700140019002500100s.t. 0.30.450.730.850.920.8 1000,1,2,.5jZxxxxxxxxxxxxxxxxj四、线性规划的图解方法四、线性规划的图解方法 1 1、线性规划的可行域、线性规划的可行域可行域：可行域：满

44、足所有约束条件的解的集合，满足所有约束条件的解的集合，即所有约束条件共同围城的区域。即所有约束条件共同围城的区域。maxZ= 3x1 +5 x2 2 x1 16 2x2 10 3x1 +4 x2 32 x1 0, x2 0S.t.2x1 =162x2 =103x1 +4 x2 =32x1x248103590ABCD2x1 =162x2 =10 x1x248103583x1 +4 x2 =320ABCD2 2、线性规划的最优解、线性规划的最优解目标函数目标函数 Z= 3x1 +5 x2 代表以代表以 Z 为参数的一族平行线。为参数的一族平行线。Z=30Z=37Z=153 3、线性规划解的特性、线

45、性规划解的特性abcd 由线性不等式组成的可行域是凸多边形由线性不等式组成的可行域是凸多边形( (凸多边形是凸集凸多边形是凸集) )凸集定义：集合内部任意两点连线上的点都属于这个集合凸集定义：集合内部任意两点连线上的点都属于这个集合 可行域有有限个顶点。可行域有有限个顶点。 目标函数最优值一定在可行域的边界达到，而不可目标函数最优值一定在可行域的边界达到，而不可能在其区域的内部。能在其区域的内部。五、线性规划解的可能性五、线性规划解的可能性1、唯一最优解：只有一个最优点、唯一最优解：只有一个最优点2、多重最优解：无穷多个最优解、多重最优解：无穷多个最优解当市场价格下降到当市场价格下降到7474

46、元，其数学模型变为元，其数学模型变为12121212max34216210s.t.3432,0Zxxxxxxx x2x1 =162x2 =103x1 +4 x2 =32x1x24810258Z=24Z=32Z=123、无界解：可行域无界，目标值无限增大、无界解：可行域无界，目标值无限增大 (缺乏必要约束缺乏必要约束)12112max35216s.t.,0Zxxxx x4、没有可行解：线性规划问题的可行域是空集、没有可行解：线性规划问题的可行域是空集 (约束条件相互矛盾约束条件相互矛盾)12121212max355s.t. 3424,0Zxxxxxxx xx1x2O2 4 6 8 2 4 6 8

47、目标冲突目标冲突利害冲突利害冲突目标强冲突目标强冲突利害弱冲突利害弱冲突 某企业生产两种产品：某企业生产两种产品：桌子和椅子，他们都桌子和椅子，他们都要经过制造和装配两要经过制造和装配两道工序，有关资料如道工序，有关资料如下表：假设市场状况下表：假设市场状况良好，企业生产出来良好，企业生产出来的产品都能卖出去，的产品都能卖出去，问何种组合的产品使问何种组合的产品使企业利润最大？企业利润最大？桌子桌子椅子椅子工序可用时间工序可用时间（小时）（小时）制造工序的时制造工序的时间（小时）间（小时）2448装配工序的时装配工序的时间（小时）间（小时）4260单利（元）单利（元）86 某厂生产某厂生产4

48、4种机器。种机器。生产每台不同型号生产每台不同型号的机器所需各种资的机器所需各种资源（人工、机器工源（人工、机器工时、材料）的数量、时、材料）的数量、所得利润及各种资所得利润及各种资源的最大可用量如源的最大可用量如下表：又知道该厂下表：又知道该厂生产第生产第4 4种机器必须种机器必须是第是第3 3种机器的种机器的2 2倍，倍，试建立该问题的线试建立该问题的线性规划模型性规划模型。1234资源可用量人工10820101000机器工时2311200材料102030155000利润100 150 200200 设某石油公司有两个原设某石油公司有两个原油库（月供应能力分别油库（月供应能力分别为为232

49、3万吨及万吨及2727万吨），万吨），供给三个炼油厂进行加供给三个炼油厂进行加工（三个炼油厂的月加工（三个炼油厂的月加工能力分别为工能力分别为1717、1818和和1515万吨）。原油从油库万吨）。原油从油库到工厂的运输费用（元到工厂的运输费用（元/ /吨）如下表。求总运费吨）如下表。求总运费最低的原油分配和运输最低的原油分配和运输计划计划费用炼厂1炼厂2炼厂3供应力原油库156723原油库26111627加工力加工力171815 设某昼夜服务公交线设某昼夜服务公交线路每天各时间区段内路每天各时间区段内所需司机和乘务员人所需司机和乘务员人数如下：数如下： 设司机和乘务人员是设司机和乘务人员是在

50、各时间段一开始时在各时间段一开始时上班，并连续工作上班，并连续工作8 8小时，问该公交线路小时，问该公交线路至少应配备多少名司至少应配备多少名司乘人员？乘人员？班次时间所需人数16：00-10：0060210：00-14：0070314：00-18：0060418：00-22：0050522：00-2：002062：00-6：0030某厂生产某厂生产，三种产品，都分别经过三种产品，都分别经过A A，B B两道工序加工。设两道工序加工。设A A工序可分别在设备工序可分别在设备A1A1或或A2A2上完成，有上完成，有B1,B2,B3B1,B2,B3三种设备可用于完成三种设备可用于完成B B工序。已

51、知产品工序。已知产品可在可在 A A，B B任何一种设备上加工；产品任何一种设备上加工；产品可在任何可在任何规格的规格的A A设备上加工，但完成设备上加工，但完成B B工序时，只能在工序时，只能在B1B1设备上加工；产品设备上加工；产品只能在只能在A2A2与与B2B2设备上加工。加工单位产品所需工序时间及其它数据如设备上加工。加工单位产品所需工序时间及其它数据如表，试安排最优生产计划，使该厂获利最大？表，试安排最优生产计划，使该厂获利最大？设备设备产品产品设备有效设备有效台时台时设备加工费设备加工费元元/时时A15106，0000.05A2791210，0000.03B1684，0000.06

52、B24117，0000.11B374，0000.05原料费原料费元元/件件0.250.350.50售价售价元元/件件1.252.002.80第四部分、网络计划技术第四部分、网络计划技术p 2020世纪世纪5050年代以来，国外陆续出现了一些计划管理的新方法，年代以来，国外陆续出现了一些计划管理的新方法，如如关键路线法关键路线法(critical path method，缩写为缩写为CPM)，计划评审计划评审方法方法(program evaluation & review technique，缩写为缩写为PERT) )等，这些方法都是建立在网络模型基础上，称为等，这些方法都是建立在网络模型基础上

53、，称为网络计划技网络计划技术术p 我国著名数学家华罗庚先生将这些方法总结概括称为我国著名数学家华罗庚先生将这些方法总结概括称为统筹方法统筹方法，在在6060年代初引入我国年代初引入我国。 网络计划技术的基本思路网络计划技术的基本思路 运运用用网络图网络图的形式表达一个计划项目中各的形式表达一个计划项目中各种活动（作业、工序）之间的先后次序和相互种活动（作业、工序）之间的先后次序和相互关系，在此基础上进行网络分析，计算关系，在此基础上进行网络分析，计算网络时网络时间，确定关键活动和关键路线；然后利用时差，间，确定关键活动和关键路线；然后利用时差，对网络进行工期、资源和成本的优化；对网络进行工期、

54、资源和成本的优化；在实施在实施过程中，通过信息反馈进行监督和控制，以确过程中，通过信息反馈进行监督和控制，以确定计划目标的实现。定计划目标的实现。例：例：某飞机发动机维修项目，包括以下作业某飞机发动机维修项目，包括以下作业 A. 拆卸，拆卸，5天；天； B. 电子器件检查，电子器件检查，8天；天； C. 机械零件检查，机械零件检查，10天；天； D. 机械零件更换，机械零件更换，6天；天； E. 机械零件维修，机械零件维修，15天；天； F. 电子器件更换，电子器件更换，9天；天； G. 组装，组装，6天；天； H. 试车，试车，3天。天。 4 46 65 53 37 78 8DEFGH1 1

55、2 2ABC51081596631.网络图的构成网络图的构成 a.活动（或作业或工序）活动（或作业或工序） 活动是一项需要消耗资源，经过一定时间才能活动是一项需要消耗资源，经过一定时间才能完成的具体工作，网络图上用箭线完成的具体工作，网络图上用箭线“”表示。箭线表示。箭线前后的结点进行编号，分别表示活动开始和结束。前后的结点进行编号，分别表示活动开始和结束。活动名称或代号一般写在箭线上方，而活动所消耗活动名称或代号一般写在箭线上方，而活动所消耗的时间或其他资源一般置于箭线下方。相邻排列的的时间或其他资源一般置于箭线下方。相邻排列的活动，前活动是后活动的近前（紧前）活动。活动，前活动是后活动的近

56、前（紧前）活动。b.事项（或事件或结点）事项（或事件或结点） 表示两项活动的连接点，既不消耗资源，也不占用时表示两项活动的连接点，既不消耗资源，也不占用时间，只表示前一活动的开始、后一活动的结束的瞬间。间，只表示前一活动的开始、后一活动的结束的瞬间。c.路线路线 路线是网络图中由始点活动出发，沿箭线方向前进，路线是网络图中由始点活动出发，沿箭线方向前进，连续不断地到达终点活动的一条通道，表示一个独立的工连续不断地到达终点活动的一条通道，表示一个独立的工作流程。网络图中一般有多条路线，作流程。网络图中一般有多条路线，其中消耗时间最长的其中消耗时间最长的一条称为关键路线（用双箭线表示），它决定总工

57、期。一条称为关键路线（用双箭线表示），它决定总工期。2.网络图绘制的规则网络图绘制的规则 a. a. 箭线一般均指向右边，不允许出现反向箭头。箭线一般均指向右边，不允许出现反向箭头。 b. b. 任一箭线的箭尾结点编号必须小于箭头结点任一箭线的箭尾结点编号必须小于箭头结点 编号；整个网络图中的编号不能重复；编号编号；整个网络图中的编号不能重复；编号 可以不连续。可以不连续。 c. c. 两个结点之间只能有一条箭线，如果有两项两个结点之间只能有一条箭线，如果有两项 平行活动，则应用平行活动，则应用 虚箭线保证此规则虚箭线保证此规则 不被破坏。不被破坏。 123ABd. 箭线不可交叉。箭线不可交叉

58、。e.一个网络图只应有一个起点和一个终点。一个网络图只应有一个起点和一个终点。543126754312675431267 3.网络图的绘制步骤网络图的绘制步骤 a. a. 任务分解与分析：任务分解与分析：确定完成项目必须进行确定完成项目必须进行 的每一项活的每一项活动，并确定活动之间的逻辑关系。动，并确定活动之间的逻辑关系。 b.b.根据活动之间的关系绘制网络图根据活动之间的关系绘制网络图（草图、美（草图、美 化图、结点编号）。化图、结点编号）。 c.c.估计和计算每项活动的完成时间。估计和计算每项活动的完成时间。 计算法计算法 估计法估计法 ： t=t=（a+4m+ba+4m+b）/6/6

59、统计确定法统计确定法 d.d.计算网络图的时间参数并确定关键路线。计算网络图的时间参数并确定关键路线。 e.e.进行网络图优化。进行网络图优化。乐观估计乐观估计 悲观估计悲观估计时间参数的计算时间参数的计算 工序所需时间的确定工序所需时间的确定 一般采用经验估算的方法：肯定估计法和非肯定估计法最佳时间a、最长时间b、最可能时间m 各工序的最早时间与最迟时间的计算各工序的最早时间与最迟时间的计算最早结束=最早开始+T 最迟开始=最迟结束-T 时差及关键路线的确定时差及关键路线的确定最迟开始-最早开始 或 最迟结束-最早结束时差时差=0=0的线路为关键线路的线路为关键线路22)6()64(61ab

60、mat工序名称工序名称该工序的先行工序该工序的先行工序该工序所需的时间（天）该工序所需的时间（天）A4B5C2D3EA3FB4GB6HC5IE,D,B2JH,F4 在紧密衔接的各工序中，在紧密衔接的各工序中，先行工序的最早结束时间，就是后继先行工序的最早结束时间，就是后继工序的最早开始时间工序的最早开始时间，加上，加上t t，就是该工序的最早结束时间：，就是该工序的最早结束时间： 最早结束时间最早结束时间EF=EF=最早开始时间最早开始时间ES+tES+t 当有几个先行工序时，取最大值当有几个先行工序时，取最大值 后继工序的最迟必须开始时间，就是它的先行工序的最迟结束后继工序的最迟必须开始时间