《ch3系统优化(学生版)》由会员分享，可在线阅读，更多相关《ch3系统优化(学生版)（52页珍藏版）》请在金锄头文库上搜索。
1、1,1 线性规划 一、应用举例例1：生产计划问题 某车间计划安排生产A、B两种产品。它们都需要经过车、铣两个工段完成。已知有关数据如下表所示。 试安排一个总利润最大的生产计划。,第3章 系统管理优化方法,2,设：A、B产品分别安排生产x1、x2 件 列出线性规划模型如下：,3,例2：合理下料问题 某工地施工需要2米长的钢筋7根，7米长的钢筋2根，配套使用。现有15米长的钢筋150根。问如何利用现有钢筋满足需要且最省料？,4,7,2,2,2,2,剩料0,7,2,2,2,7,2,2,2,2,1,1,1,1,方案二：,方案三：,设：以方案一、二、三分别切割x1、x2、x3 根钢筋,分析：下料方案：
2、方案一：,5,例3：广告渠道决策问题 某公司拟制定一个广告计划，需在电视、广播、杂志三种渠道间作出选择。已知广告效果如下：见表。 试作出最有利的广告计划。,列出线性规划模型如下：,6,该公司用于广告的费用支出共有80万元.要求是:(1)接触到的妇女人数至少200人次；（2）电视广告,7,费用不超过50万元；（3）白昼电视至少要订3个广告单元，热门电视时间至少要订2个广告单元；（4）广播和杂志的广告单元都要在10和50个单元之间。 试列出最优广告计划的线性规划模型。设：x1、x2、x3、x4分别为白昼电视、热门电视、广播和杂志的计划广告单元数。则：线性规划目标函数为： maxz = 40x1 +
3、 90x2 +50x3 + 20x4 约束条件为： （见下页）,8,9,二、线性规划的解法只含2个变量1、图解法,以 生产计划问题为例,10,目标函数图形表出目标函数等值线,x2,x1,10,6,10,12,(1),(2),O,Z1=24,Z2=48,(8,2),约束条件线性表出可行域,11,目标函数等值线，沿箭头方向移动至过（8，2）时，目标函数值达到最大。 得最优解 X* = （8，2）T。最优值 maxZ = 64。,2、关于解的有关定理,x2,x1,10,12,(1),(2),O,B(8,2),A（0，6）,C（10，0）,12,Max（Z（A）=48；Z（B）=64；Z（C）=60；
4、Z（O）=0） = Z（B）=64；所以：最优解 X* = （8，2）T； 最优值 maxZ = 64。,运用定理：Z（A）=48；Z（B）= 64；Z（C）= 60；Z（O）= 0,三、关于解的讨论,13, 2 网络计划技术,一、 网络计划技术的产生与发展,五十年代，美国最先创立了关键线路法CPM和计划评审技术PERT,14,1956年，杜邦化学公 司运用网络方法制定 出第一个网络计划， 用于找出关键路线， 称 关键线路法,1957年，美国海军 特种计划局武器局 在北极星导弹项目 计划中发明、应用 计划评审技术,统称为网络计划技术（PERT) 以网络图为基础，通过网络分析和计算， 制定出网络
5、计划和实施管理,15,二、网络图的绘制,1、网络图的构成要素 活动（作业、工作） 消耗资源才能完成的具有实际内容的实践过程,i,j,活动名称,活动时间,活动 的图示,文字表示：活动（i , j）或 i j,16,i,结点 的图示,文字表示：结点（i ）,结点（事项） 活动的开始或结束,i,j,虚活动的表示,虚活动 不消耗资源，用于表示活动之间相互依存、制约的逻辑关系。,17,线路：从始结点出发沿箭头方向，连续不断达到终点形成的一条通路。,1,2,4,5,6,3,1,2,3,5,5,6,5,3,18,1,2,4,6,1,2,5,1,2,3,4,1,3,6,6,5,1,3,4,6,5,6,5,其它
6、（略） 共有6条,关键线路CP ：在带有时间参数的网络图中，时间最长的线路为关键线路。 该网络图关键线路为：,1,3,4,6,5,6,5,19,关键线路时间（网络计划时间） 关键线 路上活动时间总和。记为: CP（t）= 5 + 6 + 5 = 16,2、网络图绘制规则双代号法下有向图时序、方向 结点编号； 两个结点间只能有一个活动； 单一始、众结点 虚活动控制,20,3、网络图的绘制 活动逻辑关系表,（1 ）,（2 ）,21,绘制网络图举例,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 ）,22,（2
7、）,1,2,3,4,6,5,B,A,C,D,E,F,G,H,23, 3 网络时间参数计算,一、活动的时间参数 活动参数的表示1）一种时间表示法：活动中时间以一个固定时间参数表示。记作：Tij 标注在箭线中下方,i,j,Tij,24,2）三种时间表示法：活动中的时间以三种时间表示。,i,j,( a, m, b ),乐观时间,最可能时间,悲观时间,乐观时间 a 最可能时间 m 悲观时间 b ,25,活动时间的估计1）经验估计法适用于：计划活动完全相同情况下。2）类推比较法 适用于：计划中的完全类似的活动,3）统计分析法 适用于：计划中活动部分类似的情况。4）技术测定法适用于：计划中的活动是全新的活
8、动。,26,二、网络 时间参数计算,1）最早时间参数 结点最早时间 TE（j）,活动最早开始时间 TES（i , j） TES（i , j）= TE（i） 活动最早结束时间 TEF（i , j） TEF（i , j）= TES（i , j）+ Tij,27,1,2,5,7,7,0.5,5,2.5,3,4,6,8,6,1.5,3,1,8,箭线中下方数字: 计划活动时间 Tij,28,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,9,16,i,j,Tij,TEF,TES,TE(i),网络图中参数图注,29,2）最迟时间参数 结点最迟时间TL（i）,活动最迟结束时间 TLF（i , j） TLF（i , j）= TL（j） 活动最迟开始时间 TLS（i , j） TLS（i , j）= TLF（i , j）- Tij,30,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,
10、3,3,0,0,9,8,1,17,8,9,17,9,16,17,i,j,Tij,TEF,TES,TLF,TLS,TE,TL,网络图中参数图注,31,3) 时差 结点时差 S（i） S（i）= TL（i）- TE（i） 活动总时差 S（i , j） S（i , j）= TLF（i , j）- TLS（i , j）- Tij = TLF（i , j）- TEF（i , j） = TLS（i , j）- TES（i , j）,32,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
11、,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,Tij,TEF,S(I,j),TES,TLF,TLS,TE,TL,网络图中参数图注,（0）,S（i）,（0）,（6）,（0）,（2）,（0）,（0）,0,6,1,0,0,6,2,1,2,1,33,关键线路 (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,
12、8,6,1.5,3,1,8,34,35,6,1,3,5,7,关键线路 (CP) : 关键线路时间: CP (t) = 3 + 6 + 0 + 8 = 17,三、寻找关键线路的其它方法 矩阵法,36,三、网络优化,网络计划的优化的内容包括： 缩短工程进度缩短的工程进度的途径主要有：1）采取技术措施，压缩关键工序的时间；2）对关键线路上的工序组织平行或交叉作业；3）从非关键工序上抽调部分人力物力集中于关键工序增加关键线路上的投入,37,最低成本进程时间与费用的转化 网络活动需要消费多种资源，其它资源归结为费用表达时，为缩短网络计划时间就需要付出费用。即“时间费用转换”。 主要的问题有：1） 如何调
13、整关键线路上的活动，以最小的费用增加，换取整个项目周期缩短得最多？,38,2）当项目工期已经确定，如何安排各项活动使整个工程计划费用最低？ 仅就1）以例说明： 举例：某一承包工程项目的网络图如下。图中标注：,1,2,A ，P,Tij ，Tij,活动名称,活动时间,活动费用率（万元/天）,活动所需最短时间,39,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,现工程发包方提出：将原定工期（网络
14、计划时间）48天 提前到 42 天完成。予以追加 550 万元赶工费用。作为承包方，请你分析是否可行？,40,思路：“最小成本加速法”每加快一天进度所支付的费用最低分析，直至达到新工期，同时，总支出费用不超过550万元，则可行。,网络计划工期 CP（t）= 48天,最小成本加速法做法：从关键线路入手，选择活动费用率最低的活动加快进度，缩短活动时间。,41,网络（工程项目）的资源平衡 有两类问题：1）工程项目工期不变，对所需要的非时间资源（人、物、财力）的需求进行平衡；2）在资源供应限定条件下，确定最短的项目工期。,42,仅就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,活动名称,活动时间,其他资源,43,现在工期 不变下，将网络所需要资源进行平衡,
