a We now focus on the simpler uncapacitated fixed-charge facility location (UFL) problem. The attached Excel file "data49points.xls" contains the x- and y-coordinates of 49 points in a 10-by-10 square, each of which is both a demand point and a candidate location for facility construction. The Excel file also contains the facility construction cost and the demand at each point. The distance between any two points can be measured by the Euclidean metric. Suppose the costs are properly prorated such that the objective is to minimize (total facility costs) + 150*(total demand- distance). Complete the following tasks. Implement the Lagrangian relaxation solution algorithm to solve the UFL problem instance with these 49 points. You may relax any constraints from the problem. You may use any programming language of your choice (e.g., C++, C#, MATLAB, VBA). Please report the best solution (number and location of facilities) found, the remaining optimality gap (if any), the computation time, and the computer platform used. Please plot the convergence process (upper bound and the best lower bound) over iterations. Please also submit your algorithm source code. . B F H C D E F G 49 nodes in a 10 by 10 square fixed cost x-coory-coor CON 1 N 2 index demand 3 4 1 312.4802 5 2 188.8998 6 3 178.3584 7 4 135.8482 8 5 124.7573 9 6 120.0213 10 7 113.8947 11 8 97.60062 12 9 81.16697 13 10 69.60069 14 11 68.02127 15 12 64.96726 16 13 63.17246 17 14 58.21367 18 15 53.72927 19 16 51.36357 20 17 51.21044 21 18 51.10027 22 19 50 20541 23 20 45.93854 24 21 44.30972 25 22 42.42616 26 23 38.69561 24 38.48489 28 25 36.61038 29 26 34.59114 30 27 34.51472 31 28 33.02864 115800 101800 72600 72400 38400 59200 66000 48400 71300 96600 71200 66600 161400 60800 61500 75200 74400 77800 138500 70900 67900 62200 61500 77100 72600 79000 133800 54900 1.89 5.71 7.85 4.69 3.46 2.73 3.61 5.13 2.02 9.74 9.86 9.14 6.83 8.73 1.98 9.02 0.44 3.88 8.78 5.70 6.80 5.46 5.26 4.32 0.21 8.85 9.22 6.09 4.48 5.04 0.37 2.28 6.43 6.99 7.98 2.85 1.55 3.74 9.37 2.41 8.22 5.74 2.43 0.40 5.81 2.04 3.62 3.40 8.39 2.93 2.85 6.09 7.82 7.10 2.41 4.36 27 31 32 34 35 39 40 41 42 43 45 46 47 48 49 50 51 52 53 27 34.51472 28 33.02864 29 29.84437 30 29.15593 31 27.01877 32 26.01453 33 24.68261 34 18.83151 35 18.08993 36 16.57304 37 15.90822 38 12.89324 39 12.61925 40 11.64715 41 10.57086 42 10.53637 43 8.390183 44 7.308042 45 6.994764 46 6.7074 47 6.37245 48 5.908959 49 4.762674 133800 54900 60300 49500 54600 48800 64200 66100 67200 61700 99000 79500 99300 112400 67700 113000 63200 59500 88700 67900 123900 94100 68700 9.22 6.09 1.91 3.84 3.27 1.20 5.50 2.40 1.75 2.68 6.35 0.36 2.00 7.51 3.54 0.93 9.19 2.08 6.29 9.60 9.09 7.88 4.38 2.41 4.36 0.56 9.82 0.04 2.34 8.51 5.15 9.47 3.28 7.21 2.73 7.15 6.80 2.33 0.94 9.68 2.90 0.66 9.97 5.76 0.13 0.63 a We now focus on the simpler uncapacitated fixed-charge facility location (UFL) problem. The attached Excel file "data49points.xls" contains the x- and y-coordinates of 49 points in a 10-by-10 square, each of which is both a demand point and a candidate location for facility construction. The Excel file also contains the facility construction cost and the demand at each point. The distance between any two points can be measured by the Euclidean metric. Suppose the costs are properly prorated such that the objective is to minimize (total facility costs) + 150*(total demand- distance). Complete the following tasks. Implement the Lagrangian relaxation solution algorithm to solve the UFL problem instance with these 49 points. You may relax any constraints from the problem. You may use any programming language of your choice (e.g., C++, C#, MATLAB, VBA). Please report the best solution (number and location of facilities) found, the remaining optimality gap (if any), the computation time, and the computer platform used. Please plot the convergence process (upper bound and the best lower bound) over iterations. Please also submit your algorithm source code. . B F H C D E F G 49 nodes in a 10 by 10 square fixed cost x-coory-coor CON 1 N 2 index demand 3 4 1 312.4802 5 2 188.8998 6 3 178.3584 7 4 135.8482 8 5 124.7573 9 6 120.0213 10 7 113.8947 11 8 97.60062 12 9 81.16697 13 10 69.60069 14 11 68.02127 15 12 64.96726 16 13 63.17246 17 14 58.21367 18 15 53.72927 19 16 51.36357 20 17 51.21044 21 18 51.10027 22 19 50 20541 23 20 45.93854 24 21 44.30972 25 22 42.42616 26 23 38.69561 24 38.48489 28 25 36.61038 29 26 34.59114 30 27 34.51472 31 28 33.02864 115800 101800 72600 72400 38400 59200 66000 48400 71300 96600 71200 66600 161400 60800 61500 75200 74400 77800 138500 70900 67900 62200 61500 77100 72600 79000 133800 54900 1.89 5.71 7.85 4.69 3.46 2.73 3.61 5.13 2.02 9.74 9.86 9.14 6.83 8.73 1.98 9.02 0.44 3.88 8.78 5.70 6.80 5.46 5.26 4.32 0.21 8.85 9.22 6.09 4.48 5.04 0.37 2.28 6.43 6.99 7.98 2.85 1.55 3.74 9.37 2.41 8.22 5.74 2.43 0.40 5.81 2.04 3.62 3.40 8.39 2.93 2.85 6.09 7.82 7.10 2.41 4.36 27 31 32 34 35 39 40 41 42 43 45 46 47 48 49 50 51 52 53 27 34.51472 28 33.02864 29 29.84437 30 29.15593 31 27.01877 32 26.01453 33 24.68261 34 18.83151 35 18.08993 36 16.57304 37 15.90822 38 12.89324 39 12.61925 40 11.64715 41 10.57086 42 10.53637 43 8.390183 44 7.308042 45 6.994764 46 6.7074 47 6.37245 48 5.908959 49 4.762674 133800 54900 60300 49500 54600 48800 64200 66100 67200 61700 99000 79500 99300 112400 67700 113000 63200 59500 88700 67900 123900 94100 68700 9.22 6.09 1.91 3.84 3.27 1.20 5.50 2.40 1.75 2.68 6.35 0.36 2.00 7.51 3.54 0.93 9.19 2.08 6.29 9.60 9.09 7.88 4.38 2.41 4.36 0.56 9.82 0.04 2.34 8.51 5.15 9.47 3.28 7.21 2.73 7.15 6.80 2.33 0.94 9.68 2.90 0.66 9.97 5.76 0.13 0.63