The Balanced Linear Programming Problem (BLPP) arises in situations which required equitable distribution of a scarce resource. The BLPP can be transformed to the standard form of the linear programming problem by introducing 2|N|+2 additional variables and 2|N| additional constraints. This transformation is not desirable from the computational point of view for larger values of |N| as it increases the problem size substantially. It is also undesirable from a theoretical perspective as it might affect the special structure of the constraint matrix. In this paper, we develop an algorithm for the BLPP which does not require problem enlargement. The algorithm is based on the relationship between the BLPP and the minimax linear programming problem, and solving the latter problem parametrically. Our algorithm, in essence, performs steps that are similar to those performed in the parametric simplex method with parametric right hand side. We then adapt our algorithm for the network flow problem and this specialized algorithm can be applied on the network directly without maintaining the simplex tableau.
