Figure 1 shows well targets identified by ecologists in an offshore oil field. The wells are to be drilled from platforms that are very expensive to erect. To reduce the cost, several wells may be drilled from the same platform. The cost of a platform designed to drill k wells is ck To drill a set of wells, the platform is located at the centroid of the wells and directional drilling is used to reach each target. A platform cannot service more than 7 wells. The operational cost of drilling a well is a(h+d), where h is the horizontal distance from the platform location to the target, d is the depth and a is a constant. The depth is assumed to be constant over the field. ylkm) 1 2 3 02 6 x(km) 8 10 12 Figure 1: Well targets for offshore drilling The problem is to find the selection of platforms that permits the drilling of all 20 wells at minimum total cost. In solving this problem, we will assume that a = 1, d=0.5, and C, as given in the following table. Number of wells (1) 1 2 3 4 5 6 7 Platform cost (ck) 10 19 27 34 40 45 49 Specific values of h must be computed. To illustrate the computation of the cost of placing a platform, consider a platform that would serve wells 4, 5, and 6. The coordinates of the centroid are the average of the coordinates of the wells in the set. Since wells 4, 5, and 6 have coordinates (2,2), (3, 2), and (3, 3), respectively. The location of the centroid is (ae, y) = (8/3,7/3). To compute the distance between well 4 and the centroid, we use the Pythagorean theorem: ha = 4 - 2)2+(94 - y)2 = (2/3)2 + (1/3)2 0.745 Similarly, hs = 0.471 and he = 0.745. The cost of building the platform and drilling the wells is therefore as follows: Cs + aha+d)+ ahs + d)? + alhe+d) 31.044 1. Design a constructive heuristic that will provide a good quality solution to this problem. Make sure you describe the steps of your algorithm clearly. 2. Apply your algorithm to the numerical data given above and present the resulting solution. In answering this problem, you are allowed to use python, C, or matlab to implement your algorithm. You can also perform computations by hand. Figure 1 shows well targets identified by ecologists in an offshore oil field. The wells are to be drilled from platforms that are very expensive to erect. To reduce the cost, several wells may be drilled from the same platform. The cost of a platform designed to drill k wells is ck To drill a set of wells, the platform is located at the centroid of the wells and directional drilling is used to reach each target. A platform cannot service more than 7 wells. The operational cost of drilling a well is a(h+d), where h is the horizontal distance from the platform location to the target, d is the depth and a is a constant. The depth is assumed to be constant over the field. ylkm) 1 2 3 02 6 x(km) 8 10 12 Figure 1: Well targets for offshore drilling The problem is to find the selection of platforms that permits the drilling of all 20 wells at minimum total cost. In solving this problem, we will assume that a = 1, d=0.5, and C, as given in the following table. Number of wells (1) 1 2 3 4 5 6 7 Platform cost (ck) 10 19 27 34 40 45 49 Specific values of h must be computed. To illustrate the computation of the cost of placing a platform, consider a platform that would serve wells 4, 5, and 6. The coordinates of the centroid are the average of the coordinates of the wells in the set. Since wells 4, 5, and 6 have coordinates (2,2), (3, 2), and (3, 3), respectively. The location of the centroid is (ae, y) = (8/3,7/3). To compute the distance between well 4 and the centroid, we use the Pythagorean theorem: ha = 4 - 2)2+(94 - y)2 = (2/3)2 + (1/3)2 0.745 Similarly, hs = 0.471 and he = 0.745. The cost of building the platform and drilling the wells is therefore as follows: Cs + aha+d)+ ahs + d)? + alhe+d) 31.044 1. Design a constructive heuristic that will provide a good quality solution to this problem. Make sure you describe the steps of your algorithm clearly. 2. Apply your algorithm to the numerical data given above and present the resulting solution. In answering this problem, you are allowed to use python, C, or matlab to implement your algorithm. You can also perform computations by hand