最短路径问题的0-1规划模型,lingo直接求解

Lingo应用——旅游路线最短问题题目:从北京乘飞机到东京、纽约、墨西哥城、伦敦、巴黎五个城市做旅游，每个城市去且仅去一次，再回到东京，问如何安排旅游线路，使总旅程最短。

各城市之间的航线距离如下表：运用lingo软件求解模型建立前问题分析：1．这是一个求路线最短的问题，题目给出了两两城市之间的距离，而在最短路线中,这些城市有的两个城市是直接相连接的（即紧接着先后到达的关系），有些城市之间就可能没有这种关系，所以给出的两两城市距离中有些在最后的最短路线距离计算中使用到了，有些则没有用。

这是一个0-1规划的问题，也是一个线性规划的问题。

2．由于每个城市去且仅去一次，最终肯定是形成一个圈的结构，这就导致了这六个城市其中有的两个城市是直接相连的，另外也有两个城市是不连接的。

这就可以考虑设0-1变量，如果两个城市紧接着去旅游的则为1，否则为0。

就如同下图实线代表两个城市相连为1,虚线代表没有相连为03． 因为每个城市只去一次，所以其中任何一个城市的必有且仅有一条进入路线和一条出去的路线。

求解：为了方便解题，给上面六个城市进行编号，如下表（因为北京是起点， 将其标为1）假设：设变量x ij 。

如果x ij =1,则表示城市i 与城市j 直接相连（即先后紧接到达关系），否则若x ij =0，则表示城市i 与城市j 不相连。

特别说明：x ij 和x ji 是同一变量，都表示表示城市i 与城市j 是否有相连的关系。

这里取其中x ij (I<j)的变量。

模型建立：由于这是一个最短路线的问题，且变量已经设好。

目标函数：min z=51*x12+78*x13+68*x14+51*x15+13*x16+56*x23+35*x24+21*x25+60*x26+21*x34+57*x35+70*x36+36*x45+68*x46+61*x56约束条件：1. 上面目标函数中的变量是表示两个城市是否直接相连接的关系，且最短路线是可以形成圈的，如下图实线代表两个城市相连为1,虚线代表没有相连为0如上图城市a和城市b有直接相连接的关系，所以之间变量为1，而城市a 与城市e则没有直接相连接的关系，之间变量为0。

一、Lingo 能做什么——Lingo 的简单模型1、简单线性规划求解（目标函数）2134maxx x z += s.t.（约束条件）⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤+0,781022122121x x x x x x x（决策变量） x 1,x 2手工计算的方法注：Lingo 中“<”代表“<=”，“>”代表“>=”，Lingo 中默认的变量都是大于等于0的，不用显式给出。

求解结果：z=26，x1=2，x2=62、整数规划求解219040Max x x z += ⎪⎩⎪⎨⎧≥≤+≤+0,702075679212121x x x x x xLingo 程序求解3、0-1规划求解Max 432215.18.04.0x x x x f +++=10106234321≤+++x x x x10,,,4321或=x x x x12344、非线性规划求解||4||3||2||min 4321x x x x z +−−=s.t. ⎪⎪⎩⎪⎪⎨⎧−=+−−=−+−=+−−2132130432143214321x x x x x x x x x x x x12345、背包问题一个旅行者的背包最多只能装 6kg 物品，现有4 件物品的重量和价值分别为 2 kg ，3 kg ，3 kg ，4 kg ；1 元，1.2元，0.9元，1.1元。

问应怎样携带那些物品使得携带物品的价值最大?建模：记j x 为旅行者携带第j 件物品的件数, 取值只能为 0 或 1。

求目标函数43211.19.02.1x x x x f +++=在约束条件643324321≤+++x x x x 下的最大值.用Lingo 软件求解0-1规划计算结果6、指派问题有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表： 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？ 设：第i 个工人做第j 项工作用时ij t ，标志变量ij f 定义如下：变量名 取值⎩⎨⎧=其他件工作个工人去做第指派第01j i f ijmin∑∑==×4141i j ij ijt fs.t. 141=∑=i ijf()4,3,2,1=j 每份工作都有一人做∑==411j ijf()4,3,2,1=i 每人都只做一项工作（1） 集合定义部分（从“SETS ：”到“ENDSET ”）：定义集合及其属性，语句“work/A,B,C,D/”其结果正是定义了4个集合元素，没有定义变量名。

摘要：本次课题主要研究的是怎样选择一条最佳的旅游路线的问题。

针对这个问题，我主要考虑的是旅游途中所花费的时间和旅游费用。

首先我通过上网以及翻阅相关的书籍查阅各景点之间的距离、门票费用和最佳参观时间，据此将景点图简化成赋权无向图。

然后利用floyd算法得到每2个景点间的最短路径。

问题一给定了时间约束，要求花最少的钱游尽可能多的地方。

据此，我们以花费最少为目标，以时间限制及线路要求为约束，建立0-1规划模型，利用lingo软件对模型求解。

对结果进行综合分析，最后我们向王先生夫妇推荐景点数为16的路线：乌鲁木齐-达坂城-哈密-库尔勒-楼兰-阿克苏-千佛洞-天鹅湖-伊犁-博乐-石河子-克拉玛依-阿勒泰-昌吉-天山天池-乌鲁木齐。

平均每个景点花费为73.4元，除了吃饭以外，这对夫妇总共花费估计为4102元。

问题二要提出2条路线游完所有景点，据此，我们首先将所有景点按南北疆分为2组。

这两条路线要求交通费用最少，即总路程最少，我们以总行驶路程为目标，以相应的条件为约束，建立0-1线性规划模型。

利用lingo求解得到每组路线所需最短时间，并求得其均衡度。

然后对其进行调整，找到均衡度最好的一种分组。

我们为王先生夫妇推荐的第一个月的路线为：乌鲁木齐-昌吉-博乐-石河子-克拉玛依-阿勒泰-额尔齐斯河-喀纳斯湖-天山天池-哈密-吐鲁番-达坂城-乌鲁木齐，交通费用为740元。

第二个月的路线为乌鲁木齐--库尔勒--楼兰--尼雅遗址--和田--喀什--阿克苏--千佛寺--伊犁--天鹅湖--乌鲁木齐，交通费用为820元。

问题三与问题二相似，我们根据各景点之间的最短路径画出以乌鲁木齐为树根的树形图，然后按分类原则分为三组。

将模型二中的目标函数换为考察时间最小得到模型三，分别用lingo求解得到每组最佳路线及时间。

求其均衡度，然后对其进行调整。

最后，我们对该考察团设计了三条考察路线。

路线一：乌鲁木齐-博乐-伊犁-昌吉-天山天池-吐鲁番-达坂城 -乌鲁木齐，考察时间为47天。

LINDO软件求线性规划、整数规划和0-1规划LINDO软件简介/求解线性规划问题LINDO是⼀种专门⽤于求解数学规划问题的软件包。

由于LINDO执⾏速度很快、易于⽅便输⼊、求解和分析数学规划问题。

因此在数学、科研和⼯业界得到⼴泛应⽤。

LINDO/GO主要⽤于解线性规划、⾮线性规划、⼆次规划和整数规划等问题。

也可以⽤于⼀些⾮线性和线性⽅程组的求解以及代数⽅程求根等。

LINDO/GO中包含了⼀种建模语⾔和许多常⽤的数学函数（包括⼤量概论函数），可供使⽤者建⽴规划问题时调⽤。

⼀般⽤LINDO（Linear Interactive and Discrete Optimizer）解决线性规划（LP—Linear Programming）。

整数规划（IP—Integer Programming）问题。

其中LINDO 6 .1 学⽣版⾄多可求解多达300个变量和150个约束的规划问题。

其正式版（标准版）则可求解的变量和约束在1量级以上。

LINGO则⽤于求解⾮线性规划（NLP—NON—LINEAR PROGRAMMING）和⼆次规则（QP—QUARATIC PROGRAMING）其中LINGO ６.0学⽣版最多可版最多达300个变量和150个约束的规则问题，其标准版的求解能⼒亦在10^4量级以上。

虽然LINDO和LINGO 不能直接求解⽬标规划问题,但⽤序贯式算法可分解成⼀个个LINDO和LINGO能解决的规划问题。

要学好⽤这两个软件最好的办法就是学习他们⾃带的HELP⽂件。

下⾯拟举数例以说明这两个软件的最基本⽤法。

（例⼦均选⾃张莹《运筹学基础》）例１.（选⾃《运筹学基础》Ｐ５４.汽油混合问题，线性规划问题）⼀种汽油的特性可⽤两个指标描述：其点⽕性⽤“⾟烷数”描述，其挥发性⽤“蒸汽压⼒”描述。

某炼油⼚有四种标准汽油，设其标号分别为１，２，３，４，其特性及库存量列于下表１中，将上述标准汽油适量混合，可得两种飞机汽油，某标号为１，２，这两种飞机汽油的性能指标及产量需求列于表２中。

车辆派送问题最短行驶路线的建模分析摘要车辆派送选取最短的行驶路线是商业公司经常要考虑的问题，一个最优的派送方案可以使公司的费用降到最低，从而使公司的利益最大化。

通过建立最优化规划模型来解决最优的车辆行驶路径问题，采用0-1整数规划简化模型，通过Lingo软件进行求解，有效解决了问题2中的具体算例，同时也给出了较普遍的求解这一类车辆行驶路径即问题3当客户i的货物需求量q i为随机参数时的数学模型及处理方法。

对于问题1，我们建立的规划模型是在客户的需求量在车辆运送的承载范围之内，我们使用0-1整数规划来解决车辆是否从客户i行驶到客户j这个问题，有效的简化了模型。

然后在考虑中心仓库的车辆数约束、车辆的载物量约束、时间约束、客户需求量约束的约束情况下，设立了行驶路径最短的目标函数。

并在问题1的具体算例中，利用Lingo软件求得了最优的规划方案：车辆最少数位3辆，行驶路径最短为910公里，路线分别为：0-3-1-2-0，0-8-5-7-0，0-6-4-0。

考虑当客户i的货物需求量q i为随机参数的情况下，客户的需求量可能大于车辆的载物量，此时每个客户可能被服务不止一次，我们通过调整约束条件，建立了车辆行驶最短路径的目标函数，使这一类的问题求解有一个更适用的模型。

关键词：车辆行径问题；0-1整数规划；目标规划模型；LINGO软件一、问题重述随着社会经济的日益发达和商业活动的日益频繁，合理的货物派送路径成了商业公司密切关注的问题。

车辆路径问题（VRP ）是指给定一个或多个中心仓库、一个车辆集合和一个客户集合，每个客户有自己不同的货物需求，由车辆集合进行派送，要求在满足一定约束条件的情况下，组织合理的行车路线，达到路径最短、成本最少、或时间最短等目的。

一个商品基地，拥有一定数量容量为Q 的车辆，负责对N 个客户进行货物派送工作，客户i 的货物需求量为q i ，且i q Q <，车辆必须在一定的时间范围[],i i a b 内到达，早于i a 到达将产生等待损失，迟于i b 到达将处以一定的惩罚，给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。

LINGO语言与0-1混合整数规划选址模型的再结合LINGO语言与0-1混合整数规划选址模型的再结合随着信息技术的不断发展，计算机在解决复杂问题方面的作用越来越重要。

特别是在生产、物流、规划等领域，计算机的运用已经成为提高效率和优化资源配置的关键。

在这一背景下，LINGO语言和0-1混合整数规划选址模型的结合应运而生，旨在通过LINGO语言的优势和0-1混合整数规划选址模型的精确性，更好地解决选址问题。

LINGO语言是一种基于高层次的数学和逻辑编程语言，它具有强大的求解能力和灵活的编程特性。

LINGO语言可以将复杂的数学模型转化为计算机可以理解和求解的形式，大大简化了数学模型的表达和求解过程。

同时，LINGO语言还提供了丰富的算法库，可以用于求解各种数学模型。

这些特点使得LINGO语言成为了解决复杂问题的理想工具。

0-1混合整数规划选址模型是一种常用的选址问题求解方法。

选址问题是指在一定的约束条件下，确定一些点或区域中的最佳（或次佳）位置。

该模型涉及在给定的候选位置中选择一些位置以最大化（或最小化）某个目标函数。

而0-1混合整数规划则是在候选位置是否被选择的问题上引入了0-1变量，使得问题更接近实际情况。

通过将选址问题转化为0-1混合整数规划问题，并利用LINGO语言的求解能力进行求解，能够得到选址问题的最优解。

具体而言，LINGO语言与0-1混合整数规划选址模型的再结合可分为以下几个步骤。

首先，需要确定选址问题的目标函数和约束条件。

目标函数可以是最大化产出、最小化成本、最小化距离等，而约束条件可以包括资源限制、市场需求等。

然后，将选址问题转化为数学模型并使用LINGO语言进行表达。

LINGO语言的丰富函数库可以用来处理各类约束和目标函数。

接下来，利用LINGO语言提供的求解器对模型进行求解。

LINGO的求解器可以采用多种算法，如整数规划、线性规划等，从而得到选址问题的最优解。

最后，对求解结果进行分析和优化。

解：对于无向图的最短路问题，可以这样理解，从点到点和点到点的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种方法编写LINGO程序相当于边(弧)增加了一倍.这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序.MODEL:1] sets:2] cities/1..11/;3] roads(cities, cities): p, w, x;4] endsets5] data:6] p = 0 1 1 1 0 0 0 0 0 0 07] 0 0 1 0 1 0 0 0 0 0 08] 0 1 0 1 1 1 1 0 0 0 09] 0 0 1 0 0 0 1 0 0 0 010] 0 1 1 0 0 1 0 1 1 0 011] 0 0 1 0 1 0 1 0 1 0 012] 0 0 1 1 0 1 0 0 1 1 013] 0 0 0 0 1 0 0 0 1 0 114] 0 0 0 0 1 1 1 1 0 1 115] 0 0 0 0 0 0 1 0 1 0 116] 0 0 0 0 0 0 0 0 0 0 0;17] w = 0 2 8 1 0 0 0 0 0 0 018] 2 0 6 0 1 0 0 0 0 0 019] 8 6 0 7 5 1 2 0 0 0 020] 1 0 7 0 0 0 9 0 0 0 021] 0 1 5 0 0 3 0 2 9 0 022] 0 0 1 0 3 0 4 0 6 0 023] 0 0 2 9 0 4 0 0 3 1 024] 0 0 0 0 2 0 0 0 7 0 925] 0 0 0 0 9 6 3 7 0 1 226] 0 0 0 0 0 0 1 0 1 0 427] 0 0 0 0 0 0 0 9 2 4 0;28] enddata29] n=@size(cities);30] min=@sum(roads:w*x);31] @for(cities(i) | i #ne# 1 #and# i #ne# n:32] @sum(cities(j): p(i,j)*x(i,j))33] =@sum(cities(j): p(j,i)*x(j,i)));34] @sum(cities(j): p(1,j)*x(1,j))=1;END在上述程序中，第6]行到第16]行给出了图的邻接矩阵，到和到的边按单向计算，其余边双向计算.第17]行到第27]行给出了图的赋权矩阵, 注意：由于有了邻接矩阵，两点无道路连接时，权值可以定义为0. 其它的处理方法基本上与有向图相同.用LINGO 软件求解，得到(仅保留非零变量)Global optimal solution found at iteration: 2 0Objective value: 13.00000Variable Value Reduced Cost X( 1, 2) 1.000000 0.000000X( 2, 5) 1.000000 0.000000X( 3, 7) 1.000000 0.000000X( 5, 6) 1.000000 0.000000X( 6, 3) 1.000000 0.000000X( 7, 10) 1.000000 0.000000X( 9, 11) 1.000000 0.000000X( 10, 9) 1.000000 0.000000即最短路径为最短路长度为13.1 2 5 6 3 7 10 11。

货物配送问题摘要随着城市经济的发展，现代服务业快速发展，城市配送已经成为支撑城市正常运作和经济发展的重要手段。

货物配送作为物流体系中基本的业务环节。

公司通过制定完善的配送方案来获取较大利益。

本文是针对梦想连锁一家主营鲜猪肉的食品加工公司的2个生产基地对其他23 个销售连锁店所需鲜猪肉的的运输调度问题提出相应的方案。

针对问题一，考虑每个城镇的销售量都是固定的，并且要满足所有连锁店的需求，要求运输成本最低，转化为路径最短的问题。

首先根据所给数据画出全省城镇交通网络图。

采用0-1规划算法，即决策变量能到达为1，否则为0，编写程序，用lingo软件直接得出每个连锁店与生产基地所在地城镇63和城镇120之间距离的最小值和所到连锁店，得最优生产与配送方案：由生产基地120向连锁店1、2、5、9、10、11、13、14、15、19、21、22运送货物，其成本为6532.0313元，由生产基地63向连锁店3、4、6、7、8、12、17、18、20、23运送货物，其成本为4008.86118.元。

因此优化得，总的最低成本为10540.89248元。

针对问题二，对于第一小问，采用描述统计的方法，求得各个城镇需求的平均值、方差，通过分析数据来描述其特征。

对于第二小问，在全省所有城镇年需求量已求的基础上，建立灰色预测模型，然后预测分析2012年以后各年份的需求总量，得出全省需求量达峰值时，时间为2014年2月份，并将出现峰值时所有城镇的需求结果进行排序，求解出需求量较大的前五位城镇分别为120、63、31 、106、 68；需求量较小的后五位城镇为 84、30 、54 、74 、129 。

针对问题三，本题需决定连锁店的增建方案，以使全省销售量最大，这是一个优化问题。

我们将采用先分析后计算，并结合0-1规划的方法。

建立目标函数和约束条件。

并利用lingo软件编写程序，城镇6 8 10 18 31 33 50 54 56 64 68 76 100 101 104 110 116 120 123 125 150 154需要增设连锁店，其中城镇120，31,64，10,123分别含有连锁店的个数是3,2,2,2,2个，其余的城镇连锁店个数为1个，使得全省销售量最大，最大值为919414公斤。

中国邮递员模型研究一、 中国邮递员问题概述著名图论问题之一。

邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。

在此条件下，怎样选择一条最短路线?关于邮递员最优投递路线问题最早是由管梅谷首先提出并进行研究的, 国际上现在统称之为中国邮递员问题。

管梅谷给出了这一问题的奇偶点图上作业法。

Edmonds 等给出了中国邮递员问题的改进算法, 较前者的计算更为有效。

管梅谷对有关中国邮递员问题的研究情况进行了综述。

早期关于中国邮递员问题的讨论总是基于无向图展开的,事实上,由于单行线或上下行路线的坡度等原因, 这一问题有时必须借助于有向图来进行研究和解决。

到目前为止,对中国邮递员问题的研究主要是从图论角度展开的, 给出的多数都是各种启发式算法或递推算法。

本文从数学规划的角度进行研究。

数学规划建模具有借助软件包求解方便、 易于修改和推广等多方面的优点,即使对于大型问题也易于建模分析和解决的优点。

1、 传统中国邮递员问题的建模 一些基本概念:定义 经过G 的每条边的迹叫做G 的Euler 迹；闭的Euler 迹叫做Euler 回路或E 回路；含Euler 回路的图叫做Euler 图。

直观地讲，Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。

定理（i ）G 是Euler 图的充分必要条件是G 连通且每顶点皆偶次。

（ii ）G 是Euler 图的充分必要条件是G 连通且 di i C G 1==，i C 是圈，)()()(j i C E C E j i ≠Φ= 。

（iii ）G 中有Euler 迹的充要条件是G 连通且至多有两个奇次点。

问题（管梅谷，1960） ：一位邮递员从邮局出发投递邮件，经过他所管辖的每条街道至少一次，然后回到邮局。

请为他选择一条路线，使其所行路程尽可能短。

图论模型：求赋权连通图中含有所有边的权最小的闭途径。

这样的闭途径称为最优回路。

2018-2019学年第一学期《运筹学》实验报告（四）班级：交通运输171学号： 1000000000姓名： *****日期： 2018.11.22实验一：用Lingo 软件求解下列整数规划问题（要求附程序和结果）12121212max 25062210,1,2i z x x x x x x x x x i =++≤⎧⎪-+≤⎪⎨+≤⎪⎪≥=⎩且取整数12312323123123123max 232452244,,01z x x x x x x x x x x x x x x x x x =+-++≤⎧⎪+≤⎪⎪+-≤⎨⎪+-≤⎪=⎪⎩或解：例题（左）解题程序及运行结果如下：sets :bliang/1,2/:x,a; yshu/1,2,3/:b;xshu(yshu,bliang):c; endsets data : a=2,1; b=5,0,21; c=1,1 -1,1 6,2; enddatamax =@sum (bliang(i):a(i)*x(i));@for (yshu(j):@sum (bliang(i):x(i)*c(j,i))<=b(j)); @for(bliang(i):@gin(x(i)));Global optimal solution found.Objective value: 7.000000 Objective bound: 7.000000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0Variable Value Reduced CostX( 1) 3.000000 -2.000000X( 2) 1.000000 -1.000000A( 1) 2.000000 0.000000A( 2) 1.000000 0.000000B( 1) 5.000000 0.000000B( 2) 0.000000 0.000000B( 3) 21.00000 0.000000C( 1, 1) 1.000000 0.000000C( 1, 2) 1.000000 0.000000C( 2, 1) -1.000000 0.000000C( 2, 2) 1.000000 0.000000C( 3, 1) 6.000000 0.000000C( 3, 2) 2.000000 0.000000Row Slack or Surplus Dual Price1 7.0000001.0000002 1.000000 0.0000003 2.000000 0.0000004 1.000000 0.000000例题（右）解题程序及运行结果如下：sets:bliang/1,2,3/:x,a;yshu/1,2,3,4/:b;xshu(yshu,bliang):c;endsetsdata:a=2,1,-1;b=2,5,2,4;c=1,3,10,4,11,2,-11,4,-1;enddatamax=@sum(bliang(i):a(i)*x(i));@for(yshu(j):@sum(bliang(i):x(i)*c(j,i))<=b(j));@for(bliang(i):@bin(x(i)));Global optimal solution found.Objective value: 2.000000Objective bound: 2.000000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 0Variable Value ReducedCostX( 1) 1.000000 -2.000000X( 2) 0.000000 -1.000000X( 3) 0.000000 1.000000A( 1) 2.000000 0.000000A( 2) 1.000000 0.000000A( 3) -1.000000 0.000000B( 1) 2.000000 0.000000B( 2) 5.000000 0.000000B( 3) 2.0000000.000000B( 4) 4.000000 0.000000C( 1, 1) 1.000000 0.000000C( 1, 2) 3.000000 0.000000C( 1, 3) 1.000000 0.000000C( 2, 1) 0.000000 0.000000C( 2, 2) 4.000000 0.000000C( 2, 3) 1.000000 0.000000C( 3, 1) 1.000000 0.000000C( 3, 2) 2.000000 0.000000C( 3, 3) -1.000000 0.000000C( 4, 1) 1.000000 0.000000C( 4, 2) 4.000000 0.000000C( 4, 3) -1.000000 0.000000Row Slack or Surplus Dual Price1 2.0000001.0000002 1.000000 0.0000003 5.000000 0.0000004 1.000000 0.0000005 3.000000 0.000000实验二：一、问题重述某学校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。

0-1规划如果要求决策变量只取0 或1的线性规划问题, 称为0-1规划.0-1 约束不一定是由变量的性质决定的, 更多地是由于逻辑关系引进问题的例5 背包问题一个旅行者的背包最多只能装6 kg 物品. 现有4 件物品的重量和价值分别为 2 kg , 3 kg, 3 kg, 4 kg, 1 元, 1.2元, 0.9元, 1.1元. 应携带那些物品使得携带物品的价值最大?建模: 记x j为旅行者携带第j 件物品的件数, 取值只能为0 或 1.求目标函数f=x 1 +1.2x 2 +0.9x 3 +1.1x 4 在约束条件2x 1 +3x 2 +3x 3 +4x 4≤ 6下的最大值.用Lingo 软件求解0-1规划Model:Max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x4<=6;@int(x1);@int(x2);@int(x3);@int(x4);end例 6 集合覆盖问题实际问题 1 某企业有5种产品要存放, 有些不能存放在一起, 有些能存放在一起的, 由于组合不同所需费用不同. 求费用最低的储存方案.实际问题 2 某航空公司在不同城市之间开辟了5 条航线, 一个航班可以飞不同的航线组合, 不同组合成本不同, 求开通所有航线且总费用最小的方案.抽象为集合覆盖问题：设集合S={1,2,3,4,5} 有一个子集类φ={{1,2},{1,3,5},{2,4,5},{3},{1},{4,5}}其中每一个元素对应一个数c j , 称为该元素的费用. 选φ的一个子集使其覆盖S , 且总费用最低.即实际问题1中5种产品能存放在一起的各种组合为, φ={{1,2},{1,3,5},{2,4,5},{3},{1},{4,5}}第 i 种组合的存储费用为 cj求这五种产品费用最低的储存方案。

模型: 设决策变量：设∆⊆φ是S 的一个覆盖（一种存储方案）. 当φ的第i 个元素属于∆, （即第i 种组合被采用）记x i=1，否则x i=0求目标函数f= ∑i c i x i在约束条件x1 +x2+ x5≥1 x1 + x3≥1 (因为第2种产品只在第1，3个组合中出现) x2+ x4≥1 x3 + x6 ≥1 x2+x3 + x6 ≥1 x i∈{0，1}，I=1,2, ⋯,6, 下的最小值.。

数学建模实验报告1．解析：此题属于0-1模型问题。

设队员序号为i ，泳姿为j ，记c ij 为队员i 第j 种泳姿的百米成绩，若选择队员i 参加泳姿j 的比赛，记x ij =1, 否则记xij =0；则有，目标函数为∑∑===4151j i ij ij x c Z Min ，每个人最多选泳姿为1，则有5,1,141=≤∑=i xj ij，每种泳姿有且仅有1人，则有4,1,151==∑=j xi ij。

若丁的蛙泳成绩退步及戊的自由泳成绩进步，则将c43的值和c54的值改变即可。

实验过程及运行结果如下：若丁的蛙泳成绩退步为1'15"2及戊的自由泳成绩进步57"5,计算结果如下：通过计算结果可知，在原数据的情况下，队伍的选择应该是甲参加自由泳，乙参加蝶泳，丙参加仰泳，丁参加蛙泳，戊不参加任何比赛，且最好的时间是253.2秒。

若丁的蛙泳成绩退步为1'15"2及戊的自由泳成绩进步57"5,则组成接力的比赛队伍调整为乙参加蝶泳，丙参加仰泳，丁参加蛙泳，戊参加自由泳，甲不参加任何比赛。

2．解析：此题属于线性规划问题。

已知某工厂用1A 、2A 两台机床加工1B 、2B 、3B 三种不同的零件，设1A 生产1B 、2B 、3B 的个数分别为1x 、2x 、3x ，2A 生产1B 、2B 、3B 的个数分别为4x 、5x 、6x ，则目标函数为min=1*2*1x +2*3*2x +3*5*3x +1*3*4x +1*3*5x +3*6*6x ;1A 加工的工时小于80小时，2A 加工的工时小于100小时，生产1B 、2B 、3B 的总数分别为70个、50个、20个。

实验过程及运行结果如下：通过计算结果可知，当1A 生产1B 、2B 、3B 的个数分别为68个、0个、4个，2A 生产1B 、2B 、3B 的个数分别为2个、50个、16个的时候，才能得到最低的成本640元。

例7.4最短路问题给定N个点p i (i 1, 2，，N )组成集合{P i},由集合中任一点P i到另一点Pj的距离用Cij表示，如果Pi到Pj没有弧联结，则规定Cij,又规定Cii 0(1 i N)，指定一个终点P N，要求从Pi点出发到P N的最短路线。

这里我们用动态规划方法来做。

用所在的点Pi表示状态，决策集合就是除Pi以外的点，选定一个点Pj以后，得到效益cij并转入新状态Pj，当状态是PN时，过程停止。

显然这是一个不定期多阶段决策过程。

定义f (i) 是由P i点出发至终点PN的最短路程，由最优化原理可得f(i) mi j n { c ij f(j)}, i 1,2, ,N 1f(N) 0这是一个函数方程，用LINGO可以方便的解决。

! 最短路问题;model:data :n=10;enddatasets :cities/1..n/: F; !10 个城市;roads(cities,cities)/1,2 1,32.4 2,5 2,63.4 3,5 3,64.7 4,85.7 5,8 5,96.8 6,97.108.109,10/: D, P;endsetsdata :D=6 53 6 97 5 119 18 7 54 10579;enddataF(n)=0;@for(cities(i) | i #lt# n:F(i)= @min(roads(i,j): D(i,j)+F(j)););! 显然，如果P(i,j)=1, 则点i 到点n 的最短路径的第一步是i --> j ，否则就不是。

由此，我们就可方便的确定出最短路径;@for(roads(i,j):P(i,j)= @if (F(i) #eq# D(i,j)+F(j),1,0)); end 计算的部分结果为：Feasible solution found at iteration:Variable N F( 1) F( 2) F( 3) F( 4) F( 5) F( 6) F( 7) F( 8) F( 9) F( 10)P( 1, 2)P( 1, 3)P( 2, 4)P( 2, 5)P( 2, 6)P( 3, 4)P( 3, 5)P( 3, 6)P( 4, 7)P( 4, 8)P( 5, 7)P( 5, 8)P( 5, 9)P( 6, 8)P( 6, 9)P( 7, 10)P( 8, 10)P( 9, 10)Value 10.00000 17.00000 11.00000 15.00000 8.000000 13.00000 11.00000 5.000000 7.000000 9.0000000.0000001.0000000.0000001.000000 0.0000000.0000001.000000 0.000000 0.0000000.0000001.000000 1.000000 0.0000000.0000001.0000000.0000001.000000 1.000000 1.000000例3.5 (最短路问题) 在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一 城市的最短路。