The paper focuses on linear programming problems with two-sided constraints whose number is much larger than the number of variables. The solution approach is based on a non-smooth convex penalty function. An appropriate penalty parameter ensures the equivalence between the original problem and the problem of minimizing the penalty function. The latter problem is tackled by means of a modification of the r-algorithm, i.e., of an iterative subgradient method with an adaptive step adjustment and a constant coefficient of space dilation in the direction of the difference of two successive subgradients. Based on an implementation of this LPralg algorithm with GNU Octave, computational results on randomly generated instances with 20.000 to 1.500.000 two-sided constraints and up to 300 variables are presented. The results turn out to be very promising compared to well-known linear programming software, such as the GLPK package as well as CPLEX and Gurobi solvers. Among other problems, the new approach can be applied to robust linear programs with a finite uncertainty set.