1. A Brief Introduction to Linear Programming

Linear programming is not a programming language like C++, Java, or Visual Basic. Linear programming can be defined as:

"A method to allocate scarce resources to competing activities in an optimal manner when the problem can be expressed using a linear objective function and linear inequality constraints."

A linear program consists of a set of variables, a linear objective function indicating the contribution of each variable to the desired outcome, and a set of linear constraints describing the limits on the values of the variables. The "answer" to a linear program is a set of values for the problem variables that results in the best -- largest or smallest -- value of the objective function and yet is consistent with all the constraints. Formulation is the process of translating a real-world problem into a linear program. Once a problem has been formulated as a linear program, a computer program can be used to solve the problem. In this regard, solving a linear program is relatively easy. The hardest part about applying linear programming is formulating the problem and interpreting the solution.

The following links describe the basic elements that linear programming problems are made of."

Now that you have a general idea -- albeit, an abstract one -- of the structure of a linear program, the next step is to consider the process of formulating a linear programming problem. The following section walks you through the process of formulating two example problems. This should help give you a more concrete idea of what a linear program is.


Next Section Previous Section