Graphical Method

1. A company manufactures two types of boxes, special and ordinary [Link] boxes undergo
two major processes: cutting and pinning operations. The profits per unit are Rs. 6 and Rs. 4
respectively. Each special 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
Let X1 = Number of units produced special boxes
Let X2 = Number of units produced ordinary boxes
Objective (Maximize the Profits)
Maximize Z = 6x1 + 4x2
Profit of special box (x1) is Rs. 6
Profit of ordinary box (x2) is Rs. 4
Constraints (Cutting and Pinning process)
Cutting operation Pinning operation
Special Box (X1) 2 3
Ordinary Box (X2) 2 1
120 mts 60 mts

Cutting operation constraint: 2x1 + 2x2 ≤ 120

Pinning operation constraint: 3x1 + x2 ≤ 60

LPP Formulation
Maximize Z = 6x1 + 4x2
Subject to the constraints
2x1 + 2x2 ≤ 120
3x1 + x2 ≤ 60
X1 , X2 ≥ 0

Graphical Method
Convert the inequality constraint as equations and find co-ordinates of each equation

Constraint 1
2x1 + 2x2 ≤ 120
Equation: 2x1 + 2x2 = 120
Let x1 = 0
2 (0) + 2x2 = 120
2x2 = 120
X2 = 120/2 = 60
(x1 , x2) = (0, 60)

Let x2 = 0
2x1 + 2(0) = 120
2x1 = 120
X1 = 120/2 = 60
(x1, x2) = (60, 0)

Constraint 2
3x1 + x2 ≤ 60

Equation: 3x1 + x2 = 60

Let x1 = 0
3(0) + x2 = 60
X2 = 60
(x1, x2) = (0, 60)

Let x2 = 0
3x1 + 0 = 60
X1 = 60/3 = 20
(x1, x2) = (20, 0)
 Feasible
Zone

Extreme Points
0 (0,0)
A (20, 0)
B (0, 60)

Points Maximize Z = 6X1 + 4X2 Value

0 (0,0) Max Z = 6*0 + 4 *0 0
A (20, 0) Max Z = 6*20 + 4*0 120
B (0, 60) Max Z = 6*0 + 4*60 240

Conclusion
The company should manufacture zero quantity of special boxes and 60 quantity of ordinary
boxes to maximize the profit at Rs. 240.
Or
At X1 = 0, X2 = 60 units the company profit would maximize with Rs. 240
2. Suppose an industry is manufacturing two 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 machine to produce one Kg of P1 and P2. Formulate the problem in the
form of linear programming model and apply graphical method.

Solution
Decision Variables
Let X1 = No. of Units to be manufacture of product P1
Let X2 = No. of units to be manufacture of product P2
Objective function (Profit)
Maximize Z = 30x1 + 40x2
Product P1 (x1) profit is Rs. 30
Product P2 (x2) profit is Rs. 40
Constraints
3x1+2x2 ≤600 (machine 1)
3x1+5x2≤800 (machine 2)
5x1+6x2≤1100 (machine 3)
LPP Formulation
Maximize Z = 30x1 + 40x2
Subject to the constraints
3x1+2x2 ≤600 (machine 1)
3x1+5x2≤800 (machine 2)
5x1+6x2≤1100 (machine 3)
X1, x2≥0
Graphical method
Constraint 1: 3x1+2x2≤600
Equation1: 3x1+2x2=600
Let x1=0
3(0)+2x2=600
2x2=600
X2=600/2
X2=300
(x1,x2)=(0,300)
Let x2=0
3x1+2(0)=600
3x1=600
X1=600/3
X1=200
(x1,x2) = (200,0)
Constraint2: 3x1+5x2≤800
Equation2: 3x1+5x2=800
Let x1=0
3(0)+5x2=800
5x2=800
X2= 800/5
X2= 160
(x1,x2)=(0,160)
Let x2=0
3x1+5(0)=800
3x1=800
X1=800/3
X1=267
(x1,x2)=(267,0)
Constraint 3: 5x1+6x2≤1100
Equation3: 5x1+6x2=1100
Let x1=0
5(0)+6x2=1100
6x2=1100
X2=1100/6
X2=183
(x1,x2)= (0,183)
Let x2=0
5x1+6(0)=1100
5x1=1100
X1=1100/5
X1=220
(x1,x2)= (220,0)
Equation 1 coordinates: (x1,x2)=(0,300) &(200,0)
Equation 2 coordinates: (x1,x2)= (0,160) & (267,0)
Equation 3 coordinates: (x1,x2)=(0,183) & (220,0)
POINT B
Point B is the intersection of 1 & 3 equations
Solve 1& 3 equations
3x1+2x2=600 x3
5x1+6x2=1100 x1
9x1+6x2=1800(-)
5x1+6x2=1100
4x1=700
X1=700/4
X1=175
Substitute x1=175 in equation 1
3x1+2x2=600
3(175)+2x2=600
2x2=600-525
2x2=75
X2=75/2
X2=37.5
Point B=(175,37.5)
POINT C
Point C is the intersection of 2&3 equations
3x1+5x2=800 *5
5x1+6x2=1100 *3
15x1+25x2=4000 (-)
15x1+18x2=3300

7x2=700
X2=700/7
X2=100
Substitute x2=100 in equation 2
3x1+5x2=800
3x1+5(100)=800
3x1=800-500
X1=300/3
X1=100
Point C = (100,100)
Points Maximize Z = 30x1 + 40x2 Value
O(0,0) Max Z = 30(0)+40(0) 0
A(200,0) Max Z = 30(200)+40(0) 6000
B(175,37.5)* Max Z = 30(175)+40(37.5) 7250*
C(100,100) Max Z=30(100)+40(100) 7000
D(0,160) Max Z= 30(0)+40(160) 6400
Conclusion
The company need to manufacture 175 units of P1 and 37.5 units of P2 products, which
maximize profit Rs. 7250.

Simplex Method

Solve the L.P.P. by Simplex method:

Subject to , , ,
Solution
Standard form of LPP

+0S1+0S2+0S3
Subject to the constraints
X1+X2 +S1 = 2
5X1+2X2+S2 = 10
3X1+8X2+S3 = 12
X1,X2,S1,S2,S3≥0
Initial simplex table
Where CB= coefficients of basic variables in the objective function
XB= RHS values of the constraints
Cj=Coefficients of decision and slack variables in the objective function
Cj 5 3 0 0 0
Basic variables CB XB X1 X2 S1 S2 S3 Min Ratio =XB/XK
S1 0 2 1 1 1 0 0 2/1=2

S2 0 10 5 2 0 1 0 10/5=2

S3 0 12 3 8 0 0 1 12/3=4
Zj= ∑CBj*XBj (0) 0 0 0 0 0
Cj-Zj 5 3 0 0 0
All Cj-Zj values are not less than or equal to zero(≤ 0). Hence, optimality is not reached
and go to next step
Select Entry variable: most postive value (5) of Cj-Zjwould be as entry variable(X1)
X1or XK: 1 5 3 are key column elements
Select Leaving variable: Calculate Minimum Ratio
Note: Don’t consider negative or zero minimum ratio values for further process (ignore it)
Minimum ration is tie at I & II rows. So, select randomly anyone (S1) and respective elements
will be called as key row elements
Key row elements: 2 1 1 1 0 0
Leaving variable is S1
Key element (1): the intersection of key column and key row element.
New simplex table
For Key row (S1)
New value= old value
Key element
Old value Key element New value
2 1 2/1=2
1 1 1/1=1
1 1 1/1=1
1 1 1/1=1
0 1 0/1=0
0 1 0/1=0

Other than key rows (S2 & S3)

New value= old value-[Corresponding Key row element *key column element]
Key element
Row Old value Key row Key column Key element New value
element element (same)
10 2 5 1 10-[2*5]/1=10-10=0
5 1 5 1 5-[1*5]/1=5-5=0
S2 2 1 5 1 2-[1*5]/1=2-5= -3
0 1 5 1 0-[1*5]/1=0-5 = -5
1 0 5 1 1-[0*5]/1=1-0 = 1
 0 0 5 1 0-[0*5]/1=0-0 = 0
12 2 3 1 12-[2*3]/1=12-6 = 6
3 1 3 1 3-[1*3]/1=3-3 = 0
8 1 3 1 8-[1*3]/1=8-3 = 5
S3 0 1 3 1 0-[1*3]/1= 0-3= -3
0 0 3 1 0-[0*3]/1= 0-0=0
1 0 3 1 1-[0*3]/1=1-0 = 1

New simplex table

Cj 5 3 0 0 0
Basic variables CB XB X1 X2 S1 S2 S3
X1 5 2 1 1 1 0 0

S2 0 0 0 -3 -5 1 0

S3 0 6 0 5 -3 0 1
Zj= ∑CBj*XBj(10) 5 5 5 0 0
Cj-Zj 0 -2 -5 0 0

All Cj-Zj values are ≤0. Hence, optimal solution is reached.

Conclusion
X1 = 2 & X2 = 0 and Maximize Z = 10
S2 =0 & S3 =6
2. Solve the following LPP by simplex method
Maximize Z = 3X1+5X2+4X3
Subject to the constraints
2x1+3x2≤8
2x2+5x3≤10
3x1+2x2+4x3≤15
And x1,x2,x3≥0
Solution
Standard form of LPP
Maximize Z= 3X1+5X2+4X3 +0S1+0S2+0S3
Subject to
2x1+3x2+S1=8
2x2+5x3+S2=10
3x1+2x2+4x3+S3=15
X1,X2,X3,S1,S2,S3≥0
Initial Simplex table
Cj 3 5 4 0 0 0
Basic variables CB XB X1 X2 X3 S1 S2 S3 Min Ratio =XB/XK
S1 0 8 2 3 0 1 0 0 8/3 = 2.67

S2 0 10 0 2 5 0 1 0 10/2 = 5

S3 0 15 3 2 4 0 0 1 15/2 = 7.5
Zj= ∑CBj*XBj (0) 0 0 0 0 0 0
Cj-Zj 3 5 4 0 0 0
All Cj-Zj values are not ≤ 0. Hence, optimal solution is not reached and go to next step.
Select Entry variable: most negative value (5) of Cj-Zj would be as entry variable(X2)
X2or XK: 3 2 2 are the key column elements
Select Leaving variable: Calculate Minimum Ratio
Note: Don’t consider negative or zero minimum ratio values for further process (ignore it)
Minimum ration is 2.67 which is occurred in I row and S1 is the leaving variable.
Respective elements will be called as key row elements
Key row elements: 8 2 3 0 1 0 0
Leaving variable is S1
Key element (3): the intersection of key column and key row element is called key element.
New simplex table
For Key row (S1)
New value = old value
Key element
Old value Key element New value
8 3 8/3 = 2.67
2 3 2/3 = 0.67
3 3 3/3=1
0 3 0/3=0
 1 3 1/3 = 0.33
0 3 0/3=0
0 3 0/3=0

Other than key rows (S2 & S3)

New value= old value - [Key row element *key column element]
Key element
Row Old value Key row Key column Key element New value
element element (same)
10 8 2 3 10-[8*2]/3=10-5.33=4.67
0 2 2 3 0-[2*2]/3=0-4/3 = -1.33
S2 2 3 2 3 2-[3*2]/3=2-2 = 0
5 0 2 3 5-[0*2]/3=5-0 = 0
0 1 2 3 0-[1*2]/3 = -0.67
1 0 2 3 1-[0*2]/3 = 1-0 = 1
0 0 2 3 0-[0*2]/3 = 0-0 = 0
15 8 2 3 15-[8*2]/3=15-5.33 = 9.67
3 2 2 3 3-[2*2]/3=3-1.33 = 1.67
2 3 2 3 2-[3*2]/3=2-2 = 0
S3 4 0 2 3 4-[0*2]/3= 4-0 = 4
0 1 2 3 0-[1*2]/3=0-0.67 = -0.67
0 0 2 3 0-[0*2]/3=0-0 = 0
1 0 2 3 1-[0*2]/3=1-0 = 1

New simplex table

Cj 3 5 4 0 0
Basic variables CB XB X1 X2 X3 S2 S3 Min Ratio =XB/XK
X2 5 2.67 0.67 1 0 0 0

S2 0 4.67 -1.33 0 5 1 0 4.67/5=0.934

S3 0 9.67 1.67 0 4 0 1 9.67/4 = 2.417

Zj=∑CBj*XBj (13.35) 3.35 5 0 0 0
Cj-Zj -0.35 0 4 0 0

All Cj-Zj values are not ≤0. Hence, optimality is not reached and go to next step
Entry variable is X3 and respective elements are called key column elements (0 5 4)
 Leaving variable is S2 because it is shows minimum ratio.
Key row elements (4.67 -1.33 0 5 1 0)
Key element (5): the intersection of key column and key row element is called key element.
New simplex table
For Key row (S2)
New value = old value
Key element
Old value Key element New value
4.67 5 4.67/5 = 0.93
-1.33 5 -1.33/5 = 0.27
0 5 0/5=0
5 5 5/5=1
1 5 1/5=0.2
0 5 0/5=0

Other than key rows (X2 & S3)

New value= old value - [Key row element *key column element]
Key element
Row Old value Key row Key column Key element New value
element element (same)
2.67 4.67 0 5 2.67-[4.67*0]/5=2.67
0.67 -1.33 0 5 0.67-[-1.33*0]/5=0.67
X2 1 0 0 5 1-[0*0]/5= 1
0 5 0 5 0-[5*0]/5=0
0 1 0 5 0-[1*0]/5 = 0
0 0 0 5 0-[0*0]/5 = 0
9.67 4.67 4 5 9.67-[4.67*4]/5=9.67-3.74 = 5.93
1.67 -1.33 4 5 1.67-[-1.33*4]/5=1.67+1.064= 2.73
0 0 4 5 0-[0*4]/5= 0
S3 4 5 4 5 4-[5*4]/5= 4-4 = 0
0 1 4 5 0-[1*4]/5=0-0.8= -0.8
1 0 4 5 1-[0*4]/5=1-0 = 1
New simplex table
Cj 3 5 4 0
Basic variables CB XB X1 X2 X3 S3
X2 5 2.67 0.67 1 0 0

X3 4 0.93 0.27 0 1 0

S3 0 5.93 2.73 0 0 1
Zj=∑CBj*XBj (17.07) 4.43 5 4 0
Cj-Zj -1.43 0 0 0

All Cj-Zj values are ≤0. Hence, optimal solution is reached.

Conclusion
X1 = 0, X2 = 2.67 & X3 = 0.93 and Maximize Z = 17.07
S1, S2 =0 & S3 =5.93