ch3系统优化(学生版)课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1 线性规划,一、应用举例,例1：,生产计划问题 某车间计划安排生产A、B两种产品。它们都需要经过车、铣两个工段完成。已知有关数据如下表所示。,试安排一个总利润最大的生产计划。,第3章 系统管理优化方法,1,1 线性规划 第3章 系统管理优化方法1,工 段,加工工时定额（小时/件）,可利用工时,（总小时数）,A产品,B产品,车工工段,5,10,60,铣工工段,4,4,40,产品利润,6元/件,8元件,设：,A、B,产品分别安排生产x,1,、x,2,件,列出线性规划模型如下：,2,工 段加工工时定额（小时/件）可利用工时A产品B产品车工,例2：,合理下料问题 某工地施工需要2米长的钢筋7根，7米长的钢筋2根，配套使用。现有15米长的钢筋150根。问如何利用现有钢筋满足需要且最省料？,3,例2：合理下料问题 某工地施工需要2米长的钢筋7根，7米,7,2,2,2,2,剩料,0,7,2,2,2,7,2,2,2,2,1,1,1,1,方案二：,方案三：,设：,以方案一、二、三分别切割x,1,、x,2,、x,3,根钢筋,分析：下料方案：,方案一：,4,72222剩料7222722221111方案二：方案三：设：,例3：,广告渠道决策问题 某公司拟制定一个广告计划，需在电视、广播、杂志三种渠道间作出选择。已知广告效果如下：见表。,试作出最有利的广告计划。,列出线性规划模型如下：,5,例3：广告渠道决策问题 某公司拟制定一个广告计划，需在电,广告渠道,广告效果,电视广告时间,广播,杂志,白昼,热门,1,、,每个广告单元费用,（万元）,2、,每个广告单元所接触未来的顾客人数,（万人）,3、每个广告单元所接触未来的妇女人数,（万人）,4,40,30,7.5,90,40,3,50,20,1.5,20,10,该公司用于广告的费用支出共有80万元.要求是:,(1)接触到的妇女人数至少200人次；（2）电视广告,6,广告渠道电,费用不超过50万元；（3）白昼电视至少要订3个广告单元，热门电视时间至少要订2个广告单元；（4）广播和杂志的广告单元都要在10和50个单元之间。,试列出最优广告计划的线性规划模型。,设：,x,1,、x,2,、x,3,、x,4,分别为白昼电视、热门电视、广播和杂志的计划广告单元数。,则：,线性规划目标函数为：,maxz = 40x,1,+ 90x,2,+50x,3,+ 20x,4,约束条件为：,（见下页）,7,费用不超过50万元；（3）白昼电视至少要订3个广告单元，热门,8,8,二、线性规划的解法,只含2个变量,1、图解法,以,生产计划问题,为例,9,二、线性规划的解法只含2个变量以 生产计划问题为例9,目标函数图形表出目标函数等值线,x,2,x,1,10,6,10,12,(1),(2),O,Z,1,=24,Z,2,=48,(8,2),约束条件线性表出可行域,10,目标函数图形表出目标函数等值线 x2x11061012,目标函数等值线，沿箭头方向移动至过（8，2）时，目标函数值达到最大。,得最优解 X,*,= （8，2）,T,。最优值 maxZ = 64。,2、关于解的有关定理,x,2,x,1,10,12,(1),(2),O,B(8,2),A（0，6）,C（10，0）,11,目标函数等值线，沿箭头方向移动至过（8，2）时，目标函数值,Max（Z,（A）,=48；Z,（B）,=64；Z,（C）,=60；Z,（O）,=0）,= Z,（B）,=64；,所以：最优解 X,*,= （8，2）,T,；,最优值 maxZ = 64。,运用定理：,Z,（A）,=48；Z,（B）,= 64；Z,（C）,= 60；Z,（O）,= 0,三、关于解的讨论,12,Max（Z（A）=48；Z（B）=64；Z（C）=60；Z（, 2,网络计划技术,一、,网络计划技术的产生与发展,五十年代，美国最先创立了,关键线路法CPM,和,计划评审技术PERT,13, 2 网络计划技术一、 网络计划技术的产生与发展五十年代，,1956年，杜邦化学公,司运用网络方法制定,出第一个网络计划，,用于找出关键路线，,称,关键线路法,1957年，美国海军,特种计划局武器局,在北极星导弹项目,计划中发明、应用,计划评审技术,统称为,网络计划技术,（PERT),以网络图为基础，通过网络分析和计算，,制定出网络计划和实施管理,14,1956年，杜邦化学公 1957年，美国海军,二、网络图的绘制,1、网络图的构成要素,活动（作业、工作,）, 消耗资源才能完成的具有实际内容的实践过程,i,j,活动名称,活动时间,活动,的图示,文字表示：活动（i , j）或 i j,15,二、网络图的绘制1、网络图的构成要素ij活动名称活动时间活动,i,结点,的图示,文字表示：结点（i ）,结点（事项）,活动的开始或结束,i,j,虚活动,的表示,虚活动,不消耗资源，用于表示活动之间相互依存、制约的逻辑关系。,16,i结点 的图示文字表示：结点（i ） 结点（事项） 活,线路：,从始结点出发沿箭头方向，连续不断达到终点形成的一条通路。,1,2,4,5,6,3,1,2,3,5,5,6,5,3,17,线路：从始结点出发沿箭头方向，连续不断达到终点形成的一条,1,2,4,6,1,2,5,1,2,3,4,1,3,6,6,5,1,3,4,6,5,6,5,其它（略）,共有6条,关键线路CP ：,在带有时间参数的网络图中，时间最长的线路为关键线路。,该网络图关键线路为：,1,3,4,6,5,6,5,18,12461251234136651346565其它（略）,关键线路时间（网络计划时间）,关键线,路上活动时间总和。,记为: CP（t）= 5 + 6 + 5 = 16,2、网络图绘制规则双代号法下,有向图时序、方向,结点编号；,两个结点间只能有一个活动；,单一始、众结点,虚活动控制,19,关键线路时间（网络计划时间） 关键线2、网络图绘制规则,3、网络图的绘制,活动逻辑关系表,活动,紧后活动,A,B,C,D,E,F,G,D,G,E,F,G,G,活动,紧前活动,A,B,C,D,E,F,G,H,A、B,A、B,B,C,C,D、E、F,（1 ）,（2 ）,20,3、网络图的绘制活动紧后活动AD活动紧前活动A（1 ）（2,绘制网络图举例,1,2,4,5,7,3,3,4,7,1,6,5,B,A,B,C,D,E,F,C,A,5,E,F,G,D,6,G,不完善！,完善！,（1 ）,21,绘制网络图举例124573347165BABCDEFC,（2 ）,1,2,3,4,6,5,B,A,C,D,E,F,G,H,22,（2 ）123465BACDEFGH22, 3,网络时间参数计算,一、活动的时间参数,活动参数的表示,1）一种时间表示法：,活动中时间以一个固定时间参数表示。记作：T,ij,标注在箭线中下方,i,j,T,ij,23, 3 网络时间参数计算一、活动的时间参数ijTij23,2）三种时间表示法：,活动中的时间以三种时间表示。,i,j,( a, m, b ),乐观时间,最可能时间,悲观时间,乐观时间 a,最可能时间 m,悲观时间 b,24,2）三种时间表示法：活动中的时间以三种时间表示。ij( a,活动时间的估计,1）经验估计法,适用于：计划活动完全相同情况下。,2）类推比较法,适用于：计划中的完全类似的活动,3）统计分析法,适用于：计划中活动部分类似的情况。,4）技术测定法,适用于：计划中的活动是全新的活动。,25,活动时间的估计3）统计分析法 25,二、网络 时间参数计算,1）最早时间参数,结点最早时间 T,E,（j）,活动最早开始时间 T,ES,（i , j）,T,ES,（i , j）= T,E,（i）,活动最早结束时间 T,EF,（i , j）,T,EF,（i , j）= T,ES,（i , j）+ T,ij,26,二、网络 时间参数计算1）最早时间参数 活动最早开始时间,1,2,5,7,7,0.5,5,2.5,3,4,6,8,6,1.5,3,1,8,箭线中下方数字: 计划活动时间,T,ij,27,125770.552.5346861.5318 箭线中下,1,2,5,7,7,0.5,5,2.5,5.5,3,4,6,9,8,6,3,1.5,3,1,0,0.5,5.5,9,3,9,17,3,3,9,3,8,5.5,7,0.5,1.5,0.5,0,0,3,0,8,17,8,9,9,16,i,j,T,ij,T,EF,T,ES,T,E,(i),网络图中参数图注,28,125770.552.55.534698631.531 00,2）最迟时间参数,结点最迟时间T,L,（i）,活动最迟结束时间 T,LF,（i , j）,T,LF,（i , j）= T,L,（j）,活动最迟开始时间 T,LS,（i , j）,T,LS,（i , j）= T,LF,（i , j）- T,ij,29,2）最迟时间参数 活动最迟结束时间 TLF（i , j）,1,2,5,7,7,0.5,5,2.5,5.5,3,4,6,9,8,5,6,3,1.5,3,1,0,2,5.5,0,6.5,7.5,3,9,9,3,9,17,9,17,7.5,9,10,6.5,9,3,3,9,4,3,8,7.5,5.5,9,7,6.5,0.5,7.5,1.5,0.5,6,0,0,3,3,0,0,9,8,1,17,8,9,17,9,16,17,i,j,T,ij,T,EF,T,ES,T,LF,T,LS,T,E,T,L,网络图中参数图注,30,125770.552.55.5346985631.531 0,3) 时差,结点时差 S（i）,S（i）= T,L,（i）- T,E,（i）,活动总时差 S（i , j）,S（i , j）= T,LF,（i , j）- T,LS,（i , j）- T,ij,=,T,LF,（i , j）- T,EF,（i , j）,= T,LS,（i , j）- T,ES,（i , j）,31,3) 时差 31,1,2,5,7,7,0.5,5,2.5,5.5,3,4,6,9,8,5,6,3,1.5,3,1,0,0.5,5.5,0,6.5,7.5,3,9,9,3,9,17,9,17,7.5,9,10,6.5,9,3,3,9,4,3,8,7.5,5.5,9,7,6.5,0.5,7.5,1.5,0.5,6,0,0,3,3,0,0,9,8,1,17,8,9,17,9,16,17,i,j,T,ij,T,EF,S(I,j),T,ES,T,LF,T,LS,T,E,T,L,网络图中参数图注,（0）,S（i）,（0）,（6）,（0）,（2）,（0）,（0）,0,6,1,0,0,6,2,1,2,1,32,125770.552.55.5346985631.531 0,关键线路 (CP) :,关键线路时间:,CP,(t) = 3 + 6 + 0 + 8 = 17,网络时间参数的表格计算,前例:,6,1,3,5,7,1,2,5,7,7,0.5,5,2.5,3,4,6,8,6,1.5,3,1,8,33,关键线路 (CP) : 关键线路时间: CP (t) =,活 动,T,ij,(1),T,E,(i),(2),T,L,(i),(3),T,ES,(4),T,EF,(5),T,LS,(6),T,LF,(7),S,( i, j ),(7) (5),S,(i ),(3) - (2),关键活动,关键结点,i,j,1,2,0.5,0,0,0,0.5,6,6.5,6,0,1,3,3,0,0,0,3,0,3,0,0,1-3,1,5,8,0,0,0,8,1,9,1,0,2,4,1,0.5,6.5,0.5,1.5,6.5,7.5,6,6,3,4,2.5,3,3,3,5.5,5,7.5,2,0,3,5,6,3,3,3,9,3,9,0,0,3-5,3,6,5,3,3,3,8,4,9,1,0,4,6,1.5,5.5,7.5,5.5,7,7.5,9,2,2,5,6,0,9,9,9,9,9,9,0,0,5-6,5,7,7,9,9,9,16,10,17,1,0,6,7,8,9,9,9,17,9,17,0,0,6-7,7,-,-,17,17,-,-,-,-,-,0,34,活 动TijTE(i) TL(i)TESTEFTLSTLFS,6,1,3,5,7,关键线路 (CP) :,关键线路时间:,CP,(t) = 3 + 6 + 0 + 8 = 17,三、寻找关键线路的其它方法,矩阵法,35,61357关键线路 (CP) : 三、寻找关键线路的其它方,三、网络优化,网络计划的优化的内容包括：,缩短工程进度,缩短的工程进度的途径主要有：,1）采取技术措施，压缩关键工序的时间；,2）对关键线路上的工序组织平行或交叉作业；,3）从非关键工序上抽调部分人力物力集中于关键工序增加关键线路上的投入,36,三、网络优化网络计划的优化的内容包括：36,最低成本进程时间与费用的转化,网络活动需要消费多种资源，其它资源归结为费用表达时，为缩短网络计划时间就需要付出费用。即,“时间费用转换”。,主要的问题有：,1） 如何调整关键线路上的活动，以最小的费用增加，换取整个项目周期缩短得最多？,37,最低成本进程时间与费用的转化37,2）当项目工期已经确定，如何安排各项活动使整个工程计划费用最低？,仅就1）以例说明：,举例：某一承包工程项目的网络图如下。图中标注：,1,2,A ，P,T,ij,，T,ij,活动名称,活动时间,活动费用率（万元/天）,活动所需最短时间,38,2）当项目工期已经确定，如何安排各项活动使整个工程计划费用最,1,2,5,7,8，7,A,，,2，2,E，25,3,4,8,F ，-,B，50,8，6,I，50,D，150,C，75,10，9,5 ，5,20，14,8，7,1，1,6 ，3,-,10，8,H，150,G，-,J，150,6,9,K，150,6 ，4,现工程发包方提出：将原定工期（网络计划时间）,48天,提前到,42,天完成。予以追加,550,万元赶工费用。作为承包方，请你分析是否可行？,39,12578，7A，2，2E，25348F ，-B，508，,思路：“,最小成本加速法”,每加快一天进度所支付的费用最低分析，直至达到新工期，同时，总支出费用不超过550万元，则可行。,网络计划工期 CP（t）= 48天,最小成本加速法做法：,从关键线路入手，选择活动费用率最低的活动加快进度，缩短活动时间。,40,思路：“最小成本加速法”每加快一天进度所支付的费用最低分,网络（工程项目）的资源平衡,有两类问题：,1）工程项目工期不变，对所需要的非时间资源（人、物、财力）的需求进行平衡；,2）在资源供应限定条件下，确定最短的项目工期。,41,网络（工程项目）的资源平衡41,仅就1）以例说明：,1,3,4,6,2,5,B. 2 (3),E. 3 (8),C. 2 (6),F. 2 (7),D. 2 (4),G. 3 (2),H. 4 (1),A. 4 ( 9),j,i,A , 3 ( 5 ),关键线路CP ：,1,2,3,5,6,关键线路时间CP（t) =11,活动名称,活动时间,其他资源,42,仅就1）以例说明：134625B. 2 (3)E. 3,现在工期 不变下，将网络所需要资源进行平衡,D.2.(4),C.2.(6),B.2.(3),A . 4 . (9),E . 3 . (8),H . 2 . (1),G .3 . (2),F.2.(7),资,源,B . 2 . (3),E . 3 . (8),A . 4 . (9),22,24,10,2,1,11,2,4,2,4,5,5,7,7,11,10,10,10,10,0,时间(天),43,现在工期 不变下，将网络所需要资源进行平衡 D.2.(4)C,本章结束,重点内容,1、线性规划有关基本概念；,2、根据实际问题列出线性规划模型；,3、对两个线性规划问题求解；,4、理解网络计划中的活动、结点、,关键线路等概念；,5、正确绘制网络图；,6、会计算时间参数,44,本章结束重点内容 44,作业1：,（1）设有两发动机生产专业厂A,1,、A,2,，月产发动机分别为23台、27台。供应3个飞机总装厂B,1,、B,2,、B,3,。各飞机厂需要的数量分别为17台、18台和15台。发动机厂到飞机厂的运费如表所示：,飞机厂,发动机厂,B,1,B,2,B,3,A,1,A,2,50,60,60,10,70,160,单位：百元,列出总运费最低的线性规划模型。,第3章作业,45,作业1： 飞机厂B1B2B3A150,作业2：,某家具厂生产两种柜子，产一台A柜、B柜的时间分别为60小时和50小时；分别占用10、20立方米的仓库空间；家具厂每周有6000小时的上产时间，仓库空间有1500立方米。此外，A的销售量每周不超过80台。A的售价150元，成本90元；B的售价100元，成本65元。如果每周要使两种柜子的的总收入不低于6000元。问如何安排生产计划最有利？（求解最优解）,46,作业2：46,3题： 某工厂计划安排生产A 和B两种产品，已知生产单位产品所需的设备和原材料如下表所示。该工厂每生产一件A产品，可获利2元，每生产一件B产品可获利3元，问应该如何安排生产，可使工厂的获利最多？,A,B,可用资源,设 备,1,2,8（台时）,原材料1,4,0,16（k g）,原材料2,0,4,12（k g）,47,3题： 某工厂计划安排生产A 和B两种产品，已知生产单,作业5: 绘制网络图,活 动,A B C D E F,紧前活动, A，B B B,活 动,G H I J K,紧前活动,B，C F、G D、E D、E I 、H,习题4：,解下列线性规划,1、minZ = 1.5x,1,+2.5x,2,2、minZ = 2x,1,- 10x,2,48,作业5: 绘制网络图 活 动 A,作业6: 绘制下表活动网络图,活动,活 动 内 容,紧后,活动,A,制定飞机战术、技术性能指标,B,B,确定飞机总体设计方案,C、D、E,C,向发动机研制单位提供技术要求,N,D,向机载设备和各系统提供技术要求,O,E,向飞机结构设计提技术要求,F,F,飞机零、部件设计,K、G、H、I,G,绘制飞机装配图,M,H,绘制飞机零件图纸,J,49,作业6: 绘制下表活动网络图活动活 动 内 容紧后A制定飞机,I,零件工装及设备制造,J,J,飞机零件加工,L,K,飞机装配工装及设备制造,M,L,飞机零件表面处理,M,M,部件装配,R,N,发动机研制,P,O,机载设备研制,Q,P,发动机装配,R,Q,机载设备安装,R,R,飞机总装,S,S,试飞,50,I 零件工装及设备制造JJ 飞机零件加工LK 飞,作业7:,绘制下列网络计划的网络图，并以图上标注、计算网络时间参数；确定关键线路。,活动,紧前活动,活动时间,活动,紧前活动,活动时间,A,B,C,D,E,A,A,B、C,B、C,3,4,5,7,7,F,G,H,I,J,C,C,D、E,G,F、H、I,8,4,2,3,2,作业8: 教材P203 第 8 题,51,作业7: 绘制下列网络计划的网络图，并以图上标注、计算网络,思 考 题,（1）线性规划的无界解图形如何？,（2）多重最优解图示怎样？,（3）网络图的关键线路是否只有一条？为什么？,（4）虚活动的运用应该注意那些问题？,52,思 考 题52,