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

1、11 线性规划线性规划 一、应用举例一、应用举例例例1：生产计划问题 某车间计划安排生产A、B两种产品。它们都需要经过车、铣两个工段完成。已知有关数据如下表所示。试安排一个总利润最大的生产计划。2工工 段段加工工时定额（小时加工工时定额（小时/件）件）可利用工时可利用工时（总小时数）（总小时数）A产品产品B产品产品车工工段车工工段51060铣工工段铣工工段4440产品利润产品利润6元元/件件8元件元件设：设：A、B产品分别安排生产x1、x2 件 列出线性规划模型如下：3040446010586max21212121xxxxxxtSxxz、例例2 2：合理下料问题 某工地施工需要2米长的钢筋7根

2、，7米长的钢筋2根，配套使用。现有15米长的钢筋150根。问如何利用现有钢筋满足需要且最省料？47 72 22 22 22 2剩料剩料0 07 72 22 22 27 72 22 22 22 21 11 11 11 1方案二：方案二：方案三：方案三：设：设：以方案一、二、三分别切割x1、x2、x3 根钢筋 分析：下料方案：分析：下料方案：方案一：方案一：5)321(015001414min32132132、jxxxxxxxtsxxzj例例3 3：广告渠道决策问题 某公司拟制定一个广告计划，需在电视、广播、杂志三种渠道间作出选择。已知广告效果如下：见表。试作出最有利的广告计划。列出线性规划模型如

3、下：6 广告渠道广告效果电视广告时间广播杂志白昼热门1、每个广告单元费用（万元）2、每个广告单元所接触未来的顾客人数（万人）3、每个广告单元所接触未来的妇女人数（万人）440307.59040350201.52010 该公司用于广告的费用支出共有80万元.要求是:(1)接触到的妇女人数至少200人次；（2）电视广告7费用不超过50万元；（3）白昼电视至少要订3个广告单元，热门电视时间至少要订2个广告单元；（4）广播和杂志的广告单元都要在10和50个单元之间。试列出最优广告计划的线性规划模型。设：设：x1、x2、x3、x4分别为白昼电视、热门电视、广播和杂志的计划广告单元数。则：则：线性规划目标

4、函数为：maxz=40 x1+90 x2+50 x3+20 x4 约束条件为：（见下页）84321010510523505.7420010204030805.135.7443212143214321、jxxxxxxxxxxxxxxxtsj9二、线性规划的解法二、线性规划的解法只含只含2 2个变量个变量1 1、图解法、图解法以 生产计划问题生产计划问题 为例0,0)2(4044)1(60105.86max21212121xxxxxxtsxxZ10 目标函数图形表出目标函数图形表出目标函数等值线目标函数等值线 x x2 2x x1 11061012(1)(1)(2)(2)OZ Z1 1=24=24

5、Z Z2 2=48=48(8,2)(8,2)约束条件线性表出约束条件线性表出可行域可行域11 目标函数等值线，沿箭头方向移动至过（目标函数等值线，沿箭头方向移动至过（8 8，2 2）时，目标函数值达到最大。时，目标函数值达到最大。得最优解 X*=（8，2）T。最优值 maxZ=64。2 2、关于解的有关定理、关于解的有关定理x x2 2x x1 11012(1)(1)(2)(2)O OB(8,2)B(8,2)A A（0 0，6 6）C C（1010，0 0）12MaxMax（Z Z（A A）=48=48；Z Z（B B）=64=64；Z Z（C C）=60=60；Z Z（O O）=0=0）=Z

6、=Z（B B）=64=64；所以：最优解所以：最优解 X X*=（8 8，2 2）T T；最优值最优值 maxZmaxZ=64=64。运用定理：运用定理：Z（A）=48；Z（B）=64；Z（C）=60；Z（O）=0 三、关于解的讨论三、关于解的讨论13 2 网络计划技术网络计划技术一、一、网络计划技术的产生与发展网络计划技术的产生与发展五十年代，美国最先创立了关键线路法关键线路法CPM和和计划评审技术计划评审技术PERT14 1956年，杜邦化学公 司运用网络方法制定 出第一个网络计划，用于找出关键路线，称 关键线路法关键线路法 1957年，美国海军 特种计划局武器局 在北极星导弹项目 计划中

7、发明、应用 计划评审技术计划评审技术 统称为网络计划技术网络计划技术（PERT)以网络图为基础，通过网络分析和计算，以网络图为基础，通过网络分析和计算，制定出网络计划和实施管理制定出网络计划和实施管理 15二、网络图的绘制二、网络图的绘制1、网络图的构成要素、网络图的构成要素 活动（作业、工作活动（作业、工作）消耗资源才能完成的具有实际内容的实践过程ij活动名称活动名称活动时间活动时间活动活动 的图示的图示 文字表示：活动（文字表示：活动（i,j）或）或 i j16i结点结点 的图示的图示文字表示：结点（文字表示：结点（i）结点（事项）结点（事项）活动的开始或结束ij虚活动虚活动的表示的表示

8、虚活动虚活动 不消耗资源，用于表示活动之间相互依存、制约的逻辑关系。17 线路：线路：从始结点出发沿箭头方向，连续不断达到终点形成的一条通路。1245631235565318线路有12461251234136651346565其它（略）共有共有6条条 关键线路关键线路CP：在带有时间参数的网络图中，时间最长的线路为关键线路。该网络图关键线路为：该网络图关键线路为：134656519关键线路时间（网络计划时间）关键线路时间（网络计划时间）关键线 路上活动时间总和。记为记为:CP（t）=5+6+5=162、网络图绘制规则、网络图绘制规则双代号法下双代号法下1)有向图有向图时序、方向时序、方向2)结

9、点编号；结点编号；3)两个结点间只能有一个活动；两个结点间只能有一个活动；4)单一始、众结点单一始、众结点5)虚活动控制虚活动控制203、网络图的绘制、网络图的绘制 活动逻辑关系表活动逻辑关系表活动活动 紧后活动紧后活动ABCDEFGDGEFGG活动活动 紧前活动紧前活动ABCDEFGHA、BA、BBCCD、E、F（1）（2）21 绘制网络图举例绘制网络图举例124573347165BABCDEFCA5EFGD6G不完善！不完善！完善！完善！（1）22（2）123465BACDEFGH23 3 网络时间参数计算网络时间参数计算一、活动的时间参数一、活动的时间参数 活动参数的表示活动参数的表示1

10、）一种时间表示法：）一种时间表示法：活动中时间以一个固定时间参数表示。记作：Tij 标注在箭线中下方ijTij242）三种时间表示法：）三种时间表示法：活动中的时间以三种时间表示。ij(a,m,b)乐观时间乐观时间最可能时间最可能时间悲观时间悲观时间乐观时间乐观时间 a 最可能时间最可能时间 m 悲观时间悲观时间 b 25 活动时间的估计活动时间的估计1）经验估计法）经验估计法适用于：计划活动完全相同情况下。适用于：计划活动完全相同情况下。2）类推比较法）类推比较法 适用于：计划中的完全类似的活动适用于：计划中的完全类似的活动3）统计分析法）统计分析法 适用于：计划中活动部分类似的情况。适用于

11、：计划中活动部分类似的情况。4）技术测定法）技术测定法适用于：计划中的活动是全新的活动。适用于：计划中的活动是全新的活动。26二、网络二、网络 时间参数计算时间参数计算1）最早时间参数）最早时间参数 结点最早时间结点最早时间 TE（j）活动最早开始时间活动最早开始时间 TES（i,j）TES（i,j）=TE（i）活动最早结束时间活动最早结束时间 TEF（i,j）TEF（i,j）=TES（i,j）+Tij27125770.552.5346861.5318 箭线中下方数字:计划活动时间 Tij28125770.552.55.534698631.531 00.55.5 9 3 917339385.5

12、70.51.50.5003081789916 ijTijTEFTESTE(i)网络图中参数图注网络图中参数图注292）最迟时间参数）最迟时间参数 结点最迟时间结点最迟时间TL（i）活动最迟结束时间活动最迟结束时间 TLF（i,j）TLF（i,j）=TL（j）活动最迟开始时间活动最迟开始时间 TLS（i,j）TLS（i,j）=TLF（i,j）-Tij 30125770.552.55.5346985631.531 0 25.506.57.5 3 9 9 3 917 9 177.59106.593394387.55.5976.50.57.51.50.5600330098117891791617 ij

13、TijTEFTESTLFTLSTE TL网络图中参数图注网络图中参数图注313)时差时差 结点时差结点时差 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）32125770.552.55.5346985631.531 00.55.506.57.5 3 9 9 3 917 9 177.59106.593394387.55.5976.50.57.51.50.5600330098117891791617 ijTijTEFS(I,j)TESTLFT

14、LSTE TL网络图中参数图注网络图中参数图注（0）S（i）（0）（6）（0）（2）（0）（0）061006212133关键线路关键线路(CP):关键线路时间关键线路时间:CP(t)=3+6+0+8=17 网络时间参数的表格计算网络时间参数的表格计算 前例前例:61357125770.552.5346861.531834活活 动动Tij(1)TE(i)(2)TL(i)(3)TES(4)TEF(5)TLS(6)TLF(7)S(i,j)(7)(5)S(i)(3)-(2)关键关键活动活动关键关键结点结点ij120.50000.566.560133000303001-3158000819102410.

15、56.50.51.56.57.566342.53335.557.520356333939003-536533384910461.55.57.55.577.5922560999999005-65779991610171067899917917006-77-1717-03561357关键线路关键线路(CP):关键线路时间关键线路时间:CP(t)=3+6+0+8=17三、寻找关键线路的其它方法三、寻找关键线路的其它方法 矩阵法矩阵法 36三、网络优化三、网络优化网络计划的优化的内容包括：网络计划的优化的内容包括：缩短工程进度缩短工程进度缩短的工程进度的途径主要有：缩短的工程进度的途径主要有：1）采取

16、技术措施，压缩关键工序的时间；）采取技术措施，压缩关键工序的时间；2）对关键线路上的工序组织平行或交叉作业；）对关键线路上的工序组织平行或交叉作业；3）从非关键工序上抽调部分人力物力集中于关）从非关键工序上抽调部分人力物力集中于关键工序增加关键线路上的投入键工序增加关键线路上的投入37 最低成本进程最低成本进程时间与费用的转化时间与费用的转化 网络活动需要消费多种资源，其它资源归结为网络活动需要消费多种资源，其它资源归结为费用表达时，为缩短网络计划时间就需要付出费费用表达时，为缩短网络计划时间就需要付出费用。即用。即“时间费用转换时间费用转换”。主要的问题有：主要的问题有：1）如何调整关键线路

17、上的活动，以最小的费用增如何调整关键线路上的活动，以最小的费用增加，换取整个项目周期缩短得最多？加，换取整个项目周期缩短得最多？382）当项目工期已经确定，如何安排各项活动使整）当项目工期已经确定，如何安排各项活动使整个工程计划费用最低？个工程计划费用最低？仅就仅就1）以例说明：）以例说明：举例：某一承包工程项目的网络图如下。举例：某一承包工程项目的网络图如下。图中标注：图中标注：12A ，PTij ，Tij活动名称活动名称活动时间活动时间活动费用率（万元活动费用率（万元/天）天）活动所需最短时间活动所需最短时间3912578，7A，2，2E，25348F，-B，508，6I，50D，150C

18、，7510，95，520，148，71，16，3-10，8H，150G，-J，15069K，1506，4 现工程发包方提出：将原定工期（网络计划时间）现工程发包方提出：将原定工期（网络计划时间）48天天 提前到提前到 42 天完成。予以追加天完成。予以追加 550 万元赶工费万元赶工费用。作为承包方，请你分析是否可行？用。作为承包方，请你分析是否可行？40思路：思路：“最小成本加速法最小成本加速法”每加快一每加快一天进度所支付的费用最低分析，直至达到新工天进度所支付的费用最低分析，直至达到新工期，同时，总支出费用不超过期，同时，总支出费用不超过550万元，则可行。万元，则可行。网络计划工期网络

19、计划工期 CP（t）=48天天 最小成本加速法做法：最小成本加速法做法：从关键线路入手，选从关键线路入手，选择活动费用率最低的活动加快进度，缩短活动时择活动费用率最低的活动加快进度，缩短活动时间。间。41 网络（工程项目）的资源平衡网络（工程项目）的资源平衡 有两类问题：有两类问题：1）工程项目工期不变，对所需要的非时间资源）工程项目工期不变，对所需要的非时间资源（人、物、财力）的需求进行平衡；（人、物、财力）的需求进行平衡；2）在资源供应限定条件下，确定最短的项目工期。）在资源供应限定条件下，确定最短的项目工期。42仅就仅就1）以例说明：）以例说明：134625B.2 (3)E.3 (8)C

20、.2(6)F.2(7)D.2(4)G.3(2)H.4(1)A.4(9)jiA,3 (5)关键线路关键线路CP：12356关键线路时间关键线路时间CP（t)=11活动名称活动名称活动时间活动时间其他资源其他资源43现在工期现在工期 不变下，将网络所需要资源进行平衡不变下，将网络所需要资源进行平衡 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)22241021112424557711101010100时间时间(天天)44重点内容重点内容 1 1、线性规划有关基本概念；、线性规划有关基

21、本概念；2 2、根据实际问题列出线性规划模型；、根据实际问题列出线性规划模型；3 3、对两个线性规划问题求解；、对两个线性规划问题求解；4 4、理解网络计划中的活动、结点、理解网络计划中的活动、结点、关键线路等概念；关键线路等概念；5 5、正确绘制网络图；、正确绘制网络图；6 6、会计算时间参数、会计算时间参数45作业作业1 1：（1）设有两发动机生产专业厂A1、A2，月产发动机分别为23台、27台。供应3个飞机总装厂B1、B2、B3。各飞机厂需要的数量分别为17台、18台和15台。发动机厂到飞机厂的运费如表所示：飞机厂飞机厂发动机厂发动机厂B1B2B3A1A25060601070160单位：

22、百元列出总运费最低的线性规划模型。46作业2：某家具厂生产两种柜子，产一台A柜、B柜的时间分别为60小时和50小时；分别占用10、20立方米的仓库空间；家具厂每周有6000小时的上产时间，仓库空间有1500立方米。此外，A的销售量每周不超过80台。A的售价150元，成本90元；B的售价100元，成本65元。如果每周要使两种柜子的的总收入不低于6000元。问如何安排生产计划最有利？（求解最优解）47 3题：某工厂计划安排生产A 和B两种产品，已知生产单位产品所需的设备和原材料如下表所示。该工厂每生产一件A产品，可获利2元，每生产一件B产品可获利3元，问应该如何安排生产，可使工厂的获利最多？AB可

23、用资源设 备128（台时）原材料14016（k g）原材料20412（k g）48作业作业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.5x1+2.5x2 2、minZ=2x1-10 x205500233212121212121xxxxxxxxxxxx、49作业6:绘制下表活动网络图活动活 动 内 容紧后活动A制定飞机战术、技术性能指标 BB确定飞机总体设计方案C、D、EC向发动机研制单位提供技术要求 ND向机载设备和各系统提供技术要求 O

24、E向飞机结构设计提技术要求 FF飞机零、部件设计K、G、H、IG绘制飞机装配图 MH绘制飞机零件图纸 J50I 零件工装及设备制造JJ 飞机零件加工LK 飞机装配工装及设备制造ML 飞机零件表面处理MM 部件装配RN 发动机研制PO 机载设备研制QP 发动机装配RQ 机载设备安装RR 飞机总装SS 试飞51作业作业7:绘制下列网络计划的网络图，并以图上标注、计算绘制下列网络计划的网络图，并以图上标注、计算网络时间参数；确定关键线路。网络时间参数；确定关键线路。活动紧前活动活动时间活动紧前活动活动时间ABCDEAAB、CB、C34577FGHIJCCD、EGF、H、I84232作业作业8:教材教材P203 第第 8 题题 52 思思 考考 题题（1）线性规划的无界解图形如何？）线性规划的无界解图形如何？（2）多重最优解图示怎样？）多重最优解图示怎样？（3）网络图的关键线路是否只有一条？为什么？）网络图的关键线路是否只有一条？为什么？（4）虚活动的运用应该注意那些问题？）虚活动的运用应该注意那些问题？