Generalizing formulation 5, the general form for a Linear Programming problem is as follows:
where ``urs'' implies unrestricted in sign.
The formulation of Equations 6 to 8 has the general structure of a mathematical programming problem, presented in the introduction of this section, but it is further characterized by the fact that the functions involved in the problem objective and the left-hand-side of the technological constraints are linear. It is the assumptions implied by linearity that to a large extent determine the applicability of the above model in real-world applications.
To provide a better feeling of the linearity concept, let us assume that the different decision variables correspond to various activities from which any solution will be eventually synthesized, and the values assigned to the variables by any given solution indicate the activity level in the considered plan(s). For instance, in the above example, the two activities are the production of items and , while the activity levels correspond to the daily production volume. Furthermore, let us assume that each technological constraint of Equation 7 imposes some restriction on the consumption of a particular resource. Referring back to the prototype example, the two problem resources are the daily production capacity of the two workstations and . Under this interpretation, the linearity property implies that:
Another approximating element in many real-life LP applications results from the so called divisibility assumption. This assumption refers to the fact that for LP theory and algortihms to work, the problem variables must be real. However, in many LP formulations, meaningful values for the levels of the activities involved can be only integer. This is, for instance, the case with the production of items and in our prototype example. Introducing integrality requirements for some of the variables in an LP formulation turns the problem to one belonging in the class of (Mixed) Integer Programming (MIP). The complexity of a MIP problem is much higher than that of LP's. Actually, the general IP formulation has be shown to belong to the notorious class of NP-complete problems. (This is a class of problems that have been ``formally'' shown to be extremely ``hard'' computationally). Given the increased difficulty of solving IP problems, sometimes in practice, near optimal solutions are obtained by solving the LP formulation resulting by relaxing the integrality requirements - known as the LP relaxation of the corresponding IP - and (judiciously) rounding off the fractional values for the integral variables in the optimal solution. Such an approach can be more easily justified in cases where the typical values for the integral variables are in the order of tens or above, since the errors introduced by the rounding-off are rather small, in a relative sense.
We conclude our discussion on the general LP formulation, by formally defining the solution search space and optimality. Specifically, we shall define as the feasible region of the LP of Equations 6 to 8, the entire set of vectors that satisfy the technological constraints of Eq. 7 and the sign restrictions of Eq. 8. An optimal solution to the problem is any feasible vector that further satisfies the optimality requirement expressed by Eq. 6. In the next section, we provide a geometric characterization of the feasible region and the optimality condition, for the special case of LP's having only two decision variables.