Operations Research/Linear Programming

< Operations Research

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

$\displaystyle a_1x_1+a_2x_2+\cdots a_nx_n$

a

1

x

1

+

a

2

x

2

+

a

n

x

n

\displaystyle a_1x_1+a_2x_2+\cdots a_nx_n

where

$\displaystyle x_1,x_2\cdots x_n$

x

1

,

x

2

x

n

\displaystyle 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[ edit ]

Example of graphical solution to a LP with two variables

$\displaystyle X_1$

X

1

\displaystyle X_1

and

$\displaystyle X_2$

X

2

\displaystyle X_2

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,

$\displaystyle x_1$

x

1

\displaystyle x_1

= Units produced daily of salt X

$\displaystyle x_2$

x

2

\displaystyle 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

$\displaystyle 5x_1+4x_2$

5

x

1

+
4

x

2

\displaystyle 5x_1+4x_2

. This is assuming that if 1 unit of X (or Y) gives a profit of 5 (or 4) then

$\displaystyle x_1$

x

1

\displaystyle x_1

(or

$\displaystyle x_2$

x

2

\displaystyle x_2

) units would give a profit of

$\displaystyle 5x_1$

5

x

1

\displaystyle 5x_1

(or

$\displaystyle 4x_2$

4

x

2

\displaystyle 4x_2

). Hence if z represents the total daily profit the objective is:

Maximize z =

$\displaystyle 5x_1+4x_2$

5

x

1

+
4

x

2

\displaystyle 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

$\displaystyle 6x_1$

6

x

1

\displaystyle 6x_1

and

$\displaystyle 4x_2$

4

x

2

\displaystyle 4x_2

are reasonably the amounts of the acid used in making the salt X and Y we may conclude that our constraint is:

$\displaystyle 6x_1+4x_2\leq 24$

6

x

1

+
4

x

2

24

\displaystyle 6x_1+4x_2\leq 24

Similarly, for the base:

$\displaystyle x_1+2x_2\leq 6$

x

1

+
2

x

2

6

\displaystyle x_1+2x_2\leq 6

Now the market dictates that the excess of the daily production of Y over X which is

$\displaystyle x_2-x_1$

x

2

x

1

\displaystyle x_2-x_1

can’t exceed 1 which means that:

$\displaystyle x_2-x_1\leq 1$

x

2

x

1

1

\displaystyle x_2-x_1\leq 1

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

$\displaystyle x_2\leq 2$

x

2

2

\displaystyle x_2\leq 2

An implicit assumption is that the variables

$\displaystyle x_1$

x

1

\displaystyle x_1

and

$\displaystyle x_2$

x

2

\displaystyle x_2

can’t assume negative values (Why?). The nonnegativity restrictions,

$\displaystyle x_1,x_2\geq 0$

x

1

,

x

2

0

\displaystyle x_1,x_2\geq 0

account for this requirement.

The complete model can be now stated as:

Maximize z =

$\displaystyle 5x_1+4x_2$

5

x

1

+
4

x

2

\displaystyle 5x_1+4x_2

subject to,

$\displaystyle 6x_1+4x_2\leq 24$

6

x

1

+
4

x

2

24

\displaystyle 6x_1+4x_2\leq 24

,

$\displaystyle x_1+2x_2\leq 6$

x

1

+
2

x

2

6

\displaystyle x_1+2x_2\leq 6

,

$\displaystyle x_2-x_1\leq 1$

x

2

x

1

1

\displaystyle x_2-x_1\leq 1

,

$\displaystyle x_2\leq 2$

x

2

2

\displaystyle x_2\leq 2

,

$\displaystyle x_1,x_2\geq 0$

x

1

,

x

2

0

\displaystyle x_1,x_2\geq 0

.

Any values of

$\displaystyle x_1$

x

1

\displaystyle x_1

and

$\displaystyle x_2$

x

2

\displaystyle x_2

that satisfy all the five constraints constitute a feasible solution. Otherwise the solution is infeasible. For example, the solution

$\displaystyle x_1=3$

x

1

=
3

\displaystyle x_1=3

and

$\displaystyle x_2=1$

x

2

=
1

\displaystyle 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

$\displaystyle x_1=4$

x

1

=
4

\displaystyle x_1=4

and

$\displaystyle x_2=1$

x

2

=
1

\displaystyle 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[ edit ]

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
$\displaystyle 6x_1$

6

x

1

\displaystyle 6x_1

. This is directly proportional to

$\displaystyle x_1$

x

1

\displaystyle 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
$\displaystyle 5x_1+4x_2$

5

x

1

+
4

x

2

\displaystyle 5x_1+4x_2

which is the sum of the individual profits

$\displaystyle 5x_1$

5

x

1

\displaystyle 5x_1

and

$\displaystyle 4x_2$

4

x

2

\displaystyle 4x_2

.

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