数学建模景区路线规划论文
景区路线规划
摘 要
本文主要研究最短旅游路线的设计问题。在满足题目中的条件下,找到最佳的路径且用最短的距离是我们追求的目标。毕竟,能否设计出合理且令人满意的旅游路径,对景区的经济效益和长远发展有着密切的关系。对此本文用数学联系实际,建立数学模型,设计出相对科学的景区旅游景点路线,来解决此类问题。
对于问题一,从题目中我们了解到我们要设计出6种只含4个景点的最短路径,且至少包括两个特色景点,而旅游内容相近的同类景点如1,6和9,10又不能同时出现。根据这些条件,我们运用floyd 算法的原理,通过matlab 编程,建立带权邻接矩阵,再用插入顶点的方法构造出距离矩阵,同时也能求出插入点矩阵,最终得到初步符合条件的旅游套餐。再经过用Excel 软件对得出的数据进行分类,整理,排序,最终得出符合题意的6种旅游套餐。同时,在我们对景点的组合中可以发现,有多种景点组合都存在游览顺序不同而导致的行程不同的现象。对这种游览顺序不同,但游览的景点是相同的情况,我们视其为同一种旅游套餐。
对于问题二,题目要求我们设计出6种不同旅游套餐,并在在景区特色景点的客流容纳人数是其他景点的两倍的情况下计算出各种套餐的人数比例,使得景点的客流量基本均衡,且总行程尽可能短。对此我们0-1变量的思想表示是否游览某个景点,从而推出总行程尽可能短的约束条件,再用Lingo 编程对模型进行求解,得出初步可能的旅游套餐。然后再引入方差的思想,方差是描述数据离散程度的量,方差越小各景点的客流量越均衡。所以,我们接下来可以利用6 个旅游套餐中所有景点的客流量的方差来刻画景点客流量的均衡程度,要使方差尽量小,首先6个套餐应覆盖尽量多的景点,再由每种套餐的比例来约束方差,使得方差尽量小。由此,我们可以建立关于游客量的方程和关于方差的函数。然后再对之前得出的旅游套餐使用综合评判的方法,并经过灵敏度的分析,得出符合要求的6种旅游套餐。
关键词 floyd算法 Exce软件 matlab软件 0-1变量 Lingo软件
一、问题重述
图1
某景区有10个景点,各景点的交通示意图如图1。边上的权为两景点间路程。其中1,3,6,9,10五个景点为景区特色景点。景区特色景点的客流容纳人数是其他景点的两倍。在特色景点中,1和6都是海滨景点,9和10都是山区景点。
为了合理规划景区的旅游,景区旅游经营者计划推出6种不同的旅游套餐,每种旅游套餐包括4个景点,其中至少2个特色景点。由于景点1、6和景点9、10分别是同类景点,游览内容相近,景区规定,旅游套餐中的特色景点不能只是同类景点。需要解决的问题:
(1)按照上述要求,找出6种路程最短的套餐。
(2)请你设计出这6种不同旅游套餐,并计算出各种套餐的人数比例,使得景点的客流量基本均衡,且总行程尽可能短。
二、问题分析
能否设计出合理且令人满意的旅游路径,对景区的经济效益和长远发展有着密切的关系。根据题目中给景点示意图,我们可以得到任意两个景点之间的距离。如下表所示:
景点之间的距离
景点1 景点2 景点3 景点4 景点5 景点6 景点7 景点8 景点9 景点10
Inf Inf 24.6 Inf Inf Inf Inf
表一
11.6 Inf 0
另外,题中要求每种旅游套餐要有4个景点,其中至少包含2个特色景点,且特色景点不能是同一类的,对此4个景点间的路程求和即为这个旅游套餐的路径。由图1可看出,4个景点所游览的顺序不同,会出现其行程也不相同的现象,我们归其为同一类套餐。根据题目的要求,我们只选取其中行程最短的路径作为这种套餐。首先,通过matlab 编程和对floyd 了解及运用,找出初步符合条件的路径,再利用穷举法以及用EXCEL 对得出的数据处理,最终可得到符合题意且路程最短的6种套餐。
对于问题二,在第一问的基础上,可以用6 个旅游套餐中所有景点的客流量的方差来描述景点客流量的均衡程度,方差越小各景点的客流量越均
衡。需注意,景区特色景点的客流容纳人数是其他景点的两倍, 所以需对方差进行简单处理,具体见模型建立。要使方差尽量小, 首先6 个套餐应覆盖尽量多的景点,(再由每种套餐的比例来约束方差,)使得方差尽量小。(在本问中,我们定义了一个函数——均衡程,描述方案对题意的符合度,具体见符号说明与模型建立。通过对均衡程的比较可以得出最优的6 个套餐。)
三、模型的假设与符号说明
1、模型的假设
(1)游客在旅游观览过程中,均按旅游套餐进行游览。且每种套餐上有且仅有4个景点。
(2)游客在旅游观览过程中,考虑到实际情况,在按照一种旅游套餐,4个景点仅仅是因为由于游览顺序不同而出现的多种游览方式的时候,视为同一种旅游套餐,并且是取总路程最短的游历路线方案。
(3)游客在旅游观览过程中,无任何意外情况的发生。
(4)每一个景点接待游客的能力都是相同的并且接待能力充分高,即可以实现多条旅游路线的游客们同时游览同一个景点。
(5)一个景点直接到达另外一个景点是指,途中经过的其他景点只是一个转站地,而并不进行游览. 2、符号说明
表2
表1对论文中出现的而符号加以解释,若有没有解释的,以文中出现的为主。
四、问题一
1、模型分析
针对第一问,我们要考虑: (1)每个旅游套餐中有4个景点 (2)4个景点中至少要有两个特色景点; (3)同类的特色景点不能同时出现; (4)经过4个景点的路程最短。
在旅游套餐中会出现旅游景点相同,但是因为游览顺序的不同而出现路程不同的情况,我们选取最短距离作为标准。我们客观的规定,在浏览过程中,不存在经过景点而不进入景点的情况。 2、模型建立
游客在景点间的直达距离可由以下矩阵给出,即x i 到x j 的直达距离为D ij ,若两景点间不能直接到达则用∞表示。得到如下矩阵W :
∞⎡031.5∞
⎢31.507.512.7⎢⎢∞7.5014.5⎢
⎢∞12.714.50⎢1917∞6.8⎢
∞∞10.8⎢∞
⎢∞∞∞16.8⎢
∞17.611.2⎢∞
⎢∞∞∞∞⎢⎢∞∞∞⎣∞
1917∞07.8∞∞∞∞
∞∞∞7.8012.8∞∞∞
∞∞∞∞12.8012.611.8∞
∞⎤
∞∞∞⎥⎥17.6∞24.6⎥
⎥
11.2∞∞⎥
(1) ⎥∞∞∞⎥
∞∞∞⎥12.611.8∞⎥
⎥
018.611.6⎥18.60∞⎥
⎥⎥11.6∞0⎦∞
∞
6.810.816.8
Floyd 算法的建立;
(0)
第一步:把带权邻接矩阵W 作为距离矩阵的初值,即D (0)=(d ij ) ν⨯ν=W, (1) (1) (0) ) (1)
D (1)= (d ij ) ν⨯ν,其中d ij =min{d ij , d i (10) +d 1(0j },d ij 是从v i 到v j 的只允许以v 1
作为中间点的路径中最短路的长度.
(2) (1) 1) (2) (1) (2)
第二步:D (2)= (d ij =min{d ij , d i (2) ν⨯ν,其中d ij +d 2j },d ij 是从v i 到v j 的只
允许以v 1 、 v 2作为中间点的路径中最短路的长度.
∙∙∙∙∙∙
(ν) (ν) (ν-1) ν-1) (ν) D (ν) =(d ij 是从v i 到v j 的只允许) ν⨯ν,其中d ij =min{d ij , d i (ν+d ν(j ν-1) }, d ij
以v 1、v 2、…、v ν作为中间点的路径中最短路的长度.即是从v i 到v j 中间可插入任何顶点的路径中最短路的长,因此D (ν) 即是距离矩阵.
第三步:在建立距离矩阵的同时可建立路径矩阵R . R=(r ij ) ν⨯ν, r ij 的含义是从v i 到v j 的最短路要经过点号为r ij 的点.
R (0) =(r ij (0) ) ν⨯ν, r ij (0) =j
每求得一个D (k)时,按下列方式产生相应的新的R (k)
r
(k )
ij
⎧k =⎨r (k -1) ⎩ij
(k -1) (k -1) (k -1) 若d ij >d ik +d kj
(2)
否则
即当v k 被插入任何两点间的最短路径时,被记录在R (k)中,依次求 R (ν) 时求得
D (ν) 可由R (ν) 来查找任何点对之间最短路的路径.
图2 第四步:利用追溯法即可在R 中找出符合条件的最短路径。即:若r ij (ν) =p 1,则点p 1是点i 到点j 的最短路的中间点. 然后用同样的方法再分头查找. 若:
(1)向点i 追朔得:r ip 1=p 2, r ip 2=p 3, „, r ip k =p k (2)向点j 追朔得:r p 1j =q 1, r q 1j =q 2, „, r q m j =j
(ν)
(ν)
(ν
)
(ν)
(ν)
(ν)
则由点i 到j 的最短路的路径为:i , p k , , p 2, p 1, q 1, q 2, , q m , j
图3
3、模型的求解
根据(1)矩阵,运用floyd 算法得出权矩阵D 和插入点矩阵R(程序及迭代过程见附录一) :
R =
1 2 2 5 5 5 5 5 5 5 1 2 3 4 5 4 4 4 4 3 2 2 3 4 4 4 8 8 8 10 5 2 3 4 5 6 7 8 7 8 1 2 4 4 5 6 6 4 6 4 5 4 4 4 5 6 7 4 7 4 6 4 8 4 6 6 7 8 9 8 4 4 3 4 4 4 7 8 9 10 7 7 8 7 7 7 7 8 9 8 8 8 8 8 8 8 8 8 8 10 程序见附录一,注意;在matlab 中 表示为inf 。 通过追溯法求得初步符合条件的路线:
表2
表2中的路线只是符合经过4个旅游景点,至少包含2个特色且不包含同类特色景点的路线,我们需要用Excel 软件对数据进行再处理。
用Excel 对数据进行处理得到表3:
表3
表3是对表2中的路线数据进行处理后所得结果,是无序的,不易直接找到路程最短的路线,再对表3数据进行排序。 对所得路程进行处理后得到满足条件的路线:
表4
表4中的路线即是满足要求的路线,即包括4个景点,其中至少2个特色景点,没有同类景点。
五、问题二
1、模型分析
针对问题2要考虑的问题有:
(1)计算各种旅游套餐的人数比例; (2)各景点的客流量基本平衡; (3)总路程最短。
要解决这3各问题,要从实际情况出发,设定一系列的变量及不变量。 (1)景区(包括10各景点)的总游客量为k 。 (2)对各景点的游客统计假定不重复。 2、模型建立
建立0-1模型;设置相邻两景点的距离函数为;
Y ij =s ij *x i *x j (3)
其中x i 、x j 为0.1变量,当旅游路线经过i ,j 景点时x i =1、x j =1,若旅游路线不经过i ,j 景点则x i =0,x j =0 目标函数:
min ∑Y ij *s ij (4)
ij =1
10
10
⎧
x i =4∑⎪
i =1
⎪⎪
⎨x 1+x 3+x 6+x 9+x 10=2 (5) ⎪x 1+x 6≤1⎪
x 9+x 10≤1⎪⎩
3、模型的求解
每个景点的客流量:
P 1=k ∑M ij (6)
j =a
f
因为总游客人数是k ,每个游客浏览4个景点,所以若假设每人只浏览一个景点,则游客总人数为4k ,所以每个景点平均接待游客量为:
p =
4k
(7) 10
为使所有景点客流量较均衡,所选的6个套餐及其比例应使所有景点接待 游客量的方差尽量小,且考虑到特色景点游客的容纳量是普通景点的两倍:
p i 122(-p )+∑(p i -p )) min μ= (8) ∑10i =1、3、6、9、102i =2、、45、、78
衡量方案是否最有的函数——均衡程,即方案中6 个套餐的平均路程与10个景点的客流量方差之积,在较优的解中均衡程应尽量小:
将上述条件在LINGO 中运行,得到结果表5(程序见附录二):
表5
六、模型的优缺点
1、对模型一 优点
1、本文思路清晰,模型恰当,得出的方案合理且符合题中的要求。 2、本文成功的使用了Floyd 算法以及插入点矩阵,追溯法和0—1变量,使模型的建立和编程得以顺利进行;
3、通过假设2回避了程序求解给出的答案中可能出现的景点相同、游览顺序不同的雷同旅游套餐,更贴近实际情况。
缺点
1、问题一由于数据庞大,对程序的要求很高,尽管经过了检验,但结果依然比较粗糙,有待进行进一步的改进。 2、此模型的求解要用到0-1规划并要熟悉掌握Floyd 算法原理,对程序的正确编写要求较高。
3. 在建立利用方差衡量模型中景点的均衡问题时未考虑到其他因素对景点的游客的影响。例如在实际问题中必须考虑的游览时间顺序问题,同一时间过多旅游套餐集中在一个景点可能会导致景点游客过多。在此模型之中不能解决这种问题,所以此模型考虑有欠周全。 2、对模型二 优点
1、用方差约束目标函数的方法来求解使各景点游客量均衡的问题,用
离散程度来刻画均衡。此模型简便易用。
2、合理假设,目标函数、景点客流量、(套餐比例关系明显,)体现
出各种变量对模型结果的影响,表达式简单,使得整个模型简单有效。
缺点
1、实际问题中必须考虑的游览时间顺序问题,同一时间过多旅游套餐
集中在一个景点可能会导致景点游客过多。在此模型之中不能解决这种问题,所以此模型考虑有欠周全。
2、在模型求解的过程中,根据此模型的变量约束条件不能直接的得出
最后的6种套餐,必须再采用一定量的数据处理,这是由于我们的程序不够完善导致的。
七、模型的推广
1、对模型一
通过对题目的解读我们不难发现这是一类规划问题。我们建立了具有约束条件的线性规划模型运用Matlab 软件以及 Floyd算法以及追溯法求解其模型。这个模型不仅仅适用于旅游景点的路线选择问题,它对类似问题的求解都可以起到指导作用。
由于该模型具有很强的普适性,所以凡是涉及到最短路径时,选取最优方案都可以借鉴此模型。例如建筑物建设的选址问题,几个城市的铁路交通路线,战争时期的粮草运输,甚至全球贸易的物流中转站的最短路径都可以借鉴此模型来解决。 2、对模型二
首先应用0-1变量列出约束条件,然后用引入方差来衡量各景点的游客量均衡的方法,具有很强的可移植性和灵活性。可应用于解决道路资源利用的不均衡等优化问题。同时此模型可用来解决国家经济开发区的分布问题,发达城市、沿海地区、落后地区的人口分布,利于国家做出宏观调控,和经济发展。
参考文献
[1] 姜启源. 数学模型(第三版)[M]. 北京:高等教育出版社,1999.
[2] 韩中庚. 数学建模方法及其应用(第二版)[M]. 北京:高等教育出版社,2009.
[3] 谢金星 薛毅,(优化建模与LINDO/LINGO软件),北京:清华大学出版社,2005。
[4]王正东. 数学软件与数学实验(第二版),北京:科学出版社,2010
八、附录
附录一:
程序1:function[D,R]=floyd(a)
n=size(a,1); D=a
for i=1:n for j=1:n R(i,j)=j; end end R for k=1:n for i=1:n for j=1:n
if D(i,k)+D(k,j)
程序2:
a=[0 31.5 inf inf 19 inf inf inf inf inf ; 31.5 0 7.5 12.7 17 inf inf inf inf inf; inf 7.5 0 14.5 inf inf inf 17.6 inf 24.6; inf 12.7 14.5 0 6.8 10.8 16.8 11.2 inf inf ; 19 17 inf 6.8 0 7.8 inf inf inf inf ; inf inf inf 10.8 7.8 0 12.8 inf inf inf ; inf inf inf 16.8 inf 12.8 0 12.6 11.8 inf; inf inf 17.6 11.2 inf inf 12.6 0 18.6 11.6; inf inf inf inf inf inf 11.8 18.6 0 inf;
inf inf inf inf inf inf inf 11.6 inf 0;] [D,R]=floyd(a)
迭代结果:
输出:
D =
0 31.5000 Inf Inf 19.0000 Inf Inf Inf Inf Inf
31.5000 0 Inf Inf
Inf 7.5000 Inf 24.6000
Inf 12.7000 Inf Inf
19.0000 17.0000 Inf Inf
Inf Inf Inf Inf
Inf Inf 11.8000 Inf
Inf Inf 18.6000 11.6000
Inf Inf 0 Inf
Inf Inf Inf 0 R =
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 k = 1 D =
0 31.5000 Inf Inf
31.5000 0 7.5000 0 Inf Inf Inf 17.6000 Inf 24.6000 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 Inf 7.5000 12.7000 17.0000 14.5000 Inf 0 6.8000 6.8000 0 10.8000 7.8000 16.8000 Inf Inf Inf Inf Inf Inf 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 Inf 19.0000 12.7000 17.0000 Inf Inf 10.8000 7.8000 0 12.8000 Inf Inf Inf 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 Inf Inf Inf Inf 16.8000 Inf 12.8000 0 11.8000 Inf Inf Inf Inf 17.6000 11.2000 Inf Inf 12.6000 0 18.6000 11.6000 Inf Inf
14.5000 11.2000 12.6000
Inf Inf
Inf 7.5000 0 14.5000 Inf Inf Inf 17.6000 Inf 24.6000
Inf 12.7000 14.5000 0 6.8000 10.8000 16.8000 11.2000 Inf Inf
19.0000 17.0000 Inf 6.8000 0 7.8000 Inf Inf Inf Inf
Inf Inf Inf 10.8000 7.8000 0 12.8000 Inf Inf Inf
Inf Inf 11.8000 Inf
Inf Inf 18.6000 11.6000
Inf Inf 0 Inf
Inf Inf Inf 0 R =
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 k = 2 D =
0 31.5000 Inf Inf
31.5000 0 Inf Inf
39.0000 7.5000 Inf 24.6000
44.2000 12.7000 Inf Inf
19.0000 17.0000 Inf Inf
Inf Inf Inf Inf
Inf Inf Inf 17.6000 Inf 24.6000 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 39.0000 7.5000 0 14.5000 24.5000 Inf Inf 16.8000 Inf Inf Inf Inf Inf Inf 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 44.2000 19.0000 12.7000 17.0000 14.5000 24.5000 0 6.8000 6.8000 0 10.8000 7.8000 16.8000 Inf 12.8000 Inf Inf Inf 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 Inf Inf Inf 10.8000 7.8000 0 12.8000 0 11.8000 Inf Inf Inf Inf 16.8000 Inf 12.8000 0 12.6000 0 18.6000 11.6000 Inf Inf 17.6000 11.2000 Inf Inf 12.6000
11.2000 12.6000
11.8000 Inf
Inf Inf 17.6000 11.2000 Inf Inf 12.6000 0 18.6000 11.6000
Inf Inf Inf Inf Inf Inf 11.8000 18.6000 0 Inf
Inf Inf 24.6000 Inf Inf Inf Inf 11.6000 Inf 0 R =
1 2 2 2 5 6 7 8 9 10 1 2 3 2 2 3 2 2 3 1 2 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 k = 3 D =
0 31.5000 Inf 63.6000
31.5000 0 Inf 32.1000
39.0000 7.5000 Inf 24.6000
44.2000 12.7000 Inf 39.1000
19.0000 17.0000 Inf 49.1000
Inf Inf Inf Inf
Inf Inf 11.8000 Inf
56.6000 25.1000 18.6000 11.6000
Inf Inf 0 Inf
63.6000 32.1000 Inf 0 R =
1 2 2 1 2 3 4 5 4 2 4 5 4 5 4 5 4 5 4 5 4 5 4 5 39.0000 7.5000 0 14.5000 24.5000 Inf Inf 17.6000 Inf 24.6000 2 5 4 5 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 44.2000 19.0000 12.7000 17.0000 14.5000 24.5000 0 6.8000 6.8000 0 10.8000 7.8000 16.8000 Inf 11.2000 42.1000 Inf Inf 39.1000 49.1000 6 7 2 6 7 3 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 Inf Inf Inf 10.8000 7.8000 0 12.8000 Inf Inf Inf 9 2 9 3
Inf Inf Inf 16.8000 Inf 12.8000 0 11.8000 Inf 56.6000 25.1000 17.6000 11.2000 42.1000 Inf 12.6000 0 18.6000 11.6000 12.6000
2 2 3 4 2 6 7 8 9 10 2 2 3 4 5 6 7 8 9 3 1 2 2 4 5 6 7 2 9 2 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 3 3 4 3 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 3 3 3 3 6 7 8 9 10 k = 4 D =
0 31.5000 Inf 63.6000
31.5000 0 Inf 32.1000
39.0000 7.5000 Inf 24.6000
44.2000 12.7000 Inf 39.1000
19.0000 17.0000 Inf 45.9000
55.0000 23.5000 Inf 49.9000
61.0000 29.5000 11.8000 55.9000
55.4000 23.9000 18.6000 11.6000
Inf Inf 0 Inf
63.6000 32.1000 Inf 0 R =
1 2 2 1 2 3 2 2 3 2 2 3 1 2 4 4 4 4 4 4 4 4 4 3 1 2 3 3 3 3 k = 5
39.0000 7.5000 0 14.5000 21.3000 25.3000 31.3000 17.6000 Inf 24.6000 2 5 4 5 4 4 4 5 4 5 4 5 4 4 4 4 4 5 3 3 44.2000 19.0000 12.7000 17.0000 14.5000 21.3000 0 6.8000 6.8000 0 7.8000 23.6000 11.2000 18.0000 Inf Inf 39.1000 45.9000 2 2 2 4 4 4 4 4 8 6 7 8 6 4 4 6 7 4 6 7 8 4 7 8 6 7 8 3 3 8 55.0000 61.0000 23.5000 29.5000 25.3000 31.3000 10.8000 16.8000 7.8000 23.6000 0 12.8000 12.8000 0 22.0000 12.6000 Inf 11.8000 49.9000 55.9000 9 2 9 3 9 10 9 3 9 4 9 4 9 4 9 10 9 10 9 10 55.4000 23.9000 17.6000 11.2000 18.0000 22.0000 12.6000 0 18.6000 11.6000 10.8000 16.8000
D =
0 31.5000 39.0000 25.8000 19.0000 26.8000 42.6000 37.0000 Inf 63.6000
31.5000 0 7.5000 12.7000 17.0000 23.5000 29.5000 23.9000 Inf 32.1000
39.0000 7.5000 0 14.5000 21.3000 25.3000 31.3000 17.6000 Inf 24.6000
25.8000 12.7000 14.5000 0 6.8000 10.8000 16.8000 11.2000 Inf 39.1000
19.0000 17.0000 Inf 45.9000
26.8000 23.5000 Inf 49.9000
42.6000 29.5000 11.8000 55.9000
37.0000 23.9000 18.6000 11.6000
Inf Inf 0 Inf
63.6000 32.1000 Inf 0 R =
1 2 2 1 2 3 2 2 3 5 2 3 1 2 4 5 4 4 4 4 4 4 4 3 1 2 3 3 3 3 k = 6 D =
0 31.5000 Inf 63.6000
31.5000 0 Inf 32.1000
39.0000 7.5000 Inf 24.6000
25.8000 12.7000 Inf 39.1000
19.0000 17.0000 21.3000 25.3000 31.3000 17.6000 Inf 24.6000 5 5 4 5 4 4 4 5 4 5 4 5 4 4 4 4 4 5 3 3 39.0000 7.5000 0 14.5000 21.3000 6.8000 0 10.8000 7.8000 16.8000 23.6000 11.2000 18.0000 Inf Inf 39.1000 45.9000 5 5 5 4 4 4 4 4 8 6 7 8 6 4 4 6 7 4 6 7 8 4 7 8 6 7 8 3 3 8 25.8000 19.0000 12.7000 17.0000 14.5000 21.3000 0 6.8000 6.8000 0 7.8000 0 12.8000 22.0000 Inf 49.9000 9 2 9 3 9 10 9 3 9 4 9 4 9 4 9 10 9 10 9 10 26.8000 23.5000 25.3000 10.8000 7.8000 23.6000 12.8000 0 12.6000 11.8000 55.9000 39.6000 29.5000 31.3000 16.8000 20.6000 18.0000 22.0000 12.6000 0 18.6000 11.6000 37.0000 23.9000 17.6000 11.2000 18.0000
Inf 45.9000
26.8000 23.5000 25.3000 10.8000 7.8000 0 12.8000 22.0000 Inf 49.9000
39.6000 29.5000 31.3000 16.8000 20.6000 12.8000 0 12.6000 11.8000 55.9000
37.0000 23.9000 17.6000 11.2000 18.0000 22.0000 12.6000 0 18.6000 11.6000
Inf Inf Inf Inf Inf Inf 11.8000 18.6000 0 Inf
63.6000 32.1000 Inf 0 R =
1 2 2 1 2 3 2 2 3 5 2 3 1 2 4 5 4 4 6 4 4 4 4 3 1 2 3 3 3 3 k = 7 D =
0 31.5000 51.4000 63.6000
31.5000 0 41.3000 32.1000
39.0000 7.5000 43.1000 24.6000
25.8000 12.7000 28.6000 39.1000
19.0000 17.0000 32.4000 45.9000
26.8000 23.5000 24.6000 49.9000
39.6000 29.5000 11.8000 55.9000
37.0000 23.9000 18.6000 11.6000
51.4000 41.3000 0 67.7000
63.6000 32.1000 24.6000 5 5 4 5 4 4 4 5 4 5 4 5 4 6 4 4 4 5 3 3 39.0000 7.5000 0 14.5000 21.3000 25.3000 31.3000 17.6000 43.1000 24.6000 39.1000 45.9000 5 5 5 4 4 4 4 4 8 6 7 8 6 6 4 6 7 4 6 7 8 4 7 8 6 7 8 3 3 8 25.8000 19.0000 12.7000 17.0000 14.5000 21.3000 0 6.8000 6.8000 0 7.8000 20.6000 11.2000 18.0000 28.6000 32.4000 39.1000 45.9000 49.9000 9 2 9 3 9 10 9 3 9 4 9 4 9 4 9 10 9 10 9 10 26.8000 23.5000 25.3000 10.8000 7.8000 0 12.8000 22.0000 24.6000 49.9000 55.9000 39.6000 29.5000 31.3000 16.8000 20.6000 12.8000 0 11.8000 55.9000 11.6000 37.0000 23.9000 17.6000 11.2000 18.0000 22.0000 12.6000 0 18.6000 11.6000
10.8000 16.8000 12.6000
67.7000 0 R =
1 2 2 5 5 5 5 5 5 2 1 2 3 4 5 4 4 4 4 3 2 2 3 4 4 4 4 8 4 10 5 2 3 4 5 6 7 8 7 3 1 2 4 4 5 6 6 4 6 4 5 4 4 4 5 6 7 4 7 4 6 4 4 4 6 6 7 8 9 4 4 4 3 7 7 7 3 3 3 k = 8 D =
0 31.5000 51.4000 48.6000
31.5000 0 41.3000 32.1000
39.0000 7.5000 36.2000 24.6000
25.8000 12.7000 28.6000 22.8000
19.0000 17.0000 32.4000 29.6000
26.8000 23.5000 24.6000 33.6000
39.6000 29.5000 11.8000 24.2000
37.0000 23.9000 18.6000 11.6000
51.4000 41.3000 0 30.2000
48.6000 32.1000 30.2000 0 R =
1 2 2 1 2 3 2 2 3 5 2 3 1 2 4 5 4 4 6 4 8 4 4 3 4 4 7 7 3 3 39.0000 7.5000 0 14.5000 21.3000 25.3000 30.2000 17.6000 36.2000 24.6000 5 5 4 5 4 4 4 5 4 5 4 5 4 6 4 4 4 7 8 7 7 8 3 3 8 25.8000 19.0000 12.7000 17.0000 14.5000 21.3000 0 6.8000 6.8000 0 7.8000 20.6000 11.2000 18.0000 28.6000 32.4000 22.8000 29.6000 5 5 5 4 4 4 4 8 8 6 7 8 6 6 4 6 7 4 6 7 8 4 7 8 9 10 9 7 3 10 26.8000 39.6000 23.5000 29.5000 25.3000 30.2000 10.8000 16.8000 7.8000 20.6000 0 12.8000 12.8000 0 22.0000 12.6000 24.6000 11.8000 33.6000 24.2000 5 5 4 3 8 10 7 8 6 4 7 4 9 8 9 10
37.0000 23.9000 17.6000 11.2000 18.0000 22.0000 12.6000 0 18.6000 11.6000 10.8000 16.8000
7 7 8 7 7 7 7 8 9 8 8 3 3 8 8 8 8 8 8 10 k = 9 D =
0 31.5000 39.0000 25.8000 19.0000 26.8000 39.6000 37.0000 51.4000 48.6000
31.5000 0 7.5000 12.7000 17.0000 23.5000 29.5000 23.9000 41.3000 32.1000
39.0000 7.5000 36.2000 24.6000
25.8000 12.7000 28.6000 22.8000
19.0000 17.0000 32.4000 29.6000
26.8000 23.5000 24.6000 33.6000
39.6000 29.5000 11.8000 24.2000
37.0000 23.9000 18.6000 11.6000
51.4000 41.3000 0 30.2000
48.6000 32.1000 30.2000 0 R =
1 2 2 1 2 3 2 2 3 5 2 3 1 2 4 5 4 4 6 4 8 4 4 3 7 7 8 8 3 3 k = 10 D =
0 31.5000 51.4000 48.6000
31.5000 0 41.3000 32.1000
39.0000 7.5000 0 14.5000 21.3000 25.3000 30.2000 17.6000 36.2000 24.6000 5 5 4 5 4 4 4 5 4 5 4 5 4 6 4 4 7 7 8 8 39.0000 7.5000 0 14.5000 21.3000 0 6.8000 6.8000 0 7.8000 20.6000 11.2000 18.0000 28.6000 32.4000 22.8000 29.6000 5 5 5 4 4 4 4 8 8 6 7 8 6 6 4 6 7 4 6 7 8 4 7 8 7 7 8 8 8 8 25.8000 19.0000 12.7000 17.0000 14.5000 21.3000 25.3000 30.2000 10.8000 16.8000 7.8000 20.6000 0 12.8000 12.8000 0 22.0000 12.6000 24.6000 11.8000 33.6000 24.2000 5 5 4 3 8 10 7 8 6 4 7 4 9 8 9 10 9 8 8 10 26.8000 39.6000 23.5000 29.5000 25.3000 30.2000 17.6000 11.2000 18.0000 22.0000 12.6000 0 18.6000 11.6000 37.0000 23.9000 17.6000
10.8000 16.8000
36.2000 24.6000
25.8000 12.7000 14.5000 0 6.8000 10.8000 16.8000 11.2000 28.6000 22.8000
19.0000 17.0000 21.3000 6.8000 0 7.8000 20.6000 18.0000 32.4000 29.6000
26.8000 23.5000 25.3000 10.8000 7.8000 0 12.8000 22.0000 24.6000 33.6000
39.6000 29.5000 30.2000 16.8000 20.6000 12.8000 0 12.6000 11.8000 24.2000
37.0000 23.9000 18.6000 11.6000
51.4000 41.3000 0 30.2000
48.6000 32.1000 30.2000 0 R =
1 2 2 1 2 3 2 2 3 5 2 3 1 2 4 5 4 4 6 4 8 4 4 3 7 7 8 8 3 3 D =
0 31.5000 51.4000 48.6000
31.5000 0 41.3000 32.1000
39.0000 7.5000 36.2000 24.6000
25.8000 12.7000 28.6000 22.8000
19.0000 17.0000 32.4000 29.6000
26.8000 23.5000 24.6000 33.6000
39.6000 29.5000 11.8000 24.2000
37.0000 23.9000 18.6000 11.6000
51.4000 41.3000 17.6000 36.2000 24.6000 5 5 4 5 4 4 4 5 4 5 4 5 4 6 4 4 7 7 8 8 39.0000 7.5000 0 14.5000 21.3000 25.3000 30.2000 17.6000 36.2000 11.2000 18.0000 28.6000 32.4000 22.8000 29.6000 5 5 5 4 4 4 4 8 8 6 7 8 6 6 4 6 7 4 6 7 8 4 7 8 7 7 8 8 8 8 25.8000 19.0000 12.7000 17.0000 14.5000 21.3000 0 6.8000 6.8000 0 7.8000 16.8000 20.6000 11.2000 18.0000 28.6000 32.4000 22.0000 12.6000 24.6000 11.8000 33.6000 24.2000 5 5 4 3 8 10 7 8 6 4 7 4 9 8 9 10 9 8 8 10 26.8000 39.6000 23.5000 29.5000 25.3000 30.2000 10.8000 16.8000 7.8000 20.6000 0 12.8000 12.8000 0 22.0000 12.6000 24.6000 11.8000 0 18.6000 11.6000 37.0000 23.9000 17.6000 11.2000 18.0000 22.0000 12.6000 0 18.6000 10.8000
0 30.2000
48.6000 32.1000 24.6000 22.8000 29.6000 33.6000 24.2000 11.6000 30.2000 0 R =
1 2 2 5 5 5 5 5 5 5 1 2 3 4 5 4 4 4 4 3 2 2 3 4 4 4 8 8 8 10 5 2 3 4 5 6 7 8 7 8 1 2 4 4 5 6 6 4 6 4 5 4 4 4 5 6 7 4 7 6 4 8 4 6 6 7 8 9 4 4 3 4 4 4 7 8 9 7 7 8 7 7 7 7 8 9 >> 附录二:
model: sets:
person/1..10/; position/1..10/;
link(person,position):s,j; endsets data:
s=0,31.5,1000,1000,19,1000,1000,1000,1000,1000, 31.5,0,7.5,12.7,17,1000,1000,1000,1000,1000, 1000,7.5,0,14.5,1000,1000,1000,17.6,24.6,1000, 1000,12.7,14.5,0,6.8,10.8,16.8,11.2,1000,1000, 19,17,1000,6.8,0,7.8,1000,1000,1000,1000, 1000,1000,1000,10.8,7.8,0,12.8,1000,1000,1000, 1000,1000,1000,16.8,1000,12.8,0,12.6,11.8,1000, 1000,1000,17.6,11.2,1000,1000,12.6,0,18.6,11.6, 1000,1000,1000,1000,1000,1000,11.8,18.6,0,1000, 1000,1000,24.6,1000,1000,1000,1000,11.6,1000,0; enddata
min=@sum(link:s*j);
4 8 10 8
x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=4; x1+x3+x6+x9+x10=2; x1+x6