Linear Programming and Dynamic Programming Application to Water Distribution Network Design

Abstract

The water distribution network design problem is to find the optimal set of investments in pipelines that are needed to satisfy water requirements. The strategy of this study has been first to define an optimality criterion for ranking alternative investment opportunities and then to formulate a mathematical programming model for solving the optimal investment problem. The least cost optimality criterion leads to a non-linear mathematical programming problem for which no computational methods exist that guarantee an optimal solution. Other existing techniques that yield "good" solutions are computationally inefficient. The strategy taken in this study has been to modify the least cost problem so that linear programming could be applied to achieve a solution to the modified form of the problem. Variables were transformed to linearize the non-linear terms in the pipe flow formula. In this way, the non-linear flow phenomenon is represented exactly. The resulting linear programming model may be used to determine the pipe diameters of pipes that must be added to the system to satisfy given sets of water requirements that are expected to occur at a given future time. Water requirements increase with increases in population and economic productivity. To meet these growing requirements, excess capacity must be provided. The problem of deciding how far into the future the system should be planned is known as a capacity expansion problem. The capacity expansion problem has been formulated as a dynamic programming problem and applied to the water distribution network expansion problem.