SVKM’s NIMIS University

Linear Programming – Graphical Solution

A graphical solution procedure is one method of solving two-variable LPP (Linear Programming
Problem). The primary purpose of this method is in helping to provide an understanding of
1. What is involved in solving an LPP?
2. What information is available in the solution?
The step-by-step procedure is explained with the help of following example:
Ex: Two types of Television sets are produced with a profit of 6 units from each
television of Type I and 4 units from each television of Type II. In addition, 2 and 3
units of raw materials are needed to produce one television of Type I and Type II,
respectively & 4 and 2 units of time are required to produce one television of Type I
and Type II, respectively. If 100 units of raw materials and 120 units of time are
available, how many units of each type of television should be produced to maximize
profit and still meet all constraints of the problem?
Step I: Write down the given information in a table format.
Given:
Type I Type II Available
Raw Material 2 3 100
Time 4 2 120
Profit/Unit 6 4
Here, the profit is to be maximized within the limited resources. This is the
maximization problem.
Step II: Initially the problem should be formulized i.e. objective function & constraints
should be written.
In this example, the main objective is to produce more number of units of
Type I & II within limited resources.
Let X1, X2 be the number of units of Type I and Type II respectively.
The objective function (the function to be optimized/maximized) is
Z = 6X1 + 4X2
Since each unit of Type I and Type II yields a profit of 6 and 4 units, this implies
that
Max Z = 6X1 + 4X2
Subject to constraints
2X1 + 3X2 ≤ 100 ………… Raw material
4X1+ 2X2 ≤ 120 …………. Time
X1, X2 ≥ 0 ...………. Non-negativity
Since only two variables are involved in this example, the problem can be solved
graphically.
Step III: To solve it graphically i.e. to draw a graph, for all constraints draw the straight
line for where the constraints are satisfied exactly. Graph the constraints as if it
were equality.
Therefore, the 1st constraint i.e. 2X1 + 3X2 ≤ 100 becomes
2X1 + 3X2 = 100
To graph the 1st constraint, determine the set of points that satisfy this constraint.
 Check whether the origin (0,0) satisfies the constraint.
In this case, 2*0 + 3*0 = 0 ≤ 100
This implies that all points below the line 2X1 + 3X2 = 100 satisfy this
constraint.
Now, to determine (X1, X2) co-ordinates, set X1=0 and find out X2 and vice-
versa.
Therefore, putting X1 = 0 in 2 X1 + 3X2= 100
We get, 3X2 = 100
X2 = 33.33
And putting X2 = 0 in 2X1 + 3X2 = 100
We get, 2X1 = 100
X1 = 50
Therefore, set of points is (50, 33.33).
Draw a line with (X1, X2) co-ordinates as (50, 33.33).
Step IV: Now in the similar way determine the set of points by substituting X1 = 0 and
X2 = 0 simultaneously in the second constraint.
The 2nd constraint is 4X1 + 2X2 = 120
Putting X1 =0 in this constraint, we get
2X2 =120
X2=60
Putting X2 = 0, we get
4X1 = 120
X1 = 30
Therefore, set of points is (30, 60).
Draw a straight line with (X1, X2) co-ordinates as (30, 60).
Step V: Determine the region where X1≥0 & X2≥0.
X2

(0,60)
4X1 + 2X2=120

D (0,33,33) Region of “Feasible Solutions”

C (20,20)

2X1 + 3X2= 100

B (30,0) (30,0)
 A (0,0) X1

Step VI: Take the region which is common to all the lines i.e. 2X1 + 3X2 ≤ 100;
4X1 + 2X2 ≤ 120 and X1, X2 ≥ 0. That region is called as “Feasible Region”.
Feasible region is a set of points that make all linear inequalities in the system true
simultaneously. That is, each point in this region satisfies all of the constraints and is a
candidate for providing the maximum profit. But the region contains infinity of feasible
solutions. Therefore, there is a need to find out the optimal solution. Find out the
intersection points.

Step VII: Therefore, to find out the optimal solution, substitute the set of points of
intersection in the objective function i.e. Z = 6X1 + 4X2
The points of intersection are:
A (0, 0)
B (30, 0)
C (20, 20)
D (0, 33.33)
Substitute these values in Z = 6X1 + 4X2
A (0, 0) Z = 6*0 + 4*0 = 0
Z=0
B (30, 0) Z = 6*30 + 4*0 = 180
Z = 180
C (20, 20) Z = 6* 20 + 4*20 = 200
Z = 200
D (0, 33.33) Z = 6*0 + 4*33.33 = 133.32
Z = 133.32
Z = 200 is the maximum value & is the optimal solution.
Therefore, 20 units of Type I and 20 units of Type II should be
produced to yield a maximum profit of 200 units.

Minimization case
Illustration:
Minimize Z= 10X1+4.5X2
Subject to constraints
2X1+3X2≥3500
6X1+2X2≥7000
X1≥0 X2≥0
We first find the points to determine the line For constraint 1 2X1+3X2≥3500
When X1=0, X2=3500/3. The coordinates of the point are (0,3500/3)
When X2=0, X1=1750. The coordinates of the point are (1750,0)
We plot these points on the graph paper to show this constraint. Similarly for the second
constraint
When X1=0, X2=7000/2. The coordinates of the point are (0,3500)
When X2=0, X1=7000/6. The coordinates of the point are (7000/6,0)
We plot these points on the graph paper lines to show this constraint.

3500 A

3000

2500
6X1+2X2≥7000

2000

2X1+3X2≥3500
1500 feasible region

1000

500 B

500 1000 1500 2000

The shaded region is the feasible region. Infinitely many points satisfy the constraints. The
objective is to minimize the value of the objective function. The feasible region is bounded
below. The points A, B and C are the points where the minimum value of the objective function
may lie.
The feasible points are
 Point Coordinates
A (0,3500)
B (1000,500)
C (0,3500/3)
The value of the objective function at these points is
Point Coordinates Value of Z
A (0,3500) 15750
B (1000,500) 12250* Minimum
C (1750,0) 17500
The solution lies at point B. X1=1000 and X2=500 value of Z=12250