The Linear Programming problem involves a linear objective function that must be minimized or maximized, and a set of linear constraints. The general form of the Linear Programming problem is as follows:

The Linear Programming problem is very useful because it can be used to find optimal solutions for many real-world scenarios. If a company has several machines, for instance, and each one can manufacture a number of different products, the management might want to know how much of each product should be manufactured by each machine to maximize profit. The constraints imposed on this problem would represent the maximum number of elements that can be produced by each machine in a unit of time. There would be additional constraints ensuring that the number of elements produced is positive, so that the results make sense.

Essentially, the Linear Programming problem is an optimization problem, and a number of techniques have been developed to solve it. One of these techniques that lends itself well to automation is the simplex method. First, the problem is simplified by converting it to a standard form, where all constraints are equalities rather than inequalities, and all variables are constrained. This task can be easily accomplished through algebraic manipulation or linear transformation. Once the problem is in standard form, a basic solution is obtained by setting all non-basic variables to zero. A basic variable is defined as a variable which appears in only one equation in the system.

Once a basic solution has been identified, the algorithm checks to see whether this solution is optimal. If it is optimal, the algorithm terminates. Otherwise, the algorithm repeatedly moves to a "nearby" basic solution and checks to see whether that solution is optimal.

As an interesting side note, the linear programming problem is NP-hard when restricted to integers, but a suitable approximation can be made using probabilistic methods. When using linear programming to solve the maximum satisfiability program, for instance, the program can be solved for real number values with the answers representing the probability of picking a particular integer value.