第-7-章--图论与网络模型

优化建模欢迎各位同学学习第七章内容导航概述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软件求解运输问题.但为便于后面的叙述，先给出图论中有关图的部分定义.mn图7-1:个产地,个销售地运输问题的图形mn优化建模1.图的基本定义从直观上看,所谓图是由点和边组成的图形,如图7-1所示.下面我们给出图的定义.优化建模注：通常有向图的边称为弧，由弧构成的集记为因此，有向图记为,而无向图记为.为方便起见，在后面的论述中，有时也用表示有向图.在无向图中,每条至多有一条边的图称为简单图(SimpleGraph).若每一对不同的顶点都有一条边相连的简单图称为完全图(CompleteGraph).若一个图中的顶点集可以分解为两个子集和,使得任何一条边都有一个端点在中,另一个端点在中,这种图称为二部图或偶图(BipartiteGraph).运输问题所构成的图7-1是偶图.,A),(EVG),(AVG),(EVG1V2V1V2V1V优化建模2.运输问题的数学表达式.11minjijijxc第个产地的运出量应小于或等于该地的生产量，即：i.1njiijax第个销地的运入量应等于该地的需求量，即：j.1mijijbx优化建模因此，运输问题的数学表达式为:称具有形如式的线性规划问题为运输问题.)4(~)1(优化建模3.运输问题的求解过程为了便于讨论，以一个运输问题实例的求解过程来介绍如何用LINDO或LINGO软件求解运输问题模型.例7.2(继例7.1)设即为有3个产地和4个销地的运输问题，其产量、销量及单位运费如表7-1所示.试求总运费最少的运输方案，以及总运费.4,3nm优化建模解：从前面的分析来看，运输问题属于线性规划问题，因此，不论是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.lg4MODEL:1]!3Warehouse,4CustomerTransportationProblem;2]sets:3]Warehouse/1..3/:a;4]Customer/1..4/:b;优化建模5]Routes(Warehouse,Customer):c,x;6]endsets7]!Herearetheparameters;8]data:9]a=30,25,2110]b=15,17,22,12;11]c=6,2,6,7,12]4,9,5,3,13]8,8,1,5;14]enddata15]!Theobjective;16][OBJ]min=@sum(Routes:c*x);优化建模17]!Thesupplyconstraints;18]@for(Warehouse(i):[SUP]19]@sum(Customer(j):x(i,j))=a(i));20]!Thedemandconstraints;21]@for(Customer(j):[DEM]22]@sum(Warehouse(i):x(i,j))=b(j));END在上述程序中，第16]表示运输问题中目标函数(7.1).第18]19]行表示约束条件(7.2),第21]22]行表示约束条件(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规划问题.ijc返回导航优化建模1.指派问题的数学表达式设变量为,当第个人作第项工作时，,否则.因此，相应的线性规划问题为1111min1,1,2,,(1,1,2,,,()01,1,2,,.mnijijijnijjnijiijcxxinxjnxjn　　　；(5)s.t.　　　　，每个人做一项工作)　(6)　　　　　　每项工作有一个人去做　(7)　　　　或　　　　　　　　　　　　(　8)ijxij1ijx0ijx优化建模2.指派问题的求解过程分别用LINDO软件和LINGO软件求解指派问题，并对两种软件的求解方法与各自的优缺点进行比较.例7.4（继例7.3）考虑例7.3中的情况,即6个人做6项工作的最优指派问题，其收益矩阵如表7-2所示.6n优化建模!Assignmentmodel!Maximizevalveofassignmentsmax20x11+15x12+16x13+5x14+4x15+7x16+17x21+15x22+33x23+12x24+8x25+6x26+9x31+12x32+18x33+16x34+30x35+13x36+12x41+8x42+11x43+27x44+19x45+14x46-99x51+7x52+10x53+21x54+10x55+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,这是因为某人无法做某项工作可以某人做该项工作的收益是,在计算中通常取一个