优化建模与LINGO第07章.ppt

欢迎各位同学学习第七章,内容导航概述7.1运输问题与转运问题7.2最短路问题和最大流问题7.3最优连线问题与旅行商问题7.4计划评审方法和关键路线法习题七,第7章图论与网络模型,本章内容概述本章介绍图论与网络(GraphTheoryandNetwork)的有关优化问题模型。在这里，我们并不打算全面系统介绍图论与网络的知识，而着重介绍与LINDO、LINGO软件有关的组合优化模型和相应的求解过程。如果读者打算深入地了解图论与网络的更全面的知识，请参阅图论或运筹学中的有关书籍.LINDO软件和LINGO软件可以求解一些著名的组合优化问题，这包括最短路问题、最大流问题、运输和转运问题、最优匹配和最优指派问题、最优连线或最小生成树问题、旅行商问题、关键路线法与计划评审方法等。,7.1运输问题与转运问题,本节内容导航7.1.1运输问题7.1.2指派问题7.1.3转运问题,7.1.1运输问题运输问题(TransportationProblem)是图论与网络中的一个重要问题，也是一个典型的线性规划问题.例7.1（运输问题）,返回导航,例7.1就是典型的运输问题，图7-1给出了个产地，个销地运输问题的图形.关于它的求解方法有两类，一类是按照图论的方法求解，另一类是化成线性规划问题.这里介绍第二类方法，即用LINDO或LINGO软件求解运输问题.但为便于后面的叙述，先给出图论中有关图的部分定义.,图7-1:个产地,个销售地运输问题的图形,1.图的基本定义从直观上看,所谓图是由点和边组成的图形,如图7-1所示.下面我们给出图的定义.,注：通常有向图的边称为弧，由弧构成的集记为因此，有向图记为,而无向图记为.为方便起见，在后面的论述中，有时也用表示有向图.在无向图中,每条至多有一条边的图称为简单图(SimpleGraph).若每一对不同的顶点都有一条边相连的简单图称为完全图(CompleteGraph).若一个图中的顶点集可以分解为两个子集和,使得任何一条边都有一个端点在中,另一个端点在中,这种图称为二部图或偶图(BipartiteGraph).运输问题所构成的图7-1是偶图.,2.运输问题的数学表达式,第个产地的运出量应小于或等于该地的生产量，即：,第个销地的运入量应等于该地的需求量，即：,因此，运输问题的数学表达式为:,称具有形如式的线性规划问题为运输问题.,3.运输问题的求解过程为了便于讨论，以一个运输问题实例的求解过程来介绍如何用LINDO或LINGO软件求解运输问题模型.例7.2(继例7.1)设即为有3个产地和4个销地的运输问题，其产量、销量及单位运费如表7-1所示.试求总运费最少的运输方案，以及总运费.,解：从前面的分析来看，运输问题属于线性规划问题，因此，不论是LINDO软件或LINGO软件都可以对该问题求解.为了便于比较两种软件的优缺点，以及各自的特点，我们用两种软件分别求解该运输问题.首先写出LINDO软件的模型（程序），程序名：exam0702.ltx.!3Warehouse,4CustomerTransportationProblem!Theobjectivemin6x11+2x12+6x13+7x14+4x21+9x22+5x23+3x24+8x31+8x32+x33+5x34subjectto,!Thesupplyconstraints2)x11+x12+x13+x14=303)x21+x22+x23+x24=254)x31+x32+x33+x34=21!Thedemandconstraints5)x11+x21+x31=156)x12+x22+x32=177)x13+x23+x33=228)x14+x24+x34=12end,LINDO软件的计算结果如下：LPOPTIMUMFOUNDATSTEP6OBJECTIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000X131.0000000.000000X140.0000002.000000X2113.0000000.000000X220.0000009.000000X230.0000001.000000,X2412.0000000.000000X310.0000007.000000X320.00000011.000000X3321.0000000.000000X340.0000005.000000ROWSLACKORSURPLUSDUALPRICES2)10.0000000.0000003)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.0000008)0.000000-5.000000NO.ITERATIONS=6,事实上，我们关心更多的是那些非零变量，因此,可选择LINDO中的命令（具体方法见第二章的2.3节),只列出非零变量.,OBJECTIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000,X131.0000000.000000X2113.0000000.000000X2412.0000000.000000X3321.0000000.000000ROWSLACKORSURPLUSDUALPRICES3)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.0000008)0.000000-5.000000NO.ITERATIONS=6,LINDO软件虽然给出最优解，但上述模型还存在着缺点，例如，上述方法不便于推广的一般情况，特别是当产地和销地的个数较多时，情况更为突出.下面写出求解该问题的LINGO程序，并在程序中用到在第三章介绍的集与数据段，以及相关的循环函数.写出相应的LINGO程序，程序名：exam0702.lg4,MODEL:1!3Warehouse,4CustomerTransportationProblem;2sets:3Warehouse/1.3/:a;4Customer/1.4/:b;,5Routes(Warehouse,Customer):c,x;6endsets7!Herearetheparameters;8data:9a=30,25,2110b=15,17,22,12;11c=6,2,6,7,124,9,5,3,138,8,1,5;14enddata15!Theobjective;16OBJmin=sum(Routes:c*x);,17!Thesupplyconstraints;18for(Warehouse(i):SUP19sum(Customer(j):x(i,j)=a(i);20!Thedemandconstraints;21for(Customer(j):DEM22sum(Warehouse(i):x(i,j)=b(j);END,在上述程序中，第16表示运输问题中目标函数(7.1).第1819行表示约束条件(7.2),第2122行表示约束条件(7.3).,下面列出LINGO软件的求解结果（仅保留非零变量）,Globaloptimalsolutionfoundatiteration:6Objectivevalue:161.0000VariableValueReducedCostX(1,1)2.0000000.000000X(1,2)17.000000.000000X(1,3)1.0000000.000000X(2,1)13.000000.000000X(2,4)12.000000.000000X(3,3)21.000000.000000RowSlackorSurplusDualPriceOBJ161.0000-1.000000SUP(1)10.000000.000000,从上述求解过程来看，两种软件的计算结果是相同的，但由于LINGO软件中采用集、数据段和循环函数的编写方式，因此更便于程序推广到一般形式使用.例如，只需修改运输问题中产地和销地的个数，以及参数a,b,c的值，就可以求解任何运输问题.所以，从程序通用性的角度来看,推荐大家采用LINGO软件来求解运输问题.,7.1.2指派问题,例7.3（指派问题）设有n个人,计划作n项工作,其中表示第i个人做第j项工作的收益,现求一种指派方式，使得每个人完成一项工作，使总收益最大.例7.3就是指派问题(AssignmentProblem).指派问题也是图论中的重要问题，有相应的求解方法，如匈牙利算法.从问题的形式来看，指派问题是运输问题的特例，也可以看成0-1规划问题.,返回导航,1.指派问题的数学表达式,设变量为,当第个人作第项工作时，,否则.因此，相应的线性规划问题为,2.指派问题的求解过程分别用LINDO软件和LINGO软件求解指派问题，并对两种软件的求解方法与各自的优缺点进行比较.,例7.4（继例7.3）考虑例7.3中的情况,即6个人做6项工作的最优指派问题，其收益矩阵如表7-2所示.,!Assignmentmodel!Maximizevalveofassignmentsmax20 x11+15x12+16x13+5x14+4x15+7x16+17x21+15x22+33x23+12x24+8x25+6x26+9x31+12x32+18x33+16x34+30 x35+13x36+12x41+8x42+11x43+27x44+19x45+14x46-99x51+7x52+10 x53+21x54+10 x55+32x56-99x61-99x62-99x63+6x64+11x65+13x66subjectto,解：与运输问题一样，先用LINDO软件求解.给出LINGO程序，程序名exam0704.ltx,!Eachpersonmustbeassignedtosomejobx11+x12+x13+x14+x15+x16=1x21+x22+x23+x24+x25+x26=1x31+x32+x33+x34+x35+x36=1x41+x42+x43+x44+x45+x46=1x51+x52+x53+x54+x55+x56=1x61+x62+x63+x64+x65+x66=1!Eachjobmustreceiveanassignmentx11+x21+x31+x41+x51+x61=1x12+x22+x32+x42+x52+x62=1x13+x23+x33+x43+x53+x63=1x14+x24+x34+x44+x54+x64=1x15+x25+x35+x45+x55+x65=1x16+x26+x36+x46+x56+x66=1end,在上述程序中，x51,x61,x62,x63前的系数均为-99,这是因为某人无法做某项工作可以某人做该项工作的收益是,在计算中通常取一个较大的负数就可以.上述程序也没有说明决策变量是0-1型变量,这是因为对于此类问题线性规划理论已保证了变量的取值只可能是0或1.,LINDO软件给出的计算结果如下（只列出非零变量）:,OBJECTIVEFUNCTIONVALUE1)135.0000VARIABLEVALUEREDUCEDCOSTX111.0000000.000000X231.0000000.000000X321.0000000.000000X441.0000000.000000X561.0000000.000000X651.0000000.000000ROWSLACKORSURPLUSDUALPRICES,2)0.0000003.0000003)0.00000015.0000005)0.000000-4.0000007)0.000000-19.0000008)0.00000017.0000009)0.00000012.00000010)0.00000018.00000011)0.00000031.00000012)0.00000030.00000013)0.00000032.000000NO.ITERATIONS=20,即第1个人做第1项工作，第2个人做第3项工作,第3个人做第2项工作，第4个人做第4项工作，第5个人做第6项工作，第6个人做第5项工作.总效益值为135.下面用LINGO程序再求解此问题，程序中仍然用到集、数据段和循环函数.写出相应的LINGO程序，程序名exam0704.lg4.,MODEL:1!AssignmentProblemModel;2sets:3Flight/1.6/;4Assign(Flight,Flight):c,x;,5endsets6!Hereisincomematrix;7data:8c=201516547917153312861091218163013111281127191412-9971021103213-99-99-9961113;14enddata15,16!Maximizevalveofassignments;17max=sum(Assign:c*x);18for(Flight(i):19!Eachimustbeassignedtosomej;20sum(Flight(j):x(i,j)=1;21!EachImustreceiveanassignment;22sum(Flight(j):x(j,i)=1;23);END,程序中第1213行中的-99意义与LINDO程序中的意义相同，当某人无法做某项工作时，取一个数值较大的负值.LINGO软件计算结果如下（只列出非零变量）:,Globaloptimalsolutionfoundatiteration:0Objectivevalue:135.0000VariableValueReducedCostX(1,1)1.0000000.000000X(2,3)1.0000000.000000X(3,2)1.0000000.000000X(4,4)1.0000000.000000X(5,6)1.0000000.000000X(6,5)1.0000000.000000,从上述两个例子，可以看出LINGO软件在处理问题方面要大优于LINDO软件，而且便于推广，只是在编程方面，LINGO程序的编写稍复杂一些.在后面的问题求解中，绝大多数的求解方法是采用LINGO软件计算.对于指派问题，也可以考虑人数不工作数不相等的情况，和考虑支付最小的情况.第一章的例1.5“混合泳接力队员选拔问题”就是属于这一类情况.,例7.5（继例1.5）用LINGO软件求解例1.5.解：在第二章的例2.7给出了该问题的LINDO软件求解方法，这里给出LINGO软件的求解方法，读者可根据问题的求解过程来考查两种软件求解问题的方法，以及每种软件各自的特点.为了便于编写程序，将5名队员的4种泳姿的百米平均成绩重新列在表7-3中.,按第1章所列的规划问题（第章中的式(1.25)式(1.28)）写出相应的LINGO程序，程序名：exam0705.lg4.,MODEL:1!5personsand4jobsAssignmentProblem;2sets:3Person/1.5/;4Job/1.4/;5Assign(Person,Job):c,x;6endsets7!Herearetheparameters;8data:,9c=66.8,75.6,87,58.6,1057.2,66,66.4,53,1178,67.8,84.6,59.4,1270,74.2,69.6,57.2,1367.4,71,83.8,62.4;14enddata15!Theobjective;16OBJmin=sum(Assign:c*x);17!Thesupplyconstraints;18for(Person(i):SUP19sum(Job(j):x(i,j)=1);20!Thedemandconstraints;21for(Job(j):DEM22sum(Person(i):x(i,j)=1);END该程序同样没有限制是01型变量.,下面列出LINGO软件计算结果（仅保留非零变量）:,Globaloptimalsolutionfoundatiteration:9Objectivevalue:253.2000VariableValueReducedCostX(1,4)1.0000000.000000X(2,1)1.0000000.000000X(3,2)1.0000000.000000X(4,3)1.0000000.000000RowSlackorSurplusDualPriceOBJ253.2000-1.000000SUP(5)1.0000000.000000,即甲游自由泳，乙游蝶泳，丙游仰泳，丁游蛙泳,没有被选拔上.平均成绩为.4132.,7.1.3转运问题,所谓转运问题(TransshipmentProblem)实质上是运输问题的一种，其区别就在于不是将工厂生产出的产品直接送的顾客手中，而是要经过某些中间环节，如仓库、配送中心等.图7-2表示的是3水平分配（即有一个中间环节）的转运问题.,返回导航,1.转运问题的数学表达式,1.转运问题的求解方法,以一个例子为例，给出求解转运问题的两种求解方法.,例7.6（转运问题）设有两个工厂A,B,产量分别为9,8个单位.四个顾客1,2,3,4,需求量分别为3,5,4,5.和三个仓库x,y,z.其中工厂到仓库、仓库到顾客的运费单价分别由表7-4所示.试求总运费最少的运输方案，以及总运费.,表7-4工厂到仓库、仓库到顾客的运费单价,说明：其中-表示两地无道路通行.,解：写出相应的LINGO程序，程序名：exam0706a.lg4.,MODEL:1!2plants,3warehousesand4customers2TransshipmentProblem;3sets:4Plant/A,B/:produce;5Warhouse/x,y,z/;6Customer/1.4/:require;7LinkI(Plant,Warhouse):cI,xI;8LinkII(Warhouse,Customer):cII,xII;9endsets10!Herearetheparameters;11data:12produce=9,8;,13require=3,5,4,5;14cI=1,2,100,153,1,2;16cII=5,7,100,100,179,6,7,100,18100,8,7,4;19enddata20!Theobjective;21OBJmin=sum(LinkI:cI*xI)+sum(LinkII:cII*xII);22!Thesupplyconstraints;23for(Plant(i):SUP24sum(Warhouse(j):xI(i,j)=level(i)+x(i,j)31-(n-2)*(1-x(i,j)+(n-3)*x(j,i);32);33!Thelevelofcityisatleast1butnomoren-1,34andis1ifitlinkstobase(city1);35bnd(1,level(i),999999);36level(i)=level(i)+x(i,j)31-(n-2)*(1-x(i,j)+(n-3)*x(j,i);32);33);,34!Makethexs0/1;35for(link:bin(x);36!Forthefirstandlaststop;37for(cities(i)|i#gt#1:38level(i)=1+(n-2)*x(i,1);40);END,水平变量(level)仍然是用来保证所选的边除第1点外不构成圈的.计算结果如下：,Globaloptimalsolutionfoundatiteration:90Objectivevalue:73.00000VariableValueReducedCostX(1,2)1.0000008.000000X(2,6)1.0000008.000000X(3,1)1.0000005.000000X(4,3)1.0000007.000000X(5,4)1.0000003.000000X(6,9)1.0000008.000000X(7,10)1.00000011.00000X(8,5)1.0000006.000000X(9,7)1.0000006.000000X(10,8)1.00000011.00000,旅行商经过10个城镇的最短距离为73公里，其连接情况如图7-11所示.,7.4计划评审方法和关键路线法,本节内容导航本节概述7.4.1计划网络图7.4.2计划网络图的计算7.4.3关键路线与计划网络图优化7.4.4完成作业期望和实现事件概率,本节内容概述计划评审方法（ProgramEvaluationandReviewTechnique,简写为PERT）和关键路线法（CritialPathMethod,简写为CPM）是网络分析的重要组成部分，它广泛用系统分析和项目管理.计划评审与关键路线方法是在20世纪50年代提出并发展起来的，1956年，美国杜邦公司为了协调企业不同业务部门的系统规划，提出了关键路线法.1958年，美国海军武装部在研制“北极星”导弹计划时，由于导弹的研制系统过于庞大、复杂，为找到一种有效的管理方法，设计了计划评审方法.由于PERT与CPM即有着相同的目标应用，又有很多相同的术语，这两种方法已合并为一种方法，在国外称为PERT/CPM，在国内称为统筹方法(SchedulingMethod).,返回导航,7.4.1计划网络图,例7.19某项目工程由11项作业组成（分别用代号A,B,J,K表示），其计划完成时间及作业间相互关系如表7-8所示，求完成该项目的最短时间.,例7.19就是计划评审方法或关键路线法需要解决的问题.,返回导航,1.计划网络图的概念,定义7.11称任何消耗时间或资源的行动为作业.称作业的开始或结束为事件，事件本身不消耗资源.在计划网络图中通常用圆圈表示事件，用箭线表示事件，如图7-12所示，1,2,3表示事件，A,B表示作业.由这种方法画出的网络图称为计划网络图.,定义7.12在计划网络图中，称从是初始事件到最终事件的由各项作业连贯组成的一条路为路线。具有累计作业时间最长的路线称为关键路线。由此看来，例7.19就是求相应的计划网络图中的关键路线。,2.建立计划网络图应注意的问题,(1)任何作业在网络中用唯一的箭线表示，任何作业其终点事件的编号必须大于其起点事件.,(2)两个事件之间只能画一条箭线，表示一项作业.对于具有相同开始和结束事件的两项以上作业，要引进虚事件和虚作业.(3)任何计划网络图应有唯一的最初事件和唯一的最终事件.(4)计划网络图不允许出现回路.(5)计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交叉.,7.4.2计划网络图的计算,以例7-19的求解过程介绍计划网络图的计算方法.1.建立计划网络图首先建立计划网络图.按照上述规则，建立例7.19的计划网络图，如图7-13所示.,返回导航,2.写出相应的规划问题,设是事件的开始时间，为最初事件，为最终事件.希望总的工期最短，即极小化.设是作业的计划时间，因此，对于事件与事件有不等式：,由此得到相应的数学规划问题,3.问题求解,例7.20(继例7.19)用LINDO软件求解例7.19解：按照数学规划问题（7.37）-（7.39）编写INDO程序，程序名：,exam0720.ltxminx8-x1subjectto2)x2-x1=53)x3-x1=104)x4-x1=115)x5-x2=4,6)x4-x3=47)x5-x3=08)x6-x4=159)x6-x5=2110)x7-x5=2511)x8-x5=3512)x7-x6=013)x8-x6=2014)x8-x7=15end,LINDO软件的计算结果如下：,LPOPTIMUMFOUNDATSTEP9OBJECTIVEFUNCTIONVALUE1)51.00000VARIABLEVALUEREDUCEDCOSTX851.0000000.000000X10.0000000.000000X25.0000000.000000X310.0000000.000000X414.0000000.000000X510.0000000.000000X631.0000000.000000X736.0000000.000000,ROWSLACKORSURPLUSDUALPRICES2)0.0000000.0000003)0.000000-1.0000004)3.0000000.0000005)1.0000000.0000006)0.0000000.0000007)0.000000-1.0000008)2.0000000.0000009)0.000000-1.00000010)1.0000000.00000011)6.0000000.00000012)5.0000000.00000013)0.000000-1.00000014)0.0000000.000000NO.ITERATIONS=9,计算结果给出了各个项目的开工时间，如,则作业A、B、C的开工时间均是第0天;作业E的开工时间是第5天;则作业D的开工时间是第10天;等等.每个作业只要按规定的时间开工，整个项目的最短工期为51天.,尽管上述LINDO程序给出相应的开工时间和整个项目的最短工期，但统筹方法中许多有用的信息并没有得到，如项目的关键路径、每个作业的最早开工时间、最迟开工时间等.因此，我们希望将程序编写的稍微复杂一些，为我们提供更多的信息.,下面利用LINGO软件完成此项工作.,例7.21用LINGO软件求解例7.19.,解：按照数学规划问题(7.37)-(7.39)编写LINGO程序只有得到整,编写相应的Lingo程序，程序名：exam0721.lg4,MODEL:1sets:2events/1.8/:x;3operate(events,events)/41,21,31,43,42,53,54,65,65,85,76,77,86,85/:s,t;6endsets7data:8t=510114401521352501520;9enddata10min=sum(events:x);11for(operate(i,j):s(i,j)=x(j)-x(i)-t(i,j);END,计算得到（只列出非零解）:VariableValueReducedCostX(2)5.0000000.000000X(3)10.000000.000000X(4)14.000000.000000X(5)10.000000.000000X(6)31.000000.000000X(7)35.000000.000000X(8)51.000000.000000S(1,4)3.0000000.000000S(2,5)1.0000000.000000S(4,6)2.0000000.000000S(5,8)6.0000000.000000S(6,7)4.0000000.000000S(7,8)1.0000000.000000,由此，可以得到所有作业的最早开工时间和最迟开工时间，如表7-9所示，方括号中第1个数字是最早开工时间，第2个数字是最迟开工时间.,从上述表可以看出，当最早开工时间与最迟开工时间相同时，对应的作业在关键路线上，因此可以画出计划网络图中的关键路线，如图7-14粗线所示.关键路线为13568.,4将关键路线看成最长路,如果将关键路线看成最长路，则可以按照求最短路的方法（将求极小改为求极大）求出关键路线.,设为变量，当作业位于关键路线上取1;否则取0.数学规划问题写成:,例7.22用最长路的方法求解例7.19.,解：按数学规划(7.40)-(7.42)写出相应的INGO程序，程序名：exam0722.lg4.,MODEL:1sets:2events/1.8/:d;3operate(events,events)/41,21,31,43,42,53,54,65,65,85,76,77,86,85/:t,x;6endsets7data:,8t=510114401521352501520;9d=1000000-1;10enddata11max=sum(operate:t*x);12for(events(i):13sum(operate(i,j):x(i,j)-sum(operate(j,i):x(j,i)14=d(i);15);END,计算得到（只列出非零解):,Objectivevalue:51.00000VariableValueReducedCostX(1,3)1.0000000.000000X(3,5)1.0000000.000000X(5,6)1.0000000.000000X(6,8)1.0000000.000000,即工期需要51天，关键路线为13568.从上述计算过程可以看到，在两种LINGO程序中，第二个程序计算在计算最短工期、关键路线均比第一个程序方便，但在某些情况下，例如，需要优化计划网络时，第一种程序的编写方法可以更好地发挥出其优点.,7.4.3关键路线与计划网络的优化,例7.23（关键路线与计划网络的优化）假设例7.19中所列的工程要求在49天内完成.为提前完成工期，有些作业需要加快进度、缩短工期，而加快进度需要额外增加费用.表7-10列出例7-19中可缩短工期的所有作业和缩短一天额外增加的费用.现在的问题是，如何安排作业才能使额外增加的总费用最少.,返回导航,例7.23所涉及的问题就是计划网络的优化问题，这时需要压缩关键路径来减少最短工期.,1.计划网络优化的数学表达式,设是事件的开始时间，是作业的计划时间,是完成作业的最短时间，是作业可能减少的时间，因此有,设是要求完成的天数，为最初事件，为最终事件,所以有而问题的总目标是使额外增加的费用最小，即目标函数为.由此得到相应的数学规划问题,2.计划网络优化的求解,例7.24用LINDO软件求解例7.23解：按照数学规划问题(7.43)-(7.47)编写LINDO程序，程序名：exam0724.ltx.,min700y13+400y14+450y25+600y56+300y57+500y58+500y68+400y78subjectto2)x2-x1=53)x3-x1+y13=104)x4-x1+y14=115)x5-x2+y25=46)x4-x3=47)x5-x3=08)x6-x4=159)x6-x5+y56=2110)x7-x5+y57=2511)x8-x5+y58=35,12)x7-x6=013)x8-x6+y68=2014)x8-x7+y78=1515)x8-x1=49endsuby132suby143suby251suby565suby573suby585suby684suby783,LINDO软件的计算结果如下：,LPOPTIMUMFOUNDATSTEP23OBJECTIVEFUNCTIONVALUE1)1200.000VARIABLEVALUEREDUCEDCOSTY131.0000000.000000Y140.000000400.000000Y250.000000450.000000Y560.000000100.000000Y570.000000100.000000Y580.000000500.000000Y681.0000000.000000Y780.000000200.000000,X25.0000000.000000X10.0000000.000000X39.0000000.000000X413.0000000.000000X59.0000000.000000X630.0000000.000000X734.0000000.000000X849.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.0000000.0000003)0.000000-700.0000004)2.0000000.0000005)0.0000000.000000,6)0.0000000.0000007)0.000000-700.0000008)2.0000000.0000009)0.000000-500.00000010)0.000000-200.00000011)5.0000000.00000012)4.0000000.00000013)0.000000-500.00000014)0.000000-200.00000015)0.000000700.000000NO.ITERATIONS=23,作业(1,3)(B)压缩一天的工期，作业(6,8)(K)压缩一天工期，这样可以在49天完工，需要多花费1200元.如果需要知道压缩工期后的关键路径，则需要稍复杂一点的计算.,例7.25用LINGO软件求解例7.23,并求出相应的关键路径、各作业的最早开工时间和最迟开工时间.解：为了得到作业的最早开工时间，仍在目标函数中加入,其他处理方法与前面相同.,写出相应的LINGO程序，程序名：exam0725.lg4.,MODEL:1sets:2events/1.8/:x;3operate(events,events)/4!ABCDE0FGHI0JK;51,21,31,43,42,53,54,65,65,85,76,77,86,86/:s,t,m,c,y;7endsets8data:9t=510114401521352501520;,10m=5884301516302201216;11c=07004000450006005003000400500;12d=49;13enddata14min=mincost+sumx;15mincost=sum(operate:c*y);16sumx=sum(events:x);17for(operate(i,j):s(i,j)=x(j)-x(i)+y(i,j)-t(i,j);18n=size(events);19x(n)-x(1)=d;20for(operate:bnd(0,y,t-m);END,计算结果得到（只列出非零解）:,VariableValueReducedCostMINCOST1200.0000.000000SUMX149.00000.000000X(2)5.0000000.000000X(3)9.0000000.000000X(4)13.000000.000000X(5)9.0000000.000000X(6)30.000000.000000X(7)34.000000.000000X(8)49.000000.000000S(1,4)2.0000000.000000,S(4,6)2.0000000.000000S(5,8)5.0000000.000000S(6,7)4.0000000.000000Y(1,3)1.0000000.000000Y(6,8)1.0000000.000000,计算结果与LINDO相同.作业(1,3)（B）减少一天,作业(6,8)(K)减少一天，最小增加费用为1200元.按照前面的方法，计算出所有作业的最早开工时间和最迟开工时间，见表7-11所示.,当最早开工时间与最迟开工时间相同时，对应的作业就在关键路线上，图7-15中的粗线表示优化后的关键路线.从图7-15可能看到，关键路线不只一条.,7.4.4完成作业期望和实现事件的概率,在例7.19中，每项作业完成的时间均看成固定的,但在实际应用中，每一作业的完成会受到一些意外因素的干扰，一般不可能是完全确定的，往往只能凭借经验过去完成类似工作需要的时间来进行估计.通常情况下，对完成一项作业可以给出三个时间上的估计值：最乐观的估计值（a），最悲观的估计值(b)和最可能的估计值（m）.,设完成作业的实际时间（是一随机变量），通常用下面的方法计算相应的数学期望与方差.,返回导航,设T为最短工期，即:,由中心极限定理，可以假设T服从正态分布，并且期望值与方差满足,设规定的工期为d,则在规定的工期内完成整个项目的概率为:,psn(x)是LINGO软件提供了标准正态分布函数（见第三章的3.3.7节），即:,例7.26已知例7.16中各项作业完成的三个估计时间，由表7-12所示.如果规定时间为52天，求在规定时间内完成全部作业的概率.进一步，如果完成全部作业的概率大于等于95%，那么工期至少需要多少天？,解：对于这个问题采用最长路的编写方法较为方便.,公式（7.48)和公式(7.49)计算出各作业的期望值与方差，再由期望时间计算出关键路线.从而由公式(7.51)和公式(7.52)得到关键路线的期望与方差的估计值，再利用分布函数,计算出完成作业的概率与完成整个项目的时间.写出相应的LINGO程序，程序名：xam0726.lg4.,MODEL:1sets:2events/1.8/:d;3operate(events,events)/4!ABCDE0FGHI0JK;,51,21,31,43,42,53,54,65,65,85,76,77,86,86/:a,m,b,et,dt,x;7endsets8data:9a=388230818261801211;10m=59114401620332501521;11b=716146501828