Linear Programming

Linear Programming (LP) is a mathematical procedure for determining optimal allocation of scarce resources. LP is a procedure that has found practical application in almost all facets of business, from advertising to production planning. Transportation, distribution, and aggregate production planning problems are the most typical objects of LP analysis. In the petroleum industry, for example a data processing manager at a large oil company recently estimated that from 5 to 10 percent of the firm's computer time was devoted to the processing of LP and LP-like models.

 

Linear programming deals with a class of programming problems where both the objective function to be optimized is linear and all relations among the variables corresponding to resources are linear. This problem was first formulated and solved in the late 1940's. Rarely has a new mathematical technique found such a wide range of practical business, commerce, and industrial applications and simultaneously received so thorough a theoretical development, in such a short period of time. Today, this theory is being successfully applied to problems of capital budgeting, design of diets, conservation of resources, games of strategy, economic growth prediction, and transportation systems. In very recent times, linear programming theory has also helped resolve and unify many outstanding applications.

 

It is important for the reader to appreciate, at the outset, that the "programming" in Linear Programming is of a different flavor than the "programming" in Computer Programming. In the former case, it means to plan and organize as in "Get with the program!", it programs you by its solution. While in the latter case, it means to write codes for performing calculations. Training in one kind of programming has very little direct relevance to the other. In fact, the term "linear programming" was coined before the word "programming" became closely associated with computer software. This confusion is sometimes avoided by using the term linear optimization as a synonym for linear programming.

 

Any LP problem consists of an objective function and a set of constraints. In most cases, constraints come from the environment in which you work to achieve your objective. When you want to achieve the desirable objective, you will realize that the environment is setting some constraints (i.e., the difficulties, restrictions) in fulfilling your desire or objective. This is why religions such as Buddhism, among others, prescribe living an abstemious life. No desire, no pain. Can you take this advice with respect to your business objective?

 

What is a function: A function is a thing that does something. For example, a coffee grinding machine is a function that transform the coffee beans into powder. The (objective) function maps and translates the input domain (called the feasible region) into output range, with the two end-values called the maximum and the minimum values.

When you formulate a decision-making problem as a linear program, you must check the following conditions:

l        The objective function must be linear. That is, check if all variables have power of 1 and they are added or subtracted (not divided or multiplied)

l        The objective must be either maximization or minimization of a linear function. The objective must represent the goal of the decision-maker

l        The constraints must also be linear. Moreover, the constraint must be of the following forms ( £, ³, or =, that is, the LP-constraints are always closed).

 

For example, the following problem is not an LP: Max X, subject to X < 1. This very simple problem has no solution.

 

As always, one must be careful in categorizing an optimization problem as an LP problem. Here is a question for you. Is the following problem an LP problem?

 

Max X2
subject to:
X1 + X2 £ 0
X1² - 4 £££ 0

Although the second constraint looks "as if" it is a nonlinear constraint, this constraint can equivalently be written as:
X1 ³ -2, and X2 £ 2. 

Therefore, the above problem is indeed an LP problem.

 

For most LP problems one can think of two important classes of objects: The first is limited resources such as land, plant capacity, or sales force size; the second, is activities such as "produce low carbon steel", "produce stainless steel", and "produce high carbon steel". Each activity consumes or possibly contributes additional amounts of the resources. There must be an objective function, i.e. a way to tell bad from good, from an even better decision. The problem is to determine the best combination of activity levels, which do not use more resources than are actually available. Many managers are faced with this task everyday. Fortunately, when a well-formulated model is input, linear programming software helps to determine the best combination.

The Simplex method is a widely used solution algorithm for solving linear programs. An algorithm is a series of steps that will accomplish a certain task.