运筹学模型与软件实践课件

运筹学模型运筹学模型与与软件软件实践实践中国科学院研究生院中国科学院研究生院 Models and Software Practice of the Operations Research第八章计划排序和统筹方法第八章计划排序和统筹方法 计划排序模型计划排序模型 装配线平衡模型装配线平衡模型 计划网络图（计划网络图（LingoLingo求解关键路径）求解关键路径）计划排序模型计划排序模型 N N个零件在一台机器加工的排序问题个零件在一台机器加工的排序问题 用用LingoLingo编制程序编制程序SETS:JOB/JOB1,JOB2,JOB3,JOB4,JOB5,JOB6,JOB7/:TIME,!Its TIME;RANK;!Its rank in time;ENDSETSDATA:TIME=1.8 2.5 0.8 2.0 0.9 1.3 1.4;ENDDATAFOR(JOB(I):RANK(I)=SUM(JOB(J)|TIME(J)#LT#TIME(I)#OR#(TIME(J)#EQ#TIME(I)#AND#J#LT#I):1)+1);参见具体的程序进行说明参见具体的程序进行说明注意规则的制定影响排名先后：注意规则的制定影响排名先后：当两个数值一样大时，认为前者比后者大当两个数值一样大时，认为前者比后者大 一台机器加工选择模型一台机器加工选择模型 有有n件工件要在一台机器上加工，每个工件都有完件工件要在一台机器上加工，每个工件都有完工的日期（工的日期（DD,Due date），加工的时间（），加工的时间（PT Processing time）和工件的价值（）和工件的价值（VAL Value if job is selected），模型要求整个选择加工的工件价值最），模型要求整个选择加工的工件价值最大。大。分析分析 此模型的目标函数比较容易建立，约束条此模型的目标函数比较容易建立，约束条件要求，对于加工的工件要按完工的日期的次序。件要求，对于加工的工件要按完工的日期的次序。因此，能在第因此，能在第j工件前，只有更早完工的日期的工工件前，只有更早完工的日期的工件进行，并且工件必须在它们完工日期前被完成。件进行，并且工件必须在它们完工日期前被完成。JOB/1.6/:!Each job has a.;DD,!Due date;PT,!Processing time;VAL,!Value if job is selected;VAL=9 2 4 2 4 6;DD=9 3 6 5 7 2;PT=5 2 4 3 1 2;对所有工作的进行时间、完成时间分析，发现不是所有的工作对所有工作的进行时间、完成时间分析，发现不是所有的工作都可以在这台机器上加工。所以需要选择部分工作在这台机器都可以在这台机器上加工。所以需要选择部分工作在这台机器上加工。上加工。SETS:!A flag variable Y indicating if the job has been selected.;JOB/1.6/:!Each job has a.;DD,!Due date;PT,!Processing time;VAL,!Value if job is selected;Y;!=1 if job is selected,else 0;ENDSETS!Maximize the total value of the jobs taken;MAX=SUM(JOB:VAL*Y);!For the jobs we do,we do in due date order;FOR(JOB(J):!Only jobs with earlier due dates can precede job J,and jobs must be completed by their due dates;SUM(JOB(I)|DD(I)#LT#DD(J)#OR#(DD(I)#EQ#DD(J)#AND#I#LE#J):PT(I)*Y(I)=0);!对于每一个工作台对于每一个工作台,分配给它的总的工作时间应该比周期的最大分配给它的总的工作时间应该比周期的最大值要小值要小;FOR(STATION(K):SUM(TXS(I,K):T(I)*X(I,K)=CYCTIME);!最小化它的最大周期最小化它的最大周期;MIN=CYCTIME;FOR(TXS:BIN(X);计划网络图计划网络图(工程网络图工程网络图)网络计划技术网络计划技术 通过网络图（有向图）来制定工程项目的时间通过网络图（有向图）来制定工程项目的时间进度计划，并用来控制计划的执行的一套现代化管进度计划，并用来控制计划的执行的一套现代化管理方法。理方法。网络计划技术的优点网络计划技术的优点 1.是协调人们共同劳动的是协调人们共同劳动的科学依据科学依据；2.尤其适用于项目规模大、技术复杂、新任务无经验尤其适用于项目规模大、技术复杂、新任务无经验 的情况；的情况；3.即便完不成任务，也知道完不成任务的即便完不成任务，也知道完不成任务的道理所在道理所在；4.可以做到时间资源及费用方面的细致的可以做到时间资源及费用方面的细致的定量分析定量分析。发展过程发展过程 1958年年，美国美国海军特种计划局研制海军特种计划局研制“北极星北极星”潜艇发射潜艇发射导弹时，首先组织人力研究开发并且应用了导弹时，首先组织人力研究开发并且应用了“网络计划网络计划”这这一新型的管理技术，使预计一新型的管理技术，使预计8 年完成的任务，提前年完成的任务，提前2年完成；年完成；1961年，美国研制年，美国研制“阿波罗阿波罗”登月飞船登月飞船，应用了该技术；，应用了该技术；1962年年，日本日本引进这种管理技术；首先在建筑、钢铁和引进这种管理技术；首先在建筑、钢铁和造船等大型民用工业中，应用这门技术；造船等大型民用工业中，应用这门技术；1964年年，前苏联前苏联引进并大力发展；引进并大力发展；1963年中国年中国在研制一台电子计算机任务中，首次应用了在研制一台电子计算机任务中，首次应用了这一技术，取得明显效果。我国早期称为这一技术，取得明显效果。我国早期称为“统筹法统筹法”。1965年年6月月6日，已故著名数学家日，已故著名数学家华罗庚教授华罗庚教授在在“人民日报人民日报”上发上发表文章表文章“统筹方法平话统筹方法平话”，后编写简易读本，后编写简易读本“统筹方法平话统筹方法平话及补充及补充”。华罗庚教授在文化大革命中带领一批数学工作者。华罗庚教授在文化大革命中带领一批数学工作者坚持在基层推广应用坚持在基层推广应用“两法两法”，作出了巨大贡献。，作出了巨大贡献。1985年逝年逝世于在日本讲学的讲台上，实现了世于在日本讲学的讲台上，实现了“树老怕空，人老怕松，树老怕空，人老怕松，戒空戒松，从严以终戒空戒松，从严以终”的人生格言。我们应该永远记住这位的人生格言。我们应该永远记住这位伟大的学者。伟大的学者。网络计划技术，原理简单但应用效果网络计划技术，原理简单但应用效果非常显著，使得我国高层管理者十分重视非常显著，使得我国高层管理者十分重视这一技术的开发和应用，大力培养人才，这一技术的开发和应用，大力培养人才，并对基层应用制定了一些鼓励措施和规定。并对基层应用制定了一些鼓励措施和规定。在葛洲坝二期工程中，采用在葛洲坝二期工程中，采用“网络计划技网络计划技术术”，用，用 110 天完成了经验工期天完成了经验工期 195 天的天的工作量，在宝钢工程和三峡工程中，也都工作量，在宝钢工程和三峡工程中，也都取得了显著的经济效益。取得了显著的经济效益。网络图的绘制网络图的绘制 一般，用一张网络图表示一项工程项目。一般，用一张网络图表示一项工程项目。绘制一张符合实际情况、逻辑关系准确、符合一定绘图规绘制一张符合实际情况、逻辑关系准确、符合一定绘图规则的网络图，是制定则的网络图，是制定“网络计划网络计划”的基础。的基础。活动代号活动代号 A活动时间活动时间(所需资源所需资源)箭线式网络箭线式网络：A节点式网络节点式网络：一、一、网络图的组成网络图的组成1.活动活动（工序、工作、作业），（工序、工作、作业），（Activity）表示方法表示方法：在工艺技术和组织管理上相对独立的、有具体内容有在工艺技术和组织管理上相对独立的、有具体内容有 名称的、消耗时间的实践过程。名称的、消耗时间的实践过程。2.事项事项（Event）箭线式网络：箭线式网络：i紧前活动紧前活动紧后活动紧后活动3.虚活动虚活动（Dummy Activity）ij箭线式网络：箭线式网络：活动（活动（i，j）：）：ij 表示方法表示方法：活动的开始或结束的瞬间；不消耗时间及资源，既表示活动的开始或结束的瞬间；不消耗时间及资源，既表示紧前活动的结束，又表示紧后活动的开始。紧前活动的结束，又表示紧后活动的开始。表示方法表示方法：只表示逻辑关系，不表示任何活动，不消耗时间和资源，只表示逻辑关系，不表示任何活动，不消耗时间和资源，不写名称。不写名称。绘制规则（箭线式网络）绘制规则（箭线式网络）1.一个起点一个起点事项、事项、一个终点一个终点事项；事项；2.活动活动表示表示唯一唯一，箭头的指向表示时间的流向；，箭头的指向表示时间的流向；3.以下表示：以下表示：ADBCAB4.两事项之间只允许有一个活动两事项之间只允许有一个活动；活动活动A、B、C全部结束后，活动全部结束后，活动D才能开始才能开始；ikjABkijAB或或5.不允许有循环不允许有循环设设计计制造制造检验检验修改设计修改设计设计设计制造制造检验检验修改设计修改设计6.事项编号：小事项编号：小大大ij规定：规定：ij即即7.尽可能少设置虚活动尽可能少设置虚活动。例例 某工程有某工程有ABCD 四项活动，关系：四项活动，关系：AC，AD，BD 绘图绘图：1234DBAC 例（例（绘图绘图）某工程有）某工程有ABCLM 等等 12 项活动，项活动，关系：关系：活动活动 A B C D E F G H I K L M 紧前活动紧前活动GM H L C AE BC AL F I BC C1234657981011HCBEMLGDAIFK时间参数计算时间参数计算 1.活动时间活动时间 tij 完成活动（完成活动（i，j）所需的时间；）所需的时间；a）一次性确定法）一次性确定法（肯定型肯定型网络）网络）标准标准：大多数（大多数（90%以上）能够完成；以上）能够完成；少部分（少部分（5%以内）提前完成；以内）提前完成；少部分（少部分（5%以内）努力才能完成；以内）努力才能完成；适用于有工时定额或相关资料、有先例可循的情况；适用于有工时定额或相关资料、有先例可循的情况；由于由于 tij 是确定的常数，因而称为是确定的常数，因而称为肯定型肯定型网络计划。网络计划。b）三种时间估计法三种时间估计法（非肯定型非肯定型网络）网络）aij 最乐观时间，最乐观时间，P tij a=0.01 bij 最悲观时间，最悲观时间，P tij b=0.01 mij最可能时间，峰值点最可能时间，峰值点 6bm4atijijijij而 tij 成为常数后同肯定型网络；成为常数后同肯定型网络；tijfij（t）0.010.01aijbijmij02.事项最早时间事项最早时间 TE（i）事项最早出现的时刻；事项最早出现的时刻；n2itkTEmaxiTE(01TEkik，）（）（工程计时起点）（计算图示：计算图示：工程最早完工期工程最早完工期 TE=TE（n）工程最早完工期工程最早完工期 TE 由网络计划本身所由网络计划本身所客观客观决定。决定。表示：表示：TEikkkt ki t ki t ki TETETETE3.事项最迟时间事项最迟时间 TL（j）在不影响工程最迟完工在不影响工程最迟完工 期期TL(人为人为决定决定)情况下，事项必须出现的最迟时刻情况下，事项必须出现的最迟时刻 122n1njtkTLminjTL0,TTnTLjkkEL，）（）（）（工程最早完工期（人为决定）工程最迟完工期）（计算图示：计算图示：表示：表示：TLjkkkt jkt jkt jkTLTLTLTL 例例 求各事项的求各事项的最早最早、最迟最迟时间及时间及工程工程(最早最早)完工期完工期；（设（设人为人为规定工程规定工程最迟最迟完工期为完工期为 17）；）；12345670.5382.5511.578600.535.5991717997.536.50 工程工程(最早最早)完工期完工期 TE=17（客观客观决定）决定）4.事项的时差事项的时差 S（i）在不影响工程最迟完工期在不影响工程最迟完工期TL (人为决定人为决定)情况下，事项的出现可以往后拖延的最多时间；情况下，事项的出现可以往后拖延的最多时间；S（i）=TL（i）TE（i）相对于相对于 =0，当，当 0 时，时，TE（i）、）、TL（i）及）及S（i）有）有 何变化？关键事项如何定义？何变化？关键事项如何定义？S（i）=0 的事项称为的事项称为关键事项关键事项；5.活动的最早开工时间活动的最早开工时间 TES（i，j）ijTEtij6.活动的最早完工时间活动的最早完工时间 TEF（i，j）TEF（i，j）=TES（i，j）+tij )i,k(TEFMaxkTES（i，j）=TE（i）7.活动的最迟完工时间活动的最迟完工时间 TLF（i，j）在不影响工程在不影响工程最最 迟完工期情况下，活动完工必须卡住的最迟时刻；迟完工期情况下，活动完工必须卡住的最迟时刻；ijtijTL8.活动的最迟开工时间活动的最迟开工时间 TLS（i，j）在不影响工程在不影响工程最迟完工期情况下，活动开工必须卡住的最迟时刻；最迟完工期情况下，活动开工必须卡住的最迟时刻；)k,j(TLSMinkTLF（i，j）=TL（j）9.活动的总时差活动的总时差 S（i，j）在不影响在不影响工程最迟完工期工程最迟完工期情况下，活动开工（完工）可以往后拖延的最大时间；情况下，活动开工（完工）可以往后拖延的最大时间；S（i，j）=TLF（i，j）TEF（i，j）=TLS（i，j）TES（i，j）TLS（i，j）=TLF（i，j）tij 10.活动的自由时差活动的自由时差（单时差）（单时差）SF（i，j）在不影在不影 响响紧后活动最早开工紧后活动最早开工情况下，活动开工（完工）可以往后情况下，活动开工（完工）可以往后 拖延的最大时间；拖延的最大时间；S（i，j）=0 的活动称为的活动称为关键活动关键活动；S（i）=0 的事项称为的事项称为关键事项关键事项；从起点到终点由关键活动连起来的一条路，称为从起点到终点由关键活动连起来的一条路，称为关键线路关键线路；SF（i，j）=TES（j，k）TEF（i，j）=TE（j）TEF（i，j）关键线路关键线路的性质：的性质：1.关键线路一定存在，可能有多条，条条长度都相等；关键线路一定存在，可能有多条，条条长度都相等；2.关键线路是从起点到终点的最长路；关键线路是从起点到终点的最长路；3.关键线路的长度就是工程（最早）完工期。关键线路的长度就是工程（最早）完工期。ijTEk 例例 求工程求工程完工期完工期及及关键线路关键线路240.5382.5511.578600.535.5991717997.536.50关键线路关键线路：13567368关键事项关键事项，关键活动关键活动，13576工程完工期工程完工期 TE=171.已知已知ijTETETLTLtij 写出以下公式：写出以下公式：TES（i，j）=TEF（i，j）=TLF（i，j）=TLS（i，j）=S（i，j）=SF（i，j）=问题问题2.0 与与 相比，以上相比，以上 6 个时间参数的变化？个时间参数的变化？0 3.当当 0时，关键事项、关键活动、关键线路如何？时，关键事项、关键活动、关键线路如何？TE（i）TE（i）+tijTL（j）TL（j）tijTL（j）TE（i）+tij TE（j）TE（i）+tij TL（i）)()()(表格计算时间参数表格计算时间参数活动（i，j）tijTESTEFTLSTLFSFS 0.5380.51.55.5985.57916917TE=17(客观)TL=17(人为)380.50.52.5651.5078工程完工期10 917173330009999947.5999317.57.56.5 56.5360（1，3）（1，5）（1，2）（2，4）（3，4）（3，5）（3，6）（4，6）（5，6）（5，7）（6，7）0014001201060162012010*得TE=17 关线：13567（最早）时间坐标网络图（最早）时间坐标网络图42.51.520.51135673684281511703917712345670.5382.5511.5786Lingo优化软件求解优化软件求解PERT模型模型假设假设Wireless WidgetWireless Widget公司计划向市场投放公司计划向市场投放一种新产品一种新产品The Solar WidgetThe Solar Widget。为了保证准时投放市场，为了保证准时投放市场，Wireless WidgetWireless Widget公司要对主要作业进行公司要对主要作业进行PERTPERT分析，其目的分析，其目的是找出是找出关键作业路线关键作业路线。位于关键路线上的。位于关键路线上的作业必须按时完成，这样才能保证作业必须按时完成，这样才能保证Wireless WidgetWireless Widget公司的产品及时投放市场，公司的产品及时投放市场，各项作业及预计完成时间如下：各项作业及预计完成时间如下：Task（作业）（作业）Weeks（时间）（时间）Finalize Design（确定方案）（确定方案）10Forecast Demand（预测需求）（预测需求）14Survey Competition（调查竞争）（调查竞争）3Set Price（确定价格）（确定价格）3Schedule Production Run（确定（确定生产时间）生产时间）7Cost Out（成本核算）（成本核算）4Train Salesmen（训练销售人员）（训练销售人员）10产品作业优先关系产品作业优先关系可以构造如下的集合：可以构造如下的集合：TASKS/DESIGN,FORECAST,SURVEY,PRICE,SCHEDULE,COSTOUT,TRAIN/:TIME,ES,LS,SLACK;对于集合的对于集合的4个属性，它们的解释如下：个属性，它们的解释如下：TIME 完成作业的时间完成作业的时间ES 作业最早开始时间作业最早开始时间LS 作业最迟开始时间作业最迟开始时间SLACK 作业作业LS和和ES之间相差的时间之间相差的时间在模型中输入优先关系：在模型中输入优先关系：PRED(TASK,TASK)/DESIGN,FORECAST,DESIGN,SURVEY,FORECAST,PRICE,FORECAST,SCHEDULE,SURVEY,PRICE,SCHEDULE,COSTOUT,PRICE,TRAIN,COSTOUT,TRAIN/;给出数据域部分的内容给出数据域部分的内容DATA:TIME=10,14,3,3,7,4,10;ENDDATA此时我们有三个属性需要计算：此时我们有三个属性需要计算：最早开始（最早开始（ES）、最迟开始（）、最迟开始（LS）和松弛时）和松弛时间（间（SLACK）。）。关键计算关键计算ES、LS，因为，因为SLACK是两者之差。是两者之差。计算计算ESES（最早开始时间）：（最早开始时间）：对于一项作业来说，作业对于一项作业来说，作业t的最早开始时间等于的最早开始时间等于作业作业t的的所有紧前作业的最早开始时间加上它自所有紧前作业的最早开始时间加上它自身完成时间之和身完成时间之和的的最大值最大值。FOR(TASKS(J)|J#GT#1:ES(J)=MAX(PRED(I,J):ES(I)+TIME(I);计算计算LS LS（最迟开始时间）（最迟开始时间）：对于一项作业来说，作业对于一项作业来说，作业t的最迟开始时间等于的最迟开始时间等于作业作业t的的所有紧后作业的最早开始时间与作业所有紧后作业的最早开始时间与作业t t自身完成时间之差自身完成时间之差的的最小值最小值。FOR(TASKS(I)|I#LT#LTASK:LS(I)=MIN(PRED(I,J):ES(J)-TIME(I);最后一项作业没有紧后作业，忽略最后一项作业没有紧后作业，忽略计算计算SLACK（松弛时间）：（松弛时间）：FOR(TASKS(I):SLACK(I)=LS(I)-ES(I);对于作业对于作业1的开始时间可以取任意值，咱们取的开始时间可以取任意值，咱们取0。最后一项作业的最迟开始时间不用计算。对于最后一项作业的最迟开始时间不用计算。对于最后一个作业，最后一个作业，最迟开始时间和最早开始时间最迟开始时间和最早开始时间应该是应该是一致的一致的。ES(1)=0;LS(7)=ES(7);SETS:TASKS/DESIGN,FORECAST,SURVEY,PRICE,SCHEDULE,COSTOUT,TRAIN/:TIME,ES,LS,SLACK;PRED(TASKS,TASKS)/DESIGN,FORECAST,DESIGN,SURVEY,FORECAST,PRICE,FORECAST,SCHEDULE,SURVEY,PRICE,SCHEDULE,COSTOUT,PRICE,TRAIN,COSTOUT,TRAIN/;ENDSETSDATA:TIME=10,14,3,3,7,4,10;ENDDATAFOR(TASKS(J)|J#GT#1:ES(J)=MAX(PRED(I,J):ES(I)+TIME(I);FOR(TASKS(I)|I#LT#LTASK:LS(I)=MIN(PRED(I,J):LS(J)-TIME(I););FOR(TASKS(I):SLACK(I)=LS(I)-ES(I);ES(1)=0;LTASK=SIZE(TASKS);LS(LTASK)=ES(LTASK);使用使用ExcelExcel软件求解关键路径软件求解关键路径 使用使用WinQSBWinQSB软件求解关键路径软件求解关键路径 成本优化的计算方法成本优化的计算方法