A development aid organization must establish a gravity water distribution network in a mountainous region of Nepal. This inexpensive system does not require pumps. The table shows the nodes to connect with the altitudes in meters and the longitudes (X) and latitudes (Y) in km. Node 0 is a source, the other nodes are villages. One can build a pipe from one node to another if the destination node has an altitude lower than the first. To simplify, it is assumed that each pipe constructed is a straight segment that takes into account the altitudes of the point of departure and the point of destination (segment in a space with 3 dimensions). The cost of building a pipe is 16,500 euros per km.

a)What pipes to build to connect the source to the villages at a minimum total cost? The network must be a tree, that is, each village must be served by a single pipe, coming from a single other node. Indications: we can calculate a matrix of distances between nodes and use binary variables xij, equal to 1 if we build a pipe from i to j. The site j must obviously be at a lower altitude than i. To prohibit connections that go up in altitude, we can put a high cost. Instead of a matrix, we can also make a smaller table with 4 columns for possible connections (starting node, finishing node, distance, binary variable

b) In this question there are also costs to connect the pipes, to the source and to each connected village. If a node connects 2 pipes, the cost of the junction is 500 euros. For more than two pipes, add 400 euros per hose from the third hose.

51 1 Node 0 1 2 3 4 5 6 7 8 9 10 11 X 0 3 472 1,5 65 1625 7 3 700 750 740 2 O Altitude 810 710 670 640 660 690 680 680 51 1 Node 0 1 2 3 4 5 6 7 8 9 10 11 X 0 3 472 1,5 65 1625 7 3 700 750 740 2 O Altitude 810 710 670 640 660 690 680 680