Home‎ > ‎Mathematical Programming‎ > ‎

Linear Programming

The Linear Programming Paradigm

Many authors propose slightly different approaches to problem solving with systems analysis methods. The differences are generally minor; the essence of most approaches is basically the same. In the case of linear programming, the following steps should prove useful:

0.  Recognize the problem
1.  Define the problem
2.  Define the decision variables
3.  Collect the necessary parametric data
4.  Formulate a model
5.  Solve the model
6.  Verify and validate the model
7.  Analyze model output
8.  Interpret model results
9.  Recommend a course of action

This list should be taken as a general guideline, not a rigid sequence of steps. It is common practice to return to previous steps as circumstances may dictate to refine the model as one acquires more experience with the problem under consideration.

0. Recognize the problem

Before a problem can be analyzed, one must become aware of the existence of a problem. In the real world, problems hardly ever come pre-identified as such. One must proactively search for and identify problems. This must be done carefully because the apparent problem one perceives may not be the real problem. The analyst must distinguish between symptoms and actual problems. Symptoms are signs that indicate the existence of certain conditions, typically anomalous, somewhere in the system. A symptom is a reflection of some root cause. Treating a symptom, doctors well know, will not cure the underlying illness. The analyst must strive to uncover root causes and not be misled by superficial appearances.

Another important point is the type of problem present. The word problem has a negative or pejorative connotation: something is not going right. Let us call these negative problems. A negative problem exists when actual system performance falls below standards or expectations, creating a performance gap. The greater the performance gap, the greater the problem. Negative problems must be corrected promptly, for underperforming systems in competitive Darwinian environments such as the business world will inexorably be driven into extinction.

In passing, keep in mind that there are two basic ways for performance gaps to arise: (1) the system may be underperforming or (2) the performance standards/expectations may be set at unrealistically high levels. If the latter is the case, then the standards/expectations must be revised so as to make them attainable. Unattainable system states are immediately excluded from consideration in all system-analytic methods, including LP, for there is nothing to be done about things which are impossible.

More important, however, are the positive problems: novel opportunities that perhaps should be pursued. Negative problems must be corrected so that attention can be focused on finding positive problems and capitalizing on the opportunity they present before our competitors do so. Positive problems represent the future, and may well prove to be more profitable in the long run than continuing with present activities. Positive problems are generally harder to detect, for no symptoms may exist or be apparent. To detect opportunities, visionary leadership is essential. It takes visionaries to convert negative problems into novel opportunities.

There is another useful way to classify problems: urgency vs. importance. Urgent problems are those that demand immediate attention, although the solution need not be optimal. Negative problems are often of this type. Important problems, on the other hand, require thorough attention and usually call for well-planned or optimal solutions. Urgent problems can typically be treated with a quick but effective solution, which may be temporary, whereas important problems entail considerable effort to devise efficient long-term solutions. Of course, a problem can be both urgent and important; therefore, be analytically prepared.

1. Define the problem

Linear programming requires that the analyst clearly define two fundamental aspects of the problem:

Objective: the system state or performance level one aims to attain

Constraints: the requirements that must be met by the proposed solution

Specifying the objective and all relevant constraints constitutes a complete LP problem definition.

2. Define the decision variables

A decision variable is a system setting whose value is assigned by the decision maker. A decision is made when a value is specified for a decision variable. Decision variables are sometimes called controllable variables because they are under the control of the decision maker.

Decision variables are defined by specifying the metric (standard of measurement) used for quantification, the entity being referenced and the time span of reference. The time span may be omitted if the problem calls for a one-time or single-period decision.

  a)  Let  x  =  dozens of widgets produced per hour
  b)  Let  y  =  pounds of chocolate consumed per person per week
  c)  Let  zi  =  dollars invested in financial instrument i  (i = 1, 2, …, n)

3. Collect the necessary parametric data

Many, if not most, of the elements needed to model the system of interest are not under the control of the decision maker. For instance, in manufacturing systems, products must comply with detailed specifications, production processes follow fixed operating procedures, and financial aspects are strictly budgeted. These requirements are normally quantified by the people involved in those activities, such as engineering and accounting & finance. The analyst must collect this information. Any piece of information in the form of a constant quantity is called a parameter. A parameter is simply a numerical constant that specifies particular system attributes. Sometimes system requirements vary depending on certain other factors, in which case they are known as uncontrollable variables.

4. Formulate a model

In LP, model formulation means expressing the objective and each of the constraints algebraically in terms of the decision variables and parameters. This is usually straightforward if the problem and the decision variables have been defined correctly. Difficulties in model formulation are typically a sign that something was amiss when defining the problem or the decision variables. Make sure steps 1 and 2 are complete and correct (coherent) before attempting to formulate a model.

There may be several possible ways to model the same problem. Which way is best depends on what information the analyst wants to obtain from the analysis. It is advisable to begin with a relatively simple model at the outset and subsequently refine it if additional information is desired.

5. Solve the model

Model solution in LP is computationally intensive and normally conducted by means of computer software. In this module, we will examine the graphical solution method to illustrate the basic concepts of LP. But the graphical method, although theoretically sound, is very limited in power and therefore practically useless for real-world applications. We will make use of Excel's Solver Add-In to illustrate a practical solution method. There are many software options available, however, all of which provide the same basic information regarding LP solutions.

6. Verify and Validate the model

Model verification means ensuring that the model is computationally correct, that it calculates what it is supposed to. A model containing errors (of both omission and commission) is useless. Model validation means ensuring that the model is representationally correct, that it accurately reproduces the behavior of the real-world system being modeled. Verification deals with the internal consistency of the model while validation addresses its external (representational) correctness. In LP, verifying and validating a model can range from a simple inspection of the output to detailed comparisons of model results to the system's operational statistics. Here's a quick reference on the subject: Model V & V.

7. Analyze model output

The computer provides the solution to the LP problem along with a sensitivity analysis. However, in LP the term solution means the optimal quantities the model assigns to the decision variables. The term value means the result obtained for the objective function with that optimal solution. The term optimal means the best possible value that complies with all problem constraints, one that maximizes or minimizes the value of the objective function. Sensitivity analysis consists of additional information provided by the model. This includes the opportunity costs (called shadow prices or dual prices) for all resources, the ranges in which these dual prices hold, and the range where the model solution remains valid if the objective function parameters (called objective function coefficients) were to change.

Keep in mind that a model is an idealized representation of a real-world system and therefore the model solution is also an idealized result. In order to make effective use of model results, the next step must be performed.

8. Interpret model results

Every model is a simplification of the actual system being analyzed. Thus model solutions must be interpreted in the light of real-world considerations that may deviate from the simplifying assumptions built into the model. One way of dealing with this is to work interactively with the model to assess the impact of different possible conditions on model results. A great deal can be learned about system behavior by experimenting with the model, without affecting the actual system. The insight thus gained can be extremely useful for managers in the implementation phase of the project as well as in control of operations.

9. Recommend a course of action

Presentation of the findings concludes the LP modeling analysis.


Constraint — a restriction that must be observed (complied with)

Controllable variable — another name for decision variable

Decision variable — a quantity that is under the control of and chosen by the decision maker (or determined by a decision model such as LP)

Dual price — a term somewhat synonymous with shadow price (there is a slight difference in how they are computed and interpreted, but they both represent the economic value of an additional unit of a resource; see Dual vs. Shadow Price)

Important problem — a situation of significance that calls for a carefully reasoned solution

Model validation — ensuring that the model adequately represents the object system

Model verification — ensuring that the model is computationally correct

Negative problem — situation that exists when a system is underperforming

Objective — the system state or performance level intended to be attained

Objective function — an algebraic equation that states the end one seeks to achieve

Opportunity cost — loss of potential gain from other alternatives incurred by choosing one course of action

Optimal — the best possible alternative that satisfies a set of constraints

Optimal solution — a solution that yields the best possible value (either maximum or minimum) for a given objective function and set of constraints

Parameter — a numerical constant defining some system attribute

Performance gap — the difference between actual system performance and established standards

Positive problem — a situation or set of circumstances that offers advantageous prospects

Problem — a matter, situation or state of affairs requiring a solution

Sensitivity analysis — a procedure that determines the effect on the model solution and the value of the objective function for small changes in model parameters; a technique that throws light on the degree of stability of a given solution when the model is slightly altered

Shadow price — the opportunity cost (economic value forgone) of not having one additional unit of a particular resource; the maximum premium one would be willing to pay for an additional unit of some resource

Solution — a set of values for the decision variables that is feasible (complies with all constraints)

Symptom — a sign indicating the existence of some condition in a system

Uncontrollable variable — a nonconstant quantity that defines some system attribute

Urgent problem — a situation demanding prompt attention

Value — the numerical quantity generated by the objective function for a given solution