Operations Research/Linear Programming

Linear Programming (LP) is a mathematical modelling technique useful for allocation of limited resources such as material, machines etc to several competing activities such as projects, services etc. A typical linear programming problem consists of a linear objective function which is to be maximized or minimized subject to a finite number of linear constraints. (By a linear function we mean a function of the form $a_{1}x_{1}+a_{2}x_{2}+\cdots a_{n}x_{n}$ where $x_{1},x_{2}\cdots x_{n}$ are all variables.)

The founders of LP are George B. Dantzig, who published the simplex method in 1947, John von Neumann, who developed the theory of the duality in the same year, and Leonid Kantorovich, a Russian mathematician who used similar techniques in economics before Dantzig and won the Nobel prize in 1975 in economics. The linear programming problem was first shown to be solvable in polynomial time by Leonid Khachiyan in 1979, but a larger major theoretical and practical breakthrough in the field came in 1984 when Narendra Karmarkar introduced a new interior point method for solving linear programming problems.

The Two Variable LP model

Two variable LP models don't usually exist in practice but their study can provide us with an example as to how a general model can be handled.

We will explain the model by an example.

Consider a chemical company which produces two salts: X and Y. Suppose an acid and a base are the only two chemicals required by the company to produce these two salts. Further suppose that by past experience the owner of the company has obtained the following data:

To make 1 unit of the salt X, 6 units of the acid and 1 unit of the base is required. To make 1 unit of the salt Y, 4 units of the acid and 2 units of the base are required. At most 24 units of the acid and 6 units of the base are available daily. 1 unit of the salt X gets him a profit of 5 (in whatever currency) and 1 unit of the salt Y gets him a profit of 4. In addition due to a market survey he knows that the daily demand for the salt Y cannot exceed that for X by more than 1 unit, and that the maximum daily demand for the salt Y is 2 units.

The company owner wants the best product mix. That is to say, he wants to know the amount of X and Y he should make daily so that he gets the highest profit.

To formulate the LP model for this problem we first need to identify the decision variables. These are the variables which will represent the entities about which we have to actually make a decision about. In our problem it is clear that the entities are the salts X and Y and so the variables should represent the amount they should be each made. So let,

$x_{1}$ = Units produced daily of salt X

$x_{2}$ = Units produced daily of salt Y

The next step is to decide what should be the objective function for our model. It is clear from the name itself that the objective function represents our objective i.e. maximizing our total profit. Since the total profit is usually the sum of the profits obtained from X and Y it should be equal to $5x_{1}+4x_{2}$ . This is assuming that if 1 unit of X (or Y) gives a profit of 5 (or 4) then $x_{1}$ (or $x_{2}$ ) units would give a profit of $5x_{1}$ (or $4x_{2}$ ). Hence if z represents the total daily profit the objective is:

Maximize z = $5x_{1}+4x_{2}$ .

Now we consider the constraints that restrict the usage of the acids and the salts. We know that the total amount of acid which we use in the day can't exceed 24. Since $6x_{1}$ and $4x_{2}$ are reasonably the amounts of the acid used in making the salt X and Y we may conclude that our constraint is:

$6x_{1}+4x_{2}\leq 24$

Similarly, for the base:

$x_{1}+2x_{2}\leq 6$

Now the market dictates that the excess of the daily production of Y over X which is $x_{2}-x_{1}$ can't exceed 1 which means that:

$x_{2}-x_{1}\leq 1$

Also the maximum daily demand for the salt Y is 2 units so that:

$x_{2}\leq 2$

An implicit assumption is that the variables $x_{1}$ and $x_{2}$ can't assume negative values (Why?). The nonnegativity restrictions, $x_{1},x_{2}\geq 0$ account for this requirement.

The complete model can be now stated as:

Maximize z = $5x_{1}+4x_{2}$

subject to,

$6x_{1}+4x_{2}\leq 24$ ,

$x_{1}+2x_{2}\leq 6$ ,

$x_{2}-x_{1}\leq 1$ ,

$x_{2}\leq 2$ ,

$x_{1},x_{2}\geq 0$ .

Any values of $x_{1}$ and $x_{2}$ that satisfy all the five constraints constitute a feasible solution. Otherwise the solution is infeasible. For example, the solution $x_{1}=3$ and $x_{2}=1$ is feasible because on substitution in the constraints none of the inequalities are violated. On the other hand the solution, the solution $x_{1}=4$ and $x_{2}=1$ is infeasible because it does not satisfy constraint (1), namely 6*4+4*1=28 which is larger then the right hand side (=24).

Our goal is to find the optimum solution, i.e. one which maximizes the objective function besides being feasible. The procedure to do that will be discussed in the succeeding sections.

Properties of the LP model

LP models have the following properties:

Proportionality: the contribution of each decision variable is directly proportional to its value in both the objective function and in the constraints. For example, the contribution of the first decision variable in the first constraint is $6x_{1}$ . This is directly proportional to $x_{1}$ with 6 as the constant of proportionality. Roughly speaking, the rule of three is followed.

Additivity: the contribution of all the variables in the objective function and the constraints to be the sum of the individual contributions of each variable. For example, the total profit is $5x_{1}+4x_{2}$ which is the sum of the individual profits $5x_{1}$ and $4x_{2}$ .

Certainty: all the objective and constraint coefficients are deterministic, that is all the data about profit, availability and requirements is constant.