最短路径问题的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个集合元素，没有定义变量名。

解：对于无向图的最短路问题，可以这样理解，从点到点和点到点的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种方法编写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 CostX( 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.→→→→→→→1256371011。

例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 (最短路问题) 在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一 城市的最短路。

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

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

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

然后利用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 到达将处以一定的惩罚，给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。