We develop an optimization algorithm for a periodic review inventory system under a stochastic budget constraint. While most conventional studies on the periodic review inventory system consider a simple budget limit in terms of the inventory investment being less than a fixed budget, this study adopts more realistic assumption in that purchasing costs are paid at the time an order is arrived. Therefore, probability is employed to express the budget constraint. That is, the probability of total inventory investment to be less than budget must be greater than a certain value assuming that purchasing costs are paid at the time an order is arrived. We express the budget constraint in terms of the Lagrange multiplier and suggest a numerical method to obtain optional values of the cycle time and the safety factor to the system. We also perform the sensitivity analysis in order to investigate the dependence of important quantities on the budget constraint. We find that, as the amount of budget increases, the cycle time and the average inventory level increase, whereas the Lagrange multiplier decreases. In addition, as budget increases, the safety factor increases and reaches to a certain level. In particular, we derive the condition for the maximum safety factor.