Linear Programming Problems

Definition :   Suppose that one is given a linear function of n real variables

z = f (x₁, x₂,..., x_n) = c₁x₁ + c₂x₂ +...+ c_nx_n

and a set of linear inequalities and/or equations, called constraints

(1.1)

where in each line either , = or occurs. The problem of finding  (x₁, x₂,..., x_n), that satisfies the constraints (1.1) and makes z a maximum (or minimum) is called a Linear Programming Problem .

We shall assume that every Linear Programming Problem has included in its constraints, the non-negativity restrictions

x_j0   
(1.2)

and these will be written separately from the other constraints. These non-negativity constraints are sometimes known as reality constraints. In examples they typically represent quantities that for physical reasons are non-negative.

Any set of values of x₁, x₂,..., x_n satisfying the constraints (1.1) and inequalities (1.2) is called a feasible solution. The set of feasible solutions is the feasible region. Somewhat perversely, any set of values of x₁, x₂,..., x_n satisfying the constraints (1.1) but not (1.2) is called a non-feasible solution.

The function f is called the objective function and z the objective variable. If set of values of x₁, x₂,..., x_n  is a feasible solution that makes f (x₁,..., x_n) a maximum (or minimum) then x is an optimal solution and the corresponding value of z is the optimal value.

Mathematical Formulation of Linear Programming Problems

There are mainly four steps in the mathematical formulation of linear programming problem as a mathematical model. We will discuss formulation of those problems which involve only two variables.

(1) Identify the decision variables and assign symbols x and y to them. These decision variables are those quantities whose values we wish to determine.

(2) Identify the set of constraints and express them as linear equations/inequations in terms of the decision variables. These constraints are the given conditions.

(3) Identify the objective function and express it as a linear function of decision variables. It might take the form of maximizing profit or production or minimizing cost.

(4) Add the non-negativity restrictions on the decision variables, as in the physical problems, negative values of decision variables have no valid interpretation.

There are many real life situations where an LPP may be formulated. The following examples will help to explain the mathematical formulation of an LPP.

01. A diet is to contain at least 4000 units of carbohydrates, 500 units of fat and 300 units of protein. Two foods A and B are available. Food A costs 2 dollars per unit and food B costs 4 dollars per unit. A unit of food A contains 10 units of carbohydrates, 20 units of fat and 15 units of protein. A unit of food B contains 25 units of carbohydrates, 10 units of fat and 20 units of protein. Formulate the problem as an LPP so as to find the minimum cost for a diet that consists of a mixture of these two foods and also meets the minimum requirements.

Suggested answer:

The above information can be represented as

Let the diet contain x units of A and y units of B.

    Total cost = 2x + 4y

The LPP formulated for the given diet problem is

Minimize Z = 2x + 4y

subject to the constraints

02. In the production of 2 types of toys, a factory uses 3 machines A, B and C. The time required to produce the first type of toy is 6 hours, 8 hours and 12 hours in machines A, B and C respectively. The time required to make the second type of toy is 8 hours, 4 hours and 4 hours in machines A, B and C respectively. The maximum available time (in hours) for the machines A, B, C are 380, 300 and 404 respectively. The profit on the first type of toy is 5 dollars while that on the second type of toy is 3 dollars. Find the number of toys of each type that should be produced to get maximum profit.

Suggested answer:

Mathematical Formulation

The data given in the problem can be represented in a table as follows.

Let x = number of toys of type-I to be produced

y = number of toys of the type - II to be produced

     Total profit = 5x + 3y

The LPP formulated for the given problem is:

Maximise Z = 5x + 3y subject to the constraints

Graphical Solution of Linear Programming Problem :

Let us take the following example :

minimise
    Z  =  180x + 160y
subject to
      6x + y >= 12
      3x + y >= 8
      4x + 6y >= 24
      x <= 5
      y <= 5
      x,y >= 0

Since there are only two variables in this LP problem we have the graphical representation of the LP given below with the feasible region (region of feasible solutions to the constraints associated with the LP) outlined.

To draw the diagram above we turn all inequality constraints into equalities and draw the corresponding lines on the graph (e.g. the constraint 6x + y >= 12 becomes the line 6x + y = 12 on the graph). Once a line has been drawn then it is a simple matter to work out which side of the line corresponds to all feasible solutions to the original inequality constraint (e.g. all feasible solutions to 6x + y >= 12 lie to the right of the line 6x + y = 12).

We determine the optimal solution to the LP by plotting (180x + 160y) = K (K constant) for varying K values (iso-profit lines). One such line (180x + 160y = 180) is shown dotted on the diagram. The smallest value of K (remember we are considering a minimisation problem) such that 180x + 160y = K goes through a point in the feasible region is the value of the optimal solution to the LP (and the corresponding point gives the optimal values of the variables).

Hence we can see that the optimal solution to the LP occurs at the vertex of the feasible region formed by the intersection of 3x + y = 8 and 4x + 6y = 24. Note here that it is inaccurate to attempt to read the values of x and y off the graph and instead we solve the simultaneous equations

• 3x + y = 8
• 4x + 6y = 24

to get x = 12/7 = 1.71 and y = 20/7 = 2.86 and hence the value of the objective function is given by 180x + 160y = 180(12/7) + 160(20/7) = 765.71

Hence the optimal solution has cost 765.71

It is clear that the above graphical approach to solving LP's can be used for LP's with two variables but most LP's have more than two variables. This brings us to the simplex algorithm for solving LP's.