Generalizing formulation 5, the general form for a Linear Programming problem is as follows:

**Objective Function:**

s.t.

**Technological Constraints:**

**Sign Restrictions:**

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:

**Additivity assumption:**- the total consumption of each resource, as well as the overall objective value are the aggregates of the resource consumptions and the contributions to the problem objective, resulting by carrying out each activity independently, and
**Proportionality assumption:**- these consumptions and contributions
for each activity are proportional to the actual activity level.

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

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.

Fri Jun 20 15:03:05 CDT 1997