Mathematical modeling -- the laying of water pipes

Description of water pipe laying problem

During the implementation of the water supply project for every village , From the perspective of ensuring the quality of water supply and convenient equipment maintenance , A central water supply station needs to be built in a certain area ,12 A primary water supply station and 168 Two secondary water supply stations , The location coordinates of water supply stations at all levels are shown in the annex table 1 Shown , The type A It means central water supply station , type V Represents the primary water supply station , type P It is a secondary water supply station . Attachment diagram 1 It is the geographical location map of water supply stations at all levels .

Now the central water supply station A The tap water at is transmitted to the primary water supply station and the secondary water supply station through pipelines . According to the design requirements , From the central station A The pipeline laid to the primary water supply station is I Type pipe , The pipeline laid from the primary water supply station to the secondary water supply station is II Type pipe .

The technical requirements for the laying of water pipes are as follows ：

• 1. The central water supply station can only be connected with the primary water supply station （ layout I Type pipe ）, It cannot be directly connected to the secondary water supply station , But the primary water supply stations can be connected （ layout I Type pipe ）.
• 2. The primary water supply station can be connected with the secondary water supply station （ layout II Type pipe ）, And the secondary water supply stations can also be connected （ layout II Type pipe ）.
• 3. The connecting pipes between water supply stations at all levels must start from the location coordinates of the upper water supply station or the same water supply station , Do not connect from a point in the middle of any pipe .
• 4. Between two adjacent water supply stations （ If there are pipes connected ） The required pipe length can be simplified as Euclidean distance .

Please combine the above pipe laying requirements , Mathematical modeling , Complete the following questions

• problem 1： From the central water supply station A set out , How to lay the water pipeline to minimize the total mileage of the pipeline ？ The laying scheme is given in figures , And give I Type pipe and II Total mileage of type I pipeline .
• problem 2： because II The market supply of type a pipeline is insufficient , There is an urgent need to reduce the number of II Total mileage of type I pipeline , The preliminary plan is to upgrade two secondary water supply stations to primary water supply stations . Ask which two secondary water supply stations to choose , How should the water pipe be laid so that it can be laid II The total mileage of type a pipeline is at least ？ Relative problem 1 The plan ,II How many kilometers has the total mileage of type a pipeline been reduced ？
• problem 3： In question 1 On the basis of , If in reality, due to the influence of power , The pipeline laid from the primary water supply station can only supply water at most 40 km （ It is calculated according to the total mileage of pipeline transmission from the primary water supply station ）, But from the central water supply station A The water supply of the pipeline laid from the start is not limited by this distance . In order to supply water to all water supply stations , Several secondary water supply stations need to be upgraded to primary water supply stations , However, the pipeline laid from the water supply station after upgrading can only supply water at most 40 km . Ask how many secondary water supply stations to upgrade at least , It can supply water to all water supply stations ？ How many kilometers is the minimum total mileage of laying pipelines under this configuration ？
• 

Modeling ideas and scheme design

Symbol description

Problem one analysis

For question 1 , The minimum total mileage of the pipeline laid from the central water supply station in the demand solution , Transform it into a minimum spanning tree problem (MST problem ) To solve the . This article takes Prim Algorithm , Take the water station as the node , The distance between water stations is used as the weight of edges , Solve the minimum spanning tree of the total mileage of the pipeline . The global optimal solution without hierarchy should not be considered here , That is, the primary water supply station and the secondary water supply station are the same nodes , Some tap water will be transmitted from the secondary water supply station to the primary water supply station or the tap water will converge , This distribution does not form circulation , And it does not conform to the distribution of dendritic pipes in real life . Requirements of problem-based design , Adopt the dendritic form with less pipeline mileage to design the pipeline laying , First consider the pipeline from the central water supply station to each primary water supply station , Then consider the pipeline from the primary water supply station to each secondary water supply station , That is, first determine I The minimum spanning tree of a pipeline , To determine the II The minimum spanning tree of a pipeline .

Question 1 Results

Question two

Results show ...

Code

...