运筹学网络计划.pptx

运筹学教程用网络分析的方法编制的计划称为网络计划。它是五十年代末发展起来的一种编制大型工程进度计划的有效方法。1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及计划执行过程中的关键路线。运筹学教程这种方法称为关键路线法（缩写为CPM）。1958年美国海军武器部，在制定研制“北极星”导弹计划时，同样也应用了网络分析方法与网络计划。但它注重于对各项工作安排的评价和审查。这种计划称为计划评审方法（缩写为PERT）。鉴于这两种方法的差别，CPM主要应用于以往在类似工程中已取得一定经验的承包工程；PERT更多地应用于研究与开发项目。运筹学教程在这两种方法得到应用推广之后，又陆续地出现了类似的最低成本和估算计划法，产品分析控制法，人员分配法，物资分配和多种项目计划制定法等等。虽然方法很多，各自侧重的目标有所不同。但它们都应用的是CPM和PERT的基本原理和基本方法。运筹学教程六十年代我国开始应用CPM与PERT，并根据其基本原理与计划的表达形式，称它们为网络技术和网络方法，又按照网络计划的主要特点统筹安排，把这些方法称为统筹法。运筹学教程国内外应用网络计划的实路表明，它具有一系列优点，特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划。例如新产品研制开发，大型工程项目，生产技术准备，设备大修等计划。还可以应用在人力、物力、财务等资源的安排，合理组织报表、文件流程等方面。运筹学教程编制网络计划包括绘制网络图，计算时间参数，确定关键路线及网络优化等环节。下面分别讨论这些内容。运筹学教程网网络计划的性划的性质及特点及特点优点：点：能全面而明确地反映出各能全面而明确地反映出各项工作之工作之间的相互依的相互依赖、相互制相互制约的关系的关系 反映出整个工程和任反映出整个工程和任务的全貌，指出的全貌，指出对全局性有全局性有影响的关影响的关键线路和关路和关键工作工作 显示了机示了机动时间，以便更好地使用人力、，以便更好地使用人力、设备 可利用可利用计算机，算机，编制程序上机制程序上机 便于便于优化和化和调整整缺点：缺点：流水作流水作业的情况很的情况很难在在计划上反映出来划上反映出来运筹学教程 第一第一节 网网络图例例1：某一：某一设备维修网修网络图4225DCBA12453A：设备拆卸；B：电器部分修理；C：机械部分修理；D：设备安装调试。网络图的组成：节点箭线（包括虚线）工作代号消耗时间运筹学教程工作或工序（作工作或工序（作业、活、活动）定义：指一项有具体内容的、需要人力、物力、财力、占用一定空间和时间才能完成的活动过程。虚活动（作业）：只表示作业之间相互依存、相互制约、相互衔接的关系，但不需人力、物力、空间和时间的虚设的活动。示例：B B12121 14 46 63 35 52 2产品设计产品设计A A自制零部件自制零部件B B1 1外购零部件外购零部件B B2 2装配装配C C样品鉴定样品鉴定D D455035155运筹学教程事事项（事件、（事件、节点）点）定义：工程（计划）的始点、终点（完成点）或其各项作业的连接点（交接瞬间）。表示方法：ii（节点编号）：表示事项时间大致顺序 自左向右自上向下排列 一般以正整数表示 一个节点只有一个编号 各节点不允许重复使用 一个编号运筹学教程路路线 定定义：从网络图始点开始，顺着箭头方向前进，连续不断地到达终点的一条通道称为网络图的一条路线。各条路线所需的周期为对应的作业时间之和。关关键路路线和关和关键工序工序：概念概念：网络图中所需工时最长的路线称为关键路线。关键路线上的工序称为关键工序 表示方法表示方法：关键路线及工序常用双线表示 注意注意：（1）关键路线的完成时间决定整个工程的完工时间；（2）关键路线可能不只一条。关键路线越多，组织工作 越好，安排越紧凑；（3）关键路线与非关键路线可以转化。运筹学教程一一 网网络图必必须只有一个网只有一个网络始点和一个始点和一个终点。点。二二 网网络图是有方向的，不允是有方向的，不允许出出现回路。回路。三三 直接直接连接两个相接两个相邻结点之点之间的工作只能有一个。的工作只能有一个。四四 逻辑关系正确，箭关系正确，箭线两端必两端必须必必须有有节点。点。五五 正确运用虚工作。正确运用虚工作。一、一、网网络图的的绘制原制原则运筹学教程一一网网络图必必须只有一个网只有一个网络始点和始点和一个一个终点点 23543145321错错错错对对对对运筹学教程二二 网网络图是有方向的，不允是有方向的，不允许出出现回路回路 12345B BA AC CD DE E错错运筹学教程三三 直接直接连接两个相接两个相邻结点之点之间的工作只能有一个的工作只能有一个3543453 3D DC CB BA AD DC CB BA A错错错错对对对对运筹学教程四四箭箭线首尾必有首尾必有结点，不能从箭点，不能从箭线中中间引引 出另一条箭出另一条箭线 14131211131211配砂配砂造型造型造型造型配砂配砂2 2配砂配砂1 1对对对对错错错错运筹学教程五 虚作业的运用不消耗资源，表示逻辑关系。必要时加虚节点。运筹学教程虚工作应用12AB321AB工作紧前ABCD-AA,BDCBA42135456运筹学教程虚工作应用12AB321AB工作紧前ABCD-AA,BDCBA42135456DCBA2143运筹学教程虚工作应用（平行与交叉）13212A12435A3A2A1444BBA:A:修路基修路基B:B:铺轨道铺轨道A=A1+A2+A3B=B1+B2+B313578642A1B2B1A3A2B31212运筹学教程作业名称和内容作业代号后续作业代号作业长度（月）设计AB、C1基本建设BD8订购设备CD3安装设备DE6试车E结束1运筹学教程124563ABDEC18613作业名称和内容作业代号后续作业代号作业长度（月）设计AB、C1基本建设BD8订购设备CD3安装设备DE6试车E结束1运筹学教程ABCDABCDB和C没有前后关系，用虚工作表示A 和D的前后关系。ABACD另一例：关系如下，如何合在一起？运筹学教程ABCDACEABCDEABCDE另一例：如何处理？OK运筹学教程网网络图的的绘制步制步骤一一 定定义各各项作作业（工作）（工作）恰当地确定各项工作范围，以使网络图复杂程度适中二二 编制工作表（示例）制工作表（示例）（1）列出各项作业清单 （2）确定或估计各项作业时间 （3）表明各项作业之间的逻辑关系三三 画网画网络图（1）确定各项作业层次：无紧前作业的层次为1；其它各作业层次数=紧前作业层次中最大者+1（2）画草图 （3）画正图 （4）进行节点编号运筹学教程(1)任务分解二、实例工作工作内容紧前工作工时（周）ABCDEFGHIJKL市场调查资金筹备需求分析产品设计产品研制制定成本计划制定生产计划筹备设备筹备原材料安装设备调集人员准备开工投产AADC,EFB,GB,GHGI,J,K4103682328521运筹学教程(2)绘制网络图（尽量用水平和竖直线）12345678910AFECDGKIHJLB4103682328251ABCDEFGHIJKL紧前AADC,EFB,GB,GHGI,J,K运筹学教程(3)节点编号 箭尾编号小于箭头编号。进入节点的所有箭头的箭尾都必须编号，该节点才能编号运筹学教程三、网三、网络计划的分划的分类（一）按性（一）按性质分分类 1.确定型网确定型网络计划划 2.概率型网概率型网络计划划（二）按表示方法分（二）按表示方法分类 1.单代号代号 2.双代号双代号（三）按目（三）按目标分分类 1.单目目标网网络计划划 2.多目多目标网网络计划划运筹学教程（四）按有无（四）按有无时间坐坐标分分类 1.时标网网络计划划 2.非非时标网网络计划划（五）按（五）按层次分次分类 1.总网网络计划划 2.局部网局部网络计划划（六）按工作（六）按工作衔接特点分接特点分类 1.普通网普通网络计划划 2.搭接网搭接网络计划划 3.流水网流水网络计划划运筹学教程第二节 时间参数计算例9-3四条路线1-2-3-5-8：131-2-4-6-7-8：171-2-6-7-8：121-2-3-4-6-7-8：21关键线路决定工期，各项工作有轻重缓急之分。158236474523421342运筹学教程一、作业时间t(i,j)的确定 完成某一工序所需要的时间（1）确定型 资源确定，时间可确定计算（2）概率型（三点时间估计）乐观时间：在顺利情况下，完成工序所需要的最少时间，常用符号a表示；最可能时间：在正常情况下，完成工序所需要的时间，常用符号m表示；悲观时间：在不顺利情况下，完成工序所需要的最多时间，常用符合b表示。运筹学教程二、事项时间参数(1)事项最早时间(后面工作的最早可能开工时间)tE(i)：与事项j相邻的各紧前事项的最早时间。tE(n)=总最早完工期。从前向后计算，取大值运筹学教程（2）事项最迟时间(后面工作的最迟必须开工时间)tL(j)：与事项i相邻的各紧后事项的最迟时间。确定工期，从右向左计算取小值。运筹学教程三、工作的时间参数1.最早可能开工时间与最早可能完工时间。tES(i,j)（i事项最早时间），tEF(i,j)1.所有从总开工事项出发的工作所有从总开工事项出发的工作(1,j),其最早可能开工时间其最早可能开工时间=0；2.任一工作任一工作(i,j)其最早可能开工时间其最早可能开工时间,要与它的所有的紧前工要与它的所有的紧前工作（作（k,i）的最早开工时间决定；）的最早开工时间决定；3.工作工作(i,j)其最早完工时间等于其最早开工时间与工时之和。其最早完工时间等于其最早开工时间与工时之和。运筹学教程2.最迟必须开工时间与最迟必须完工时间。tLS(i,j)，tLF(i,j)(j事项最迟时间)1.总完工事项的工作总完工事项的工作(i,n),其最迟完工时间其最迟完工时间=预定总工期或者预定总工期或者等于这个工作的最早可能完工时间；等于这个工作的最早可能完工时间；2.任一工作任一工作(i,j)其最迟必须开工时间其最迟必须开工时间,要与它的所有的紧后工要与它的所有的紧后工作（作（j,k）的最迟开工时间决定；）的最迟开工时间决定；3.工作工作(i,j)其最迟完工时间等于其最迟开工时间与工时之和。其最迟完工时间等于其最迟开工时间与工时之和。运筹学教程四、时差：工作的机动时间或富裕时间（1）工作总时差 不影响总工期的最多机动时间。某工作可以延迟其开工时间的最大幅度。（2）工作单时差 不影响紧后工作的最早开工时间。运筹学教程工作及时差关系工作工作AES工作工作A的紧后工作的紧后工作ESEFLFLFEFLSLS总时差总时差单时差单时差(自由浮动自由浮动)运筹学教程例118972310654468322382510041018202323253132323126232320181040044101820232323232531010041513182029232324263110tEStLSRr001100000013611001100006130100运筹学教程五、时间参数的图上计算法六、表上计算法见下表 原则：工作的排列应严格按照箭尾事项编号由小到大的顺序排列，箭尾事项相同的工作，按其箭头事项有小到大排列。工作工作工时t(i,j)最早开工tES(i,j)最早完工tEF(i,j)最迟开工tLS(i,j)最迟完工tLF(i,j)总时差R(i,j)单时差r(i,j)关键工作箭尾i箭头j1234567891041063823022851040104104 71018 18 20 2023 23 23 23 25 23 25 23 3125 3031323231312631232624312923232320201818101815104231340013011000061010013011000060010*运筹学教程第三节 网络计划的优化应从工期、成本、资源消耗等方面综合评价。一、把串联工作改为平行工作或平行交叉工作。124444运筹学教程二、利用时差 尽量利用单时差，其次总时差。非关键路上的工作有时差，可以考虑放慢非关键工作的进度，减少其资源，转去支援关键工作。三、资源配置优化12354642234395763134时间人数运筹学教程 1 2 3 4 5 6 7 8 9 10 01114235642234395763134时标网络图0人数5102015181920951总时差 按照最早开工时间安排，人力需求不均匀 1 2 3 4 5 6 7 8 9 10 01114235642234395763134时标网络图0人数51020159192018511、尽量保证关键工作的日资源需求量。2、利用非关键工作的时差错开各工作的使用资源时间。3、在技术允许下，可适当延长时差大的工作的工时，或切断某些非关键工作，减少日总需求量。运筹学教程 1 2 3 4 5 6 7 8 9 10 01114235642234395763134时标网络图0人数51020159102018141运筹学教程 1 2 3 4 5 6 7 8 9 10 01114235642234395763134时标网络图0人数51020159107910运筹学教程四、工期费用优化直接费用：指人工、材料、能源等与各项活动直接有关的费用；活动作业时间越短，直接费用就越大。间接费用：指管理费用，销售费用等费用；它与各项活动时间无直接关系，而与工程周期长短直接相关。运筹学教程工程费用与工期关系图 0直接费用间接费用总费用费用时间1.直接直接费用的用的计算算假定直接费用与工期为线性关系，如图：MdMijmij Dij费用时间BA dijmij为极限费用；Mij为正常费用；dij为极限工期；Dij为正常工期；d为压缩后的作业时间；M为压缩后的直接费用运筹学教程几个概念Mij指当工期延长到定程度，直接费用不能再随之下降时的费用；Dij指对应正常费用（Mij）的工期；mij指当工期缩短到一定程度，再增加直接费用，工期也不能再缩短时的费用；dij指对应极限费用（mij）的工期。运筹学教程直接费用变动率指活动作业时间每缩短或延长一个单位时间所需增加或减少的费用。结论：直接费用变动率越大，则缩短工期而增加的直接费用越多。时间费用优化时，首先应缩短关键线路上cij值最小的活动作业时间。运筹学教程2.间接接费用的用的计算算设单位时间间接费用额为Cj 则工期Tx对应的间接费用CJ 为：CJ=CjTx 运筹学教程（三）（三）时间费用用优化的原化的原则 关键线路上的活动优先；直接费用变化率小的活动优先；逐次压缩活动的作业时间以不超过赶工时间为限；运筹学教程具体步骤：1)用正常作业时间计算网络时间参数、活动直接费用变化率及工程周期。2)计算正常时间条件下的工程总费用。3)逐步压缩关键线路的延续时间，找出最低费用及最佳工期。注意：每次优化以后，会引起关键线路的变化，因而要重新绘制网络图，寻找出关键线路。运筹学教程例3 工作 正常工时 特急工时成本斜率cij(元d)时间(d)费用(元)时间(d)费用(元)24302226241818500090004000100008000540064001618182420181070001020048001030090005400680025010020015025050运筹学教程 直接费用Mij=47800元 正常情况下，总间接费用18000，缩短一天减少间接费用330元。求最低成本日程。12345624302226241818T=74250,8100,12200,4150,2250,4,050,8Cij,d运筹学教程12345624302226241818T=74250,8100,12200,4150,2250,4,050,812345624182226241818T=6412?20运筹学教程12345624202226241818T=64250,8100,2200,4150,2250,4,050.812345624182026241818T=62250,8100,0200,2150,2250,4,050.8增加的直接费用1000；总成本：63500增加的直接费用600总成本：63440运筹学教程不能继续缩短工期以降低成本。总工期62天，总成本63440元。关键线路多条，必须同时缩短。寻求费用最小的缩短边可以化为寻求最小割集问题。12345624181824241818T=60250,8100,0200,0150,0250,4,050.8增加的直接费用700总成本：63480运筹学教程小结：1、网络图的编制。2、时间参数的计算。作业：教材例1:时间参数的计算