This Java program was created using Sun Java JDK 1.5.0 _Version 2.

Linear programming is used extensively in business and economics, as well as being relevant to certain engineering problems.

Linear Programming - or linear optimisation, as it is sometimes called - enables the maximising or minimising of a linear function over a complex polyhedron as defined by linear and non-negativity constraints.

The Simplex algorithm, developed by George Dantzig et al in 1949, solves linear programming problems by constructing an admissible solution at the vertex of the polyhedron and then walking along the edges of the polyhedron to vertices with successively higher values of the objective function until the optimum is reached. This process is depicted in the first diagrams.

Within each problem, the problem constraints are set up as a set of inequalities. These are converted into simultaneous equations by the introduction of "basic" variables or “slack” variables. This arrangement of the matrix data worked on by the algorithm is shown in the second diagram. The algorithm provides solutions to large numbers of such simultaneous equations, which are arranged as matrices, formed by elimination of variables and back substitution.

The “forcing out” of the slack variables maximises or minimises particular sets of equations, which could define conditions for maximum profit, production, weapon effectiveness, utilisation of resources, etc.