A water quality monitoring network (WQMN) must be designed so as to adequately protect the water quality in a catchment. Although a simulated annealing (SA) method was previously applied to design a WQMN, the SA method cannot ensure the solution it obtained is the global optimum. Therefore, two new linear optimization models are proposed in this study to minimize the deviation of the cost values expected to identify the possible pollution sources based on uniform cost (UC) and coverage elimination uniform cost (CEUC) schemes. The UC model determines the expected cost values by considering each sub-catchment being covered by which station, while the CEUC model determines the coverage of each station by eliminating the area covered by any upstream station. The proposed models are applied to the Derchi reservoir catchment in Taiwan. Results show that the global optimal WQMN can be effectively determined by using the UC or CEUC model, for which both results are better than those from the SA method, especially when the number of stations becomes large.