数学规划模型

1、课 程 设 计课 程 数学模型课程设计 题 目 应用数学规划模型求解实际数学问题 学 院 数学与统计学院 专业班级 信计13-2 学生姓名 学生学号 指导教师 2015年 7 月 5 日东北石油大学课程设计任务书课程 数学模型课程设计题目 应用数学规划模型求解实际数学问题专业 姓名 学号 主要内容、基本要求、主要参考资料等主要内容简单介绍数学规划模型基本理论及本文所用的规划模型和相关软件LINGO，并通过实例来掌握如何应用数学规划模型求解实际数学问题。并利用本文所介绍的方法来分析林区汽车修理网的布局课程设计的要求：1.独立完成建模，并提交一篇建模论文。2.论文的主要内容包括：摘要，问题的提出，

2、问题的分析，模型假设，模型设计， 模型解法与结果，模型结果的分析和检验，包括误差分析、稳定性分析等。模型的优缺点及改进方向。必要的计算机程序。3.文档格式：参照东北石油大学课程设计撰写规范和数学模型课程设计教学大纲。4.课程设计结束时参加答辩。主要参考资料： 1 唐焕文，贺明峰，数学模型(第三版)，北京：高等教育出版社，2005.3 2 杨云峰等，数学建模与数学软件，哈尔滨： 哈尔滨工程大学出版社，2012.63 陈东彦，李冬梅，王树忠，数学建模，北京：科学出版社，20074 吴建国等，数学建模案例精编，北京：中国水利水电出版社，20055 胡运权，吴中启，李树青等，运筹学，北京：清华出版社，

3、20036 焦永兰，管理运筹学，北京：中国铁道出版社，2002完成期限 2016年6月27日-7月8日 指导教师 专业负责人 2016年7月5日东北石油大学本科课程设计论文摘 要人们需要了解各种不确定现象中隐含的必然规律性，并用数学方法研究各种结果。在研究过程中需要处理大量数据，而统计学正是对社会经济数据进行定量分析的重要工具，应用统计方法来整理这些数据，就可以省去不必要的过程。本文简要介绍了了数学规划模型的概念、特点，以及LINGO软件的发展及用途。本文在求解的过程中主要借助了这个软件。必要的求解过程是利用MATLAB和LINGO来求解的。本文在详细介绍了数学规划模型的几个基本模型的过程中，

4、并且每种模型都举了实例，并且通过LINGO操作，对每种方法所举实例归纳总结了较为简便的求解方法，并且给出了具体答案。最后，本文着重的探讨了典型数学模型应用规划模型方法结合LINGO求解，在解决林区汽车修理网的布局问题中，很好的体现了规划模型方法在解决典型数学模型问题时应用的广泛性和有效性。林区的汽车往往需要定期送往不同的修理厂进行大修,不同的汽车分配方案往往需要消耗不同的修理成本. 本文主要利用图论和运筹学理论建立了一套线性规划数学模型,用于求解不同的修理厂规模的条件下最优的汽车分配方案，以及所对应的总费用，并对其进行分析评估。但为寻求最佳的修理厂规模调整方案，本文模拟实际情况中的市场机理，把

5、市场作为资源分配的主要手段，国家（此处为方案制定制者）对市场进行必要的宏观调控。在此方案下得到了相当满意的结果，这也是本文的独到之处。本模型对实际情况中汽车修理分配方案的制定有很大的指导作用.且本模型的处理思想,对市场体制下的很多类似问题都有借鉴作用.本模型对实际情况中汽车修理分配方案的制定有很大的指导作用.且本模型的处理思想，对市场体制下的很多类似问题都有借鉴作用.应用规划模型结合实际数学问题可以简化求解步骤，省去繁琐的过程。为实际问题的研究提供了较为简便的方法。 关键词：LINGO；汽车修理网布局；图论；布局规划模型 目 录第1章 基础理论11.1 数学规划模型的相关软件介绍11.2 数学

6、规划模型的基本概念21.3 本章小结3第2章 常用模型42.1 模型1目标规划模型42.2 模型2最短路和最大流模型52.3 本章小结8第3章 典型实例93.1 实例1生产安排问题93.2 实例2设备更新问题103.3 本章小结12第4章 数学模型案例134.1符号说明144.2 模型的建立和求解144.3 结果分析154.4 模型改进与模型评价154.5 本章小结15结 论16参考文献17附 录18 III第1章 基础理论1.1 数学规划模型的相关软件介绍1.1.1 LINGO相关介绍美国芝加哥大学的 Linus Schrage 教授于1980年前后开发了一套专门用于求解最优化问题的软件包，

7、后来又经过了多年的不断完善和扩充，并成立了LINDO系统公司进行商业化运作，取得了巨大成功. 在最优化软件的市场中具有绝对的优势，根据该公司网上提供的信息，位列全球财富杂志500强的企业中一半以上使用上述产品，其中位列全球财富杂志25强企业中有23家使用上述产品. 读者可以从该公司的主页上了解更多的相关信息，特别是可以下载该公司产品的演示版(DEMO)和大量应用例子。演示版和正式版的基本功能是一样的，只是试用版求解问题的规模(决策变量和约束条件的个数)受到严格限制。LINGO的前身是LINDO，LINDO只能求解线性规划和二次规划(求解二次规划时又较繁琐的程序转换)，有丰富的结果分析；后来为了

8、解决非线性规划问题，LINDO公司开发了LINGO，当前LINGO的版本是10.0，最近一次更新是2006年12月。LINGO(包括LINDO)的最大特色在于可以允许决策变量是整数(甚至0-1整数)，而且运行速度快。 LINGO实际上还是最优化问题的一种建模语言，包括许多常用的数学函数供使用者调用，并可以接受其他数据文件 ( 如 文本文件.txt，电子表格文件.xml, 数据库文件，)，既是对优化方面的专业知识了解不多的用户，也能方便的建立和输入、有效的求解和分析实际中遇到的大规模优化问题，并通常能够快速得到复杂优化问题的高质量的解。 此外，LINGO还提供了与其他开发工具(如C+、JAVA等

9、语言)的接口软件LINDO API，因此使LINGO还能方便的融入到用户应用软件的开发中去；最后LINGO提供了与电子表格软件(如EXCEL等)的接口，能够直接集成到电子表格软件中使用。 由于自LINGO9开始LINGO完全地包含了LINDO的功能，所以LINDO公司已经将LINDO从其产品目录中删去，这意味着以后不会再有LINDO软件的新版本了。1.1.2 LINGO程序模版 LINGO的程序结构1.集合段 以sets开始、endsets结束，作用在于定义必要的集合变量及其元素(含义类似于数组的下标)和属性(含义类似于数组)；2.数据段 以data开始、enddata结束，作用在于对集合的属

10、性(数组)输入已知数据；3.初始段 以init开始、endinit结束，作用在于对集合的属性(数组)定义初值；4.计算段 以calc开始、endcalc结束，作用在于对一些原始数据进行计算处理；5.目标与约束段 无开始和结束标志，作用在于定义目标函数和约束条件.1.1.3 LINGO常用命令 一、运算符及优先级1、算术运算符(5个)： + (加法), (减法或负号), * (乘法), / (除法), (乘方)2、逻辑运算符(9个)： (1) #and#(与)，#or#(或)，#not#(非)； (2) #eq#(等于), #ne#(不等于), #gt#(大于), #lt#(小于), #ge#(

11、大于等于)，#le#(小于等于).2、 数学函数 abs(), cos(), exp(), floor(), mod(x,y), pow(x,y), sign(), sin(), smax(), smin(), sqr(), sqrt(), tan(), lgm(), log().3、 集合函数1、集合循环函数 for(), max(), min(), prod, sum()2、集合操作函数 in(), index(), wrap(), size四、变量定界函数bnd(l,x,u), bin(), free(), gin()1.2 数学规划模型的基本概念1.2.1 数学规划模型的概念 数学规划

12、理论是运筹学这门学科的主要内容，而运筹学的基本特点是：考虑系统的整体优化、多学科的配合以及模型方法的应用。细化为如下步骤：1、分析与表述问题。2、建立数学模型。3、求解数学模型。4、对模型和由模型导出的解进行检验。5、建立起对解的有效控制。6、方案的实施。定义：实际问题均为函数问题，对实际问题的优化就是求描述此问题的函数f(x)的极值，其中变量x来自实际问题，他们必然满足一些条件，这就是数学规划问题。数学规划的标准形式为： x决策变量 f(x)目标函数 gi(x)£0约束条件 所以，数学规划本质上是(多元)函数条件极值 1.2.2数学规划模型的特点根据目标函数和约束条件的形式，数学规

13、划可以分为 (1)线性规划模型: f(x),gi(x)均为1次多项式 (2)二次规划模型: f(x)为2次,gi(x)均为1次多项式 (3)整数规划模型: 决策变量x的取值全为整数 (4)0-1规划模型 : 决策变量x的取值全为0或1 (5)其他优化模型: 其他情形1.3 本章小结 本章主要介绍了数学规划模型的概念、特点及作用等基础信息。并且介绍了将要用到的LINGO的特点，以及在实际生活中它们的用处。本文主要用到LINGO来操作解决一些实例问题4第2章 常用模型 2.1 模型1目标规划模型2.1.1目标规划的基本概念 目标规划是为了克服线性规划的局限性而引入的，与线性规划相比，目标规划采用了

14、如下手段： 1、设置偏差变量； 2、统一处理目标与约束； 3、目标的优先级与权系数。2.1.2目标规划的一般模型 设XJ(J=1.N)是目标规划的决策变量，共有M个约束是刚性的(可能是等式，也可能是不等式)；还有L个柔性约束，偏差变量为D+,D-(I=1.L)；设有Q个优先级，分别为P1,P2,PQ，在同一优先级PK下，有不同的权重，分别记为： 这样目标规划的一般数学模型为： 2.1.3求解目标规划的序贯式算法序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序，将目标规划分解成一系列的单目标规划问题，然后再依次求解。2.2 模型2最短路和最大流模型2.2.1 最短路模型 例：

15、管道铺设问题见下图，图中点表示城市，现有A,B1,B2, C1,C2,C3,D共7个城市。点与点之间的连线表示城市间有道路相连，连线上的数字表示道路的长度。现计划从城市A到城市D铺设一条天然气管道，请设计出最小价格管道铺设方案。问题分析 此问题本质上是求从城市A到城市D的一条最短路。为了书写上的方便，我们将7个城市编号如下： A,B1,B2,C1,C2,C3,D=1,2,3,4,5,6,7。 定义邻接矩阵AM=(aij)n*n，其元素为每两个城市之间的距离记为则矩阵W=(wij)n*n称为赋权矩阵。下面i,j之间的道路记为(i,j)，定义变量则xij组成如下一个上三角矩阵求最短路等价于求上述上

16、三角阵中那些为1，那些为0模型建立 决策变量即是xij，已知量即是赋权矩阵。易知目标函数为： 由决策变量矩阵，可得决策变量应满足的约束条件为：这样最短路的数学模型就建立起来了，是 0-1 线性规划模型。 2.2.2最大流模型最大流问题涉及图论中的网络及相关概念，下面给出相关知识。一、网络与最大流的基本概念 定义1 图(Graph)：图是一些顶点(Vertex)和连接这些定点的边(Edge)的集合，记为G(V,E)。譬如，一个地区的交通图，顶点集V是各城市和乡镇，而边集E则是连接这些城市或乡镇的路(铁路、公路、乡村小路等) ；一栋办公楼里的机构示意图，顶点集V是各机构的办公室，而边集E则是连接各

17、办公室的通道；一个城市的(天然气、自来水)管道分布图； 若顶点集V是有限集，则称图G(V,E)为有限图。 我们只讨论有限图。 若图G(V,E)中所有的边都是没有方向的，则称图G(V,E)为无向图。否则称为有向图。有向图中的边称为弧(Arc)，以u为起点v为终点的弧记为(u,v)。有向图另记为G(V,A)。有向图的例子：自来水输送管道图，天然气输送管道图，石油输送管道图， 定义2 网络(Network)：设G(V,A)为有向图，如果在V中有两个不同的顶点子集S和T，且在弧集A上定义了一个从弧集A到非负实数集R>=0上函数c,则称G(V,A)为一个网络，简记为N。 S中的顶点称为源(sour

18、ce)，T中的顶点称为汇(Sink)，既非源又非汇的顶点称为中间点。而c则称为网络N的容量函数(capacity function)；设a<A，则称c(a)为弧a上的容量，弧(u,v)上的容量为c(u,v)。 对于网络N中的弧(u,v) ，除了有容量外，还有一个流量(flow) ，记为f(u,v) 。显然， 0<=f(u,v)<=c(u,v)称满足此不等式的网络N是相容的。 对于所有中间点v，流入的总量=流出的总量：（1）：网络N的流量值V(f)定义为从源s流出的总流量，即（2）：易知N的流量值V(f)也为流入汇t的总流量，即（3）：设V1和V2为V的子集，用(V1,V2)记

19、起点在V1中、终点在V2中的弧的集合， f(V1,V2)记(V1,V2)中弧的流量的总和，即特别地，令V1=v,V2=V，结合(1),(2),(3)三式，得到（4）：满足(4)式的网络N是守恒的。定义3 如果流 f 同时满足相容性和守恒性，则称流 f 是可行的。若存在可行流 f*，使得对所有的可行流 f，均有V(f*)>= V(f ),则称 f* 为最大流(maximum flow).最大流问题的数学模型通过上述推导得到最大流的数学模型为 max V(f)最大流问题的求解程序最大流问题的Lingo求解程序为：Model: sets: vertex/1.200/; arcs(vertex,

20、vertex)/1,2 1,3 2,3 2,4 3,5 4,3 4,6 5,4 5,6/:c,f; endsets data: c=8 7 5 9 9 2 5 6 10; enddata obj max =flow; for(vertex(i)|i #ne# 1 #and# i#ne# size(vertex): sum(arcs(i,j):f(i,j)-sum(arcs(i,j):f(j,i)=0); sum(arcs(i,j)|i#eq#1:f(i,j)=flow; for(arcs:bnd(0,f,c);End2.3 本章小结 本章主要介绍了数学规划模型中的目标规划模型、最短路和最大流模

21、型，并且通过一个例题解释了最短路问题模型。了将了这些模型的基本的特点，以及在实际生活中它们的用处。本章主要用到模型和LINGO来操作解决一些实例问题11第3章 典型实例3.1 实例1生产安排问题 某企业生产甲乙两种产品，需要用到A、B、C三种设备，关于产品的盈利与使用设备的工时及限制如下表：甲乙设备能力(h)A (h/件)2212B (h/件)4016C (h/件)0515盈利200300问：在下述生产要求下该企业应如何安排生产使得在计划期内总利润最大？生产要求：（1）力求使利润指标不低于1500元；（2)考虑到市场需求，甲乙产量尽量保持1:2；（3）设备A为贵重物品，严格禁止超时使用；(4）

22、设备C可以适当加班，但要控制；（5）设备B既要充分使用又要尽可能不加班；（6）在重要性上B是C的3倍。问题分析与建模 每一个生产要求都是目标，所以所求问题是目标规划问题。在生产要求中设备A是刚性约束，其余是柔性约束首先，我们需拟定各目标的优先级及权系数： P1 对企业而言，最重要的指标是利润，因此，将利润的优先级列为第一级； P2 产品是利润的载体，所以将甲乙产量保持1:2列为第二级； P3 设备是产品的来源，所以对设备B,C的工时要求列为第三集；在此级中，B,C的重要性不同，表明B,C的权系数不一样。然后，给出决策变量及变差变量： x1,x2分别为甲乙的产量； d1,d2,d3,d4分别为利

23、润、产品比例、B的工时、C的工时的偏差变量。则目标规划为：模型求解程序 用序贯式算法求解目标规划的Lingo通用程序.3.2 实例2设备更新问题张先生打算购买一辆新轿车，新轿车售价是12万元人民币。轿车购买后，每年的各种保险费、养护费等费用见表1。如果在5年之内，张先生将轿车售出，并再购买新车。5年之内的二手车销售价见表2。请帮助张先生设计一种购买轿车的方案，使5年内用车的总费用最少。 表1 轿车的维护费 车龄/年01234费用/万元245912 表2 二手车的售价车龄/年12345售价/万元76210 问题分析 设备更新问题是动态规划的一类问题，此处借助于最短路方法解决设备更新问题。用6个点

24、(1,2,3,4,5,6)表示各年的开始，各点之间的边的长度(权)表示从左端点开始年至右端点结束年所花的费用，这样构成购车的小费的网络图如后：记 cij = 第i年开始到第j-1年结束因车的总费用 = 第i年开始到第j-1年结束轿车的维护费用 + 第i年开始时的购车费用 - 第j年开始时的 二手车销售收入。我们首先须将cij求出来，这可以在程序中自动实现模型建立 (1) 赋权矩阵为C=(cij)5*5，为一上三角阵(有向最短路问题均为上三角阵)；(2) 决策变量：由前面分析我们可建立如下设备更新的最短路模型：用Lingo求解，结果如下(程序)：Global optimal solution f

25、ound. Objective value: 31.00000 Total solver iterations: 0 Model Title: 设备更新问题 Variable Value Reduced Cost X( 1, 2) 1.000000 0.000000 X( 2, 4) 1.000000 0.000000 X( 4, 6) 1.000000 0.000000 上述结果翻译为实际意思，就是：第1年初买新车，第2年初卖掉，再购买新车，到第4年初卖掉，在购买新车使用到第5年末，总费用最小，为31万元。3.3 本章小结 本章主要介绍了数学规划模型在实践中的实例生产模型和设备更新问题。并且

26、介绍了这些问题的求解过程。通过这俩个实例可以让我们更好的理解与接受规划模型在日常生活中的简单应用。第4章 数学模型案例规划模型赛题解析林区汽车修理网的布局在林业生产中，汽车是主要的运输工具。为了确保汽车在使用中有良好的技术状态和较长的使用寿命，需定期对汽车进行保养与维修，大修是重要的一个环节。但目前各林业局都设有大修厂，由于厂点多、规模小、技术落后等原因，导致了大修成本高、质量低等问题。现需对林区的大修厂作出合理布局，使林区整体经济效益最优。 表1 给出了某林区某年各大修厂的产量及成本。 表2 给出了某林区各大修厂的现有生产规模和车辆数。图1是林区18个林业局的分布图： 各线段上的数字是两林业

27、局的距离（单位：公里；线的长短和真实的距离不成比例，括号“( )”里的数字是林业局编号）。 当把一个林业局的汽车送到另一个林业局大修时，每辆车的运送费（双程）： 公路每公里6元，铁路每公里5元。假设：(1) 每辆汽车一年大修一次；(2) 不考虑关闭、扩建大修厂的费用。 分别对以下几种情况求出该林区汽车大修方案，作出大修厂的布局规划。情形1 分协作区大修；情形2 不分协作区大修(整个林区)；情形3 拟定对林业局(2)、(5)、(8)、(14)、(16)所属大修厂进行扩建，使生产规模分别增加80辆；情形4 集中到情形3中拟定的两个厂点大修是否更好？给出是那两个厂点和生产规模。你还有更好的建议吗？

28、表1 各林业局汽修厂的产量及单位生产成本 林业局123456789101112131415161718产量（辆）52520102015401907545254040130451105060单位成本（元/辆）570048504300550064006500550045005800600061007200560047005600500053005100 表2 林业局所属林区、车辆拥有数及其汽修厂的生产规模协作区一区二区三区四区五区林业局123456789101112131415161718生产规模（辆）3040405012060502009070607080180501104060汽车数（辆）25

29、35304580554018070605060601504010035554.1符号说明变量符号第i个大修厂i第j个大修厂j从第i个大修厂运送到第j个大修厂的汽车数Xij构造二次函数的待定系数a，b，c第k区所用的总费用P（k）从第i个大修厂运送到第j个大修厂的路费Si j第i个林业局现有的汽车数Ai第i个林业局现有生产规模 Di4.2 模型的建立和求解模型假设 问题中已经给出了两条基本假设：1、每辆汽车一年大修一次；2、不考虑关闭、扩建大修厂的费用。为了讨论问题的方便，我们再增加如下假设：3、每辆汽车的大修时间是分散的，没有排队、等待修理的情况发生；4、不考虑待修汽车在运输途中公路、铁路转运

30、所发生的时间和费用；5、修车总费用由运输费用和修理成本两部分组成； 模型建立、计算及结果首先，计算各林业局之间的运输费用：1、公路运输费用的计算程序及结果.2、铁路运输费用的计算程序及结果.3、混合交通运输费用的计算程序及结果.4、单位维修成本的计算程序及结果.然后，所有问题都是0-1规划，比较容易建立，此处我们给出各问题的Lingo求解程序：1、分协作区大修维修方案的计算程序及结果.2、不分协作区大修维修方案的计算程序及结果.3、第3问维修方案的计算程序及结果.4、第4问维修方案的计算程序及结果.5、综合结果.4.3 结果分析 任选两个进行扩建比较总成本，做少的为优4.4 模型改进与模型评价

31、 本模型的不足之处主要在于忽略了扩建修理厂的费用，因此所得方案在实际实施时所产生的效应可能与模型的预测有较大的出入。本模型的最大特色在于通过模拟现实中的市场机制，放宽管理者对企业的过多干预，收到了非常可观的经济效益。 我们认为,管理者的规划固然重要。但是有时过多的人为干预又会减弱市场的作用。同时市场有很大的弊端，需要管理者宏观上调节。本模型的思想就是先模拟市场自由竞争的过程，分析其竞争结果,在对结果进行分析,提出干预措施,从而提出既能充分利用市场功能又能克服市场弊端的合适方案。这种处理问题,制定方案的思想应该是具有普遍意义的，尤其是在现在有中国特色的社会主义市场经济体系下。因此本文的思想不仅可

32、以推广到其它类似的供需分配问题，甚至可以推广到所有以市场为背景的管理规划问题中。4.5 本章小结 本章研究的是林区汽车修理网的布局模型，应用本文中上面所说的方法，利用LINGO软件进行求结果。23结 论随着人类的社会实践，规划模型知识和思想在越来越多的领域显示了它的应用性和实用性。人们需要了解各种不确定现象中隐含的必然规律性，并用数学方法研究各种结果。然而其大量数据的处理分析需要借助一些具有强大功能的软件，比如SPSS，MATLAB和LINGO等。利用这些软件就可以很快得到问题的结果。本文共四部分。第一部分简要介绍了数学规划模型的概念、特点，以及LINGO软件的发展及用途。本文在求解的过程中主

33、要借助了这个软件。第二部分和第三部分详细介绍了规划模型的一些基本模型，每一个模型都列举的实际数学问题，并且每个问题都给出了详细的求解过程及软件操作的程序。第四部分是将所研究的规划模型应用到数学建模竞赛试题当中，建立数学模型并且应用LINGO建立模型，通过LINGO得到了详细的结果分析，并通过LINGO求解出最终的结果。通过求解实际数学问题的过程，可以了解到，数学规划模型结合相应的软件，可以为求解实际问题提供相应的简便的过程。本模型对实际情况中汽车修理分配方案的制定有很大的指导作用.且本模型的处理思想，对市场体制下的很多类似问题都有借鉴作用.参考文献1 贾俊平，统计学（第三版），北京，中国人名大

34、学出版社，20082 唐焕文，贺明峰，数学模型(第三版)，北京：高等教育出版社，2005.3 3 杨云峰等，数学建模与数学软件，哈尔滨： 哈尔滨工程大学出版社，2012.64 陈东彦，李冬梅，王树忠，数学建模，北京：科学出版社，20075 唐焕文，秦学志，实用最优化方法（第三版），大连，大连理工大学出版社，20046 胡运权，吴中启，李树青等，运筹学，北京：清华出版社，20037薛毅，耿美英，运筹学与实验，北京：电子工业出版社，2008.98 姜启源，谢金星，叶俊，数学模型（第三版），北京：高等教育出版社，2003.89 焦永兰，管理运筹学，北京：中国铁道出版社，200210杨瑞，线性规划的网

35、络流量流向控制技术，电子商务，201511蓝洋，基于0-1规划的规则中文文件碎片自动拼接技术，计算机系统应用，201512倪志伟，面向数据中心虚拟机部署的智能优化策略，模式识别与人工智能，201513刘心，经济优化分析方法的研究及扩展，东北财经大学，200914杨勇，智能化综合评价理论与方法研究，浙江工商大学，201415陈国华，模糊投资组合优化研究，湖南大学，200916管屏，求解0-1规划的生长竞争蚁群算法，201217王远干，多目标线性规划模型的模糊数学解法，软件学院学报，200818王晓，一种新的席位公平分配方法，北京师范大学学报，201117附 录 %floyd1.m文件 %d是求得

36、的任意两点间的最短距离（即运费最少的路径） %(vx,vy)从0开始编号的任意两个节点 %r1表示从vi到vj点的最短路中经过的结点（大修厂）的编号 %r1从0开始编号 function d,r1=floyd1(vx,vy,a) d=a; vx=vx+1; vy=vy+1; global r; r=a; n=size(a,1); for i=1:n for j=1:n d(i,j)=a(i,j); r(i,j)=j; k=1; end end for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j)<d(i,j) d(i,j)=d(i,k)+d(k,j

37、); r(i,j)=k; end end end end r1=r+1; fun3(vx,vy); disp('以下两个矩阵分别为：任意两点间的最短路中经过的结点（大修厂）的编号（为空则是不经过其他结点） 和 任意两点间的最少运费') %fun3.m文件 function fun3(vx,vy) global r a t=r(vx,vy); if vy=t Returnelse fun3(vx,t); disp(t-1); fun3(t,vy); end 一区 1 2 3 1 0 180 420 2 180

38、0 240 3 420 240 0 通过excel与matlab的接口求的图中所有任意两点间最少运费 1 2 3 1 0 180 420 2 180 0 240 3 420 240 0 LinGO求解结果： Local optimal solution found. Objective value: 510052.1 Objective bound: 510052.1 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 10 Variable Value A -7.290600 B 5827.874 C 1928.726 X11 20.00000 X21 0.000000 X31 0.000000 X12 5.000000 X22 35.00000 X32 0.000000 X13 0.000000 X23 0.000000 X33 30.00000 Row Slack or Surplus 1 510052.1 2 0.000000 3 0.000000 4 0.000000 5 20.00000 6 5.000000 7 0.000000 8 0.000000 9 35.00000 10 0.000000 11 0.000000 12 0.000