The synthesis of Heat-Exchanger-Network (HEN) structures consuming minimum total utility and possessing a desired operational flexibility is accomplished via a non-iterative, superstructure-based, simultaneous-MILP formulation. The formulation presumes that the feasible region in the space of uncertain input parameters is convex. Thus, the optimal solution is explored based on the vertices of the polyhedral uncertainty region in the space of source-stream temperatures. The optimal value of the objective function is the lower bound of the total utility consumption for the HEN satisfying the targeted flexibility. When the target-flexibility value is set to zero, the optimal value of the objective function becomes equal to the minimum total-utility level as predicted by the application of the Pinch method to the HEN problem. The formulation is also used, with minor modifications, to compute the flexibility indexes of the synthesized HEN structures. The flexibility index of the HEN structure gives the upper bound for the target flexibility corresponding to the minimum level of the total utility consumption. Using a well-known HEN superstructure and a HEN problem, the formulation is solved successively, for increasing values of the targeted flexibility, to reveal the necessary structural modifications and their corresponding minimum-utility-consumption levels.