We propose a new method for making the inventory replenishment decisions in distribution systems. In particular, we consider distribution systems consisting of multiple retailers that face random demand and a warehouse that supplies the retailers. The method that we propose is based on formulating the distribution problem as a dynamic program and relaxing the constraints that ensure the nonnegativity of the shipments to the retailers by associating Lagrange multipliers with them. We show that our method provides lower bounds on the value functions and a good set of values for the Lagrange multipliers can be obtained by maximizing a concave function in a relatively straightforward
manner. Computational experiments indicate that our method can provide significant improvements
over the traditional approaches for making the inventory replenishment decisions, in terms of both the tightness of the lower bounds on the value functions and the performance of the policies.