运筹学-网络计划课件

1、OPERATIONS RESE运 筹 学提醒：五月27、28日（即下周二、周三）的下午2：30到系机房上实验课，不得缺席。OR3 1OPERATIONS RESE运 筹 学提醒：五 第五节 网络计划引言： 国外实践证明：应用网络计划技术组织与管理生产和项目，一般能缩短工期20左右，降低成本10左右。 上海宝钢炼铁厂1号高炉土建工程施工中，应用网络法，缩短工期21，降低成本9.8。OR3 2 第五节 网络计划引言：OR3 1、基本概念网络图（有向赋权图）的构成：节点和箭线节点：每个节点称为事件，是箭线两端的连接点。表示工序的开始或结束。剪线：代表工序。剪尾表示该工序的开始，箭头表示该工序的结束。

2、工序：是组成整个任务的局部任务，需要消耗一定资源或占用一定时间。注意：与工序相比，节点不需要时间或所需要时间少到可以忽略不计。OR3 31、基本概念网络图（有向赋权图）的构成：节点和箭线OR3 例: 景泰蓝的制作工序：制胎、掐丝、点蓝、烧蓝、打磨、镀金。ij工作名称或代号持续时间注意： 网络计划图是有向、有序的赋权图，应按项目的工作流程从左向右编制。在时序上反应各项工作的先后顺序。节点编号必须是箭尾编号小于箭头编号。1234567制胎掐丝点蓝烧蓝打磨镀金0.511222OR3 4例: 景泰蓝的制作工序：制胎、掐丝、点蓝、烧蓝、打磨2、画网络图的基本规则1）网络图中只能有一个总起点节点和一个总终

3、点节点。总起点节点和总终点节点分别表示计划的开始和结束。紧前工序：紧排在本工作之前的工作。紧后工序：指紧排在本工作之后的工序。1342567ABCDEFOR3 52、画网络图的基本规则1）网络图中只能有一个总起点节点和一个2）网络图不允许出现循环回路。3)节点i,j之间不允许有两道或两道以上的工序。21312ABOR3 62）网络图不允许出现循环回路。21312ABOR3 4)需正确表示工序之间的前行后继关系，工序之间的逻辑关系的分解图归纳如下：（1）A完成后进行B和C。ABCOR3 74)需正确表示工序之间的前行后继关系，工序之间的逻辑关系的分(2)A,B均完成后进行C。ABCOR3 8(2

4、)A,B均完成后进行C。ABCOR3 （3）A，B均完成后进行C和D。 ABCDOR3 9（3）A，B均完成后进行C和D。ABCDOR3 (4)A完成后进行C，A,B完成后进行D。虚工序：只表示相邻工作之间的逻辑关系，不占用资源的虚设工序。ACBDOR3 10(4)A完成后进行C，A,B完成后进行D。ACBDOR3 （5）A，B均完成后进行C；B,D均完成后进行E。ACBDEOR3 11（5）A，B均完成后进行C；B,D均完成后进行E。ACBDE5)虚工序的运用：可以用于正确表示平行工序与交叉工序。平行工序：一道工序分为几道工作同时进行，称为平行工序。交叉工序：两件或两件以上的工序交叉进行，称

5、为交叉工序。OR3 125)虚工序的运用：可以用于正确表示平行工序与交叉工序。OR3举例挖沟：挖沟，埋钢管。挖一段埋一段。24挖沟挖沟8挖沟8挖沟8a1a2a3b1b2b3十八岗拖拉机厂十五里河姚公庙OR3 13举例挖沟：24挖沟挖沟8挖沟8挖沟8a1a2a3b1b2b3工 序ABCDEFGHI紧前工序-ABBC、DC、DE、FG工序时间466759748例题1：请按照下表编制该项目的网络计划图A BCDEGH467675F94I8OR3 14工 序ABCDEFGHI紧前工序-ABB课堂练习：请编制下表的网络计划图P287工序紧后工序工序时间AB,C,D,E60BL45CF10DG,H20EH

6、40FL18GK30HL15KL25L/35OR3 15课堂练习：请编制下表的网络计划图P287工序紧后工序工序时间线路：网络图中，从起点节点沿箭线方向顺序通过一系列箭线与节点，最后到达终点节点的通路。关键路线：即持续时间最长的路线。关键路线上的各工作叫做关键工作。A BCDEGH467675F94I8OR3 16线路：网络图中，从起点节点沿箭线方向顺序通过一系列箭线与节点A BCDEGH467675F94I8网络计划图的布局要求：尽可能将关键路线布置在网络图的中心位置，按工作的先后顺序将联系紧密的工作布置在临近的位置；箭线应是水平或具有水平线的折线。A4C6B6D7G7I8F9E5H4OR3

7、 17A BCDEGH467675F94I8网络计3、网络计划图的时间参数计算1）工作持续时间的计算方法：（1）单时估计法。D工作的持续时间Q工作的工作量。R可投入人力和设备的数量S每人或每台设备每工作班能完成的工作量。n-每天正常工作班次。OR3 183、网络计划图的时间参数计算1）工作持续时间的计算方法：OR（2）三时估计法。先估计三种时间值，然后求其平均数。乐观时间，记为a最可能时间，记为m悲观时间，记为b工作持续时间：OR3 19（2）三时估计法。先估计三种时间值，然后求其平均数。OR3 2）其它时间的计算公式（1）工作最早开始时间（ES)；工作最早完成时间（EF） 从网络图的起点开始

8、进行计算。 第一项工作的最早开始时间为0，记为： ES1j0； 最早完成时间为：EF1j= ES1j+D 1j注意：前一项工序完成以后，其紧后的工序才能开始。前一项工作的最早完成时间是其紧后工序的最早开始时间。所以有：EFij= ESij+D ijOR3 202）其它时间的计算公式EFij= ESij+D ijO(2)工作最迟开始时间（LS）；工作最迟完成时间（LF）从网络图的终点开始采用逆序法进行计算。网络图中最后一项工序的最迟完成时间应为工程的计划工期。若未给定计划工期，则取其为最早完成时间。即LFi-n=EFi-n.，LSi-n= LFi-n- Di-n其它工序： LSi-j= LFi-

9、j- Di-j即LF=min(紧后工作的LS).OR3 21(2)工作最迟开始时间（LS）；工作最迟完成时间（LF）OR（3）工作时差 时差又叫机动时间或富余时间。常用的时差有两种：a)工作总时差TFi-j。指在不影响工期的前提下，工作所具有的机动时间。计算公式：TFi-j=EFi-j-ESi-j-Di-j=LSi-j-ESi-j或者为： TFi-j=LFi-j-EFi-jb)工作自由时差FF。在不影响其紧后工作最早开始的前提下，工作所具有的机动时间。计算公式：FFi-j=ESj-k-ESi-j-Di-j 或： FFi-j= ESj-k- EFi-j 注意：关键路线上无机动时间，工作总时差为零

10、。最后一道工序的FF为总工期将该工序的最早结束时间。.OR3 22（3）工作时差OR3 . 例 计算上例工序时间参数 工序ijD(i,j)ESEFLSLFTFFFA4043730B6060600C641071333D761361300E561119241311F91322152420G71320132000H42226242822I82028202800OR3 23. 例 计算上例工序时间参数 工序ijD(i,j)ESEFL4 网络优化(1)工期优化： 使用技术措施，缩短关键路线。 采取组织措施，合理调配人力，物力，资金等资源。(2)资源优化： 优先安排关键工作所需的资源； 利用非关键工作的总

11、时差，错开各工作的开始时间。 的确受到资源约束时，考虑推迟工期12123网络优化在上述基础上，寻求时间更短、资源更省、成本更低的方案。OR3 244 网络优化(1)工期优化：12123网络优化在上述基础上(3)时间费用优化时间和费用双目标优化，一般来讲二者是矛盾的。通过仔细分析，寻找既省时又省钱的方案，即最低成本日程。费用：直接费用和间接费用直接费用：建造工程本身所需材料、人工间接费用：工程所需管理费用、设备租赁费用等。ct间接费用总费用直接费用赶工：直接费用增加，间接费用减少。OR3 25(3)时间费用优化ct间接费用总费用直接费用赶工：直接费用费用优化的步骤(1)计算工作费用增加率；(2)

12、在网络图中找出费用率最低的一项关键工作或一组关键工作作为缩短持续时间的对象。(3)计算相应的增加的总费用，然后考虑由于工期的缩短间接费用的变化，在这个基础上计算项目的总费用。重复上述步骤，直至获得满意的方案为止。赶工直接费用率费用差时间差OR3 26费用优化的步骤(1)计算工作费用增加率；赶工直接费用率费用前面内容总复习：第一章：绪论。（了解）第二章：线性规划与单纯形法1，掌握线性规划的建模方法。2，掌握将非标准型LP模型转变为标准型。3，掌握LP问题的解法：图解法，单纯形解法。（图解法：什么情况下会出现唯一最优解，无穷多最优解，无界解，无可行解。）（单纯形法：会运用单纯形法求解LP问题；会根

13、据单纯形表中出现的特征判断出该问题是否有唯一最优解，无穷多最优解，无界解以及无可行解P24。OR3 27前面内容总复习：第一章：绪论。（了解）OR3 4，掌握大M法以及两阶段法。5，理解书P3637页的表19，110，图19。第三章：对偶理论与灵敏度分析1，掌握原问题与对偶问题数学模型的转化。书P56，表24。2，对偶问题的基本性质P57。特别是性质3、5、6、73，理解影子价格，影子价格的应用。OR3 284，掌握大M法以及两阶段法。OR3 影子价格：对偶解yi* 的经济意义：其它条件不变的情况下，第i种资源改变一个单位所引起的目标函数最优解的变化。 情况 某资源对偶解0，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。 情况 直接用影子价格与市场价格相比较，进行决策，决定是否买入该资源。 即：影子价格所含有的信息：1、资源紧缺状况；2、确定资源转让基价；3、取得紧缺资源的代价。OR3 29影子价格：对偶解yi* 的经济意义：其它条件不变的情况下，第 CjC1 C2 CnCBXBbX1 X2 X3 X4 X5j 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X