北交大LINGO考试2旅行商问题,最大流问题等

《物流软件》实验报告

实验编号：实验2

学号：序号：

姓名：

班级：

2015年10月

一、 旅行商问题

（1） 数学模型

设di是两点i与j之间的距离，Xij=0或1（1表示连接，0表示不连接）则有

Mindij*Xij

jV

s.t. （每个点只有一条边出去），iV Xij =1 ，

jV

（每个点只有一条边进入），iV Xji =1，

jV

(除起点与重点外，个边不构成圈)

（2） LINGO程序

MODEL:

SETS:

CENTERS/1..8/:LEVEL;

LINK(CENTERS,CENTERS):DISTANCE,X;

ENDSETS

DATA:

DISTANCE = 0 3 2 3 4 3 5 6

3 0 2 3 2 3 1 4

2 2 0 1 4 3 2 5

3 3 1 0 1 14 3 4

4 2 4 1 0 2 2 3

3 3 3 14 2 0 8 4

5 1 2 3 2 8 0 3

6 4 5 4 3 4 3 0;

ENDDATA

N=@SIZE(CENTERS);

MIN=@SUM(LINK(I,J)|i #ne# j :distance(i,j)*x(i,j));

@for(centers(i):

@sum(centers(j)|j #ne# i:x(j,i))=1;

@SUM(CENTERS(J)|J #NE# I:X(I,J)) = 1;

@FOR(CENTERS(j)|J #GT# 1 #AND# J #NE# I :

LEVEL(J)>=LEVEL(I)+X(I,J)-(N-2)*(1-X(i,J))+(N-3)*X(J,I););); @FOR(LINK:@BIN(X));

@FOR(CENTERS(I)|I #GT# 1:

LEVEL(I)

LEVEL(I)>=1+(N-2)*X(I,1););

END

CENTERS/1..8/是基本集合名字，元素为1到8。LEVEL为其元素。 LINK是派生集合

（3） 运行结果

Global optimal solution found.

Objective value: 17.00000

Extended solver steps: 0

Total solver iterations: 56

X( 1, 2) 1.000000 3.000000

X( 2, 7) 1.000000 1.000000

X( 3, 1) 1.000000 2.000000

X( 4, 3) 1.000000 1.000000

X( 5, 4) 1.000000 1.000000

X( 6, 5) 1.000000 2.000000 X( 7, 8) 1.000000 3.000000

X( 8, 6) 1.000000 4.000000

从以上结果可以看出，最短的经过距离是17.路径为

1 2 7 8 6 5 4 3 1

二、最大流问题

（1）数学模型

Max vf;

s.t.

jV(i,j)Avf(is);fijfij=-vf(it); jV0(is,t)(j,i)A

0

（2）LINGO程序

MODEL:

SETS:

NODES/1,2,3,4,5,6,7/;

arcs(nodes,nodes)/1,2,1,3,1,4,2,5,3,6,4,3,4,6,5,7,6,5,6,7/:c,f;

endsets

data:

c =40 13 15 25 20 26 12 32 18 42;

enddata

max=flow;

@for(nodes(i)|i #ne# 1 #and# i #ne# @size(nodes):

@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);

@sum(arcs(i,j)|i #eq# 1:f(i,j))= flow;

@for(arcs:@bnd(0,f,c));

End

NODES是基本集合名字，1到7为元素，

acrs是派生集合，各个路径是其元素。Cf为属性

（3）运行结果

Global optimal solution found.

Objective value: 53.00000

Total solver iterations:

Variable Value Reduced Cost

FLOW 53.00000 0.000000

F( 1, 2) 25.00000 0.000000

F( 1, 3) 13.00000 -1.000000

F( 1, 4) 15.00000 -1.000000

F( 2, 5) 25.00000 -1.000000

F( 3, 6) 16.00000 0.000000

F( 4, 3) 3.000000 0.000000

F( 4, 6) 12.00000 0.000000

F( 5, 7) 25.00000 0.000000

F( 6, 5) 0.000000 0.000000

F( 6, 7) 28.00000 0.000000

从以上结果可以看出各个线路的流量，如第一行表示点1到点2流 25，第二行表示点1到点3流13,依此类推。得到

v1，v2，v5，v7=25

V1，v4，v6，v7=12

V1，v3，v6，v7=13

V1，v4，v3，v6，v7=3.

最大流为53

二、 最小费用最大流问题

（1） 数学建模

Min

s.t.(i,j)ACijFij;

jV(i,j)AFijjV(j,i)AFji=di,

0

di=vf(i=s);-vf(i=t);0(i≠s,t)

（当vf为网络的最大流时，就为最大费用最小流问题。）

（2） LINGO程序

MODEL:

SETS:

NODES/1,2,3,4,5,6,7/:d;

arcs(nodes,nodes)/1,2,1,3,1,4,2,5,3,6,4,3,4,6,5,7,6,5,6,7/:c,u,f; endsets

data:

d = 53 0 0 0 0 0 -53;

c = 3 1 2 4 3 3 1 1 1 2;

u = 40 13 15 25 20 26 12 32 18 42;

enddata

min=@sum(arcs:c*f);

@for(nodes(i)|i #ne# 1 #and# i #ne# @size(nodes):

@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=d(i));

@sum(arcs(i,j)|i #eq# 1:f(i,j))=d(1);

@for(arcs:@bnd(0,f,u));

end

NODES为基本集合名，1到7为元素，d为属性

arcs为派生集合名，各个路径为元素，c，u，f为属性

（3） 运行程序

Global optimal solution found.

Objective value: 368.0000

Total solver iterations: 0

Variable Value Reduced Cost U( 1, 2) 40.00000 0.000000

U( 1, 3) 13.00000 0.000000

U( 1, 4) 15.00000 0.000000

U( 2, 5) 25.00000 0.000000

U( 3, 6) 20.00000 0.000000

U( 4, 3) 26.00000 0.000000

U( 4, 6) 12.00000 0.000000

U( 5, 7) 32.00000 0.000000

U( 6, 5) 18.00000 0.000000

U( 6, 7) 42.00000 0.000000

F( 1, 2) 25.00000 0.000000

F( 1, 3) 13.00000 -4.000000 F( 1, 4) 15.00000 0.000000

F( 2, 5) 25.00000 -2.000000 F( 3, 6) 16.00000 0.000000

F( 4, 3) 3.000000 0.000000

F( 4, 6) 12.00000 -5.000000 F( 5, 7) 32.00000 0.000000

F( 6, 5) 7.000000 0.000000

F( 6, 7) 21.00000 0.000000

V，v2，v5，v7

V1，v4，v6，v7

V1，v3，v6，v7

V1，v3，v6，v5，v7

V1，v4，v3，v6，v7

由以上结果可知，最大流为53，最小费用为368

（4） 对比

v1，v2，v5，v7=25

V1，v4，v6，v7=12

V1，v3，v6，v7=13

V1，v4，v3，v6，v7=3

这是实验（2）的结果

V，v2，v5，v7

V1，v4，v6，v7

V1，v3，v6，v7

V1，v3，v6，v5，v7

V1，v4，v3，v6，v7

这个是实验（三）的结果

两个实验的路径选择是一样的，如果图更复杂，很有可能遇到有多个最大流的情况，这时候引入最小费用最大流就有了经济意义，帮助决策。


相关文章

  • 旅游线路的优化设计论文

    • 旅游线路的优化设计 摘要 旅游一向被认为是提高人们生活质量的重要活动,如何针对旅行者的不同要求或者偏好,从而设计一条合理的旅游线路,已经成为旅游爱好者及旅游公司的关注热点.本文通过分析旅游行程安排与旅游用时及所需费用间的动态影响,以整个旅游日程安排系统为研究对象,通过Lingo求解获得可信结果. 问 ...

  • 缴费站选址问题

    • 论文题目:缴费选址问题 摘要 本文根据社区的公路网络图,求解不同条件下的选址问题,及分组巡视问题.文中首先将网络图转换为赋权连通图. 对于问题一,本文首先通过赋权连通图求出社区间的邻接矩阵,通过Floyd 算法求出任意两点间的的最短距离,通过matlab 编程利用枚举法,在24个社区中任意求出三点, ...

  • 运筹学实验报告[1]

    • 中南民族大学管理学院 学生实验报告 课程名称: 年 级: 2012级 专 业: 指导教师: 胡丹丹 学 号: 姓 名: 实验地点:管理学院5号楼综合实验室 学年度第 目 录 实验一实验二实验三实验四实验五实验六 线性规划建模及求解 运输问题整数规划问题 目标规划 用lingo求解简单的规划问题 用E ...

  • 会议筹备问题数学建模优秀模板

    • 青岛科技大学自动化与电子工程学院测控技术与仪器131 会议筹备问题 摘 要 本文主要研究会议的筹备问题.一次成功的会议,是以前期充分的筹备为前提的.会议筹备的完善与否,将直接关系着会议的经费问题,调动人员是否方便以及与会代表的满意程度,因此,会议筹备的优化问题具有重要意义.本文对此问题建立了线性拟合 ...

  • 蔬菜供应方案设计

    • 蔬菜供应方案设计 摘 要 由于人们生活水平的发展,开始讲求天然产品,这使蔬菜产品有了广阔的市场.商业企业要求最好的销售和利润的最大化,于是要设定合适的蔬菜供应方案力求利润的最大化和市场供应的便捷性. 本文利用Floyd算法求出各蔬菜采购点到每个菜市场的最短运输距离,然后用lingo软件计算蔬菜调运费 ...

  • 六年级下册英语课程纲要

    • 2014-2015学年下学期六年级英语 课 单位: 姓名: 时间: 程 纲 要 小学六年级<英语(下册)<课程纲要> 课程名称:英语 课程类型: 必修 教材来源:人民教育出版社2013年版 适用年级:小学六年级 课时:48课时 设计者:常静/郑州航空港区第十小学 目标 英语是基础教 ...

  • 北交大法律硕士考研心态如何调节

    • 北交大法律硕士考研心态如何调节 本文系统介绍北交大法律硕士考研学习方法及经验,北交大法律硕士考研难度,北交大法律硕士就业,北交大法律硕士学费,北交大法律硕士考研参考书,北交大法律硕士考研初试复试经验以及北交大法律硕士考研心态调整等七大方面的问题,凯程北交大法律硕士老师给大家详细讲解.特别申明,以下信 ...

  • 北京交通大学法律硕士就业前景论坛

    • 北京交通大学法律硕士就业前景论坛 本文系统介绍北交大法律硕士就业情况,北交大法律硕士考研难度,北交大法律硕士学费,北交大法律硕士考研参考书,北交大法律硕士考研初试经验五大方面的问题,凯程北交大法律硕士老师给大家详细讲解.特别申明,以下信息绝对准确,凯程就是王牌的北交大考研机构! 一.北交大法律硕士就 ...

  • 交大[管理运筹学]课程教学大纲

    • <管理运筹学>课程教学大纲 2.具体要求 第一章-第八章 规划论(数学规划) [目的要求] 主要研究如何有效利用有限资源,合理分配生产任务,选择最佳生产布置以及合理安排物资调运方案,以求取得最好的经济效果.它包括:线性规划.整数规划和动态规划.其中线性规划是运筹学中发展较成熟.应用最广泛 ...

© 2024 范文中心 | 联系我们 webmaster# onjobs.com.cn