MBA-H2040 Quantitative Techniques for Managers

UNIT I
LESSON

2 LINEAR PROGRAMMING –GRAPHICAL METHOD

LESSON STRUCTURE

2.1 Introduction to Linear Programming

2.2 Linear Programming Problem
Formulation
2.3 Formulation with Different Types of
Constraints
2.4 Graphical Analysis of Linear
Programming
2.5 Graphical Linear Programming Solution
2.6 Multiple Optimal Solutions
2.7 Unbounded Solution
2.8 Infeasible Solution
2.9 Summary
2.10 Key Terms
2.11 Self Assessment Questions
2.12 Key Solutions
2.13 Further References
MBA-H2040 Quantitative Techniques for Managers

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

 Formulate Linear Programming Problem

 Identify the characteristics of linear
programming problem
 Make a graphical analysis of the linear
programming problem
 Solve the problem graphically
 Identify the various types of solutions
MBA-H2040 Quantitative Techniques for Managers

2.1 Introduction to Linear Programming

Linear Programming is a special and versatile technique which can be applied to a variety of
management problems viz. Advertising, Distribution, Investment, Production, Refinery Operations, and
Transportation analysis. The linear programming is useful not only in industry and business but also in
non-profit sectors such as Education, Government, Hospital, and Libraries. The linear programming
method is applicable in problems characterized by the presence of decision variables. The objective
function and the constraints can be expressed as linear functions of the decision variables. The
decision variables represent quantities that are, in some sense, controllable inputs to the system being
modeled. An objective function represents some principal objective criterion or goal that measures the
effectiveness of the system such as maximizing profits or productivity, or minimizing cost or
consumption. There is always some practical limitation on the availability of resources viz. man,
material, machine, or time for the system. These constraints are expressed as linear equations involving
the decision variables. Solving a linear programming problem means determining actual values of the
decision variables that optimize the objective function subject to the limitation imposed by the
constraints.
The main important feature of linear programming model is the presence of linearity in the
problem. The use of linear programming model arises in a wide variety of applications. Some model
may not be strictly linear, but can be made linear by applying appropriate mathematical transformations.
Still some applications are not at all linear, but can be effectively approximated by linear models. The
ease with which linear programming models can usually be solved makes an attractive means of dealing
with otherwise intractable nonlinear models.

2.2 Linear Programming Problem Formulation

The linear programming problem formulation is illustrated through a product mix problem. The product
mix problem occurs in an industry where it is possible to manufacture a variety of products. A product
has a certain margin of profit per unit, and uses a common pool of limited resources. In this case the
linear programming technique identifies the products combination which will maximize the profit
subject to the availability of limited resource constraints.

Example 2.1:

Suppose an industry is manufacturing tow types of products P1 and P2. The profits per Kg of the two
products are Rs.30 and Rs.40 respectively. These two products require processing in three types of
machines. The following table shows the available machine hours per day and the time required on each
18
MBA-H2040 Quantitative Techniques for Managers
machine to produce one Kg of P1 and P2. Formulate the problem in the form of linear programming
model.

Profit/Kg P1 P2 Total available Machine

Rs.30 Rs.40 hours/day
Machine 1 3 2 600
Machine 2 3 5 800
Machine 3 5 6 1100

Solution:

The procedure for linear programming problem formulation is as follows:

Introduce the decision variable as follows:

Let x1 = amount of P1
x2 = amount of P2

In order to maximize profits, we establish the objective function as

30x1 + 40x2

Since one Kg of P1 requires 3 hours of processing time in machine 1 while the corresponding
requirement of P2 is 2 hours. So, the first constraint can be expressed as

3x1 + 2x2 ≤ 600

Similarly, corresponding to machine 2 and 3 the constraints are

3x1 + 5x2 ≤ 800

5x1 + 6x2 ≤ 1100
In addition to the above there is no negative production, which may be represented algebraically as

x1 ≥ 0 ; x2 ≥ 0

Thus, the product mix problem in the linear programming model is as follows:

Maximize
30x1 + 40x2

Subject to:
3x1 + 2x2 ≤ 600
3x1 + 5x2 ≤ 800
5x1 + 6x2 ≤ 1100
x1≥ 0, x2 ≥ 0

2.3 Formulation with Different Types of Constraints

19
MBA-H2040 Quantitative Techniques for Managers
The constraints in the previous example 2.1 are of “less than or equal to” type. In this section we are
going to discuss the linear programming problem with different constraints, which is illustrated in the
following Example 2.2.
Example 2.2:

A company owns two flour mills viz. A and B, which have different production capacities for high,
medium and low quality flour. The company has entered a contract to supply flour to a firm every month
with at least 8, 12 and 24 quintals of high, medium and low quality respectively. It costs the company
Rs.2000 and Rs.1500 per day to run mill A and B respectively. On a day, Mill A produces 6, 2 and 4
quintals of high, medium and low quality flour, Mill B produces 2, 4 and 12 quintals of high, medium
and low quality flour respectively. How many days per month should each mill be operated in order to
meet the contract order most economically.
Solution:

Let us define x1 and x2 are the mills A and B. Here the objective is to minimize the cost of the machine
runs and to satisfy the contract order. The linear programming problem is given by
Minimize
2000x1 + 1500x2

Subject to:
6x1 + 2x2 ≥ 8
2x1 + 4x2 ≥ 12
4x1 + 12x2 ≥ 24

x1 ≥ 0, x2 ≥ 0

2.4 Graphical Analysis of Linear Programming

This section shows how a two-variable linear programming problem is solved graphically, which is
illustrated as follows:

Example 2.3:
Consider the product mix problem discussed in section 2.2

Maximize
30x1 + 40x2

Subject to:
3x1 + 2x2 ≤ 600
3x1 + 5x2 ≤ 800
5x1 + 6x2 ≤ 1100
x1≥ 0, x2 ≥ 0

20
 MBA-H2040 Quantitative Techniques for Managers
From the first constraints 3x1 + 2x2 ≤ 600, draw the line 3x1 + 2x2 = 600 which passes through the point
(200, 0) and (0, 300). This is shown in the following graph as line 1.

300
3x1 + 2x2 = 600(line 1)

200

B
X2

C
100

3x1 + 5x2 = 800(line 2)

5x1 + 6x2 = 1100(line 3)

A
D
0 50 100 150 X1
200 275

Graph 1: Three closed half planes and Feasible Region

Half Plane - A linear inequality in two variables is called as a half plane.

Boundary - The corresponding equality (line) is called as the boundary of the half plane.

Close Half Plane – Half plane with its boundary is called as a closed half plane.
21
MBA-H2040 Quantitative Techniques for Managers
In this case we must decide in which side of the line 3x1 + 2x2 = 600 the half plane is located. The

easiest way to solve the inequality for x2 is

3x1 ≤ 600 – 2x2

And for the fixed x1, the coordinates satisfy this inequality are smaller than the corresponding ordinate

on the line and thus the inequality is satisfied for all the points below the line 1.

Similarly, we have to determine the closed half planes for the inequalities 3x1 + 5x2 ≤ 800 and
5x1 + 6x2 ≤ 1100 (line 2 and line 3 in the graph). Since all the three constraints must be satisfied
simultaneously we have consider the intersection of these three closed half planes. The complete
intersection of these three closed half planes is shown in the above graph as ABCD. The region ABCD
is called the feasible region, which is shaded in the graph.
Feasible Solution:
Any non-negative value of x1, x2 that is x1 ≥ 0 and x2 ≥ 0 is known as feasible solution of the linear
programming problem if it satisfies all the existing constraints.
Feasible Region:
The collection of all the feasible solution is called as the feasible region.

Example 2.4:
In the previous example we discussed about the less than or equal to type of linear programming
problem, i.e. maximization problem. Now consider a minimization (i.e. greater than or equal to type)
linear programming problem formulated in Example 2.2.

Minimize
2000x1 + 1500x2

Subject to:
6x1 + 2x2 ≥ 8
2x1 + 4x2 ≥ 12
4x1 + 12x2 ≥ 24

x1 ≥ 0, x2 ≥ 0

The three lines 6x1 + 2x2 = 8, 2x1 + 4x2 = 12, and 4x1 + 12x2 = 24 passes through the point
(1.3,0) (0,4), (6,0) (0,3) and (6,0) (0,2). The feasible region for this problem is shown in the following
Graph 2. In this problem the constraints are of greater than or equal to type of feasible region, which is
bounded on one side only.

22
MBA-H2040 Quantitative Techniques for Managers

X2 A
4
6x1 + 2x2 ≥ 8

2 2x1 + 4x2 ≥ 12

C 4x1 + 12x2 ≥ 24
0
X1
2 4 6 8

Graph 2: Feasible Region

2.5 Graphical Liner Programming Solution

A two variable linear programming problem can be easily solved graphically. The method is simple but
the principle of solution is depends on certain analytical concepts, they are:
Convex Region:
A region R is convex if and only if for any two points on the region R the line connecting those points
lies entirely in the region R.
Extreme Point:
The extreme point E of a convex region R is a point such that it is not possible to locate two distinct
points in R, so that the line joining them will include E. The extreme points are also called as corner
points or vertices.
Thus, the following result provides the solution to the linear programming model:
 “If the minimum or maximum value of a linear function defined over a convex region exists,
then it must be on one of the extreme points”.
23
 MBA-H2040 Quantitative Techniques for Managers

In this section we are going to describe linear programming graphical solution for both the
maximization and minimization problems, discussed in Example 2.3 and Example 2.4.

Example 2. 5:

Consider the maximization problem described in Example 2.3.

Maximize
30x1 + 40x2
Subject to:
3x1 + 2x2 ≤ 600
3x1 + 5x2 ≤ 800
5x1 + 6x2 ≤ 1100
M = 30x1 +40x2
x1 ≥ 0, x2 ≥ 0

The feasible region identified in the Example 2.3 is a convex polygon, which is illustrated in the
following Graph 3. The extreme point of this convex region are A, B, C, D and E.

300

200

X2 C

100

A D
E

0 50 100 150 X1
200 275
24
MBA-H2040 Quantitative Techniques for Managers

Graph 3: Graphical Linear Programming Solution

In this problem the objective function is 30x1 + 40x2. Let be M is a parameter, the graph 30x1 +
40x2 = M is a group of parallel lines with slope – 30/40. Some of these lines intersects the feasible region
and contains many feasible solutions, whereas the other lines miss and contain no feasible solution. In
order to maximize the objective function, we find the line of this family that intersects the feasible
region and is farthest out from the origin. Note that the farthest is the line from the origin the greater will
be the value of M.
Observe that the line 30x1 + 40x2 = M passes through the point D, which is the intersection of the
lines 3x1 + 5x2 = 800 and 5x1 + 6x2 = 1100 and has the coordinates x1 = 170 and x2 = 40. Since D is the
only feasible solution on this line the solution is unique.
The value of M is 6700, which is the objective function maximum value. The optimum value
variables are x1 = 170 and X2 = 40.
The following Table 1 shows the calculation of maximum value of the objective function.

Extreme Point Coordinates Objective Function

X1 X2 30x1 + 40x2
A X1 = 0 X2 = 0 0
B X1 = 0 X2 = 160 6400
C X1 = 110 X2 = 70 6100
D X1 = 170 X2 = 40 6700
E X1 = 200 X2 = 0 6000

Table 1: Shows the objective function Maximum value calculation

Example 2.6:
Consider the minimization problem described in Example 2.4.

Minimize
2000x1 + 1500x2

Subject to:
6x1 + 2x2 ≥ 8
2x1 + 4x2 ≥ 12
4x1 + 12x2 ≥ 24
x1≥ 0, x2 ≥ 0

The feasible region for this problem is illustrated in the following Graph 4. Here each of the half
planes lies above its boundary. In this case the feasible region is infinite. In this case, we are concerned
with the minimization; also it is not possible to determine the maximum value. As in the previous

25
 MBA-H2040 Quantitative Techniques for Managers
example let us introduce a parameter M in the objective function i.e. 2000x1 + 1500x2 = M and draw the
lines for different values of M, which is shown in the following Table 2.

X2 A
4

C
0
2000x1+ 1500x2=M X1
2 4 6 8

Graph 4: Graphical Linear Programming Solution

Extreme Point Coordinates Objective Function

X1 X2 2000x1 + 1500x2
A X1 = 0 X2 = 4 6000
B X1 = 0.5 X2 = 2.75 5125
C X1 = 6 X2 = 0 12000

Table 2: Shows the objective function Minimum value computation

The minimum value is 5125 at the extreme point B, which is the value of the M (objective
function). The optimum values variables are X1 = 0.5 and X2 = 2.75.

2.6 Multiple Optimal Solutions

26
MBA-H2040 Quantitative Techniques for Managers
When the objective function passed through only the extreme point located at the intersection of two
half planes, then the linear programming problem possess unique solutions. The previous examples i.e.
Example 2.5 and Example 2.6 are of this types (which possessed unique solutions).
When the objective function coincides with one of the half planes generated by the constraints in
the problem, will possess multiple optimal solutions. In this section we are going to discuss about the
multiple optimal solutions of linear programming problem with the help of the following Example 2.7.

Example 2.7:

A company purchasing scrap material has two types of scarp materials available. The first type has 30%
of material X, 20% of material Y and 50% of material Z by weight. The second type has 40% of
material X, 10% of material Y and 30% of material Z. The costs of the two scraps are Rs.120 and
Rs.160 per kg respectively. The company requires at least 240 kg of material X, 100 kg of material Y
and 290 kg of material Z. Find the optimum quantities of the two scraps to be purchased so that the
company requirements of the three materials are satisfied at a minimum cost.
Solution

First we have to formulate the linear programming model. Let us introduce the decision variables x1 and
x2 denoting the amount of scrap material to be purchased. Here the objective is to minimize the
purchasing cost. So, the objective function here is
Minimize
120x1 + 160x2

Subject to:
0.3x1 + 0.4x2 ≥ 240
0.2x1 + 0.1x2 ≥ 100
0.5x1 + 0.3x2 ≥ 290

x1 ≥ 0; x2 ≥ 0

Multiply by 10 both sides of the inequalities, then the problem becomes

Minimize
120x1 + 160x2
Subject to:
3x1 + 4x2 ≥ 2400
2x1 + x2 ≥ 1000
5x1 + 3x2 ≥ 2900

x1 ≥ 0; x2 ≥ 0

27
 MBA-H2040 Quantitative Techniques for Managers
Let us introduce parameter M in the objective function i.e. 120x1 + 160x2 = M. Then we have to

determine the different values for M, which is shown in the following Table 3.

Extreme Point Coordinates Objective Function

X1 X2 120x1 + 160x2
A X1 = 0 X2 = 1000 160000
B X1 = 150 X2 = 740 136400
C X1 = 400 X2 = 300 96000
D X1=800 X2=0 96000

Table 3: Shows the calculation of Minimum objective function value

Note that there are two minimum value for the objective function (M=96000). The feasible
region and the multiple solutions are indicated in the following Graph 5.

1100

A
1000

900

800

700

5x1 + 3x2 ≥ 2900

600

X2
500

400 2x1 + x2 ≥ 1000

300 C

200

3x1 + 4x2 ≥ 2400

100
28
0 D