Graphical

Method of Linear
Programming
ESSENTIALS OF LINEAR PROGRAMMING MODEL

For a given problem situation, there are certain essential

conditions that need to be solved by using linear programming.
1. Limited resources : limited number of labour, material equipment and
finance

2. Objective : refers to the aim to optimize (maximize the profits

or minimize the costs).

3. Linearity : increase in labour input will have a proportionate

increase in output.
PROPERTIES OF LINEAR
PROGRAMMING MODEL
The following properties form the linear programming
model:
1. Relationship among decision variables must be
linear in nature.
2. A model must have an objective function.
3. Resource constraints are essential.
4. A model must have a non-negativity constraint.
 FORMULATION OF LINEAR PROGRAMMING

Formulation of linear programming is the representation of problem

situation in a mathematical form. It involves well defined decision
variables, with an objective function and set of constraints.
Objective function:

The objective of the problem is identified and converted into a suitable objective
function. The objective function represents the aim or goal of the system (i.e.,
decision variables) which has to be determined from the problem. Generally, the
objective in most cases will be either to maximize resources or profits or, to
minimize the cost or time.
Constraints:
When the availability of resources are in surplus, there will be no problem in making
decisions. But in real life, organizations normally have scarce resources within which
the job has to be performed in the most effective way. Therefore, problem situations are
within confined limits in which the optimal solution to the problem must be found.
Non-negativity constraint

Negative values of physical quantities are impossible, like producing negative number of
chairs, tables, etc., so it is necessary to include the element of non-negativity as a
constraint
GENERAL LINEAR PROGRAMMING MODEL

A general representation of LP model is given as follows:

Maximize or Minimize, Z = p1 x1 + p2 x2 ………………pnxn
Subject to constraints,
w11 x1 + w12 x2 + ………………w1n xn ≤ or = or ≥ w1 ……………(i)
w21 x1 + w22 x2 ………………w2nxn ≤ or = or ≥ w2 ……………(ii)
....
....
....
wm1 x1 + wm2 x2 +………………wmn xn ≤ or = ≥ wm …………(iii)
Non-negativity constraint,
xi ≥ o (where i = 1,2,3…..n)
 Example
A company manufactures two types of boxes, corrugated and ordinary
cartons.

The boxes undergo two major processes: cutting and pinning operations.

The profits per unit are Rs. 6 and Rs. 4 respectively.

Each corrugated box requires 2 minutes for cutting and 3 minutes for pinning
operation, whereas each ordinary box requires 2 minutes for cutting and 1
minute for pinning.

The available operating time is 120 minutes and 60 minutes for cutting and
pinning machines.

The manager has to determine the optimum quantities to be

manufacture the two boxes to maximize the profits.
 Solution
Decision variables completely describe the decisions to be made (in this case, by
Manager). Manager must decide how many corrugated and ordinary cartons should be
manufactured each week. With this in mind, he has to define:

xl be the number of corrugated boxes to be manufactured.

x2 be the number of Ordinary boxes to be manufactured

Objective function is the function of the decision variables that the decision maker
wants to maximize (revenue or profit) or minimize (costs). Manager can concentrate on
maximizing the total weekly profit (z).
Here profit equals to (weekly revenues) – (raw material purchase cost) – (other variable costs) .
Hence Manager’s objective function is:
Maximize z = 6X1 +4x2
Constraints show the restrictions on the values of the decision variables. Without
constraints manager could make a large profit by choosing decision variables to be very
large. Here there are three constraints:
Available machine-hours for each machine
Time consumed by each product

Sign restrictions are added if the decision variables can only assume nonnegative values
(Manager can not use negative negative number machine and time never negative number )
 Cutting Pinning
Corrugated Box 2 3
Ordinary Box 2 1
 All these characteristics explored above give the following
Linear
Programming (LP) problem
max z = 6x1+ 4x2 (The Objective function)
s.t. 2x1 + 3x2 ≤ 120 (cutting timeconstraint)
2x1 + x2 ≤ 60 (pinning constraint)
x1, x2 ≥ 0 (Sign restrictions)

This type of linear programming can be solve by two methods

1) Graphical method
2) Simplex algorithm method
 Graphical Method

Step 1:Convert the inequality constraint as equations and find co-ordinates of the line.

Step 2: Plot the lines on the graph.

(Note: If the constraint is ≥ type, then the solution zone lies away from the centre.
If the constraint is ≤ type, then solution zone is towards the centre.)

Step 3: Obtain the feasible zone.

Step 4: Find the co-ordinates of the objectives function (profit line) and plot it on the graph representing it
with a dotted line.
Step 5: Locate the solution point.
(Note: If the given problem is maximization, zmax then locate the solution point at the far
most point of the feasible zone from the origin and if minimization, Zmin then locate the solution at
the shortest point of the solution zone from the origin).

Step 6: Solution type

i. If the solution point is a single point on the line, take the corresponding values of x1 and x2.
ii. If the solution point lies at the intersection of two equations, then solve for x1 and x2 using the
two equations.
iii. If the solution appears as a small line, then a multiple solution exists.
iv. If the solution has no confined boundary, the solution is said to be an unbound solution.
 1) Remove Inequalities and find Co- ordinate

Constraint Equation Co -Ordinates

2x1+3x2= 120 (0, 40) (60,0)

2x1+x2= 60 (0, 60) (30,0)

 CONT…

The inequality constraint of the first line is

When the second constraint is drawn, you may notice that a portion of
(less than or equal to) ≤ type which means the feasible area is cut. This indicates that while considering both the
feasible solution zone lies towards the origin. constraints, the feasible region gets reduced further. Now any point in
the shaded portion will satisfy the constraint equations.
(Note: If the constraint type is ≥ then the
the objective is to maximize the profit. The point that lies at the
solution zone area lies away from the origin in
furthermost point of the feasible area will give the maximum
the opposite direction). Now the second profit. To locate the point, we need to plot the objective function
constraints line is drawn. (profit) line.
Points Co -Ordinates Optimum
Z = 6x1 + 4x2

A (0,0) 0

B (0, 40) 160

P (15, 30) 210

2x1+3x2= 120
2x1+x2= 60 X1 = 15 and X2 = 30
C (30, 0) 180

Z max = 210 at Point Pi.e. at 15,30

A furniture factory produces tables and chairs. Production
process on both are same as both require carpentry work and
painting work. Each table takes 4 hrs. in carpentry and 2 hrs. in
painting department. Each chair needs 3 hrs. in carpentry and 1
hr. in painting department . During the current production period
, only 300 hrs. of carpentry time and 120 hrs. of painting time
are available. Each table yields a profit of Rs. 70 and each chair
produced may be sold for of Rs. 50.
The furniture factory owners wants to determine the best possible
combination of tables and chairs to manufacture, in order to get
maximum profit. Assuming that any mix of tables and chairs can
be sold , the manufacturer would like this production mix
situation to be formulated as LPP.
 Table (Hrs) Chairs (Hrs) Availability

Carpentry 4 3 300

Painting 2 1 120

Profit 70 50
Formulation of the Problem
Let x1 be no. of tables to be produced.
Decision Variables
i.e. unknowns
Let x2 be no. of chairs to be produced.

Profit made by each Table = Rs. 70

Profit made by each Chair = Rs. 50

.: Total Profit = by selling Table and Chairs

.: Total Profit = 70 x1 + 50 x2
Maximize or Minimize ????
Formulation of the Problem

Constraints: Carpentry Time and Painting Time

1) Total Available Time for Carpentry = 300 hrs.

For making 1 Table (x1) , Carpentry Time = 4 hrs.
For making 1 Chair (x2) , Carpentry Time = 3 hrs.

.: Carpentry Constraint = 4 x1 + 3 x2 ≤ 300

2) Total Available Time for Painting = 120 hrs.

For making 1 Table (x1) , Painting Time = 2 hrs.
For making 1 Chair (x2) , Painting Time = 1 hr.

.: Painting Constraint = 2 x1 + 1 x2 ≤ 120

Formulation of the Problem

Maximize Z = = 70 x1 + 50 x2

subject to

4 x1 + 3 x2 ≤ 300

2 x1 + 1 x2 ≤ 120

x1 , x2 ≥ 0
 1) To remove Inequalities

4 x1 + 3 x2 = 300 ( 0,100) (75,0)

2 x1 + 1 x2 = 120 ( 0,120) (60,0)
Poin Co - Optimum
130
ts Ordinates Z = 70x1 + 50x2
120
A (0,0) 0
110

B
100
B (0, 100) 5000
90
X2 80 C (30, 60) 5100
70
4x1+3x2= 300
60
2x1+x2= 120
C X1 = 30 and X2 = 60
50

40 D (60, 0) 4200
30

20

10

D Zmax = 5100 at
A 10 20 30 40 50 60 70 80 90 100 110 120
Point C (30,60)
X1
Upon completing the construction of his house , Mr.
Sharma finds that 100 Sq.Ft of plywood scrap and 80 Sq.Ft
of White Pine scrap are in usable form for construction of
Tables and Book cases. It takes 16 Sq. Ft of Plywood and 8
Sq. Ft of white pine to make a table and 12 Sq. Feet of
plywood and 16 Sq. Feet of white pine are required to make
a book case. By selling the finished products to a local
furniture store , Mr. Sharma can make a profit of Rs. 125 on
each table and Rs. 100 on each book case. How can he
make the use of the left over scrap most profitably.
Formulate the LPP and solve using Graphical method.
 Table (Sq.Ft) Book Case (Sq.Ft) Availability

Plywood 16 12 100

White pine 8 16 80

Profit 125 100

Maximize Z = 125 x1 + 100 x2

Subject to

16 x1 + 12 x2 ≤ 100

8 x1 + 16 x2 ≤ 80

x1 , x2 ≥ 0
 1) To remove Inequalities

16 x1 + 12 x2 = 100 ( 0,8.33) (6.25,0)

8 x1 + 16 x2 = 80 ( 0,5) (10,0)
Poin Co - Optimum
ts Ordinates Z = 125x1 + 100x2
12
A (0,0) 0
11

B
10
(0, 5) 500
9
X2 8 C (4, 3) 800
7
16x1+12x2= 100
6
8x1+162= 80
B X1 = 4 and X2 = 3
5

4 D (6.25, 0) 781.25
3 C
2

1
D Zmax = 800 at
A 1 2 3 4 5 6 7 8 9 10 11 12
Point C (4,3)
X1
A firm manufactures and sells two products Alpha and Beta.
Each unit of Alpha requires 1 hour of machining and 2 hrs
of skilled labour, whereas each unit of Beta uses 2hrs of
machining and I hour of skilled labour. For the coming
month , the machine capacity is limited to 720 machine hrs.
and the skilled labour is limited to 780 hrs. Not more than
320 units of Alpha can be sold in the market during a
month. Develop a suitable model that will enable
determination of the optimal product mix. Determine
optimal product mix and maximum contribution. Unit
contribution from Alpha is Rs. 6 and Beta is Rs. 4
 Alpha Beta Availability

Machining 1 2 720

Skilled labours 2 1 780

Market 320

Profit 6 4
Maximize Z = 6 x1 + 4 x2

Subject to

x1 + 2 x2 ≤ 720

2x1 + x2 ≤ 780

x1 ≤ 320

x1 , x2 ≥ 0
Minimize Z = 80x1 + 120 x2

Subject to

x1 + x2 ≤ 9
x1 ≥ 2
x2 ≥ 3
20x1 + 50x2 ≤ 300
x1 , x2 ≥ 0
1) To remove Inequalities
x1 + x2 = 9 ( 0,9) (9,0) x2 = 3 ( 0,3) (0,0)
x1 = 2 ( 0,0) (0,2) 20x1 + 50x2 = 300 ( 0,6) (15,0)

2
Poin Co - Optimum
ts Ordinates Z = 80x1 + 120x2
12
A (2,3) 520
11
1
B
10
(2, 5.2) 784
9
X2 8 C (5, 4) 880
7

6 B
A
B D (6, 3) 840
5

4 C
3 C
2 A D
1
D 4 Zmax = 520 at
1 2 3 4 5 6 7 8 9 10 11 12 15
Point A (2,3)
X1
1) To remove Inequalities
1) x1 + x2 = 9 ( 0,9) (9,0) 3) x2 = 3 ( 0,3) (0,0)
2) x1 = 2 ( 0,0) (0,2) 4) 20x1 + 50x2 = 300 ( 0,6) (15,0)

12 Feasible Constraint Constraint Equations Coordinates

Area Lines
11 Point Intersecting

10

A 2,3 x1 = 2 2,3
9
x2 = 3
X2 8
B 2,4 x2 = 3 2, 5.2
7 20x1 + 50x2 = 300
6
B B
A 1 C 1,4 x1 + x2 = 920 5,4
x1 + 50x2 = 300
5
4 C
4 1,3 x1 + x2 = 920 6,3
D
3 3 C 3 x2 = 3
A
2
2 D 1
1
D
1 2 6 8 11 13 14 15 16
3 4 5 7 9 10 12

X1
Maximize Z = 5x1 + 4 x2

Subject to

6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
x2 ≤ 2
x2 - x1 ≤ 1
x1 , x2 ≥ 0
1) To remove Inequalities
6x1 + 4x2 = 24 (0,6) (4,0) x2 = 2 ( 0,2) (0,0)
x1 + 2x2 = 6 (0,3) (6,0) x2 - x1 = 1 ( 0,1) (-1,0)
1) To remove Inequalities
1) 16x1 + 4x2 = 24 (0,6) (4,0) 3) x 2 = 2 ( 0,2) (0,0)
2) x1 + 2x2 = 6 (0,3) (6,0)
4) x2 - x1 = 1 ( 0,1) (-1,0)
Feasible Constraint Constraint Equations Coordinates
X2 Area Lines
Point Intersecting
7

A 0,0 x1 = 0 x2 = 0 0,0

6 0,4 x2 = 1 0, 1
B
C 3,4 x2 = 2 1,2
5 1 X2 -x1 = 1
2,3 x1 + 2x2 = 6 2,2
4 D x2 = 3
4

E 1,2 16x1 + 4x2 = 24 3 , 1.5

x1 + 2x2 = 6
3
2 F 1 16x1 + 4x2 = 24 4,0

2
C D 3
B E
1 2
4
F
-1
A 1 2 3 4 5 6 7 8

X1
Maximize Z = x1 + x2

Subject to

2x1 + x2 ≤ 2
3x1 + 4x2 ≥ 12

x1 , x2 ≥ 0
1) To remove Inequalities
1) 2x1 + x2 = 2 (0,2) (1,0)
2) 3x1 + 4x2 = 12 (0,3) (4,0)
X2
7

-1 1 3 4 5 7 8
2 6

X1
Maximize Z = x1 + x2

Subject to

3x1 + x2 ≥ 6
x1 + 3x2 ≥ 6

x1 , x2 ≥ 0
Maximize Z = 3x1 + 5x2

Subject to

12x1 + 20x2 ≤ 40
x1 - 4x2 ≤ 4

x1 , x2 ≥ 0