UNIT 2 LINEAR PROGRAMMING

PROBLEMS
Structure
2.1 Introduction
Objectives
2.2 Linear Programming Problem (LPP)
2.3 Mathematical Formulation of LPP
2.4 Graphical Solution of Linear Programming Problems
2.5 Canonical and Standard Forms of LPP
General Linear Programming Problem
Slack and Surplus Variables
Canonical Form
Standard Form
2.6 Summary
2.7 Solutions/Answers

2.1 INTRODUCTION
In Unit 1, you have learnt about the origin, scope, uses and limitations of
Operations Research. We have also discussed the concept of optimisation
and explained the basic feasible solution of linear programming problem.
In this unit, we discuss linear programming problems and explain how they
are formulated mathematically in Secs. 2.2 and 2.3, respectively. We also
define the objective function and explain how its optimum value is obtained
graphically in Sec. 2.4. The objective function may be profit, cost, revenue,
production capacity, etc. Linear programming can be applied to a variety of
problems such as production, transportation, advertising and problems in
public and private organisations, e.g., business, industry, hospitals, libraries
as also in education. In order to solve linear programming problems, we
need to convert them into a canonical or standard form, as explained in
Sec. 2.5.
In the next unit, you will learn how to solve an LPP using trial and error
method and the Simplex method. We shall also discuss the artificial variable
technique and the Big-M method.

Objectives
After studying this unit, you should be able to:

 describe a linear programming problem and its mathematical

formulation;
 discuss the applications and limitations of linear programming
problems;
 formulate the linear programming problems;
 explain how linear programming problems are solved graphically; and
 express the linear programming problems to their canonical and standard
form.
21
Optimisation Techniques-I
2.2 LINEAR PROGRAMMING PROBLEM (LPP)
In Unit 1, you have learnt about the concept of optimisation. Usually, the
requirements of any agency, industry or country far exceed their limited
resources of land, workforce, capital, organisational facilities, etc. Since the
resources at their disposal are limited, the problem is to use them in such a
way as to obtain the maximum production or profit, or to minimise the cost
of production. You have learnt that such problems are called optimisation
problems. A problem wherein the objective is to allot the limited available
resources to the jobs in such a way as to optimise the overall effectiveness,
minimising the total cost or maximising the total profit, is called
mathematical programming. Mathematical programming in which
constraints are expressed as linear equalities/inequalities is called linear
programming.
Linear programming deals with the optimisation of the total effectiveness
expressed as a linear function of decision variables, known as the objective
function, subject to a set of linear equalities/inequalities known as
constraints. Decision variables are the variables in terms of which the
problem is defined.
Every organisation, big or small, has at its disposal four Ms, i.e., Men,
Machines, Money and Materials. The supply of each of these four Ms is
limited. If the supply of these resources is unlimited, the need for
management tools such as linear programming will not arise at all. Since it
is limited, there is a need to find the best allocation of resources in order to
optimise the objective function. Linear programming can be used if the
following conditions are satisfied:
1. Objective function, to be optimised, should be well defined and can be
expressed as a linear function of the decision variables.
2. Resources leading to constraints should be finite and can be expressed
as linear equalities or inequalities in terms of variables.
3. There must be alternative and finite courses of action.
4. Decision variables should be non-negative.
Applications
Linear programming methods are used in various fields including business
and industry by almost all their departments such as production, marketing,
finance, personnel. For example, using linear programming methods, we
can:
i) maximise profits or the number of effective exposures or returns or
revenue; or
ii) minimise costs or times of assembling the parts or the number of
personnel for a job or the transportation cost or the travelling distance of
a salesman.
There are many more applications. However, there are some limitations as well.
Limitations
1. Linear programming method cannot be applied if relationships are not
linear.
2. It may give non-integral values even for those decision variables which
have only integral values.
22
3. Constraints in the linear programming methods are written assuming all Linear Programming
parameters are known. However, in real problems, sometimes these are Problems
not known and hence the full set of constraints cannot be written.

2.3 MATHEMATICAL FORMULATION OF LPP

The mathematical formulation of linear programming problem (LPP) is
described in the following steps:
1. Identify the decision variables of the problem.
2. Express the objective function, which is to be optimised, i.e., maximised
or minimised, as a linear function of the decision variables.
3. Identify the limited available resources, i.e., the constraints and express
them as linear inequalities or equalities in terms of decision variables.
4. Since negative values of the decision variables do not have any valid
physical interpretation, introduce non-negative restrictions.
Let us take an example to illustrate these steps.
Example 1: A small scale industry manufactures two products P and Q
which are processed in a machine shop and assembly shop. Product P
requires 2 hours of work in a machine shop and 4 hours of work in the
assembly shop to manufacture while product Q requires 3 hours of work in
machine shop and 2 hours of work in assembly shop. In one day, the
industry cannot use more than 16 hours of machine shop and 22 hours of
assembly shop. It earns a profit of `3 per unit of product P and `4 per unit of
product Q. Give the mathematical formulation of the problem so as to
maximise profit.
Solution: Let x and y be the number of units of product P and Q, which are
to be produced. Here, x and y are the decision variables. Suppose Z is the
profit function.
Since one unit of product P and one unit of product Q gives the profit of
`3 and `4, respectively, the objective function is
Maximise Z = 3x + 4y
The requirement and availability in hours of each of the shops for
manufacturing the products are tabulated as follows:

Machine Shop Assembly Shop Profit

Product P 2 hours 4 hours `3 per unit
Product Q 3 hours 2 hours `4 per unit
Available hours per day 16 hours 22 hours

Total hours of machine shop required for both types of product = 2x + 3y

Total hours of assembly shop required for both types of product = 4x + 2y
Hence, the constraints as per the limited available resources are:
2x + 3y  16
and 4x + 2y  22
Since the number of units produced for both P and Q cannot be negative, the
non-negative restrictions are:
x  0, y  0 23
Optimisation Techniques-I Thus, the mathematical formulation of the given problem is

Maximise Z = 3x + 4y
subject to the constraints
2x + 3y  16
4x + 2y  22
and non-negative restrictions
x  0, y  0

Now, you should try to formulate the following problem mathematically.

g is the symbol of gram.
E1) A company produces two types of items P and Q that require gold
and silver. Each unit of type P requires 4g silver and 1g gold while
that of Q requires 1g silver and 3g gold. The company can produce
8g silver and 9g gold. Suppose each unit of type P brings a profit of
`44 and that of type Q, `55. Give the mathematical formulation for
the problem to determine the number of units of each type that the
company should produce to maximise the profit.
Before studying the next section, match your solution with the solution
given in Sec. 2.7.

2.4 GRAPHICAL SOLUTION OF LINEAR

PROGRAMMING PROBLEMS
In Sec. 2.3, you have learnt the mathematical formulation of a linear
programming problem (LPP). In this section, we discuss how to solve this
linear programming problem graphically using the method of graphs of the
inequalities.

The graphical method is used to solve linear programming problems having

two decision variables. For solving LPPs involving more than two decision
variables, we use another method called the Simplex method. We shall
discuss it in Unit 3. But you need to learn the graphical method to acquire
the necessary grounding for learning the Simplex method.

The graphical method of solving a linear programming problem comprises

the following steps:

1. First of all, the graphs are plotted for the equalities corresponding to the
given inequalities for constraints as well as restrictions. That is, we first
draw the straight lines. For example, suppose one of the given
inequalities is 2x + 3y  6. Then, we first plot the graph for the equation
2x + 3y = 6, which is a straight line. For this, we take any two points on
it as follows and join them:

x 0 3

y 2 0

For example, for x = 0, y = 6/3 = 2 and for y = 0, x = 6/2 = 3. So we get

the straight line shown in Fig. 2.1.
24
 Linear Programming
Y
Problems

(0,2)
1

X
(0,0) 1 2 (3,0)

Fig. 2.1
2. Then we determine the region corresponding to each inequality. Let us
consider the inequality 2x + 3y  6 again. We can find the region on the
graph satisfied by this inequality by substituting x = 0 and y = 0 in it. We get
2(0) + 3(0)  6  0  6
which is correct. So it is the region containing the point (0, 0). Hence, the
half plane shown in Fig. 2.2 by arrows starting from the line towards the
point (0, 0) is the graph of the given inequality.

(0,2)

X
(0,0) (3,0)

Fig. 2.2

Had the given inequality been 2x + 3y  6, then we would have drawn

the arrows on the opposite side of the line. This is because on putting
x = 0, y = 0 in the inequality, we get
2(0) + 3(0)  6  06
which is not correct.
Thus the point (0, 0) does not satisfy the inequality and hence does not lie
in this region. The graph for the inequality 2x + 3y  6 would, therefore,
be as shown in Fig. 2.3.
25
Optimisation Techniques-I Y

(0, 2)

X
(0,0) (3, 0)
Fig. 2.3
In this example, we have used the point (0, 0) to determine which half
plane corresponds to the given inequality. However, you can take any
other point. But using (0, 0) is far easier. If the right hand side of the
given inequality is zero, using the point (0, 0) in it is meaningless. For
example, suppose the given inequality is 2x−3y  0. The plot of
2x−3y =0 is given in Fig. 2.4. It is a straight line passing through the
origin. Using the point (0, 0) in the inequality 2x − 3y  0, we get
2(0) − 3(0)  0, i.e., 0  0. So we cannot decide which half plane is the
region of the given inequality. Therefore, in this case, we use any other
point, say (2, 0). On putting x=2, y=0 in the given inequality, we get
2(2) − 3(0)  0  40
which is true. Therefore, the half plane containing (2, 0) is the required
region as shown in Fig. 2.4.
2x
2x − 3y = 0  3y = 2x  y =
3
x x 0 3
y 0 2
Y

(3, 2)
(0,2) 

(0,0)
 X
(3,0)

Fig. 2.4
26
3. After determining the regions for each inequality, we find their Linear Programming
common region, i.e., the region obtained on superimposing their Problems
regions of inequality. This is the region where all the given
inequalities and the non-negative restrictions are satisfied. This
common region is known as the feasible region or the solution set or
the polygonal convex set (Recall that you have learnt about the
convex set in Sec. 1.6 of Unit 1).
4. Next we determine each of the corner points (vertices) of the polygon
obtained in step 3. This is done either by plotting the graphs on graph
paper or by solving the two equations of the lines intersecting at that
point.
5. a) The objective function at each corner point is evaluated. If the feasible
region is bounded, then
i) the maximum of the values obtained for the objective function at
the corner points is the optimum value when the objective function
is of the maximisation form. The point corresponding to this
maximum value gives the required values of the decision variables.
ii) the minimum of the values obtained for the objective function at
the corner points is the optimum value when the objective function
is of the minimisation form. The point corresponding to this
minimum value gives the required values of the decision variables.
b) The feasible region may not be bounded. Then either there are
additional hidden conditions which can be used to bound the region or
there is no solution to the problem.
c) If the same optimum value exists at two of the vertices, then there are
multiple solutions to the problem. Suppose these two points are (x1, y1)
and (x2, y2). Then other solutions are given by the points as follows:
[First ordinate of first point × t + First ordinate of second point × (1t),
Second ordinate of first point × t + Second ordinate of second point × (1t)]
For the points (x1, y1) and (x2, y2), the other solutions exist at the
points: [(x1× t + x2 × (1  t), y1× t + y2×(1  t)]
where t is any real number lying between 0 and 1.
For example, let the objective function be Z = 3x  y and let A (2, 1) and Z = 3x - y
B(3, 4) be the points which give the same optimum value of the objective æ5 ö 5
function, i.e., Z = 5. Then other solutions which give the same value of the = 3 çç ÷÷-
objective function are: è2ø 2
15 5
(2 × t + 3 ×(1  t), 1 × t + 4 ×(1  t)) = - =5
2 2
or (2t + 3  3t, t + 4  4t)
or (3  t, 4  3t), 0  t  1
Here t = 0 gives the point (3, 4), which is point B and t = 1 gives the point
(2, 1), which is point A. The real values of t between 0 and 1 give other points
which give the same optimum solution. One such point other than A and B is
 1 1 1 5 5
 3  , 4  3×  , for t , i.e.,  , 
 2 2 2 2 2
5 5
You can verify that Z = 5 at the point  ,  . We illustrate this method in
2 2
Example 2.
27
Optimisation Techniques-I Example 2: A company produces two types of items P and Q that require
gold and silver. Each unit of type P requires 4g silver and 1g gold while that
of type Q requires 1g silver and 3g gold. The company can produce 8g
silver and 9g gold. If each unit of type P brings a profit of `44 and that of
type Q `55, determine the number of units of each type that the company
should produce to maximise the profit. What is the maximum profit?
Solution: Let x be the number of units of type P to be produced and y be the
number of units of type Q to be produced. It is given that:
Silver Gold Profit
Type P 4g 1g `44 per unit
Type Q 1g 3g `55 per unit
Available (at the most) 8g 9g

Let Z be the profit function. The mathematical formulation of the given

problem is
Max. Z = 44x + 55y
Max. stands for subject to the constraints:
Maximisation 4 x + y  8,
x + 3y  9,
x  0, y  0.
First of all, we plot the graphs for the following equations:
4 x + y = 8, x + 3y = 9, x = 0 , y = 0.
Since these equations are of straight lines, only two points are sufficient to
plot the graphs (see Fig. 2.5). For the line 4 x + y = 8, we take the following
two points:
x 0 2
y 8 0
Similarly, for the line x + 3y = 9, we take
x 0 9
y 3 0
Now, plotting the above lines, we get Fig. 2.5.

4x+y = 8

8
7
6
5
4
x+3y = 9
3
2
1
y=0   X
(0,0) 1 2 3 4 5 6 7 8 9

x=0
Fig. 2.5
28
Note that x = 0 is the y-axis and y = 0 is the x-axis. Linear Programming
Problems
For plotting the graph of the inequality 4x + y  8 we put (0, 0) in it. We get
0  8, which is true. Therefore, starting from the line 4x + y  8, we shall
shade towards origin. Similarly, for the graph x + 3y  9, we shall shade
towards origin. For the graph x  0, we shall shade towards right side of
x = 0 and for the graph y  0, the region above y = 0 will be shaded.
Thus, the regions for the inequalities are shown in Fig. 2.6 by arrows:

4x+y = 8

8 D
7
6
5
4
x+3y = 9 C
3 B

2
1
E
 X
O 1 2A 3 4 5 6 7 8 9

Fig. 2.6
The most common shaded portion is the region inside and on the polygon
OABC shown in Fig. 2.6. You can see from Fig. 2.6 that the coordinates of
O, A and C are (0,0), (2,0) and (0,3), respectively.
4x + y = 8 (i)
The coordinates of the point B are obtained by solving the equations
4x + y = 8 and x + 3y = 9 as it is the point of intersection of the two lines x + 3y = 9 (ii)
represented by them. The solution of 4x + y = 8 and x + 3y = 9 is given as We multiply equation (i) by 3:

15 28 12x + 3y = 24 (iii)
x and y 
11 11 We subtract equation (ii) from
equation (iii):
 15 28 
So the vertices of OABC are O (0, 0), A (2, 0), B  ,  and C(0, 3).
 11 11  11x = 15
We now obtain the values of Z = 44x+ 55y at each of the vertices of OABC 15
So we get x =
as follows: 11
15
At O (0, 0), Z = 44 (0) + 55 (0) = 0 Putting x = in equation (ii),
11
At A (2, 0), Z = 44 (2) + 55 (0) = 88 15 28
we get + 3y = 9 Þ y =
æ15 28 ö æ15 ö æ28 ö 11 11
At B çç , ÷ ÷, Z = 44 çç ÷ ÷ + 55 çç ÷ ÷
è 11 11 ø è 11 ø è 11 ø
= 60 + 140 = 200
At C (0, 3), Z = 44(0) + 55(3) = 165
29
Optimisation Techniques-I
 15 28 
Thus, the value of Z is maximum at B  , 
 11 11 
and the optimum solution is
15 28
Max. Z = 200 when x  and y  .
11 11
Now, you should try to solve the following exercises.

E2) Maximise Z = 6X + 3Y
subject to the constraints
2X  5Y  120
4X  2Y  80
X  0, Y  0
E3) Maximise z  3x1  2x 2
subject to the constraints
x1  x 2  1
x1  x 2  3
x1  0, x 2  0
E4) Maximise Z  x1  x 2
subject to the constraints
x1  x 2  1
3x1  x 2  3
x1  0, x 2  0
E5) A company manufactures two products X and Y, each of which
requires three types of processing. The length of time for processing
each unit and the profit per unit are given in the following table:

Product X Product Y Available capacity

(hr/unit) (hr/unit) per day (hr)
Process I 12 12 840
Process II 3 6 300
Process III 8 4 480
Profit per unit (`) 5 7

How many units of each product should the company manufacture

per day in order to maximise profit?
E6) A company produces soft drinks and has a contract requiring that a
minimum of 80 units of chemical A and 60 units of chemical B go
into each bottle of the drink. The chemicals are available in a
prepared mix from two different suppliers. The supplier X1 has a mix
of 4 units of A and 2 units of B that costs `10, and the supplier X 2 has
a mix of 1 unit of A and 1 unit of B that costs `4. How many mixes
from the company X1 and company X 2 should the company purchase
to honour contract requirement and yet minimise cost?
Before studying the next section, match your solution with the solution
given in Sec. 2.7.
30
 Linear Programming
2.5 CANONICAL AND STANDARD FORMS OF Problems
LPP
After formulating a linear programming problem, our next step is to solve it.
You have learnt in Secs. 2.3 and 2.4 that linear programming problems can
be presented as problems of maximisation or minimisation with constraints
such as ≤ , = or ≥. In order to develop a standard procedure for solving
LPPs, we need to convert them into well known forms, namely, the
Canonical form and the Standard form. We now discuss the General LPP
along with these two forms. The canonical form is especially used in the
duality theory and the standard form is used to develop the general
procedure for solving any linear programming problem. In order to
understand these forms you also need to learn about slack and surplus
variables.

2.5.1 General Linear Programming Problem

Let us formulate the general linear programming problem. Let Z be a linear
function of n basic variables X1, X2, …, Xn, which is to be maximised
(or minimised). We write the problem as
Maximise(or Minimise) Z = C1X1 + C2 X2 +... +Cn Xn … (1)
where C1, C2, …, Cn are known constants termed as cost coefficients of
basic variables.
Let (aij) be an m × n real matrix of m×n constants aij’s and let {b1, b2, …,
bm} be a set of constants such that
a11x1 + a12 x 2 +... +a1n x n ³ or £ or = b1

a 21x1 + a 22 x 2 +... + a 2n x n ³ or £ or = b 2
. . . .
…(2)
. . . .
a m1x1 + a m2 x 2 +... + a mn x n ³ or £ or = b m

and x j  0 for all j=1, 2, …, n …(3)

The linear function Z in equation (1) is called the objective function. The
set of inequalities given in (2) is called constraints of a general LPP and the
set of inequalities given in (3) are known as non-negative restrictions of a
general LPP.

2.5.2 Slack and Surplus Variables

In general, if in any linear programming problem, we have a constraint of
the type
a11x1 + a12 x 2 +... + a1n x n £ b1 , where b1 ³ 0

then this inequality can be converted into an equation by adding one

non-negative variable s1 to the left hand side. This new variable is called a
slack variable and the constraints are transformed into the following
equation:

a11x1 + a12 x 2 +... + a1n x n + s1 = b1 , where s1 ³ 0, b1 ³ 0

31
Optimisation Techniques-I Thus, a non-negative variable added to the left-hand side of a less than or
equal to    type of constraint that converts it into an equation is called a
slack variable. The value of this variable can be interpreted as the amount
of unused resource.
Similarly, if in any linear programming problem, we have a constraint of the
type
a11y1 + a12 y2 +... + a1n yn ³ b1 , b1 ³ 0
then this inequality can be converted into an equation by subtracting one
non-negative variable s1 from the left hand side. This new variable is called
a surplus variable and the constraints are transformed into an equation as

a11y1 + a12 y2 +... + a1n yn - s1 = b1 , where s1 ³ 0, b1 ³ 0

Thus, a non-negative variable subtracted from the left-hand side of a

greater than or equal to    type of constraint that converts it into an
equation is called a surplus variable. The value of this variable can be
interpreted as the amount over and above the required minimum level.
Let us now obtain the canonical form of the LPP.

2.5.3 Canonical Form

The characteristics of the canonical form are explained in the following
steps:
i) The objective function should be of maximisation form. If it is given in
the minimisation form, it should be converted into maximisation form.
Suppose Z = ax + by is the given objective function which is to be
minimised. Then, it is equivalent to maximising its negative function,
i.e., Z. The reason is that if a function f(x) is minimum at the same
point x = a (say), then f(x) will be maximum at x = a as shown in
Fig. 2.7:

 y = f(x)

a
X

 y = f(x)

Fig. 2.7

Note: The graph of y = f(x) is the mirror image of the graph of y = f(x)
about the x-axis as shown Fig. 2.7 and x = a is the point where f(x) is
minimum and f(x) is maximum.
32
ii) All constraints should be of “ ” type, except for non-negative Linear Programming
restrictions. Inequality of “ ” type, if any, should be changed to an Problems

inequality of the “ ” type by multiplying both sides of the inequality

by 1. For example, suppose a given inequality is
2x + 3y  5
Then it can be written as
2x 3y  5
iii) All the variables should be non-negative. If a given variable is unrestricted
in sign (i.e., positive, negative or zero), it can be written as a difference of
two non-negative variables. Suppose x is unrestricted in sign, then x can
be written as
x = x  x, where x  0, x  0.
Let us explain this point further: Suppose x = 5. Then it can be written as
the difference of two non-negative numbers: 2  7 (say). Here 2 and 7 are
non-negative.
Example 3: Rewrite the following linear programming problem in
canonical form:
Minimise Z  2x1  x 2  4x 3
subject to the constraints:
2x1  4x 2  4
x1  2x 2  x3  5
2x1  3x 3  2
x1 , x 2 ³ 0 and x 3 is unrestricted in sign
Solution: Here, the objective function is of the minimisation form. We
rewrite it in the maximisation form as follows:
Minimise Z  2x1  x 2  4x 3
Thus, we have to maximise - Z = - 2x1 - x 2 - 4x 3 . So the problem becomes,
Maximise Z' =  2x1  x 2  4x 3 , where Z  Z
Now, the second constraint is of the type “  ”. Hence, to convert it into type
“” , we multiply the inequality by 1 and write
 x1  2x 2  x 3  5
Other constraints are already in the desired form. But x3 is unrestricted in
sign. So we write
x3  x3  x3 , where x3  0, x3  0.
The canonical form of the given problem, therefore, is
Maximise Z'  2x1  x 2  4(x3  x3 ), where Z'  Z
subject to the constraints:
- 2x1 + 4x 2 £ 4
x1  2x 2  (x3  x3 )  5
2x1  3(x3  x3 )  2
x1  0, x 2  0, x3  0, x3  0
We now discuss the standard form.
33
Optimisation Techniques-I
2.5.4 Standard Form
The characteristics of the standard form are explained in the following steps:
i) The objective function should be in the maximisation form as already
explained in Sec. 2.5.3.
ii) The right side element of each constraint should be non-negative. If it
is negative, we multiply the inequality by 1.
iii) All constraints should be expressed in the form of equations, except
for the non-negative restrictions. The inequalities should be converted
into equations by augmenting the non-negative variables to the left
side of each constraint. For inequalities of the “ ≤ ” type, we add the
slack variables. If the inequalities are of the “  ” type, we subtract
surplus variables.
Example 4: Rewrite the following linear programming problem in the
standard form:
Minimise Z  2x1  x 2  4x 3
subject to the constraints:
2x1  4x 2  4
x1  2x 2  x3  5
2x1  3x 3  2
x1  0, x 2  0 x 3  0.
Solution: The objective function should be of maximisation form, i.e., we
have to
Maximise Z' =- 2x1 - x 2 - 4x 3 , where Z¢=- Z
subject to the constraints:
2x1  4x 2  4
x1  2x 2  x3  5
- 2x1 - 3x 3 £ 2 [ Right side should be non-negative]
x1  0, x 2  0 x 3  0.

Now, the inequalities are to be converted to equations. Note that the first
and third inequalities are of the type “less than or equal to ()”.
Therefore, a slack variable is to be added to the left side of each of these
inequalities. The second inequality is of the type “more than or equal to ()”.
So a surplus variable is to be subtracted from the left side of this inequality.
Thus, the standard form of the given LPP is
Max. Z' = - 2x1 - x 2 - 4x 3 + 0s1 + 0s2 + 0s3 , where Z' = - Z
subject to the constraints:
2x1  4x 2  s1  4
x1  2x 2  x 3  s2  5
2x1  3x 3  s3  2
x1  0, x 2  0, x 3  0, s1  0, s2  0, s3  0
Now, you should try to solve the following exercises.
34
E7) Express the following LPP in canonical form: Linear Programming
Problems
Minimise Z  x1  2x 2  x3
subject to the constraints:
2x1  3x 2  4x 3  4
3x1  5x 2  2x 3  7

x1  0, x 2  0, x 3  0

E8) Express the following LPP in standard form:

Minimise Z  x1  2x 2  x 3
subject to the constraints:
2x1  3x 2  4x 3  4
3x1  5x 2  2x 3  7

x1  0, x 2  0 x 3  0.

You may like to match your solution with the solution given in Sec. 2.7.
Let us now summarise the main points which have been covered in this unit.

2.6 SUMMARY
1. A problem wherein the objective is to allot the limited available
resources to the jobs in such a way as to optimise the overall
effectiveness, i.e., minimise the total cost or maximise the total profit, is
called mathematical programming. Mathematical programming
wherein constraints are expressed as linear equalities/inequalities is
called linear programming. Linear programming deals with the
optimisation of the total effectiveness expressed as a linear function of
decision variables, known as the objective function, subject to a set of
linear equalities/inequalities known as constraints.

2. Steps involved in the mathematical formulation of a linear

programming problem (LPP) are: i) Identification of the decision
variables of the problem; ii) expressing the objective function as a
linear function of the decision variables; iii) identifying the limited
available resources to write the constraints as linear inequalities or
equalities in terms of decision variables; iv) introducing the non-
negative restrictions.

3. Graphical method is used to solve linear programming problems

having two decision variables. The graphical method of solving linear
programming programs comprises the following steps: i) The graphs are
plotted for the equations corresponding to the given inequalities for
constraints as well as restrictions; ii) The region corresponding to each
inequality is shaded; iii) After shading the regions for each inequality,
the most common shaded portion, i.e., the region obtained on
superimposing all the shaded regions is determined. This is the region
where all the given inequalities, including non-negative restrictions are 35
Optimisation Techniques-I satisfied. This common region is known as the feasible region or the
solution set or the polygonal convex set; iv) Each of the corner points
(vertices) of the polygon is then determined; v) The objective function at
each corner point is evaluated.

4. If the feasible region is bounded, then the greatest value obtained for
the objective function at the corner points is the optimum value when
the objective function is of maximisation form; and the least value
obtained for the objective function at the corner points is the optimum
value when the objective function is of minimisation form.

5. The feasible region may not be bounded. Then either there are
additional hidden conditions which can be used to bound the region or
there is no solution to the problem.

6. If the same optimum value occurs at two vertices, then there are
multiple optimal solutions to the problem.

7. The characteristics of the canonical form are: i) Objective function

should be of maximisation form. If it is given in minimisation form, it
should be converted into maximisation form; ii) All the constraints
should be of “  ” type, except for non-negative restrictions. Inequality
of “  ” type, if any, should be changed to an inequality of the “  ” type;
iii) All variables should be non-negative.

8. The characteristics of standard form are: i) The objective function

should be of maximisation form; ii) The right side element of each
constraint should be non-negative; iii) All constraints should be
expressed in the form of equations, except for the non-negative
restrictions by augmenting slack or surplus variables.

2.7 SOLUTIONS/ANSWERS
E1) Let x be the number of units of type P to be produced and y be the
number of units of type Q to be produced. It is given that:

Silver Gold Profit

Type P 4g 1g `44 per unit
Type Q 1g 3g `55 per unit
Available (at the most) 8g 9g

Let Z be the profit function.

 The mathematical formulation of the given problem is
Max. Z = 44x + 55y
subject to the constraints:
4x+y8
x + 3y  9
x  0, y  0.

36
E2) Max. Z = 5x + 7y Linear Programming
Problems
subject to the constrains:
12x + 12y  840  x + y  70
3x + 6y  300  x + 2y  100
8x + 4y  480  2x + y  120
x0, y0

Y
2x + y = 120
120 
110
100
x + y =70 90
80

70F 
x + 2y = 100 60
D
50  (0,50)
40
C(40,30)
30 
 E
20 B(50,20)
10
   X
O(0,0) 10 20 30 40 50 60 70 80 90 100
A(60,0)

Fig. 2.8
At O(0, 0), Z = 5(0) + 7(0) = 0
At A(60, 0), Z = 5(60) + 7(0) = 300
At B(50, 20), Z = 5(50) + 7(20)
= 250 + 140 = 390
At C(40, 30), Z = 5(40) + 7(30)
= 200 + 210 = 410
At D(0, 50), Z = 5(0) + 7(50) = 350
The maximum value of Z is 410 at C(40, 30), i.e., at x = 40, y = 30.
E3) Minimise Z = 10x1 + 4x2
subject to the constraints
4x1  x 2  80
2x1  x 2  60
x1  0, x 2 0
37
Optimisation Techniques-I . X2

4x1+x2=80

80  C(0, 80)
70 80)
60 
50
 B(10,40)
40
Fig. 2.9
30
20
10
  X1
O(0,0) 10 20 30 A(30,0)

Fig. 2.9

At A(30, 0), Z = 10(30) + 4(0) = 300

At B(10, 40), Z = 10(10) + 4(40)
= 100 + 160 = 260
At C (0, 80), Z = 10(0) + 4(80) = 320
The minimum value of Z is 260 at B(10, 40), i.e., when x1 = 10 and
x2 = 40.

Note: Had the objective function been of maximisation form, the

problem would have the unbounded solution. This is because the
values of x1 and x2 could be increased beyond any limit, which
would result in higher and higher value of Z with no upper bound.

E4) At O(0, 0), Z = 6(0) + 3(0) = 0

At A(20, 0), Z = 6(20) + 3(0) = 120

At B(10, 20), Z = 6(10) + 3(20) = 60 + 60 = 120

At C(0, 24), Z = 6(0) + 3(24) = 0 + 72 = 72

The maximum value of Z is 120 at A(20, 0) as well as at B(10, 20).

Therefore, the given LPP has multiple optimal solutions (Fig. 2.10).

Other points at which Z gives the same maximum value are given as
(20×t + 10×(1  t), 0×t + 20×(1  t))
or (20t + 10 10t, 0 + 20  20t)
or (10 + 10t, 20  20t), 0 t  1.

38
 Linear Programming
Problems
Y

40  D(0, 40)

2x+5y=120
30

C(0, 24) 
B(10,20)
20

10
E(60,0)
  X
O(0,0) 10 20 30 40 50 EE60
A(20,0)

4x+2y=80
Fig. 2.10

E5) Here, we have to maximise the objective function. But the values of
decision variables can be increased infinitely without violating the
feasibility condition and hence the value of the objective function
can be increased infinitely. Thus, the solution in this case is
unbounded (Fig.2.11).

X2

x1 + x2 = 3
3 
B(0,3)
x1  x2 = 1
2

1  A(2, 1)

 X1
0(0,0) 1 2 3
1 

Fig. 2.11

Note: Had it been a minimisation problem, then it would have the

optimum solution at one of the points A (2, 1) and B (3, 0) where it
has the minimum value.
39
Optimisation Techniques-I At A(2, 1), Z = 3(2) + 2(1) = 8
At B(3, 0), Z = 3(3) + 2(0) = 9
The minimum value is at A(2, 1), i.e., when x1 = 2 and x2 = 1.

E6) We find no common region for all the four graphs and hence the
given LPP has no solution (Fig. 2.12).
X2

3
x1+x2 = 1
2

X1
1 1

Fig. 2.12

E7) Maximise Z'  x1  2x 2  x 3 , where Z'  Z

subject to the constraints
2x1  3x 2  4x 3  4
3x1  5x 2  2x3  7

x1  0, x 2  0 x 3  0.

E8) Maximise Z'  x1  2x 2  x 3  0s1  0s2 , where Z'  Z

subject to the constraints
2x1  3x 2  4x 3  s1  4
3x1  5x 2  2x 3  s2  7

x1  0, x 2  0 x 3  0, s1  0, s2  0.

40