大学生计划

问题的优化模型

摘 要

本文针对地面搜索过程中人员安排和路线选择问题，建立了优化模型，并给出了相应算法，用LINGO软件编程，在确保所有地点都不遗漏且不重复的情况下，合理安排人员和线路，使得搜索用时最短。

问题二的求解中，首先对50名人员分3组进行分析，由于矩形区域被分割后形成的小区域恰好能被20人组成的一个队列一次搜索覆盖，以及10人组成的一个队列一个来回的搜索覆盖，于是3组可分为：2个队伍为20人，1个队伍为10人。随后进行队伍搜索区域的划分，根据各个队伍人数确定该组分配到的方格的数量，划分出各个队伍的搜索区域。然后对三个区域进行搜索路径的优化求解，改进问题一的模型，求出三个区域的搜索路径。再根据实际情况，对路径进行适当修改，得出20人的2个队伍，需要19.816小时，10人的队伍需要20.294小时。根据先完成搜索任务的队伍能否有足够的时间来帮助未完成搜索任务的队伍提早完成任务的时间要求，判断出该解是可以接受的。于是得到50人进行搜救的时间为20.294小时。

最后，对文中的模型进行了优缺点的分析。

关键词：搜索模型；最优路径；一笔画；遍历网格；转弯策略

一、问题重述

1．假定有一支20人一组的搜索队伍, 拥有1台卫星电话。请设计一种你认为耗时最短的搜索方式。按照你的方式，搜索完整个区域的时间是多少? 能否在48小时内完成搜索任务? 如果不能完成，需要增加到多少人才可以完成。

2．为了加快速度，搜索队伍有50人，拥有3台卫星电话，分成3组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计一种你认为耗时最短的搜索方式。按照你的搜索方式, 搜索完整个区域的时间是多少?

二、模型假设

1

1.假设搜索必须完全，不存在遗漏情况。

2.假设如果发现需要救助的人员，只需报告组长，不影响其搜索速度。 3.假设救援人员进食休息的时间不计。 4.队员间不能间接向组长报告情况。 5.假设每组队员只能向本组组长报告。 6.假设队员的身体和心理状态不影响进度。 7.假设搜索区域地面状况不影响搜索速度。 8.假设设备在搜索过程中都正常工作。

三、 符号说明

s 20人排成队列的长度 n 增加的人数

v1 不搜索时候行进的速度 v2 搜索时候行进的速度

t 搜索需要花费的时间 ti 搜索时间的各个组成部分 Ai 表示矩形分割后的区域的标号

Ai,j 表示标号为i的区域的各个方向的连接数 T1 表示1个180度转弯需要多耗费的时间 T2 表示1个90度转弯需要多耗费的时间

四、问题分析

本题针对一块矩形区域进行全境搜索问题,在保证全部搜索到的情况下，使搜索时间最短，我们将20人看成排成一排的整体,并将大的矩形区域划分为126个以800米为边长的正方形小区域，根据图论中的一笔画问题,以转弯最少为约束条件进行LINGO编程，计算出搜索路径.当队伍增加为3时，先根据人数比例进行大体的区域划分，然后在根据问题1的求解方法，计算出三个队的最优路径。

五、模型的建立与求解

2

5.1 求解问题一

5.1.1建立队伍前进和转弯模型：

由于每个搜索队员的搜索半径为20米，为了简化模型，把20名搜索队员排成一条直线，其中队长处于中间，这样就更好的保证了队员与队长的通讯：

共20个 总长为800米

图(1-1)

搜索时候可以把20人组成的队列看作一条长800米的直线，搜索方向是沿着直线的垂线的方向，直线行进的速度为搜索的速度。如下图所示，直线向其垂线方向进行时，会形成一个矩形轨迹，见图(1-2)。

移动方向

800米

图(1-2)

但需要进行转弯时，分为2种情况，180度转弯和90度转弯： 1、180度转弯：

图(1-3)

如图(1-3)所示，原直线沿着AB 边向右移动，当到达CD边时，整体向上移动，使得原CD边与EC边重合，然后EC边继续向左边运动，搜索遇难人员。 由 T1?s得，T1?666.67s?0.185h

v1 即过180度的弯需要多耗费0.185h的时间

3

2、90度转弯

o

A B

C D

图(1-4)

如图(1-4)所示，原直线沿着AB 边向右移动，当到达CD边时，直线上处于C点的人向O点运动，D点上的人向C点运动，点，直线中间的人员依然可以找到合适的路径向OC边移动，使得CD与CO重合，然后CO边继续向上边运动，搜索遇难人员。

容易得出，该调整过程也需要0.185h的时间，即由以上2个转弯模型，可以得出，转弯的时间为T?0.185h

5.1.2建立搜索路线模型：

如表(1-1)所示，把矩形区域划分为如下小块，并且标号为：Ai

表(1-1) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 根据图论中关于奇顶点个数为偶数就能一次走完全程而不重复行走的原理，判断出这些方格可以用一条不重复的线路走完。

4

由于出发点在矩形区域中央，即A63和A64交线的中点处，设定搜索队首先进入A64区域，然后在搜索完全部区域后，最后回到A57，过程是一笔画成的，没有重复，由于在转弯时，需要额外花费时间来进行调整，所以，当转弯数为最少时，是该题目的最优解答。 如表(1-1)可以看出：矩形中的各个小区域在前后左右有另外的小区域与其相邻（边界的区域较特殊，可能某个方向没有相邻的区域）。把各个小区域看成一个点，如果要进行一笔画，则除了开始点A64只有一个出口和结束点A57只有一个入口，每个点均有两个接口与其他区域连接。

（1）一个点有上下左右四个方向，用字母Aij表示Ai这个点在j方向上是否

2，3，4分别表示上下左右四个方向。与其它点连接，1为连接，0为不连接，j?1，

以2个特殊的点为例，如：

A1点：由于在顶角，则其上边和左边必定没有连接，所以，A1， 1?0，A1，3?0。 A114点：由于在下边沿，则其下边必定没有连接，所以A114，2?0 全面的表示出这些点的特征，表达式为：

Ai,1?0 ；i?1...14 Ai,２?0 ；i?113...126

Ai,3?0 ；i?1，15，29，43，57，71，85，99，113 Ai,4?0 ；i?14，28，42，56，70，84，98，112，126

（2）由于每个点的连接个数只能为2个（A57A64除外）， 所以

?Aj?14i,j64 ?2，i?1...126，且i?57，

（3）如果有2个点，一个点的左边与另一个点连接，则另一个点的右端必定与该点连接。基于这个原则，得到如下表达式：

Ai,1?Ai?14,2 ， i?15...126 Ai,3?Ai?1,4 ， i?2...126

（4）为了判定在一个点处是否转弯，只要判定该点的2个接口是否为上和

下，或者左和右，当一个为上，一个为下，可以说明该点处不转弯；当一个为左，一个为右，也可以说明该点处不转弯。 用表达式来表示如下：

5

当Ai,1?Ai,2?Ai,3?Ai,4?1时，为不转弯。

根据以上（1）（2）（3）（4）四点，可以转化为一个优化问题的求解。

目标函数：

max??Ai,1Ai,2?Ai,3Ai,4

i?1126约束条件：

Ai,1?0 ；i?1，2?14 Ai,２?0 ；i?113，114?126 Ai,3?0 ；i?1，15，29，43，57，71，85，99，113 Ai,4?0 ；i?14，28，42，56，70，84，98，112，126

?Aj?14i,j64 ?2，i?1...126，且i?57，4?Aj?1i,j?1 ，i?57，64

Ai,1?Ai?14,2 ， i?15，16?126 Ai,3?Ai?1,4 ， i?2，3?126

用LINGO编写程序（见附录），可以得到Ai对应的上下左右四个方向是否有连接的数据，根据数据可以表示出其路线图。

为了方便观看，用线路图表示路线如图(1-5):

6

图(1-5)

如图(1-5)可知，通过LINGO软件解决了不重复和弯角最小的问题，可是其没有解决一笔画问题，在图中出现了一个闭合的路径，不和其他路径进行相连接，由于程序为我们解决了不重复和弯角最小的问题，我们如果进行适当的微调，对最优结果的影响是很微小的。观察图形，对那个闭合路径进行修改，使得他和其他路径相连接。

对图像的调整结果如下：

图（1-6）

如图(1-6)所示该路线经过了所有的区域，一共需要转弯17个，则转弯所需的时间为t1?17T?3.15s

除转弯外的时间外，其余时间设都为搜索前进，为 t2?126sv2得，

7

t2?168000s?46.667h

由于在开始搜索时，所有队员都处在矩形区域中央，即A64左边沿的中点处，为了让队员排列成一条直线，则所有队员向两边散开，使其均匀分布在A64左边沿，这一过程需要耗费的时间为t3?0.5sv1得，t3?333.33s?0.093h

在搜索结束时候，所有队员都均匀分布在A57的下边沿，为了让他们到达集

5s合地点（A57的左边沿的中点），需要耗费的时间为t4?2t4?745.36s?0.207h 则

t??ti?50.117h

i?14v1得，

所以搜索完整个区域的时间是50.117小时，不能在48小时内完成搜索。

5.1.3建立增加人数的模型

为了满足能够在48小时内搜索完成搜索任务，决定增加人数为n，这n个人的作用就是为了帮助原20个人的队伍分担部分搜索区域，来达到原20人的队伍能在48小时内完成搜索任务的目的。

队伍搜索区域的时间包括t1，t2，t3，t4，其中t2?46.667h是最有可能进行优化的数据，也是可以减少幅度最大的时间因素。让增加的n个人在这段时间里发挥作用，来减少t2。

建立模型：只考虑队员搜索所有路线的时间t2，由于不转弯所以队员行进路线可视为一条直线。把原20人和新增加的n个人分为2个队伍，只要n个人的队伍离原20人的队伍距离不超过1000米，就可以和组长保持连续，但两队伍的搜索是独立完成的。

A B C D E

8

图（1-7）

如图(1-7)，可以把行进路线分割为一大一小交替的段落。其中A为原20人队伍搜索的区域，B为增加的n个人队伍趁着原20人队伍在搜索A区域时，以速度v1移动过去搜索的路线。当原20人队伍搜索完A时，要继续搜索C区域，可以速度v2经过B区域，此时n个人的队伍又以速度v1移动到D，如此交替。 可以发现，总共搜索节约的时间，就是20 人队伍以速度v1穿过B，D所节省的时间，且节约的时间为原来大部队经过B，D时间的一半。

得到方程：

2(t?48)n ?t220，取整，得到n?2 解得n?1.81 因此，如果想在48小时内完成搜索应该增加2个搜索队员。

5.2 求解问题二

由问题一的选择路径模型可知，需要搜索的矩形区域长和宽可以被20人组成的直线的长度整除，也可以被10人组成的直线的长度整除，为了便于计算和工作安排，我们做如下设定：

1.把50人分为三组，人数分别为20、20、10人； 2.为了使搜索所用时间最短，则三组所用时间相等；

3.在不考虑转弯时间的条件下，如问题一所示，把矩形区域分为126个区域由于最终所有队伍必须回到一点，所以除去该点所在的区域，三队分得的区域个数为为50，50，25时时间最短。

如图(2-1)，分出了区域，上下两个图形块为20人搜索的面积，中间区域10个人队伍搜索的区域。

以上理论是理想化的图形，实际上要考虑转弯等因素，所以时间可能会不相同。 图(2-1) 如图(2-1)可知，上下两个区域是对称的，他们的搜索路径时相同的。而中间区域必须把每个小区域的边长变为400，才能利用问题一种的方法进行10人搜

9

索。

取出上边区域单独考虑，对方格标号如表(2-1)：

表(2-1) 1 2 3 4 5 6 7 8 9 10 15 29 43 16 30 17 31 18 32 19 33 20 34 21 35 22 36 44 23 37 45 24 38 46 11 25 39 47 12 26 40 48 13 27 41 49 14 28 42 50 对问题一中的模型进行修改： 目标函数：

max??Ai,1Ai,2?Ai,3Ai,4

i?150约束条件：

Ai,２?0 ；i?43...50 Ai,3?0 ；i?1，15，29 Ai,4?0 ；i?14，28，42，50

?Aj?14i,j44 ?2，i?1...50，且i?43，4?Aj?1i,j?1 ，i?43，44

Ai,1?Ai?14,2 ， i?15...43 Ai,1?Ai?18,2 ， i?44...50 Ai,3?Ai?1,4 ， i?2...42 Ai,3?Ai?1,4 ， i?45...50

通过LINGO编程(见附件：程序2)，在进行适当的路径调整后，得到

10

图(2-2)

由于中间区域的搜索队员的人数为10人,展开的长度为400米，于是把区域再划分为4个区域，得到如下区域表：

表(2-2) 对问题一中的模型进行修改得： 目标函数：

max??Ai,1Ai,2?Ai,3Ai,4

i?1100 约束条件：

Ai,1?0 ；i?1...12， 37...50 Ai,２?0 ；i?63...76，89...100 Ai,3?0 ；i?1，13，25，51，77，89 Ai,4?0 ；i?12，24，50，76，88，9100

?Aj?14i,j51 ?2，i?1...100，且i?37，4?Aj?1i,j?1 ，i?37，51

Ai,1?Ai?12,2 ， i?13...36 Ai,1?Ai?26,2 ， i?51...76

Ai,1?Ai?12,2 ， i?77...100

11

Ai,3?Ai?1,4 ， i?2...100

通过LINGO编程(见附件：程序3)，在进行适当的路径调整后，得到：

图(2-3)

由于在求中间区域时候，不可避 免的进行了较多的转弯，所以图(2-3)中“X”点处为没有进行分配的区域应该平均分给20人的2个队伍。

依然使用t?t1?t2?t3?t4来表示搜索某一区域的时间，其中t1，t2，t3，t4分别表示，转弯时间，搜索时间，开始搜索时候人员调配的时间，结束时候人员集合的时间。

t上?t1上?t2上?t3上?t4上＝0.925?18.613?0.093?0.185?19.816h t中?t1中?t2中?t3中?t4中＝1.388?18.5?20.09?30.29?320.29 4h t下?t上?19.81 6h由上述结果可以得出，20人的队伍在比10人的队伍早完成任务0.478h。

设定搜索上边区域和下边区域的队伍分别为第一、二队，搜索中间区域的为第三队。

如果第一队和第二队有必要帮助第三队完成搜索任务以缩短搜索时间，那么第一二两队和第三队完成任务相差时间必须大于已经结束搜索任务第一二队走出集结点所在的区域时刚好碰到中间的队伍完成搜索一起到集结点的时间，通过计算这段时间为0.555h，如果第一二队比第三队至少早完成搜索任务0.555h，才能帮助第三队减少任务时间。

由于第三队比第一二队晚完成搜索0.478h，小于0.555h小时，则没有必要再减少第三队的搜索时间，所以我们的方案是合理的。所以50个人分三组最少搜索时间是20.294h 。

六、优缺点分析

优点：划分为网格，确定了队员的大体移动方向，避免了无规则的移动，简

12

化了问题的求解。利用图论的判断了对搜索路线可以一笔画，在编写程序中避免了搜索过程中的重复搜索，节省了时间，

缺点：用LINGO程序求出的搜索路径不一定是最优解，只是一个较好的可行解。在考虑增加人数问题的处理上，没有考虑转弯时间的变化，导致求出的人数相对变小。

七、参考文献

[1] 姜启源，谢金星，《数学模型（第三版）》，北京：高等教育出版社，2003。 [2] 谢金星，薛毅，《优化建模与LINDO/LI NGO软件》，北京：清华大学出版社，

2005。 [3] 汤代焱，《运筹学》长沙：中南大学出版社，2002。 [4] 高隆昌，杨元，《数学建模基础理论》，北京：科学出版社，2007。

附录：

LINGO软件编程

sets:

num/1..126/:; fx/1..4/:; link(num,fx):A; endsets

MAX=@SUM(NUM(I):A(I,1)*A(I,2)+A(I,3)*A(I,4));

@sum(fx(j):A(64,j))=1; @sum(fx(j):A(57,j))=1;

@for(num(i)|(i#NE#64)#AND#(i#NE#57):@sum(fx(j):A(i,j))=2;); @FOR(link(i,j):A(i,j)<=1);

@FOR(LINK(I,J):@GIN(A(I,J));); @for(num(i)|I#LE#14:A(I,1)=0); @for(num(i)|I#GE#113:A(I,2)=0);

13

A(1,3)=0;A(15,3)=0;A(29,3)=0;A(43,3)=0; A(57,3)=0;A(71,3)=0;A(85,3)=0;A(99,3)=0; A(113,3)=0;

A(14,4)=0;A(28,4)=0;A(42,4)=0;A(56,4)=0; A(70,4)=0;A(84,4)=0;A(98,4)=0;A(112,4)=0; A(126,4)=0;

14

本文来源：https://www.bwwdw.com/article/dr77.html