Linear Programming

Simplex Method
1

PREPARED BY:
HANSIKA KHURANA
DEPARTMENT OF COMMERCE

FOR B.COM(H)
SEMESTER IV, SECTIONS A & B

Department of Commerce, Gargi College 23/03/20

 Introduction to Simplex Method
2

— In Graphical method, we used only two variables, x &

y to plot on the graph
— Beyond 2 variables, graphical method becomes
difficult to solve
— In reality, Linear Programming Problems do not
have only 2 variables with pure inequalities; there
could be multiple variables with mixed constraints
— Simplex method allows mathematical solutions to
linear programming problems

Department of Commerce, Gargi College 23/03/20

 Terms you should know
3

1. Slack Variable
— To convert an inequality to an equality, we add a
variable to the left side of a less than or equal to
constraint
— It makes up for the slack/deficiency on the left side
— For Instance, X + 3Y <=20
To convert this inequality into an equality, we add a
slack variable, “s” on the L.H.S.

The equation now becomes X + 3Y + s = 20

Department of Commerce, Gargi College 23/03/20

 4

2. Surplus Variable
— Similar to slack variable, to convert an inequality to
equality, we subtract a variable from the left side of a
greater than or equal to constraint
— This is done to reduce/remove the excess on the left side
— For instance, X + 3Y >= 20
To convert this inequality into an equality, we subtract a
surplus variable “s” from the L.H.S.

The equation now becomes X + 3Y – s = 20

Department of Commerce, Gargi College 23/03/20

 How to Solve an LPP using Simplex
5

MAXIMIZATION CASE

— Refer to Scanned notes uploaded online

— Refer to videos sent for detailed explanation

— Refer to next slide for Example 3, Page 4.8

Department of Commerce, Gargi College 23/03/20

 Step 1 – Problem Formulation
6

Let the number of chairs produced be x

Let the number of tables produced be y

Profit is Rs.20/chair and Rs.30/table

Based on the information and constraints given, the LPP can be

formulated as follows:
Maximize Z = 20x + 30y
Subject to:
3x + 3y <=36
5x + 2y <=50
2x + 6y <=60
x, y >=0
Department of Commerce, Gargi College 23/03/20
 Step 2 - Introduction of Slack/Surplus Variables,
as per question
7

Maximize Z = 20x + 30y + 0s1 + 0s2 + 0s3

Subject to:
3x + 3y + s1 =36
5x + 2y + s2 =50
2x + 6y + s3 =60
x, y, s1, s2, s3 >=0

The Slack variables need to be introduced in the Objective function as

well, so
Maximize Z = 20x + 30y
becomes:
Maximize Z = 20x + 30y + 0s1 + 0s2 + 0s3

The Slack Variables have 0 values in the Objective Function

Department of Commerce, Gargi College 23/03/20
 Step 3 – Formulating a Basic Feasible Solution
8

— We have a basic feasible solution when we equate our variables to 0 i.e. x = 0 and y =
0

— Using Maximize Z = 20x + 30y + 0s1 + 0s2 + 0s3

Subject to:
3x + 3y + s1 =36
5x + 2y + s2 =50
2x + 6y + s3 =60
x, y, s1, s2, s3 >=0
And setting x = 0 and y = 0, we get the values of s1, s2 and s3

Maximize Z = 0
s1 = 36
s2 = 50
s3 = 60

— Now, we make the First Simplex Tableau

Department of Commerce, Gargi College 23/03/20

 Solutio 20 30 0 0 0
Basic
n/
Cj Varia Ratio
Quantit 9
bles
y x y s1 s2 s3

0 s1 36 3 3 1 0 0 36/3 = 12

0 s2 50 5 2 0 1 0 50/2 = 25

60/6 = 10
0 s3 60 2 6 0 0 1
ç

0*0 + 0*0 +
36*0 + 3*0 + 3*0 + 1*0 +
1*0 + 0*0 +
Zj 50*0 + 5*0 + 2*0 + 0*0+0*
0*0 = 0 1*0 = 0
60*0 = 0 2*0 = 0 6*0 = 0 0=0

20 – 0 30 – 0 0–0= 0–0= 0–0=

Cj - Zj
=20 =30 é 0 0 0
Department of Commerce, Gargi College 23/03/20
 Step 4 – Test for Optimality
10

— Solution is Optimal if all values in the Cj-Zj row are

either Negative or 0.
— If there is any positive value, then the solution can be
improved.
— The variable with the highest Cj-Zj value will enter
the table (the logic is that 30 > 20 i.e. it will bring in
more profit, therefore, that variable should be given
higher priority)

Department of Commerce, Gargi College 23/03/20

 Step 5 – Deriving Key Row and Key Column
11

— Refer video for explanation

— The arrow marked é indicates the entering variable

i.e. y because it has the highest Cj –Zj value. It is
called the Key Column
— The arrow marked ç indicates the exiting variable
i.e. s3 because it has the lowest ratio. It is called the
Key Row.
— The intersection of the Key Row and the Key Column
is called the Key Number i.e. 6
Department of Commerce, Gargi College 23/03/20
 12

— How to derive the “Ratio” Column

Each value in the “Solution/Quantity” column will be

divided by each positive entry in the Key Column

The variable with the minimum non-negative value

will depart/leave the table. This becomes the Key Row.

Department of Commerce, Gargi College 23/03/20

 Step 6 – Deriving table 2 and testing that for
optimality
13

— Since there is one variable that is departing, i.e. s3, and one variable entering, i.e. y,
the values in each row will now have to be changed, to reflect changes in variables

i. Transformation of Key Row

Divide each value of row s3 with the key number, i.e. 6.
Replace the old values with the resulting values. The values of row “y” (entering
variable) will be obtained.

ii. Transformation of Non-Key Rows

New Non-Key Row = Old Non Key Row – (Key Column Entry x New Key
Row Value)

Eg: For Row s1, we will calculate the new value under “Solution/Quantity” column as
follows:
36 – 3 x 10 = 6
36 – Old Value
3 – The old value in the same row (s1) under the key column (y)
10 – The new key row number which we obtained in step (i) above i.e. 60/6 = 10
Now make Table/Tableau 2 (refer next slide)
Department of Commerce, Gargi College 23/03/20
 Solutio 20 30 0 0 0
Basic
n/
Cj Varia Ratio
Quantit 14
bles
y x y s1 s2 s3

0 s1 6 2 0 1 0 -1/2 6/2 = 3 ç

30/(13/3)
0 s2 30 13/3 0 0 1 -1/3
= 90/13

10/(1/3) =
30 y 10 1/3 1 0 0 1/6
30

6*0 +
30*0 +
Zj 10 30 0 0 5
10*30 =
300

Cj - Zj 10 é 0 0 0 -5
Department of Commerce, Gargi College 23/03/20
 15

— Again, the solution is optimal when all values in the

Cj-Zj row are either negative or 0
— In Simplex Tableau 2, we have a positive value in the
“x” column, therefore, x becomes the entering
variable
— All other values are either 0 or negative
— The lowest positive ratio is for row s1, therefore, s1
becomes the departing variable
— Using this, and transforming the table using
formulae given in slide 13, we will derive simplex
tableau 3 and test that for optimality

Department of Commerce, Gargi College 23/03/20

 Solutio 20 30 0 0 0
Basic
n/
Cj Varia Ratio
Quantit 16
bles
y x y s1 s2 s3

20 x 3 1 0 1/2 0 -1/4

0 s2 17 0 0 -13/6 1 3/4

30 y 9 0 1 -1/6 0 1/4

3*20 +
17*0 +
Zj 20 30 5 0 5/2
9*30 =
330

Cj-Zj 0 0 -5 0 -5/2
Department of Commerce, Gargi College 23/03/20
Step 7 - Interpreting the Final Table and Deriving
Solution
17

— Since all values in the Cj-Zj row are either 0 or negative, we have found the optimum
solution
— The answer is:
Maximum Profit is 330
When we produce:
x = 3 i.e. 3 chairs &
y = 9 i.e. 9 tables
s1, s3 = 0, s2 = 17

— The Cj-Zj row in the final tables shows the shadow prices
i.e. for s1, it is 5, which means that if we increase the utilization of the
resource by one additional hour, we can increase the value of our objective
function (profit) by Rs.5
— The existence of a slack variable in the final table, i.e. s2 = 17, shows that our
resources have not been completely utilized. At the same time, the value in the Cj-Zj
row for column s2 = 0, which again indicates that even if we add an additional hour
for this resource, we will add Rs. 0 (or nothing) to the objective function.

Department of Commerce, Gargi College 23/03/20

 18

— This topic was LPP for a Pure Maximization Case.

— Kindly practice: All solved examples from the book,
starting from Ex 4 to Ex 12
— All unsolved questions asked in the past years

Department of Commerce, Gargi College 23/03/20