美赛数模论文 - 图文

Team # 35565 Page 33 of 47

a1?a2???aN（Nis the number of planes meeting the precondition）

Step 2 Dinkelbach arithmetic

Equations can be worked out by using Dinkelbach arithmetic: first constructs an aux-iliary problem with parameters which have the same optimal solution of the model, and then through the iterative search method. The specific algorithm is as follow:

Assume that: f1?p0,f2?q0

f(x)??maxf(x)?1 ?f2(x) ?x?X?N??N X??x|x??0,1?,?xi?Qa,1?Qa?N? f1(x)?0,f2(x)?0

i?1??

Constructs an auxiliary problem with parameters which have the same optimal solu-tion of model:

?G(?)?maxg(x)?f1(x)??f2(x)?

x?X?

Then we can get the optimal solution:

x*?{xij?1,j?1,?,n;xij?0,i?n?1,?N},

Dinkelbach algorithm has been proved to be needing iteration times in the worst case

in solving model, so the algorithm can meet the needs of the actual according to cal-culate.

6.2 The Area Partition Algorithm

6.2.1 Preparation of the Model

? The area partition algorithm aims to scientifically assign searching resources

and enhance interloper ability. In practical searching process, scientists usually adopt polygon to establish search area. By using the global optimiza-

Team # 35565 Page 34 of 47

tion model, we can select some kind high quality searching plane and calcu-late the overarea of each plane.

? For arbitrary polygon, there exists kinds of polynomial time algorithm to di-vide the polygon into non-overlaping convex polygon. We name it as “CP” to for convenience.

For any two of the CP, CIk, CIj , if k < j, CIk is the forerunner of CIj, CIj is the successor of CIk. If CIk, CIj has a side in common, they are neighbor to each other. For CI, all the neighbor CP can be named as NextNeighbor(CI).

The set of vertex and anchor W(CI) number the point according to coun-ter-clockwise order. And the line segment (wn,w1) is the common between CI and its NextNeighbor(CI).

The polygon made up by CI and NextNeighbor(CI) is originated from CI. We name it as Poly(CI).

L = (Ls, Le) means the lie with two endpoint on the polygon. Ls is the start point of L, while Le is the end point. When both points begins to move, the moving range will be restricted by the anchor point of CI.

? and Lare the feasible moving range of Ls and Le.

6.2.2 Modeling

Conditions of the model:

?. Polygon I stands for the area to be searched, whose area is STThere will be N planes assigned to conduct the search and rescue work. The search ability of plane I isAii?(1,?,N), and it satisfys

a?Ai?1Nai?. ?STAll the search planes set off form initial point at full speed, and enter into the search area from a particular point Sk,k?{1,?,N}, we name it as CSP.

To perform the task quickly, the search planes carry out search work instantly when

arriving at CSP.

Team # 35565 Page 35 of 47

Considering overarea of searching plane and the position CSP, we can transform the problem into the following two cases:

Case 1: No search planes is in the search area the search begins.

Case 2: Some searching planes happen to be in the area the search begins.

6.2.3 Solution of the Model

Case 1: No search planes is in the search area at the beginning.

We can combine NonconvexDivide and DetachAndAssign algorithm to work out the best dispatch of coverage of the search area.

The cutting algorithm of arbitrary polygon I is on the basis of the scan lines. First, we cut I into

CIj,j?(1,?,i)

Then dealing with these parts to form a new and complete polygon Ii, Because CIj usually is not self-contained. So when Area(CIj) < AreaRequired

(S(CIj)), CIj needs to get some parts of area from its neighbor to increase itself.

When Area(CIj) < AreaRequired(S(CIj)), CIj needs to give some parts to his neighbor to decrease itself. In both cases, the unhandled parts in I should be connected.

The Nonconvex Divde algorithm is used to build scanning lines and cut the PredPoly() into two parts. The DetachAndAssign algorithm is used to distribute the two parts to the anchor or cut them when necessary [10]. We alternate the two algorithms to deal with each CP.

Case 2 Some planes happen to be in the area at the beginning.

When the search begins, the planes in the searching area can carry out search in time. The CSP of the planes are the initial position of them. We also need to assign searcing task to them according to the searching ability.

First, we should subdivide the search zone into CPs. And the CSP is in the edge of CP. We can see this from figure 10. This zone is a non-convex polygon that has 4 anchor point. S1S2 are in the edge while S3S4are inside.

Team # 35565 Page 36 of 47

Figure 10 sample of searching zone I

We subdivide I into four CPs (CI1 - CI4) to guaranteeS3 and S4 is in the boundary line of respectively. Thus we can use the method above to realize the subdivision of anchor area.

Figure 11 The subdivision of searching zone

6.2.4 Improvement of the Model

By alternating the two algorithms, we can make a reasonable allocation according to searching ability of each plane in order to cover the whole searching zone. Because subdividing arbitrary polygon is not necessarily a convex polygon. The new polygon is depending on the shape of the CPs and the position of the scanning lines.

When the shape of the zone keep unchanged, we can maximize the minimum angle. That is to adjust the interior angles on the same side by moving the scanning line.