管理运筹学-ERP.ppt

管理运筹学-,研究领域：管理科学、运营管理、供应链管理讲授课程：管理运筹学-管理科学方法、管理系统工程、运营管理、供应链管理、ERP、国际物流、企业物流管理、管理决策模型与方法单位：E-mail：jiaping,教材与参考书籍,教材：谢家平编著.管理运筹学：管理科学方法，中国人民大学出版社，2010参考书：Davidetal.数据、模型与决策，机械工业出版社，2004费雷德里克.数据、模型与决策，中国财政经济出版社，2004Jamesetal.数据、模型与决策，中国人民大学出版社，2006,32课时讲授提纲,绪论第一章线性规划第二章线性规划讨论第三章对偶规划静态规划第四章整数规划第五章目标规划第六章动态规划动态优化第七章网络分析第八章网络计划第九章决策分析第十章方案排序第十一章库存控制第十二章排队理论,离散优化,随机优化,淡化数学算法LINDO求解,考核方式,结课考试：笔试（开卷or闭卷？）每章一题80%案例研究：选择合适方法结合企业实际进行应用20%,管理运筹学的称谓,管理运筹学是一门研究如何最优安排的学科。OperationsResearch日本译作“运用学”香港、台湾译为“作业研究”我国译作“运筹学”源于古语“运筹帷幄之中，决胜千里之外”取“运筹”二字，体现运心筹谋、策略取胜ManagementScience管理科学运用数学、统计学和运筹学中的量化分析原理和方法，建立数学模型/计算机仿真，给管理决策提供科学依据。,绪论,一、发展历史二、学科作用三、学科性质四、工作程序五、学科体系六、学习要求,一、发展历史,1.早期的运筹思想齐王赛马渭修皇宫沈括运军粮科学管理2.军事运筹学阶段20世纪40年代诞生于英美1940年，英国为对付德国空军的空袭，使用了雷达，但没有科学布局，效果不好。为解决这个问题，成立运筹学小组，称OperationalResearch，意为作战研究。美国和加拿大也在军队设立运筹学小组，称OperationsResearch，协助指挥官研究战略及战术问题。3.管理运筹学阶段战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹学在企业管理方面的应用得到了长足进展。,企业的成功要素中：观念意识更新47人文文化35技术优势18决策意识的科学性成功决策正确决策,二、学科作用,理念的重要性,？,二、学科作用,1.量化管理的重要性管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策的一门学科。目的：用科学方法分析管理问题，为管理者决策提供依据目标：在企业经营内外环境的限制下，实现资源效用最大,量化管理是第一步,它导致控制,并最终实现改进如果不能量化某些事情，那么就不能理解它如果不能理解它，那么就不能控制它如果不能控制它，那么就不能改进它H.JamesHarrington,定性到定量分析，数量界限的重要性：量变引起质变,听一场音乐会：网络订票的票价500元，不去可退票情况1：在你马上要出发的时候，发现你把最近的价值500元的电话卡弄丢了。你是否还会去听这场音乐会？情况2：假设昨天花500元钱买一张今晚的音乐会取票单。在你出发时，发现把票单丢了。如果去听音乐会，就必须再花500元钱买张票，去还会不去？,二、学科作用,2.量化思考使人理性冰淇淋实验：一杯A有70克，装在50克的杯子里，看上去要溢出了一杯B是80克，装在100克的杯子里，看上去还没装满,单独凭经验判断时，在相同的价格上，人们普遍选择A,实验表明，大部分的回答者仍旧会去听,结果却是，大部分人回答说不去了,二、学科作用,3.量化分析辅助决策盈亏平衡分析,利润：I=(PCmCh)Q-F策略1差异化，领先者战略策略2规模化，大规模市场策略3机械化，第一利润源策略4技能化，第二利润源策略5信息化，第三利润源,二、学科作用,量化辅助决策案例：盈亏平衡分析例：某企业总销售额1100万元物料成本700万元员工工资200万元管理费用100万元现在利润=100万元，目标利润150万元,利润实现的方法有：将销售收入增加100%将员工工资减少25%将管理费用减少50%将物料成本减少7.1%,二、学科作用,4.决策意识的重要性生产计划决策,一星期工作5天,每天正常工作8小时一周作业费用：11000(直接人工成本与间接费用)直接人工成本：10/1h(一台机器需一位作业人员)间接费用：人工成本2.5倍,二、学科作用,甲产品产量40,乙产品80,丙产品40利润=4066+8089+4070=12560人员有限如何实现?采取什么薪酬制度?计件工资制，让员工自愿加班,决策的科学性？方案一,二、学科作用,甲产品产量40,乙产品80,丙产品40总收入=40173+80233+40170=32360原料成本=4065+8095+4065=12800营运费用=11000总利润=32360-12800-11000=8560人员有限如何实现?采取什么薪酬制度?岗位工资制（定岗定员），让员工自觉加班,决策的科学性？方案二,二、学科作用,决策的科学性？产能符合计算,乙与丙哪一个产品比较赚钱?,E是瓶颈,二、学科作用,方案三：计时工资，且以单位利润率高低为决策意识。乙比较赚钱,假如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=5800,三、学科性质,1.研究对象经济和管理活动中能用“数量关系”描述的如运营、规划与组织管理问题解决的理论模型和优化方法实践2.学科特点强调科学性和定量分析强调应用性和实践性强调从整体上进行把握,四、工作程序,五、学科体系,1.管理问题,五、学科体系,2.学科内容,五、学科体系,3.学科应用管理既是科学又是艺术低层管理的科学成分较多，高层管理的艺术成分较多运营管理需较多管理科学，人力资源管理需较多管理艺术例行管理需要较多管理科学，例外管理需要较多管理艺术,M:管理决策问题,MC:定量解决方法,方案选择依据,问题导向,技术支持,战略决策营销决策生产安排财务分析人力资源方案优选,应用统计线性规划整数规划目标规划网络计划网络分析决策分析动态规划,管理科学：运用合理的分析来改善决策的制定,管理者:制定决策,六、学习要求,1.学科地位,六、学习要求,经济学,企业战略、公司治理,会计学财务管理,人力资源管理组织行为学,管理科学方法支持,六、学习要求,2.如何学习,重点在结合实际的应用发挥自己管理实践经验丰富和理论联系实际的能力强化结合实际问题建立管理优化模型的能力强化解决问题的方案或模型的解的分析与应用能力充分借用管理运筹学教学软件,第1章线性规划,Subtitle,内容提要,第一节线性规划的一般模型一、线性规划的三个要素二、线性规划模型的特征三、线性规划的图解方法四、线性规划解的可能性第二节线性规划的单纯形法一、线性规划的标准型式二、线性规划之解的概念三、单纯形法的基本原理,一、线性规划的三个要素,第一节线性规划的一般模型,决策变量决策问题待定的量值取值要求非负约束条件任何管理决策问题都是限定在一定的条件下求解把各种限制条件表示为一组等式或不等式称约束条件约束条件是决策方案可行的保障约束条件是决策变量的线性函数目标函数衡量决策优劣的准则，如时间最省、利润最大、成本最低目标函数是决策变量的线性函数有的目标要实现极大，有的则要求极小,二、线性规划模型的举例,第一节线性规划的一般模型,1、生产计划问题,例.某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。据市场分析，单位甲乙产品的销售价格分别为73和75元，试确定获利最大的产品生产计划。,第一节线性规划的一般模型,(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。(2)约束条件：生产受设备能力制约，能力需求不能突破有效供给量。设备A的约束条件表达为2x116同理，设备B的加工能力约束条件表达为2x210设备C的装配能力也有限，其约束条件为3x1+4x232(3)目标函数：目标是企业利润最大化maxZ=3x1+5x2(4)非负约束：甲乙产品的产量为非负x10，x20,综上的LP模型：,二、线性规划模型的举例,第一节线性规划的一般模型,2、物资运输问题,例：某产品商有三个供货源A1、A2、A3，其经销商有4个（需求市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及从Ai到Bj的单位运费为Cij。为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。,第一节线性规划的一般模型,(1)决策变量：设从Ai到Bj的运输量为xij，(2)目标函数：运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+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),二、线性规划模型的举例,第一节线性规划的一般模型,3、产品配比问题,例：用浓度45%和92%的硫酸配置100吨浓度80%的硫酸。,决策变量：取45%和92%的硫酸分别为x1和x2吨约束条件：,求解二元一次方程组得解,非负约束：x10，x20,第一节线性规划的一般模型,若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢？,取这5种硫酸分别为x1、x2、x3、x4、x5，有,有多少种配比方案？何为最好？,若5种硫酸价格分别为400,700,1400,1900,2500元/t，则：,三、线性规划模型的特征,第一节线性规划的一般模型,1、模型隐含假定,（1）线性化假定函数关系式f(x)=c1x1+c2x2+cnxn，称线性函数。建模技巧：将非线性的函数进行分段线性化。（2）同比例假定决策变量变化引起目标函数和约束方程的改变量比例。（3）可加性假定决策变量对目标函数和约束方程的影响是独立于其他变量的。目标函数值是决策变量对目标函数贡献的总和。（4）连续性假定决策变量取值连续。（5）确定性假定所有参数都是确定的，不包含随机因素。,三、线性规划模型的特征,第一节线性规划的一般模型,2、一般数学模型,用一组非负决策变量表示的一个决策问题；存在一组等式或不等式的线性约束条件；有一个希望达到的目标，可表示成决策变量的极值线性函数。,四、线性规划的图解方法,第一节线性规划的一般模型,1、线性规划的可行域,可行域：满足所有约束条件的解的集合，即所有约束条件共同围城的区域。,maxZ=3x1+5x22x1162x2103x1+4x232x10,x20,S.t.,四、线性规划的图解方法,第一节线性规划的一般模型,2、线性规划的最优解,目标函数Z=3x1+5x2代表以Z为参数的一族平行线。,四、线性规划的图解方法,第一节线性规划的一般模型,3、线性规划解的特性,由线性不等式组成的可行域是凸多边形(凸多边形是凸集)凸集定义：集合内部任意两点连线上的点都属于这个集合,可行域有有限个顶点。目标函数最优值一定在可行域的边界达到，而不可能在其区域的内部。,五、线性规划解的可能性,第一节线性规划的一般模型,1、唯一最优解：只有一个最优点,2、多重最优解：无穷多个最优解,当市场价格下降到74元，其数学模型变为,五、线性规划解的可能性,第一节线性规划的一般模型,3、无界解：可行域无界，目标值无限增大(缺乏必要约束),五、线性规划解的可能性,第一节线性规划的一般模型,4、没有可行解：线性规划问题的可行域是空集(约束条件相互矛盾),一、线性规划的标准型式,第二节线性规划的一般模型,1、标准型表达方式,(1)代数式,(2)向量式,(3)矩阵式,A：技术系数矩阵，简称系数矩阵；B：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策向量。,一、线性规划的标准型式,第二节线性规划的一般模型,2、标准型转换方法,(1)如果极小化原问题minZ=CX，则令Z=-Z，转为求maxZ=-CX(2)若某个biPk+1。同一优先等级下目标的相对重要性赋以不同权数w。,第二节目标规划的数学模型,例如P1级目标实现利润至少30元；P2级目标是甲乙产品的产量假设：乙产品产量不少于4件比甲产品产量不少于6件更重要，取其权重为2minG=P1d1-+P2(2d2-+d3+)3x1+5x2+d1-d1+=30 x2+d2-d2+=4x1+d3-d3+=6x1,x2,dk-,dk+0(k=1,2,3),第三节目标规划的图解法,目标规划的图解法首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。,F,G,H,x1=5,x2=4,第四节目标规划的应用案例,一、无穷多满意解,解：设x1,x2表示A、B产品的产量。两个等级的目标：P1：充分利用电量限额，正负偏差之和为最小目标达成函数目标约束条件P2：利润额希望不能低于100元，负偏差最小目标达成函数目标约束条件,计划生产两种产品，首先要充分利用设备工时而不加班；然后考虑利润不低于100元。问应如何制定产品A、B的产量。,第四节目标规划的应用案例,一、无穷多满意解,由于材料供应限量为8单位，所以有系统约束条件，如下,该问题的目标规划模型如下，图解法求解如图,C,G,第四节目标规划的应用案例,二、加班时间问题,例：某音像店有5名全职售货员和4名兼职售货员，全职售货员每月工作160小时，兼职售货员每月工作80小时。根据记录，全职每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元。兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元。现在预测下月CD销售量为27500张，商店每周开门营业6天，所以可能要加班。每出售一张CD盈利1.5元。商店经理认为，保持稳定的就业水平加上必要的加班，比不加班就业水平要好，但全职销售员如果加班过多，就会因为疲劳过度而造成效率下降，因此不允许每月加班超过100小时，建立相应的目标规划模型。,第四节目标规划的应用案例,二、加班时间问题,首先，确定目标约束的优先级。如下：P1：下月的CD销售量达到27500张；P2：全职售货员加班时间不超过100小时；P3：保持全体售货员充分就业，对全职的要比兼职的加倍优先考虑；P4：尽量减少加班时间，对两种售货员区别对待，权重由他们对利润的贡献而定。其次，建立目标约束函数（1）销售目标约束，设全体全职售货员下月的工作时间x1，全体兼职售货员下月的工作时间x2；达不到销售目标的偏差d1-，超过销售目标的偏差d1+。,第四节目标规划的应用案例,二、加班时间问题,（2）正常工作时间约束。设全体全职售货员下月的停工时间d2-，加班时间d2+；全体兼职售货员下月的停工时间d3-，加班时间d3+。（3）加班时间的限制。设全体全职售货员下月的加班不足100小时的偏差d4-，加班超过100小时的偏差d4+。两类售货员区别对待，权重比d2+:d3+=1:3，另一加班目标约束为,第四节目标规划的应用案例,二、加班时间问题,第三，按目标的优先级，写出相应的目标规划模型：,运用LINGO软件求解得x1=900,x2=500，下月共销售CD盘27500张，获利275001.5-80015-10022.5-50010=22000。,第四节目标规划的应用案例,三、目标管理方案,例：某公司准备生产甲、乙产品，据市场调查：甲产品的最大市场需求3台，乙产品的最大市场需求2台。,在满足现有电力资源严格供给约束的前提下，该厂长考虑两个目标：一是总利润不低于3600元；二是充分利用设备台时，但尽量少加班。问应如何制定产品甲、乙的产量，试建立其目标规划的数学模型。,第四节目标规划的应用案例,三、目标管理方案,1.利润期望优先目标规划数学模型：,运用图解法进行求解,F,E,G,x1=8,x2=3,第四节目标规划的应用案例,1.利润期望优先,满意解：x1=8,x2=3设备能力：需求：308+603=420，实际：360实现目标P1和P2，降低甲乙产品的设备消耗:降低率(420-360)/360=17%，甲产品的设备消耗降为30(1-17%)=25,乙产品的设备消耗降为60(1-17%)=50。,第四节目标规划的应用案例,三、目标管理方案,2.设备工时优先目标规划数学模型：,运用图解法进行求解,F,E,G,x1=8,x2=2,第四节目标规划的应用案例,2.设备工时优先,满意解：x1=8,x2=2利润总额3008+4002=3200，目标：3600不能提价，就必须降低成本以增加利润，利润增长率为12.5%甲产品的成本需要降为1200-300(1+12.5%)=862.5元/台，降低幅度4.2%乙产品的成本需要降为1800-400(1+12.5%)=1350元/台，降低幅度3.6%,第7章网络分析,Subtitle,内容提要,第一节图论的概念第二节最小树问题第三节最短路问题第四节网络最大流第五节最小费用流,18世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？,第7章网络分析,陆地A,陆地B,岛D,岛C,A,D,B,C,1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。,第一节图论的概念,一、图的内涵,1、图的定义,v1,v4,v2,v3,e1,e2,e3,e4,e5,e6,v1,v4,v2,v3,e1,e2,e3,e4,e5,e6,v1,v2,v3,v4,e1,e2,e3,e4,e5,e6,图论的图与一般几何图形或代数函数图形是完全不同的图论中的图:由一些点和连接点的线所组成的“图形”点和线的位置是任意的线的曲直、长短与实际无关，代表的只是点与点之间的相互关系例：表示苏州v1、杭州v2、上海v3、南京v4仓储网点之间的物流运输线路关系,第一节图论的概念,一、图的内涵,2、图的分类,不带箭头的连线称为“边”，如公路运输线路；带箭头的连线称为“弧”，如供排水的管道运输线路。,1、无向图,由点和边的集合所构成,由点和弧的集合所构成,2、有向图,链：无向网络中，前后相继点和边的交替序列称为一条链。圈：闭合的链称为一个圈。,路径：有向网络图中，前后相继并且方向一致的点弧序列称为一条路径。回路：闭合的路径称为一个回路。,第二节最小树问题,例：一家企业分别要在6间办公室铺设网线接入口，网线的可行走线方式如下图所示，如何铺设网线才能使网线总长为最短？,最短网线总长度为最小树权之和2+3+4+6+6=21,8,2,3,5,4,6,6,6,8,v1,v4,v2,v3,v5,v6,无圈的连通图就是一棵树。权数总和为最小的那棵支撑树，称为最小树。求解方法：破圈法避圈法,第三节最短路问题,一、双标号算法,狄克斯特拉(Dijkstra)算法路权：弧(vi,vj)的权为wij；路权是路p中各条弧权之和最短路：在所有从vs到vt的路p中，求一条路权最短的路算法说明：1959年提出，目前公认的最短路算法适合于求解所有弧权wij0的最短路问题算法假设：有向图D是完备图图D中任意两点vi,vj之间，恰有两条弧(vi,vj)和(vj,vi)若vivj不存在弧,可设想一条从vivj的弧,权wij=+；若vivj有重复的弧，则保留弧权最小的弧,第三节最短路问题,一、双标号算法,基本思路:从始点vs出发，逐步探寻，给每个点标号；标号分永久标号P(vk)和临时标号T(vk)两种：永久标号P(vk)是从点vsvk的最短路权临时标号T(vk)是从点vsvk最短路权的上界算法的每一步从临时标号集中选最小者变为永久标号；经过逐次改变，就可以得到从点vs到各点的最短路。标号形式：单标号法是对每一点赋予一个路权标号双标号法是对每一点赋予两个标号：路标、路权,第三节最短路问题,一、双标号算法,例：用双标号法求下图网络最短路,3,9,4,7,3,2,6,1,4,1,2,8,7,1,10,第三节最短路问题,一、双标号算法,第一步：,3,9,4,7,3,2,6,1,4,1,2,8,7,1,10,第三节最短路问题,一、双标号算法,第二步：,3,9,4,7,3,2,6,1,4,1,2,8,7,1,10,第三节最短路问题,一、双标号算法,第三步：,3,9,4,7,3,2,6,1,4,1,2,8,7,1,10,第三节最短路问题,一、双标号算法,最终：依此类推，重复上述标号过程。得最短路。,3,9,4,7,3,2,6,1,4,1,2,8,7,1,10,第三节最短路问题,二、最短路的应用,1、网络的中心,所谓网络的中心是指一个网络中，选择某一点，使之其余各点到该中心点的距离之和为最小。,例：如果要在下表中6个销售点中选一个作为仓库所在地，应该建在哪个经销点，使其余各销售点都离它较近？,第三节最短路问题,二、最短路的应用,2、网络的重心,引进点的权系数，将权系数与最短距离阵各列对应元素加权求和，再从中选择最小的即为网络重心。,第四节网络最大流,一、相关概念与定理,1、弧容量与容量网络,对于有向图D=(V,A),，弧的容量表示弧的最大流通能力。在V中指定一点称为发点(记为vs)，另一点称收点(记为vt)，其余点叫中间点，这样的赋权有向图就称为一个容量网络，记N=(V,A,B),2、弧的流量与可行流,弧的实际通过量称为该弧的流量。弧集A上的流量集合称为网络上的流。满足下述条件的流称为可行流。容量限制：对每条弧，都有平衡条件：中间点流出量=流入量,第四节网络最大流,一、相关概念与定理,3、前向弧与后向弧,4、饱和弧与非饱和弧,弧的流量与之容量比较：满足的弧称为饱和弧，弧的流量不能再扩充；满足的弧称为非饱和弧，弧的流量允许再被扩大。,是从vs到vt的链，方向从vsvt，则链上的弧分为两类前向弧：弧的方向与链的方向相同，记+后向弧：弧的方向与链的方向相反，记-,5、零弧与非零弧,满足的弧称为零弧。由于，所以弧的流量不能减小；满足的弧称为非零弧。弧的流量可以被减小，但要满足0。,第四节网络最大流,一、相关概念与定理,6、流量可以扩充的路,设是一可行流，是从vs到vt的链，若链满足：上的所有前向弧为非饱和弧，即满足，可以扩充流量上的所有后向弧为非零弧，即满足，可以减少流量；则称是一条关于可行流的可扩充流量的路，亦称增广链。,7、流量可以扩充的路,可行流中，网络发点的流出量（或网络收点的流入量）就是网络的流量。一个容量网络的诸可行流中，网络流量最大的可行流，称为最大流,第四节网络最大流,二、求最大流标号法,1956年，福特和富尔克逊提出了寻求网络最大流的基本方法，称为福特-富尔克逊算法（Fold-FulkersonAlgorithm）。,给定可行流X=xij，标号判断有无增广链先给vs标上(vs,+)，vs已标号尚未检查，其余未标号取一个已标号但未检查的点vi进行检查，对未标号点vj：前向弧(vi,vj)可以扩充流量(xijrij)vj尚未标号，则给vj标号(vi，+)，vj成为己标号尚未检查的点后向弧(vk,vi)可以减少流量(xki0)vk尚未标号，则给vk标号(vi,-)，vk成为己标号尚未检查的点vi成为已标号已检查的点，在其标号下划横线检查收点vt是否已标号：vt被标上号则找到增广链，进行流量调整；否则转第步若所有标号都已检查，vt又未标号，则不存在增广链,标号过程,第四节网络最大流,二、求最大流标号法,流量调整过程反向追踪找出vs到vt的增广链计算增广链上可调整的流量,调整可行流的流量，得新的可行流xij,抹去所有标号，对新的可行流X=xij，重新进入标号过程,第四节网络最大流,二、求最大流标号法,例：下图表示了企业所处的供应市场（v1和v2）、配送中心（v3和v4、以及销售市场（v5、v6和v7）组成的网络，各弧上括号里的前一个数字表示弧的容量，后一个数字是目前的实际流量。试求这个供应-销售网络的最大流方案。,第四节网络最大流,二、求最大流标号法,供应-销售网络的可行流,(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,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),第四节网络最大流,二、求最大流标号法,调整后的可行流,最大流量为,(4,1),(10,8),(15,11),(4,4),(5,5),(6,5),(6,6),(15,8),(12,12),(5,4),(10,10),(8,6),第四节网络最大流,三、网络的瓶颈识别,1、截集-截量与最小截集,2、最大流-最小截量定理,网络中，任一可行流的流量恒不超过任一截集的截量，称为流量-截量定理。最小截量的大小影响总流量的提高,截集：对于网络N=(V,A,R)，将V分为两个非空集合S和S，使发点vsS，收点vtS所有起点属于S而终点属于S的弧的集合称为截集(S,S)截量：截集(S,S)中所有弧的容量之和r(S,S)最小截集：截量最小的截集,第五节最小费用流,一、调整法求解步骤,先不考虑费用问题，求得任一可行流X据此构造赋权有向图W(X)顶点是原网络N的顶点弧权根据可行流X确定弧(vi,vj)的流量可以增加，则照原方向画弧，标上费用bij弧(vi,vj)的流量可以减少，则照反方向画弧，标上费用-bij在赋权有向图W(X)中寻找负回路(总权为负值的回路)：若没有负回路，则得到最小费用流若存在负回路，则调整与负回路相对应的弧上的流量计算调整量，进行流量调整若弧(vi,vj)与负回路方向一致，则其流量调整为xij+若弧(vi,vj)与负回路方向相反，则其流量调整为xij-赋权有向图寻找负回路调整流量直到没有负回路,第五节最小费用流,二、调整法应用举例,例：下图表示了企业所处的供应市场（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),第五节最小费用流,二、调整法应用举例,1、赋权有向图,2、寻找负回路,在赋权有向图中，寻找总权数为负的回路选取负权绝对值大的那条负回路进行流量分布调整,-10,30,5,-35,6,4,-3,-1,1,8,-10,-30,-1,-1,1,-8,-4,-5,-6,第五节最小费用流,二、调整法应用举例,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),第8章网络计划,Subtitle,内容提要,第一节网络图的绘制第二节关键路线法结点的时间参数作业的时间参数时差与关键路线第三节计划评审技术第四节网络计划优化缩短工程工期工期-费用优化工期-资源优化第五节缓冲时间设置,第8章网络计划,网络计划的发展历程,关键路线法(CriticalPathMethod，CPM)计划评审技术(ProgramEvaluationandReviewTechnique，PERT)图示评审技术(GraphicEvaluationandReviewTechnique，GERT)风险评审技术(VentureEvaluationReviewTechnique，VERT),网络计划技术的特性,网络计划技术只不过是反映和表达项目计划安排的一种方法，是被项目施工技术所决定的，它只能适应项目施工方法的要求。是把工程进度安排通过网络的形式直观地反映出来。,第一节网络图的绘制,一、网络计划的图示形式,工序(作业)：一项需要人财物或时间等资源的相对独立的活动过程在网络图中用箭线“”表示，前面直接相连工序称紧前工序，直接相连的后继工序为紧后工序。结点(事项)：相邻工序的分界点一般用圆圈来表示，每个结点编上顺序号，结点既不消耗人力、物力，也不占用时间。网络图由工序、事项及时间参数所构成的有向图即为网络图。箭线表示工序,结点为工序间相互关系的网络图，称箭线式网络结点表示工序,箭线为工序间相互关系的网络图，称结点式网络,第一节网络图的绘制,一、网络计划的图示形式,1、箭线式网络图,2、结点式网络图,第一节网络图的绘制,二、箭线式网络图的规则,工序表示的规定一条箭线和它的相关事项只能代表一道工序，不能代表多道工序，两个结点之间只能有一条箭线相连。不允许出现缺口与回路网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。虚工序虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。不消耗时间、费用和资源，一般用虚箭线表示。方向的规定网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系从左向右排列。编号的规定编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。编号时不允许箭头编号小于箭尾编号。,第一节网络图的绘制,三、箭线式网络图举例,某工程的工程一览表,1,2,4,5,3,6,b,a,d,c,e,g,f,3,6,4,4,5,8,10,第二节关键路线法,一、结点的时间参数,结点的最早时间tE(j)tE(j)等于从始点开始到本结点的最长路线上各道工序时间之和。从始点事项开始，自左向右，顺着箭线方向逐个计算。,结点的最迟时间tL(j)指以该结点为结束的各道工序最迟必须完工的时刻，否则将会影响后续工序按时开工，以至推迟整个工程的完工时间。从终点开始，从右向左，逆箭线方向逐个计算。,第二节关键路线法,一、结点的时间参数,计算结点时间参数,1,2,4,5,3,6,b,a,d,c,e,g,f,5,4,8,3,6,4,10,第二节关键路线法,二、作业的时间参数,最早可能开工时间tES(i,j)一个作业必须在其各紧前作业都完工后才能开工，作业最早可能开工时间等于其箭尾事项的最早时间。tES(i,j)=tE(i)最早可能完工时间tEF(i,j)从最早可能开工时间开工，完成本作业的时间。tEF(i,j)=tES(i,j)+t(i,j)最迟必须开工时间tLS(i,j)在不影响工程如期完工的前提下，作业最迟必须开工的时刻。等于它的箭头事项的最迟时间减去本作业的作业时间tLS(i,j)=tL(j)-t(i,j)最迟必须完工时间tLF(i,j)在不影响工程如期完工的前提下，作业最迟必须完工的时刻。tLF(i,j)=tLS(i,j)+t(i,j)=tL(j),第二节关键路线法,三、时差与关键路线,时差又称宽裕时间：不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。总时差R(i,j)：不影响其紧后工序最迟必须开工的前提下，本工序最早可能完工时间可以推迟的时间。R(i,j)=tLS(i,j)-tES(i,j)=tLF(i,j)-tEF(i,j)=tL(j)-tE(i)-t(i,j)单时差r(i,j)：不影响其紧后工序最早可能开工的前提下，本工序最早可能完工时间可以推迟的时间。r(i,j)=tE(j)-tE(i)-t(i,j)总时差为零的工序称为关键工序；关键工序组成关键路线。,R(i,j),r(i,j),第二节关键路线法,三、时差与关键路线,1,2,4,5,3,6,b,a,d,c,e,g,f,5,4,8,3,6,4,10,第二节关键路线法,四、时间参数算例,计算作业最早开始时间、最迟开始时间、最早结束时间、最迟结束时间以及时差，从表中寻找总时差与单时差都为零的作业，即为关键作业，将其连接起来就是关键路线。,第三节计划评审技术,一、作业时间估计,工序时间的三种可能估计：最乐观时间：在最理想的情况下完成工序所需时间a；最悲观时间：在最不利的情况下完成工序所需时间b；最可能时间：在正常情况下完成工序所需时间m。加权平均就是工序时间t,工程期望工期等于关键路线上各道工序的时间之和。,设规定的工程完工时间为Tk，则完工时间的概率为,二、计算期望工期,第三节计划评审技术,三、PERT应用举例,某项目的作业流程及其时间估计,若合同规定工期为20，求如期完工的概率；若要求有90%的把握如期完工，求可接受的合同工期的为多少。,第三节计划评审技术,三、PERT应用举例,1,2,3,4,5,6,0,4,4,9,17,23,23,17,9,7,4,0,参数计算工程期望工期TE=23，关键工序的方差2=49/9，则(x)=-1.29，查表知P(x)=9.9%P(x)=90%，查表知(x)=1.3，则可接受的合同工期为TE+(x)=26,第四节网络计划优化,一、缩短工程工期,改进工艺和技术装备，压缩关键工序的作业时间合理组织平行作业、交叉作业平行作业指两道以上相互独立的工序同时进行交叉作业指将紧前工序完成的部分任务分期分批地转入下道工序利用时差，合理调配资源等途径实现,第四节网络计划优化,二、工期-费用优化,1、工期与成本之间关系,工期的缩短与费用是密切相关的工程费用最低的完工时间(最低成本日程),极限完工时间,正常完工时间,直接费用,间接费用,最优完工时间,工程总费用,第四节网络计划优化,二、工期-费用优化,寻求最低成本日程的思路：从网络计划的关键工序着手，对增加直接费用做少的某些关键工序采取措施，缩短其作业时间。,极限完工时间,正常完工时间,第四节网络计划优化,2、工期-费用优化案例,某工程作业流程及其费用统计资料,第四节网络计划优化,方案I：各道作业正常完工,工程费用=正常完工直接费用+间接费用=88+215=118万元。,2,3,a,5,b,6,d,4,5,h,4,g,5,e,5,6,3,f,0,3,5,11,10,15,3,1,5,c,第四节网络计划优化,方案2：关键路线d上赶进度,工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用=88+21+213=116万元。,2,3,a,5,b,4,d,4,5,h,4,g,5,e,5,6,3,f,0,3,5,9,10,13,3,1,5,c,第四节网络计划优化,方案3：关键路线b上赶进度,工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用=88+21+21.5+211=115万元。,2,3,a,3,b,4,d,4,5,h,4,g,5,e,5,6,3,f,0,3,3,7,8,11,3,1,5,c,第四节网络计划优化,方案4：关键路线b、e上赶进度,工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用=88+21+21.5+1(1+1.2)+211=115.2万元。,2,3,a,3,b,3,d,4,5,h,4,g,4,e,5,6,3,f,0,3,3,6,7,10,3,1,5,c,第四节网络计划优化,三、工期-资源优化,资源平衡准则：,在压缩工程时间及费用的同时，要分别考量每道作业所需资源的用量与供应能力及时间限制，以便确定每道作业可压缩时间的限度及其进度安排。优先保证关键路线上关键作业对资源的需求量。对非关键作业要资源，利用时差调整非关键作业的开工时间和完工时间，以达到与关键作业在占用资源的时间上错开，拉平资源需要量的高峰。当资源绝对受限制时，在保证不推迟或尽量少推迟工程完工时间的前提下，全面统筹安排，最大限度地利用资源。,第四节网络计划优化,1,2,3,4,5,0,3,5,9,10,10,9,5,3,0,所需工作日：313+15+28+32+46+112+55=12710天完成，则平均每天所需机器12.7台，现有机器13台，适当安排可以完工,每天只有13台设备可用，计划10天完成，试合理安排生产进度,第四节网络计划优化,三、工期-资源优化,3、制定初始方案,以最早开工时间，安排初始进度如表,131313,5,88,222,6666,12,55555,第四节网络计划优化,三、工期-资源优化,4、调整开工时间第一次调整,非关键作业b延至第4天开工，非关键作业d和g延至第5天开工。,131313,5,88,222,6666,12,55555,第四节网络计划优化,三、工期-资源优化,4、调整开工时间第二次调整,将非关键作业d延至第6天开工,131313,5,88,222,6666,12,55555,第五节缓冲时间设置,具体的思路是：削减每道作业的预估时间，不为单道作业设置安全缓冲时间，而将节省的时间建立一个任务缓冲（某项任务的总体安全时间）,第五节缓冲时间设置,任务1,任务2,任务3,任务4,1234,项目缓冲,将每项任务的预估时间减去一半，然后将减去时间的和的一半作为项目缓冲，共用，所需时间为原来的3/4,463518,231.52.54.513.5,第五节缓冲时间设置,考虑资源冲突，使制约因素（瓶颈资源）不受非制约因素的影响，在每条衔接路径与关键路线汇合的地方插入衔接时间缓冲，例如零件的供货缓冲时间,项目缓冲,衔接缓冲,衔接缓冲,A1A2,B1B2,C1C2C3C4,第9章决策分析,Subtitle,内容提要,第一节决策分析概论第二节不确定性决策第三节风险型决策决策准则决策树法情报价值第四节贝叶斯决策第五节效用决策理论,悲观决策准则乐观决策准则乐观系数准则等可能性准则最小后悔准则,第一节决策分析概论,一、决策要素,对于任何决策应包括以下几个基本决策要素：,决策目标决策如果只有一个目标称为单目标决策，如果决策目标很多并形成目标体系，这类决策称为多目标决策。行动方案为了实现预订的目的，可以采取几种不同的行动自然状态决策环境可能出现的状态损益矩阵决策的结果或者是收益或者是损失决策准则比较、选择方案时的判决标准和评价规则后果评估通常采用损益或效用作为后果指标。,第一节决策分析概论,二、决策程序,确定决策目标,预测自然状态,拟定决策方案,决策方案优选,方案实施与控制,确定性决策：自然状态的信息是确知的风险性决策：已知状态概率分布，但确知不确定决策：未来状态信息全无,第一节决策分析概论,三、决策分类,1.按决策方法的性质分类,定性决策和定量决策,2.按决策问题的层次分类,不同管理层级决定不同层次的管理问题，分成战略性决策、战术性决策和运作层决策。,3.按决策出现的频率划分,程序性决策和非程序性决策,4.按自然状态的熟知度分,按对自然状态的认识程度可分为确定性决策、风险性决策和不确定性决策。,第二节不确定性决策,悲观准则决策者对客观情况持悲观态度，将结果估计得比较保守基本想法是坏中求好乐观准则决策者总是对客观情况抱乐观的态度基本思路是好中求好乐观系数准则决策者对客观情况既不那么乐