管理运筹学讲义

1、管理运筹学-管理科学方法谢家平 博士 教授博士生导师研究领域：管理科学、运营管理、供应链管理讲授课程：管理运筹学-管理科学方法、管理系统工程、 运营管理、 供应链管理、ERP、国际物流、 企业物流管理、管理决策模型与方法单 位：上海财经大学工商学院 物流管理系 E-mail：1教材与参考书籍教材：谢家平编著.管理运筹学：管理科学方法， 中国人民大学出版社，2010参考书：David et al. 数据、模型与决策，机械工业出版社，2004费雷德里克. 数据、模型与决策，中国财政经济出版社，2004James et al. 数据、模型与决策，中国人民大学出版社，2006232课时讲授提纲绪 论第

2、一章 线性规划第二章 线性规划讨论第三章 对偶规划 静态规划第四章 整数规划第五章 目标规划第六章 动态规划 动态优化第七章 网络分析第八章 网络计划第九章 决策分析第十章 方案排序第十一章 库存控制第十二章 排队理论离散优化随机优化淡化数学算法LINDO求解3考核方式结课考试：笔试（开卷 or 闭卷？） 每章一题 80%案例研究：选择合适方法结合企业实际进行应用 20%4管理运筹学的称谓管理运筹学是一门研究如何最优安排的学科。 Operations Research日本译作“运用学”香港、台湾译为“作业研究”我国译作“运筹学”源于古语“运筹帷幄之中，决胜千里之外”取“运筹”二字，体现运心筹谋

3、、策略取胜Management Science 管理科学运用数学、统计学和运筹学中的量化分析原理和方法，建立数学模型/计算机仿真，给管理决策提供科学依据。 5绪 论一、发展历史二、学科作用 三、学科性质四、工作程序五、学科体系六、学习要求6一、发展历史1. 早期的运筹思想 齐王赛马 渭修皇宫沈括运军粮 科学管理 2. 军事运筹学阶段 20世纪40年代诞生于英美1940年，英国为对付德国空军的空袭，使用了雷达，但没有科学布局，效果不好。为解决这个问题，成立运筹学小组，称Operational Research，意为作战研究。美国和加拿大也在军队设立运筹学小组，称Operations Resear

4、ch，协助指挥官研究战略及战术问题。3. 管理运筹学阶段战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹学在企业管理方面的应用得到了长足进展。7企业的成功要素中：观念意识更新 47人文文化 35技术优势 18决策意识的科学性成功决策正确决策二、学科作用 理念的重要性？8二、学科作用1. 量化管理的重要性 管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策的一门学科。目的：用科学方法分析管理问题，为管理者决策提供依据目标：在企业经营内外环境的限制下，实现资源效用最大组织中存在的问题定量分析定性分析评价与评估决策量化管理是第一步,它导致控制,并最终实现改进如果不能量化

5、某些事情，那么就不能理解它如果不能理解它，那么就不能控制它如果不能控制它，那么就不能改进它 H. James Harrington定性到定量分析，数量界限的重要性：量变引起质变9听一场音乐会：网络订票的票价500元，不去可退票情况1：在你马上要出发的时候，发现你把最近的价值500元的电话卡弄丢了。你是否还会去听这场音乐会？情况2：假设昨天花500元钱买一张今晚的音乐会取票单。在你出发时，发现把票单丢了。如果去听音乐会，就必须再花500元钱买张票，去还会不去？二、学科作用 2. 量化思考使人理性 冰淇淋实验：一杯A有70克，装在50克的杯子里，看上去要溢出了一杯B是80克，装在100克的杯子里，

6、看上去还没装满 单独凭经验判断时，在相同的价格上，人们普遍选择A 实验表明，大部分的回答者仍旧会去听结果却是，大部分人回答说不去了10二、学科作用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 信息化，

7、第三利润源11二、学科作用量化辅助决策案例：盈亏平衡分析例：某企业 总销售额 1100万元 物料成本 700万元 员工工资 200万元 管理费用 100万元现在利润=100万元，目标利润150万元利润实现的方法有：将销售收入增加100%将员工工资减少 25%将管理费用减少 50%将物料成本减少 7.1%12二、学科作用4. 决策意识的重要性 生产计划决策一星期工作5天, 每天正常工作8小时一周作业费用：11000 (直接人工成本与间接费用)直接人工成本：10/1h (一台机器需一位作业人员)间接费用：人工成本2.5倍甲乙丙原料659565直接工时65分95分65分直接人工121410间接費用3

8、03525总成本107144100售价173233170利润668970H 18H 6H 10甲设备数EGHFHGG20H 13E 6F 10裝配E 24E 15G 7DG 14G10H 7F 10G 7G 4CBA裝配H 14乙丙13二、学科作用甲产品产量40, 乙产品 80, 丙产品 40利润=4066+8089+4070=12560 人员有限如何实现?采取什么薪酬制度?计件工资制，让员工自愿加班甲乙丙单位产品总成本107144100单位产品售价173233170单位产品利润668970市场每周需求408040决策的科学性？方案 一14二、学科作用甲产品产量 40, 乙产品 80, 丙产品

9、 40总收入=40173+80233+40170=32360原料成本=4065+8095+4065=12800营运费用=11000总利润=32360-12800-11000=8560人员有限如何实现?采取什么薪酬制度?岗位工资制（定岗定员），让员工自觉加班甲乙丙原料659565运营费用11000售价173233170市场每周需求408040决策的科学性？方案 二15二、学科作用 决策的科学性？产能符合计算甲乙丙总成本107144100售价173233170利润668970乙与丙哪一个产品比较赚钱? 产品市场需求单位产品设备工时消耗EFGH甲400103131乙8030202113丙401502

10、124需求产能3000200037603240可用产能2400240048004800E是瓶颈16二、学科作用方案 三：计时工资，且以单位利润率高低为决策意识。 乙比较赚钱, 假如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个需

11、用E产能600(4015)分钟剩下1800分钟, 可生产60个乙 (1800/30)方案：甲产品 40个，乙产品 60个，丙产品 40个总收入=40173+60233+40170=27700原材料=4065+6095+406540=10900 ，营运费用=11000利润=27700-10900-11000=580017三、学科性质 1. 研究对象经济和管理活动中能用“数量关系”描述的如运营、规划与组织管理问题解决的理论模型和优化方法实践 2. 学科特点强调科学性和定量分析强调应用性和实践性强调从整体上进行把握 18四、工作程序管理者制定决策：管理运筹学的步骤：明确问题环境分析确定目标制定准则收

12、集资料数量关系结构分析数学模型制定决策方案选择算法求解方案优选否是方案实施持续改进识别问题量化分析建立模型软件求解结果分析确定方案实施方案控制管理者解的分析19五、学科体系 1. 管理问题 需求预测产品的市场需求量有多大，需求类别如何，对企业盈利有何影响?生产计划在有限资源约束下，生产什么，生产多少，获利最大？资源配置需要哪些资源，如何进行最优配置，资源紧缺性如何，以什么代价获取?作业排序作业的重要次序如何，作业的顺序安排如何?市场营销广告预算、媒介选择、产品定价、销售计划等如何安排？运输问题最佳运输线路是哪条？物流配送集载如何优化？物流设施布局如何设置？设施选址运营点如何选择，需要哪些运作设

13、施，设施如何布局?库存控制应保持多大库存量，何时应进行订货，订货批量多少为宜?项目规划项目完工工期多长为宜，哪些作业起关键性作用，资源如何分配?设备更新设备运转状况如何演进，运行可靠性如何，何时和如何更新或改造?人力资源人员需求预测，技能要求，编制与任务指派，绩效测评，留用多长时间?财务资金资金投放的数量，从何处进行融资，资金成本是多少?排队问题队列多长，有无容量限制，多少服务台为宜，能提供什么水平的服务?20五、学科体系2. 学科内容 模型类型解决的典型办法线性规划在线性目标和约束条件间取得最优化结果整数规划在线性目标和约束条件间寻求整数决策最优目标规划在相对立的目标间寻得多目标妥协的满意解

14、动态规划寻求多阶段动态系统的整体决策优化问题网络分析寻求网络路径、流量分布、网络瓶颈及其改进网络计划用各种作业和结点的网络排列来说明项目实施计划管理决策依据决策准则权衡比较备选方案的决策结果方案排序综合各方案的优势与不足寻求多指标排名次序库存模型寻求订货、存储和缺货等库存成本降至最低的经济批量统计方法从一个抽样得到普遍结果的推论和曲线拟合排队理论分析正在等待的队列特点及其运行指标仿真模拟动态观察复杂的管理问题的行为，模拟管理系统的结构关系21五、学科体系3. 学科应用管理既是科学又是艺术低层管理的科学成分较多，高层管理的艺术成分较多运营管理需较多管理科学，人力资源管理需较多管理艺术例行管理需要

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

16、企业A商务2商务3商务1职能b职能c职能a小组ii小组iii小组i运营管理市场营销质量管理项目管理信息管理流程管理物流管理供应链管理24六、学习要求2. 如何学习重点在结合实际的应用发挥自己管理实践经验丰富和理论联系实际的能力强化结合实际问题建立管理优化模型的能力强化解决问题的方案或模型的解的分析与应用能力充分借用管理运筹学教学软件25第1 章 线性规划Sub title内容提要第一节 线性规划的一般模型一、线性规划的三个要素二、线性规划模型的特征三、线性规划的图解方法四、线性规划解的可能性第二节 线性规划的单纯形法一、线性规划的标准型式二、线性规划之解的概念三、单纯形法的基本原理26一、线性

17、规划的三个要素 第一节 线性规划的一般模型 决策变量决策问题待定的量值取值要求非负约束条件任何管理决策问题都是限定在一定的条件下求解把各种限制条件表示为一组等式或不等式称约束条件约束条件是决策方案可行的保障约束条件是决策变量的线性函数目标函数衡量决策优劣的准则，如时间最省、利润最大、成本最低目标函数是决策变量的线性函数有的目标要实现极大，有的则要求极小27二、线性规划模型的举例 第一节 线性规划的一般模型 1、生产计划问题例. 某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。 据市场

18、分析，单位甲乙产品的销售价格分别为73和75元，试确定获利最大的产品生产计划。 产品设备工时消耗甲 乙工时成本元/h生产能力hABC 2 0 0 2 3 420151016103228第一节 线性规划的一般模型 (1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。(2)约束条件：生产受设备能力制约，能力需求不能突破有效供给量。设备A的约束条件表达为 2 x1 16同理，设备B的加工能力约束条件表达为 2x2 10设备C的装配能力也有限，其约束条件为 3x1+ 4x2 32(3)目标函数：目标是企业利润最大化 max Z= 3x1 +5x2 (4)非负约束：甲乙产品的产量为非负 x1 0，

19、 x2 0综上的LP模型：29二、线性规划模型的举例 第一节 线性规划的一般模型 2、物资运输问题例：某产品商有三个供货源A1、A2、A3，其经销商有4个（需求市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及从Ai 到Bj 的单位运费为Cij。为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。 销地产地B1B2B3B4产量A1632550A2758420A3329730销量2030104030第一节 线性规划的一般模型 (1)决策变量：设从Ai到Bj的运输量为xij，(2)目标函数：运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x

20、22+8x23+4x24+3x31+2x32+9x33+7x34 (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二、线性规划模型的举例 第一节 线性规划的一般模型 3、产品配比问题例：用浓度45%和92%的硫酸配置100吨浓度80%的硫酸。 决策变量：取45%和92%的硫酸分

21、别为 x1 和 x2 吨 约束条件： 求解二元一次方程组得解 非负约束： x1 0， x2 032第一节 线性规划的一般模型 若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢？取这5种硫酸分别为 x1、x2、x3、x4、x5 ，有有多少种配比方案？何为最好？若5种硫酸价格分别为400, 700, 1400, 1900, 2500元/t，则：33三、线性规划模型的特征 第一节 线性规划的一般模型 1、模型隐含假定（1）线性化假定 函数关系式f(x)= c1x1+c2x2+ +cnxn，称线性函数。 建模技巧：将非线性的函数进行分段线性化。（2）同比例假定决策变量变化引

22、起目标函数和约束方程的改变量比例。（3）可加性假定 决策变量对目标函数和约束方程的影响是独立于其他变量的。目标函数值是决策变量对目标函数贡献的总和。 （4）连续性假定 决策变量取值连续。（5）确定性假定 所有参数都是确定的，不包含随机因素。34三、线性规划模型的特征 第一节 线性规划的一般模型 2、一般数学模型 用一组非负决策变量表示的一个决策问题； 存在一组等式或不等式的线性约束条件； 有一个希望达到的目标，可表示成决策变量的极值线性函数。35四、线性规划的图解方法 第一节 线性规划的一般模型 1、线性规划的可行域可行域：满足所有约束条件的解的集合，即所有约束条件共同围城的区域。maxZ=

23、3x1 +5 x2 2 x1 16 2x2 10 3x1 +4 x2 32 x1 0, x2 0S.t.2x1 =162x2 =103x1 +4 x2 =32x1x248103590ABCD362x1 =162x2 =10 x1x248103583x1 +4 x2 =320ABCD四、线性规划的图解方法 第一节 线性规划的一般模型 2、线性规划的最优解目标函数 Z= 3x1 +5 x2 代表以 Z 为参数的一族平行线。Z=30Z=37Z=1537四、线性规划的图解方法 第一节 线性规划的一般模型 3、线性规划解的特性abcd由线性不等式组成的可行域是凸多边形(凸多边形是凸集)凸集定义：集合内部

24、任意两点连线上的点都属于这个集合可行域有有限个顶点。 目标函数最优值一定在可行域的边界达到，而不可能在其区域的内部。38五、线性规划解的可能性第一节 线性规划的一般模型 1、唯一最优解：只有一个最优点2、多重最优解：无穷多个最优解当市场价格下降到74元，其数学模型变为 2x1 =162x2 =103x1 +4 x2 =32x1x248102580ABCDZ=24Z=32Z=1239五、线性规划解的可能性第一节 线性规划的一般模型 3、无界解：可行域无界，目标值无限增大 (缺乏必要约束)40五、线性规划解的可能性第一节 线性规划的一般模型 4、没有可行解：线性规划问题的可行域是空集 (约束条件相

25、互矛盾)目标冲突利害冲突目标强冲突利害弱冲突41一、线性规划的标准型式 第二节 线性规划的一般模型 1、标准型表达方式(1)代数式 (2)向量式 (3)矩阵式 A：技术系数矩阵，简称系数矩阵；B：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策向量。42一、线性规划的标准型式 第二节 线性规划的一般模型 2、标准型转换方法(1)如果极小化原问题minZ=CX，则令 Z=-Z，转为求 maxZ=-CX (2)若某个bi Pk+1 。同一优先等级下目标的相对重要性赋以不同权数w。95第二节 目标规划的数学模型例如P1 级目标实现利润至少30元； P2级目标是甲乙产品的产量

26、假设：乙产品产量不少于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)96第三节 目标规划的图解法目标规划的图解法首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。F2x1 =162x2 =10BCx14A103x1 +4 x2 =326x20D2642EGHx1=5, x2=497第四节 目

27、标规划的应用案例一、无穷多满意解解：设x1,x2表示A、B产品的产量。两个等级的目标：P1：充分利用电量限额，正负偏差之和为最小 目标达成函数 目标约束条件 P2 ：利润额希望不能低于100元，负偏差最小 目标达成函数 目标约束条件 计划生产两种产品，首先要充分利用设备工时而不加班；然后考虑利润不低于100元。问应如何制定产品A、B的产量。982A24BDx26810 x1第四节 目标规划的应用案例一、无穷多满意解由于材料供应限量为8单位，所以有系统约束条件，如下该问题的目标规划模型如下，图解法求解如图CG99第四节 目标规划的应用案例二、加班时间问题例：某音像店有5名全职售货员和4名兼职售货

28、员，全职售货员每月工作160小时，兼职售货员每月工作80小时。根据记录，全职每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元。兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元。现在预测下月CD销售量为27500张，商店每周开门营业6天，所以可能要加班。每出售一张CD盈利1.5元。 商店经理认为，保持稳定的就业水平加上必要的加班，比不加班就业水平要好，但全职销售员如果加班过多，就会因为疲劳过度而造成效率下降，因此不允许每月加班超过100小时，建立相应的目标规划模型。100第四节 目标规划的应用案例二、加班时间问题首先，确定目标约束的优先级。如下：P1

29、：下月的CD销售量达到27500张；P2：全职售货员加班时间不超过100小时；P3：保持全体售货员充分就业，对全职的要比兼职的加倍优先考虑；P4：尽量减少加班时间，对两种售货员区别对待，权重由他们对利润的贡献而定。其次，建立目标约束函数（1）销售目标约束，设全体全职售货员下月的工作时间x1，全体兼职售货员下月的工作时间 x2；达不到销售目标的偏差d1-，超过销售目标的偏差 d1+。 101第四节 目标规划的应用案例二、加班时间问题 （2）正常工作时间约束。设全体全职售货员下月的停工时间d2-，加班时间d2+ ；全体兼职售货员下月的停工时间d3-，加班时间d3+。（3）加班时间的限制。设全体全职

30、售货员下月的加班不足100小时的偏差d4-，加班超过100小时的偏差 d4+ 。两类售货员区别对待，权重比d2+:d3+ =1:3，另一加班目标约束为102第四节 目标规划的应用案例二、加班时间问题 第三，按目标的优先级，写出相应的目标规划模型：运用LINGO软件求解得 x1=900,x2=500，下月共销售CD盘27500张，获利275001.5-80015-10022.5-50010=22000。103第四节 目标规划的应用案例三、目标管理方案 例：某公司准备生产甲、乙产品，据市场调查：甲产品的最大市场需求3台，乙产品的最大市场需求2台。 在满足现有电力资源严格供给约束的前提下，该厂长考虑

31、两个目标：一是总利润不低于3600元；二是充分利用设备台时，但尽量少加班。问应如何制定产品甲、乙的产量，试建立其目标规划的数学模型。104第四节 目标规划的应用案例三、目标管理方案 1. 利润期望优先目标规划数学模型： 运用图解法进行求解 FECx1 =8x2 =65x1 +5x2 =600 x12410126ABx20842D10Gx1 =8, x2 = 3105第四节 目标规划的应用案例1. 利润期望优先 总利润：3600单位甲：300单位乙：400生产部目标甲产品的产量：8，成本：900乙产品的产量：3，成本：1400技术部目标甲的设备单耗25，需降低5工时 乙的设备单耗50，需降低10

32、工时 销售部目标甲产品的销量：8，单价：1200乙产品的销量：3，单价：1800满意解：x1 =8, x2 = 3设备能力：需求：308+60 3=420，实际：360实现目标P1和P2，降低甲乙产品的设备消耗:降低率(420-360)/360=17%， 甲产品的设备消耗降为30 (1-17%)=25, 乙产品的设备消耗降为60 (1-17%)=50。106第四节 目标规划的应用案例三、目标管理方案 2. 设备工时优先目标规划数学模型： 运用图解法进行求解 FECx1 =8x2 =65x1 +5x2 =600 x12410126ABx20842D10Gx1 =8, x2 = 2107第四节 目

33、标规划的应用案例2. 设备工时优先 总利润：3600单位甲：337.5单位乙：450 生产部目标甲产品的产量：8，成本：862.5 乙产品的产量：2 ，成本：1350 技术部目标保证设备的正常运行甲的设备单耗30 ，乙的单耗60 销售部目标甲产品的销量：8，单价：1200乙产品的销量：2 ，单价：1800满意解：x1 =8, x2 = 2利润总额3008+4002=3200，目标：3600不能提价，就必须降低成本以增加利润，利润增长率为12.5% 甲产品的成本需要降为1200-300(1+12.5%)=862.5元/台，降低幅度4.2% 乙产品的成本需要降为1800-400(1+12.5%)=

34、1350元/台，降低幅度3.6% 108第7 章 网络分析Sub title内容提要第一节 图论的概念第二节 最小树问题第三节 最短路问题第四节 网络最大流第五节 最小费用流10918世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？ 第7 章 网络分析陆地A陆地B岛D岛CAD B C 1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。110第一节 图论的概念一、图的内涵 1、图的定义 v1 v4v2 v3e1e2e3e4e5e6

35、v1 v4v2v3 e1e2e3e4e5e6 v1 v2 v3 v4e1e2e3e4e5e6图论的图与一般几何图形或代数函数图形是完全不同的图论中的图:由一些点和连接点的线所组成的“图形”点和线的位置是任意的线的曲直、长短与实际无关，代表的只是点与点之间的相互关系例：表示苏州v1 、杭州v2 、上海v3 、南京v4仓储网点之间的物流运输线路关系 111第一节 图论的概念一、图的内涵 2、图的分类 不带箭头的连线称为“边”，如公路运输线路； 带箭头的连线称为“弧”，如供排水的管道运输线路。1、无向图 由点和边的集合所构成由点和弧的集合所构成 2、有向图 链：无向网络中，前后相继点和边的交替序列称

36、为一条链。 圈：闭合的链称为一个圈。 路径：有向网络图中，前后相继并且方向一致的点弧序列称为一条路径。 回路：闭合的路径称为一个回路。 112第二节 最小树问题例：一家企业分别要在6间办公室铺设网线接入口，网线的可行走线方式如下图所示，如何铺设网线才能使网线总长为最短？ 最短网线总长度为最小树权之和2+3+4+6+6=21 8 2 3 546 6 6 8v1v4v2v3v5v6 无圈的连通图就是一棵树。 权数总和为最小的那棵支撑树，称为最小树。 求解方法： 破圈法 避圈法113第三节 最短路问题一、双标号算法 狄克斯特拉(Dijkstra)算法路权：弧(vi, vj)的权为wij；路权是路p中

37、各条弧权之和最短路：在所有从vs到vt 的路p中，求一条路权最短的路算法说明：1959年提出，目前公认的最短路算法适合于求解所有弧权wij 0的最短路问题算法假设：有向图D是完备图图D中任意两点vi , vj 之间，恰有两条弧(vi , vj)和(vj , vi)若vivj 不存在弧, 可设想一条从vi vj 的弧, 权wij=+；若vi vj 有重复的弧，则保留弧权最小的弧114第三节 最短路问题一、双标号算法 基本思路:从始点vs 出发，逐步探寻，给每个点标号；标号分永久标号P(vk)和临时标号T(vk) 两种：永久标号P(vk) 是从点 vs vk 的最短路权临时标号T(vk) 是从点

38、vs vk 最短路权的上界算法的每一步从临时标号集中选最小者变为永久标号；经过逐次改变，就可以得到从点vs 到各点的最短路。 标号形式：单标号法是对每一点赋予一个路权标号双标号法是对每一点赋予两个标号：路标、路权115第三节 最短路问题一、双标号算法 例：用双标号法求下图网络最短路3947326141287110116第三节 最短路问题一、双标号算法 第一步：3947326141287110117第三节 最短路问题一、双标号算法 第二步：3947326141287110118第三节 最短路问题一、双标号算法 第三步：3947326141287110119第三节 最短路问题一、双标号算法 最终：

39、依此类推，重复上述标号过程。得最短路。 3947326141287110120第三节 最短路问题二、最短路的应用 1、网络的中心所谓网络的中心是指一个网络中，选择某一点，使之其余各点到该中心点的距离之和为最小。例：如果要在下表中6个销售点中选一个作为仓库所在地，应该建在哪个经销点，使其余各销售点都离它较近？121第三节 最短路问题二、最短路的应用 2、网络的重心引进点的权系数，将权系数与最短距离阵各列对应元素加权求和，再从中选择最小的即为网络重心。122第四节 网络最大流一、相关概念与定理1、弧容量与容量网络 对于有向图 D=(V,A),，弧 的容量表示弧的最大流通能力。在V中指定一点称为发点

40、(记为vs )，另一点称收点(记为vt)，其余点叫中间点，这样的赋权有向图就称为一个容量网络，记N=(V,A,B)2、弧的流量与可行流 弧的实际通过量称为该弧的流量。弧集A上的流量集合 称为网络上的流。满足下述条件的流称为可行流。 容量限制：对每条弧 ，都有 平衡条件：中间点流出量=流入量123第四节 网络最大流一、相关概念与定理3、前向弧与后向弧 4、饱和弧与非饱和弧 弧 的流量 与之容量 比较：满足 的弧称为饱和弧，弧的流量不能再扩充；满足 的弧称为非饱和弧，弧的流量允许再被扩大。是从vs 到vt 的链，方向从vs vt ，则链上的弧分为两类 前向弧：弧的方向与链的方向相同，记+ 后向弧：

41、弧的方向与链的方向相反，记-5、零弧与非零弧 满足 的弧称为零弧。由于 ，所以弧的流量不能减小；满足 的弧称为非零弧。弧的流量可以被减小，但要满足 0。 124第四节 网络最大流一、相关概念与定理6、流量可以扩充的路 设 是一可行流，是从vs 到vt 的链，若链满足： 上的所有前向弧为非饱和弧，即满足 ，可以扩充流量 上的所有后向弧为非零弧，即满足 ，可以减少流量；则称是一条关于可行流 的可扩充流量的路，亦称增广链。7、流量可以扩充的路 可行流中，网络发点的流出量（或网络收点的流入量）就是网络的流量。一个容量网络的诸可行流中，网络流量最大的可行流，称为最大流 125第四节 网络最大流二、求最大

42、流标号法 1956年，福特和富尔克逊提出了寻求网络最大流的基本方法，称为福特-富尔克逊算法（Fold-Fulkerson Algorithm）。给定可行流X=xij ，标号判断有无增广链先给vs 标上(vs, +)，vs已标号尚未检查，其余未标号取一个已标号但未检查的点vi进行检查，对未标号点vj ：前向弧(vi, vj)可以扩充流量(xijrij)vj尚未标号，则给vj 标号(vi，+)，vj 成为己标号尚未检查的点后向弧(vk, vi)可以减少流量(xki0) vk尚未标号，则给vk 标号(vi, -)，vk成为己标号尚未检查的点vi 成为已标号已检查的点，在其标号下划横线检查收点vt 是

43、否已标号：vt被标上号则找到增广链，进行流量调整；否则转第步若所有标号都已检查，vt又未标号，则不存在增广链标号过程 126第四节 网络最大流二、求最大流标号法 流量调整过程反向追踪找出vs 到vt 的增广链计算增广链上可调整的流量调整可行流的流量，得新的可行流xij 抹去所有标号，对新的可行流X =xij，重新进入标号过程127第四节 网络最大流二、求最大流标号法 例：下图表示了企业所处的供应市场（v1和v2）、配送中心（v3和v4、以及销售市场（v5、v6和 v7）组成的网络，各弧上括号里的前一个数字表示弧的容量，后一个数字是目前的实际流量。试求这个供应-销售网络的最大流方案。 (4,3)

44、(10,6)(15,9)(4,4)(5,5)(6,3)(6,6)128第四节 网络最大流二、求最大流标号法 供应-销售网络的可行流 (4,3)(10,6)(15,9)(4,4)(5,5)(6,3)(6,6)(15,6)(12,12)(5,4)(10,8)(8,6)129第四节 网络最大流二、求最大流标号法 供应-销售网络的可扩充路 (4,3)(10,6)(15,9)(4,4)(5,5)(6,3)(6,6)(15,6)(12,12)(5,4)(10,8)(8,6)(+ ,)(+ ,4)(+ ,9)(- ,3)(+ ,3)(+ ,3)(+ ,2)130第四节 网络最大流二、求最大流标号法 调整后的

45、可行流 最大流量为(4,1)(10,8)(15,11)(4,4)(5,5)(6,5)(6,6)(15,8)(12,12)(5,4)(10,10)(8,6)131第四节 网络最大流三、网络的瓶颈识别 1、截集-截量与最小截集 2、最大流-最小截量定理 网络中，任一可行流的流量恒不超过任一截集的截量，称为流量-截量定理。最小截量的大小影响总流量的提高 截集：对于网络N=(V,A,R)，将V分为两个非空集合S和S，使发点vsS，收点vtS 所有起点属于S而终点属于S的弧的集合称为截集 (S,S)截量：截集(S,S) 中所有弧的容量之和 r(S,S) 最小截集：截量最小的截集132第五节 最小费用流一

46、、调整法求解步骤 先不考虑费用问题，求得任一可行流X据此构造赋权有向图W(X) 顶点是原网络N的顶点弧权根据可行流X确定弧(vi, vj)的流量可以增加，则照原方向画弧，标上费用bij弧(vi, vj)的流量可以减少，则照反方向画弧，标上费用-bij在赋权有向图W(X)中寻找负回路(总权为负值的回路)：若没有负回路，则得到最小费用流若存在负回路，则调整与负回路相对应的弧上的流量计算调整量，进行流量调整若弧(vi,vj)与负回路方向一致，则其流量调整为xij +若弧(vi,vj) 与负回路方向相反，则其流量调整为xij -赋权有向图寻找负回路调整流量直到没有负回路133第五节 最小费用流二、调整

47、法应用举例 例：下图表示了企业所处的供应市场（v1和v2）、配送中心（v3和v4、以及销售市场（v5、v6和 v7）组成的网络。弧旁的数字为 ,分别表示弧的容量、实际流量、费用。试求这个供应-销售网络流的最小费用流 (4,1)(10,8)(15,11)(4,4)(5,5)(6,5)(6,6)(15,8)(12,12)(5,4)(10,10)(8,6)3053564311181010134第五节 最小费用流二、调整法应用举例 1、赋权有向图 2、寻找负回路 在赋权有向图 中，寻找总权数为负的回路选取负权绝对值大的那条负回路进行流量分布调整 -10305-3564-3-118-10-30-1-11

48、-8-4-5-6135第五节 最小费用流二、调整法应用举例 3、调整弧流量 重复上述步骤,直至找不到负回路 最小费用为各弧上流量和单位费用的乘积之和，从左向右依次为930+1135+95+60+114+410+510+58+63+41+101+61=912。(4,0)(10,9)(15,11)(4,4)(5,5)(6,5)(6,6)(15,9)(12,11)(5,4)(10,10)(8,6)3053564311181010136第8 章 网络计划Sub title内容提要第一节 网络图的绘制第二节 关键路线法 结点的时间参数 作业的时间参数 时差与关键路线第三节 计划评审技术第四节 网络计划优

49、化 缩短工程工期 工期-费用优化 工期-资源优化第五节 缓冲时间设置 137第8 章 网络计划 网络计划的发展历程 关键路线法(Critical Path Method，CPM )计划评审技术(Program Evaluation and Review Technique，PERT )图示评审技术(Graphic Evaluation and Review Technique，GERT )风险评审技术(Venture Evaluation Review Technique，VERT ) 网络计划技术的特性 网络计划技术只不过是反映和表达项目计划安排的一种方法，是被项目施工技术所决定的，它只能适

50、应项目施工方法的要求。是把工程进度安排通过网络的形式直观地反映出来。 138第一节 网络图的绘制一、网络计划的图示形式 工序(作业)：一项需要人财物或时间等资源的相对独立的活动过程在网络图中用箭线“” 表示，前面直接相连工序称紧前工序，直接相连的后继工序为紧后工序。 结点(事项)：相邻工序的分界点一般用圆圈来表示，每个结点编上顺序号，结点既不消耗人力、物力，也不占用时间。网络图由工序、事项及时间参数所构成的有向图即为网络图。 箭线表示工序,结点为工序间相互关系的网络图，称箭线式网络结点表示工序,箭线为工序间相互关系的网络图，称结点式网络139第一节 网络图的绘制一、网络计划的图示形式 1、箭线

51、式网络图 21A25B343C55D5Et作业时间iN作业名称j2、结点式网络图 t作业时间N作业名称iNti作业序号122543355560140第一节 网络图的绘制二、箭线式网络图的规则 工序表示的规定一条箭线和它的相关事项只能代表一道工序，不能代表多道工序， 两个结点之间只能有一条箭线相连。不允许出现缺口与回路网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。 虚工序虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。不消耗时间、费用和资源，一般用虚箭线表示。方向的规定网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系从左向右排列。编号的规定编号应从始结点

52、开始，按照时序依次从小到大对结点编号，直到终结点。 编号时不允许箭头编号小于箭尾编号。 141第一节 网络图的绘制三、箭线式网络图举例 某工程的工程一览表 工序abcdefg紧前工序-aa,cbb,d,e工序时间63445108124536badcegf36445810142第二节 关键路线法一、结点的时间参数 结点的最早时间tE(j)tE(j)等于从始点开始到本结点的最长路线上各道工序时间之和。从始点事项开始，自左向右，顺着箭线方向逐个计算 。结点的最迟时间 tL(j)指以该结点为结束的各道工序最迟必须完工的时刻，否则将会影响后续工序按时开工，以至推迟整个工程的完工时间。从终点开始，从右向左

53、，逆箭线方向逐个计算。143第二节 关键路线法一、结点的时间参数 计算结点时间参数124536badcegf548364100366111996611190144第二节 关键路线法二、作业的时间参数 最早可能开工时间tES(i, j)一个作业必须在其各紧前作业都完工后才能开工，作业最早可能开工时间等于其箭尾事项的最早时间。 tES(i, j)= tE(i)最早可能完工时间 tEF(i, j)从最早可能开工时间开工，完成本作业的时间 。 tEF(i, j)= tES(i, j) +t(i, j)最迟必须开工时间 tLS(i, j)在不影响工程如期完工的前提下，作业最迟必须开工的时刻。等于它的箭头

54、事项的最迟时间减去本作业的作业时间 tLS(i, j)= tL( j) - t(i, j)最迟必须完工时间 tLF(i, j)在不影响工程如期完工的前提下，作业最迟必须完工的时刻 。 tLF(i, j)= tLS(i, j) +t(i, j) = tL( j) 145第二节 关键路线法三、时差与关键路线 时差又称宽裕时间：不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。总时差R(i, j)：不影响其紧后工序最迟必须开工的前提下，本工序最早可能完工时间可以推迟的时间。R(i, j)= tLS(i, j) -tES(i, j) = tLF(i, j) -tEF(i, j) = tL(

55、j) -tE(i) -t(i, j) 单时差r(i, j)：不影响其紧后工序最早可能开工的前提下，本工序最早可能完工时间可以推迟的时间。r(i, j)= tE( j) -tE(i) -t(i, j) 总时差为零的工序称为关键工序；关键工序组成关键路线。tEStEFtLStLFtEStEFtLStLFR(i,j)r(i,j)146第二节 关键路线法三、时差与关键路线 路线 路线的组成 路线长度13+10=13 23+0+8=11 36+4+8=1846+0+5+8=1954+5+8=17124536badcegf548364100366111996611190147第二节 关键路线法四、时间参数

56、算例 计算作业最早开始时间、最迟开始时间、最早结束时间、最迟结束时间以及时差，从表中寻找总时差与单时差都为零的作业，即为关键作业，将其连接起来就是关键路线。作业关键作业a6b3c4d4e5f10g800066311a-e-g06210606961111191906276911634101113190021000148第三节 计划评审技术一、作业时间估计 工序时间的三种可能估计：最乐观时间：在最理想的情况下完成工序所需时间a；最悲观时间：在最不利的情况下完成工序所需时间b；最可能时间：在正常情况下完成工序所需时间m。加权平均就是工序时间t 工程期望工期等于关键路线上各道工序的时间之和 。设规定的

57、工程完工时间为Tk，则完工时间的概率为二、计算期望工期 149第三节 计划评审技术三、PERT应用举例 某项目的作业流程及其时间估计 若合同规定工期为20，求如期完工的概率；若要求有90%的把握如期完工，求可接受的合同工期的为多少。 作业紧前作业作业时间估计作业时间乐观时间悲观时间可能时间期望方差a-35441/9b-24331/9ca,b13221/9da3114516/9ec,d2109816/9fa71310101ge,f2106616/9150第三节 计划评审技术三、PERT应用举例 1234a3b2c45d8e10f566g0449172323179740参数计算工程期望工期 TE=

58、23 ，关键工序的方差2 =49/9，则 (x)=-1.29，查表知 P(x)=9.9%P(x)=90% ，查表知 (x)=1.3，则可接受的合同工期为TE+ (x) =26151第四节 网络计划优化一、缩短工程工期改进工艺和技术装备，压缩关键工序的作业时间合理组织平行作业、交叉作业平行作业指两道以上相互独立的工序同时进行交叉作业指将紧前工序完成的部分任务分期分批地转入下道工序利用时差，合理调配资源等途径实现152第四节 网络计划优化二、工期-费用优化1、工期与成本之间关系工期的缩短与费用是密切相关的工程费用最低的完工时间(最低成本日程)时间费用极限完工时间正常完工时间直接费用间接费用最优完工

59、时间工程总费用153第四节 网络计划优化二、工期-费用优化寻求最低成本日程的思路：从网络计划的关键工序着手，对增加直接费用做少的某些关键工序采取措施，缩短其作业时间。时间直接费用极限完工时间正常完工时间154第四节 网络计划优化2、工期-费用优化案例某工程作业流程及其费用统计资料 作业紧前作业作业时间（天）作业直接费用（万元）费率正常完工极限完工正常完工极限完工A-3388-B-5316191.5C-5420233DB6320231EB5258.61.2FE331010-GD439112HA5220282合计88间接费用2万元/天155第四节 网络计划优化方案I：各道作业正常完工工程费用=正常

60、完工直接费用+间接费用=88+215=118万元。 23a5b6d45h4g5e563f0351110150531011121515c156第四节 网络计划优化方案2：关键路线d上赶进度 工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用 =88+21+213=116万元。23a5b4d45h4g5e563f0359101305389101315c157第四节 网络计划优化方案3：关键路线b上赶进度 工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用 =88+21+21.5+211=115万元。23a3b4d45h4g5e563f03378110336781115c158第四节