Quantitative Analysis for

Management
Goa Institute of Management
PGDM-FT 2023-2024

14-10-2023 Deepti Mohan | Goa Institute of Management

• The simplex method starts with a linear program in standard form.

14-10-2023 Deepti Mohan | Goa Institute of Management

Standard form of an LPP
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
s𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜:
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 = 𝑏2
.
.
.
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 = 𝑏𝑚
and
𝑥1 ≥ 0, 𝑥2 ≥ 0, … , 𝑥𝑛 ≥ 0[𝑁𝑜𝑛 − 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠]
𝑏1 ≥ 0, 𝑏2 ≥ 0, … , 𝑏𝑚 ≥ 0[𝑁𝑜𝑛 − 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑅𝐻𝑆 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑠 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠]

14-10-2023 Deepti Mohan | Goa Institute of Management

I. Converting a <= type inequality to equation
[Slack variable]
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = 4𝑥1 + 5𝑥2
𝑠. 𝑡.
𝑥1 − 5𝑥2 ≤ 6
−3𝑥1 + 4𝑥2 ≤ 1
𝑥1 , 𝑥2 ≥ 0

To convert a “≤” constraint to an equality, use a slack variable.

In Standard form:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = 4𝑥1 + 5𝑥2 + 0𝑠1 + 0𝑠2
𝑠. 𝑡.
𝑥1 − 5𝑥2 + 𝑠1 = 6
−3𝑥1 + 4𝑥2 + 𝑠2 = 1
𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 ≥ 0

14-10-2023 Deepti Mohan | Goa Institute of Management

II. Converting a >= type inequality to equation
[Surplus variable]
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = −4𝑥1 + 5𝑥2
𝑠. 𝑡.
𝑥1 − 5𝑥2 ≥ 6
−3𝑥1 + 4𝑥2 ≥ 1
𝑥1 , 𝑥2 ≥ 0

To convert a “≥” constraint to an equality, use a surplus variable.

In Standard form:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = 4𝑥1 + 5𝑥2 + 0𝑢1 + 0𝑢2
𝑠. 𝑡.
𝑥1 − 5𝑥2 − 𝑢1 = 6
−3𝑥1 + 4𝑥2 − 𝑢2 = 1
𝑥1 , 𝑥2 , 𝑢1 , 𝑢2 ≥ 0

14-10-2023 Deepti Mohan | Goa Institute of Management

III. Converting a negative RHS of constraint to
positive
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = −4𝑥1 + 5𝑥2
𝑠. 𝑡.
𝑥1 − 5𝑥2 ≥ 6
−3𝑥1 + 4𝑥2 ≥ −1
𝑥1 , 𝑥2 ≥ 0
𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑦 𝑡ℎ𝑒 𝑖𝑛𝑒𝑞𝑢𝑎𝑙𝑖𝑡𝑦 𝑏𝑦 − 1 :
−3𝑥1 + 4𝑥2 ≥ −1 => 3𝑥1 − 4𝑥2 ≤ 1
In Standard form:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = −4𝑥1 + 5𝑥2 + 0𝑢 + 0𝑠
𝑠. 𝑡.
𝑥1 − 5𝑥2 − 𝑢 = 6
3𝑥1 − 4𝑥2 + 𝑠 = 1
𝑥1 , 𝑥2 , 𝑢, 𝑠 ≥ 0

14-10-2023 Deepti Mohan | Goa Institute of Management

IV. Converting a minimization problem to a
maximization problem
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑍 = −4𝑥1 + 5𝑥2
𝑠. 𝑡.
𝑥1 − 5𝑥2 ≥ 6
−3𝑥1 + 4𝑥2 ≤ 1
𝑥1 , 𝑥2 ≥ 0
𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑦 𝑡ℎ𝑒 𝑜𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑏𝑦 − 1 :

In Standard form:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = 4𝑥1 − 5𝑥2 + 0𝑢 + 0𝑠
𝑠. 𝑡.
𝑥1 − 5𝑥2 − 𝑢 = 6
−3𝑥1 + 4𝑥2 + 𝑠 = 1
𝑥1 , 𝑥2 , 𝑢, 𝑠 ≥ 0

14-10-2023 Deepti Mohan | Goa Institute of Management

Reduce to Standard form:
1) Standard form:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = 𝑥1 − 4𝑥2 + 0𝑠 + 0𝑢
Maximize Z = x1 - 4x2
𝑠. 𝑡.
s.t. −𝑥1 + 5𝑥2 + 𝑠 = 5
-x1 + 5x2 ≤ 5 3𝑥1 + 4𝑥2 − 𝑢 = 12
& 𝑥1, 𝑥2, 𝑠, 𝑢 ≥ 0
3x1 + 4x2 ≥ 12
& x1, x2 ≥0

14-10-2023 Deepti Mohan | Goa Institute of Management

Reduce to Standard form:
2)
Minimize Z = 4x1 - 7x2 Standard form:
s.t. 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = −4𝑥1 + 7𝑥2 + 0𝑢1 + 0𝑢2
𝑠. 𝑡.
2x1 - 3x2 ≤ -3
−2𝑥1 + 3𝑥2 − 𝑢1 = 3
4x1 - x2 ≥ 5 4𝑥1 − 𝑥2 – 𝑢2 = 5
x1 + 2x2 =2 𝑥1 + 2𝑥2 = 2
& 𝑥1, 𝑥2 , 𝑢1 , 𝑢2 ≥ 0
& x1, x2 ≥0

14-10-2023 Deepti Mohan | Goa Institute of Management

Building intuition for the Simplex Method
Solve graphically
Maximize
Z = 40x1 + 10x2
s.t.
2x1 + x2 ≤ 50
2x1 + 5x2 ≤ 100
2x1 + 3x2 ≤ 90
& x1, x2 ≥0

14-10-2023 Deepti Mohan | Goa Institute of Management

Building intuition for the Simplex Method
Solve graphically
Maximize
Z = 40x1 + 10x2
s.t.
2x1 + x2 ≤ 50
2x1 + 5x2 ≤ 100
2x1 + 3x2 ≤ 90
& x1, x2 ≥0

14-10-2023 Deepti Mohan | Goa Institute of Management

Building intuition for the Simplex Method
Solve graphically
Maximize
Z = 40x1 + 10x2
s.t.
2x1 + x2 ≤ 50
2x1 + 5x2 ≤ 100
2x1 + 3x2 ≤ 90
& x1, x2 ≥0

14-10-2023 Deepti Mohan | Goa Institute of Management

Building intuition for the Simplex Method
Maximize
In Standard form:
Z = 40x1 + 10x2 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
s.t. 𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
2x1 + x2 ≤ 50 2𝑥1 + 𝑥2 + 𝑠1 = 50
2x1 + 5x2 ≤ 100 2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90
2x1 + 3x2 ≤ 90
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
& x1, x2 ≥0

14-10-2023 Deepti Mohan | Goa Institute of Management

Building intuition for the Simplex Method
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3 Number of variables?
𝑠. 𝑡. Number of equations?
2𝑥1 + 𝑥2 + 𝑠1 = 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90 Basic variables
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0 Non-basic variables (value set to zero)

14-10-2023 Deepti Mohan | Goa Institute of Management

Building intuition for the Simplex Method
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 Number of variables = n
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3 Number of equations = m
𝑠. 𝑡.
2𝑥1 + 𝑥2 + 𝑠1 = 50
Basic variables
2𝑥1 + 5𝑥2 + 𝑠2 = 100 Non-basic variables (value set to zero)
2𝑥1 + 3𝑥2 + 𝑠3 = 90
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
Number of basic variables = m
Number of non-basic variables = n-m

14-10-2023 Deepti Mohan | Goa Institute of Management

Building intuition for the Simplex Method
S.N Basic Non-basic Solution Feasible? Z
o variables variables
1 𝑠1 , 𝑠2 , 𝑠3 𝑥1 , 𝑥2 𝑥1 = 0, 𝑥2 = 0, 𝑠1 =? , 𝑠2 =? , 𝑠3 =?
2 𝑥2 , 𝑠2 , 𝑠3 𝑥1 , 𝑠1 𝑥1 = 0, 𝑠1 = 0, 𝑥2 , =? 𝑠2 =? , 𝑠3 =?
3 𝑥2 , 𝑠1 , 𝑠3 𝑥1 , 𝑠2 𝑥1 = 0, 𝑠2 = 0, 𝑥2 , =? 𝑠1 =? , 𝑠3 =?
4 𝑥2 , 𝑠1 , 𝑠2 𝑥1 , 𝑠3 𝑥1 = 0, 𝑠3 = 0, 𝑥2 , =? 𝑠2 =? , 𝑠1 =?
5 𝑥1 , 𝑠2 , 𝑠3 𝑥2 , 𝑠1
6 𝑥1 , 𝑠1 , 𝑠3 𝑥2 , 𝑠2
7 𝑥1 , 𝑠1 , 𝑠2 𝑥2 , 𝑠3
8 𝑥1 , 𝑥2 , 𝑠3 𝑠1 , 𝑠2
9 𝑥1 , 𝑥2 , 𝑠1 𝑠2 , 𝑠3
10 𝑥1 , 𝑥2 , 𝑠2 𝑠1 , 𝑠3
14-10-2023 Deepti Mohan | Goa Institute of Management
Building intuition for the Simplex Method
S.No Basic Non-basic Solution Feasible? Z
variables variables
1 𝑠1 , 𝑠2 , 𝑠3 𝑥1 , 𝑥2 𝑥1 = 0, 𝑥2 = 0, 𝑠1 = 50, 𝑠2 = 100, 𝑠3 = 90 Yes 0
2 𝑥2 , 𝑠2 , 𝑠3 𝑥1 , 𝑠1 𝑥1 = 0, 𝑥2 = 50, 𝑠1 = 0, 𝑠2 = −150, 𝑠3 = −60 No -
3 𝑥2 , 𝑠1 , 𝑠3 𝑥1 , 𝑠2 𝑥1 = 0, 𝑥2 = 20, 𝑠1 = 30, 𝑠2 = 0, 𝑠3 = 30 Yes 200
4 𝑥2 , 𝑠1 , 𝑠2 𝑥1 , 𝑠3 𝑥1 = 0, 𝑥2 = 30, 𝑠1 = 20, 𝑠2 = −50, 𝑠3 = 0 No -
5 𝑥1 , 𝑠2 , 𝑠3 𝑥2 , 𝑠1 𝑥1 = 25, 𝑥2 = 0, 𝑠1 = 0, 𝑠2 = 50, 𝑠3 = 40 Yes 1000
6 𝑥1 , 𝑠1 , 𝑠3 𝑥2 , 𝑠2 𝑥1 = 50, 𝑥2 = 0, 𝑠1 = −50, 𝑠2 = 0, 𝑠3 = −10 No -
7 𝑥1 , 𝑠1 , 𝑠2 𝑥2 , 𝑠3 𝑥1 = 45, 𝑥2 = 0, 𝑠1 = −40, 𝑠2 = 10, 𝑠3 = 0 No -
8 𝑥1 , 𝑥2 , 𝑠3 𝑠1 , 𝑠2 𝑥1 = 18.75, 𝑥2 = 12.5, 𝑠1 = 0, 𝑠2 = 0, 𝑠3 = 8.75 Yes 875
9 𝑥1 , 𝑥2 , 𝑠2 𝑠1 , 𝑠3 𝑥1 = 15, 𝑥2 = 20, 𝑠1 = 0, 𝑠2 = −30, 𝑠3 = 0 No -
10 𝑥1 , 𝑥2 , 𝑠1 𝑠2 , 𝑠3 𝑥1 = 37.5, 𝑥2 = 5, 𝑠1 = −30, 𝑠2 = 0, 𝑠3 = 0 No -

14-10-2023 Deepti Mohan | Goa Institute of Management

Building intuition for the Simplex Method
S.No Basic Non-basic Solution Feasible? Z
variables variables
1 𝑠1 , 𝑠2 , 𝑠3 𝑥1 , 𝑥2 𝑥1 = 0, 𝑥2 = 0, 𝑠1 = 50, 𝑠2 = 100, 𝑠3 = 90 Yes 0
2 𝑥2 , 𝑠2 , 𝑠3 𝑥1 , 𝑠1 𝑥1 = 0, 𝑥2 = 50, 𝑠1 = 0, 𝑠2 = −150, 𝑠3 = −60 No -
3 𝑥2 , 𝑠1 , 𝑠3 𝑥1 , 𝑠2 𝑥1 = 0, 𝑥2 = 20, 𝑠1 = 30, 𝑠2 = 0, 𝑠3 = 30 Yes 200
4 𝑥2 , 𝑠1 , 𝑠2 𝑥1 , 𝑠3 𝑥1 = 0, 𝑥2 = 30, 𝑠1 = 20, 𝑠2 = −50, 𝑠3 = 0 No -
5 𝑥1 , 𝑠2 , 𝑠3 𝑥2 , 𝑠1 𝑥1 = 25, 𝑥2 = 0, 𝑠1 = 0, 𝑠2 = 50, 𝑠3 = 40 Yes 1000
6 𝑥1 , 𝑠1 , 𝑠3 𝑥2 , 𝑠2 𝑥1 = 50, 𝑥2 = 0, 𝑠1 = −50, 𝑠2 = 0, 𝑠3 = −10 No -
7 𝑥1 , 𝑠1 , 𝑠2 𝑥2 , 𝑠3 𝑥1 = 45, 𝑥2 = 0, 𝑠1 = −40, 𝑠2 = 10, 𝑠3 = 0 No -
8 𝑥1 , 𝑥2 , 𝑠3 𝑠1 , 𝑠2 𝑥1 = 18.75, 𝑥2 = 12.5, 𝑠1 = 0, 𝑠2 = 0, 𝑠3 = 8.75 Yes 875
9 𝑥1 , 𝑥2 , 𝑠2 𝑠1 , 𝑠3 𝑥1 = 15, 𝑥2 = 20, 𝑠1 = 0, 𝑠2 = −30, 𝑠3 = 0 No -
10 𝑥1 , 𝑥2 , 𝑠1 𝑠2 , 𝑠3 𝑥1 = 37.5, 𝑥2 = 5, 𝑠1 = −30, 𝑠2 = 0, 𝑠3 = 0 No -

14-10-2023 Deepti Mohan | Goa Institute of Management

Building intuition for the Simplex Method
Why is Simplex more efficient than algebraic method?
• Initialization
• Going in the direction which leads to better objective function value
• Avoiding infeasible solutions
• Terminating when no adjacent vertex can give a better objective
function value.

14-10-2023 Deepti Mohan | Goa Institute of Management

Simplex Method
Maximize
In Standard form:
Z = 40x1 + 10x2 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
s.t. 𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
2x1 + x2 ≤ 50 2𝑥1 + 𝑥2 + 𝑠1 = 50
2x1 + 5x2 ≤ 100 2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90
2x1 + 3x2 ≤ 90
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
& x1, x2 ≥0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
Simplex Tableau 𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
Initialization: set 𝑥1 =0 and 𝑥2 =0. Basic variables are 𝑠1 , 𝑠2 , and 𝑠3
2𝑥1 + 𝑥2 + 𝑠1 = 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
𝑐𝑗 is the objective function coefficient of variable j 2𝑥1 + 3𝑥2 + 𝑠3 = 90
𝑥𝐵 is the set of basic variables. & 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑐𝐵 is the objective function coefficient of the basic variable

𝒄𝒋
Iteration 1: 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2
𝒔𝟏
𝒔𝟐
𝒔𝟑
𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
Simplex Tableau 𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
2𝑥1 + 𝑥2 + 𝑠1 = 50
Iteration 1:
2𝑥1 + 5𝑥2 + 𝑠2 = 100
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2 2𝑥1 + 3𝑥2 + 𝑠3 = 90
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0

𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS

0 𝒔𝟏 2 1 1 0 0 50
0 𝒔𝟐 2 5 0 1 0 100
0 𝒔𝟑 2 3 0 0 1 90
𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
Simplex Tableau 𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
2𝑥1 + 𝑥2 + 𝑠1 = 50
Iteration 1: 2𝑥1 + 5𝑥2 + 𝑠2 = 100
Basic variables: 𝑠1 , 𝑠2 , 𝑠3 2𝑥1 + 3𝑥2 + 𝑠3 = 90
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
Non-basic variables: 𝑥1 , 𝑥2
Basic feasible solution: 𝑠1 = 50 , 𝑠2 = 100, 𝑠3 = 90. 𝑍 = 0

𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS

0 𝒔𝟏 2 1 1 0 0 50
0 𝒔𝟐 2 5 0 1 0 100
0 𝒔𝟑 2 3 0 0 1 90
𝑧𝑗 0 0 0 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

• How to find the basic variables for the next iteration?
• One non-basic variable enters into the basic set (entering variable)
and one basic variable leaves the basic set (leaving variable).
• First, we find the entering variable and then we find the leaving
variable.

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3

Simplex Tableau 𝑠. 𝑡.
2𝑥1 + 𝑥2 + 𝑠1 = 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
Iteration 1: 2𝑥1 + 3𝑥2 + 𝑠3 = 90
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2
Basic feasible solution: 𝑠1 = 50 , 𝑠2 = 100, 𝑠3 = 90. 𝑍 = 0
Compute 𝑐𝑗 − 𝑧𝑗 to determine the entering variable.

𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS

0 𝒔𝟏 2 1 1 0 0 50
0 𝒔𝟐 2 5 0 1 0 100
0 𝒔𝟑 2 3 0 0 1 90
𝑧𝑗 0 0 0 0 0 0
𝑐𝑗 − 𝑧𝑗 40 10 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3

Simplex Tableau 𝑠. 𝑡.
2𝑥1 + 𝑥2 + 𝑠1 = 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
Iteration 1:
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2

𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS

0 𝒔𝟏 2 1 1 0 0 50
0 𝒔𝟐 2 5 0 1 0 100
0 𝒔𝟑 2 3 0 0 1 90
𝑧𝑗 0 0 0 0 0 0
𝑐𝑗 − 𝑧𝑗 40 10 0 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

Simplex Tableau
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
Iteration 1: 2𝑥1 + 𝑥2 + 𝑠1 = 50
Basic variables: 𝑠1 , 𝑠2 , 𝑠3 2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90
Non-basic variables: 𝑥1 , 𝑥2 & 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
Basic feasible solution: 𝑠1 = 50 , 𝑠2 = 100, 𝑠3 = 90. 𝑍 = 0

Out of the non-basic variables, 𝑥1 ℎ𝑎𝑠 𝑡ℎ𝑒 ℎ𝑖𝑔ℎ𝑒𝑠𝑡 𝑐𝑗 − 𝑧𝑗 value. Hence it will enter the set of basic variables in the
next iteration
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS

0 𝒔𝟏 2 1 1 0 0 50
0 𝒔𝟐 2 5 0 1 0 100
0 𝒔𝟑 2 3 0 0 1 90
𝑧𝑗 0 0 0 0 0 0
𝑐𝑗 − 𝑧𝑗 40 10 0 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3

Simplex Tableau 𝑠. 𝑡.
2𝑥1 + 𝑥2 + 𝑠1 = 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
Iteration 1: 2𝑥1 + 3𝑥2 + 𝑠3 = 90
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2
Basic feasible solution: 𝑠1 = 50 , 𝑠2 = 100, 𝑠3 = 90. 𝑍 = 0
𝑥1 will enter the set of basic variables in the next iteration.
Compute ratios to determine the leaving variable.
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

0 𝒔𝟏 2 1 1 0 0 50 25
0 𝒔𝟐 2 5 0 1 0 100 50
0 𝒔𝟑 2 3 0 0 1 90 45
𝑧𝑗 0 0 0 0 0 0
𝑐𝑗 − 𝑧𝑗 40 10 0 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3

Simplex Tableau 𝑠. 𝑡.
2𝑥1 + 𝑥2 + 𝑠1 = 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
Iteration 1: 2𝑥1 + 3𝑥2 + 𝑠3 = 90
Basic variables: 𝑠1 , 𝑠2 , 𝑠3 & 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
Non-basic variables: 𝑥1 , 𝑥2
Basic feasible solution: 𝑠1 = 50 , 𝑠2 = 100, 𝑠3 = 90. 𝑍 = 0

𝑥1 will enter the set of basic variables in the next iteration.

The variable with the lowest ratio will be leaving.
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

0 𝒔𝟏 2 1 1 0 0 50 25
0 𝒔𝟐 2 5 0 1 0 100 50
0 𝒔𝟑 2 3 0 0 1 90 45
𝑧𝑗 0 0 0 0 0 0
𝑐𝑗 − 𝑧𝑗 40 10 0 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3

Simplex Tableau 𝑠. 𝑡.
2𝑥1 + 𝑥2 + 𝑠1 = 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
Iteration 1: 2𝑥1 + 3𝑥2 + 𝑠3 = 90
Basic variables: 𝑠1 , 𝑠2 , 𝑠3 & 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0

Non-basic variables: 𝑥1 , 𝑥2
Basic feasible solution: 𝑠1 = 50 , 𝑠2 = 100, 𝑠3 = 90. 𝑍 = 0
𝑥1 will enter the set of basic variables in the next iteration.
𝑠1 will leave the set of basic variables in the next iteration.
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

0 𝒔𝟏 2 1 1 0 0 50 25
0 𝒔𝟐 2 5 0 1 0 100 50
0 𝒔𝟑 2 3 0 0 1 90 45
𝑧𝑗 0 0 0 0 0 0
𝑐𝑗 − 𝑧𝑗 40 10 0 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

• How to find the basic variables for the next iteration?
• One non-basic variable enters into the basic set (entering variable)
and one basic variable leaves the basic set (leaving variable).
• We find the entering variable first by computing 𝑐𝑗 − 𝑧𝑗 . Non-basic
variable with the highest positive 𝑐_𝑗 − 𝑧_𝑗 value will be the entering
variable.
• Then we find the leaving variable using ratio test. The variable with
the lowest positive ratio will be the leaving variable. (Do not compute
ratios for which denominator is zero or negative).

14-10-2023 Deepti Mohan | Goa Institute of Management

 Iteration 1:
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2
Basic feasible solution: 𝑠1 = 50 , 𝑠2 = 100, 𝑠3 =
90. 𝑍 = 0

𝑥1 will enter the set of basic variables in the

next iteration.
𝑠1 will leave the set of basic variables in the
next iteration.

14-10-2023 Deepti Mohan | Goa Institute of Management

Simplex Tableau
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
0 𝒔𝟏 2 1 1 0 0 50 25
2𝑥1 + 𝑥2 + 𝑠1 = 50 0 𝒔𝟐 2 5 0 1 0 100 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90 0 𝒔𝟑 2 3 0 0 1 90 45
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑧𝑗 0 0 0 0 0 0

Iteration 2: 𝑐𝑗 𝒄−𝒋 𝑧𝑗 40 10 0 0 0 0
Basic variables: 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑥1 , 𝑠2 , 𝑠3
Non-basic 40 𝒙𝟏
variables: s1 , 𝑥2
0 𝒔𝟐
0 𝒔𝟑
𝑧𝑗
𝑐𝑗 − 𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

Simplex Tableau
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
0 𝒔𝟏 2 1 1 0 0 50 25
2𝑥1 + 𝑥2 + 𝑠1 = 50 0 𝒔𝟐 2 5 0 1 0 100 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90 0 𝒔𝟑 2 3 0 0 1 90 45
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑧𝑗 0 0 0 0 0 0

Iteration 2: 𝑐𝑗 𝒄−𝒋 𝑧𝑗 40 10 0 0 0 0
Basic variables: 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑥1 , 𝑠2 , 𝑠3
Non-basic 40 𝒙𝟏
variables: s1 , 𝑥2
0 𝒔𝟐

Identify the pivot 0 𝒔𝟑

element and the 𝑧𝑗
pivot row 𝑐𝑗 − 𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

Simplex Tableau
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
0 𝒔𝟏 2 1 1 0 0 50 25
2𝑥1 + 𝑥2 + 𝑠1 = 50 0 𝒔𝟐 2 5 0 1 0 100 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90 0 𝒔𝟑 2 3 0 0 1 90 45
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑧𝑗 0 0 0 0 0 0
Iteration 2: 𝑐𝑗 𝒄−𝒋 𝑧𝑗 40 10 0 0 0 0
Basic variables:
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑥1 , 𝑠2 , 𝑠3
Non-basic
variables: s1 , 𝑥2 40 𝒙𝟏 1 1/2 1/2 0 0 25
0 𝒔𝟐
Divide the pivot row by
pivot element to get 0 𝒔𝟑
the row corresponding 𝑧𝑗
to 𝑥1
𝑐𝑗 − 𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

 Simplex Tableau
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝒄𝒋 40 10 0 0 0
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡. 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
2𝑥1 + 𝑥2 + 𝑠1 = 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90 0 𝒔𝟏 2 1 1 0 0 50 25
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
0 𝒔𝟐 2 5 0 1 0 100 50
Iteration 2: 0 𝒔𝟑 2 3 0 0 1 90 45
Basic variables: 𝑥1 , 𝑠2 , 𝑠3
Non-basic variables: s1 , 𝑥2 𝑧𝑗 0 0 0 0 0 0
𝑐𝑗 𝒄−𝒋 𝑧𝑗 40 10 0 0 0 0
Do row operations such that
in each row the 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
corresponding basic variable
has coefficient 1 and the 40 𝒙𝟏 1 1/2 1/2 0 0 25
other basic variables have
coefficient as 0. New row 2 = 0 𝒔𝟐 0 4 -1 1 0 50
old row 2 – pivot row 0 𝒔𝟑 0
𝑧𝑗
𝑐𝑗 − 𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

 Simplex Tableau
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
0 𝒔𝟏 2 1 1 0 0 50 25
2𝑥1 + 𝑥2 + 𝑠1 = 50 0 𝒔𝟐 2 5 0 1 0 100 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90 0 𝒔𝟑 2 3 0 0 1 90 45
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑧𝑗 0 0 0 0 0 0
Iteration 2:
Basic variables: 𝑐𝑗 𝒄−𝒋 𝑧𝑗 40 10 0 0 0 0
𝑥1 , 𝑠2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Non-basic
variables: s1 , 𝑥2 40 𝒙𝟏 1 1/2 1/2 0 0 25
New row 3 = old row 3 – pivot 0 𝒔𝟐 0 4 -1 1 0 50
row
0 𝒔𝟑 0 2 -1 0 1 40
𝑧𝑗
𝑐𝑗 − 𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

Simplex Tableau
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
0 𝒔𝟏 2 1 1 0 0 50 25
2𝑥1 + 𝑥2 + 𝑠1 = 50 0 𝒔𝟐 2 5 0 1 0 100 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90 0 𝒔𝟑 2 3 0 0 1 90 45
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑧𝑗 0 0 0 0 0 0
Iteration 2:
Basic variables: 𝑐𝑗 𝒄−𝒋 𝑧𝑗 40 10 0 0 0 0
𝑥1 , 𝑠2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Non-basic
variables: s1 , 𝑥2 40 𝒙𝟏 1 1/2 1/2 0 0 25
0 𝒔𝟐 0 4 -1 1 0 50
Basic feasible solution:
𝑥1 = 25 , 𝑠2 = 50, 𝑠3 = 0 𝒔𝟑 0 2 -1 0 1 40
40. 𝑍 = 1000 𝑧𝑗 40 20 20 0 0 1000
𝑐𝑗 − 𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

Simplex Tableau
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
0 𝒔𝟏 2 1 1 0 0 50 25
2𝑥1 + 𝑥2 + 𝑠1 = 50 0 𝒔𝟐 2 5 0 1 0 100 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90 0 𝒔𝟑 2 3 0 0 1 90 45
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑧𝑗 0 0 0 0 0 0
Iteration 2:
Basic variables: 𝑐𝑗 𝒄−𝒋 𝑧𝑗 40 10 0 0 0 0
𝑥1 , 𝑠2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Non-basic
variables: s1 , 𝑥2 40 𝒙𝟏 1 1/2 1/2 0 0 25
Compute 𝑐𝑗 − 𝑧𝑗 0 𝒔𝟐 0 4 -1 1 0 50
0 𝒔𝟑 0 2 -1 0 1 40
𝑧𝑗 40 20 20 0 0 1000
𝑐𝑗 − 𝑧𝑗 0 -10 -20 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 Simplex Tableau
𝒄𝒋 40 10 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = 40𝑥1 + 10𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡.
0 𝒔𝟏 2 1 1 0 0 50 25
2𝑥1 + 𝑥2 + 𝑠1 = 50 0 𝒔𝟐 2 5 0 1 0 100 50
2𝑥1 + 5𝑥2 + 𝑠2 = 100
2𝑥1 + 3𝑥2 + 𝑠3 = 90 0 𝒔𝟑 2 3 0 0 1 90 45
& 𝑥1, 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑧𝑗 0 0 0 0 0 0
Iteration 2:
Basic variables: 𝑐𝑗 𝒄−𝒋 𝑧𝑗 40 10 0 0 0 0
𝑥1 , 𝑠2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Non-basic
variables: s1 , 𝑥2 40 𝒙𝟏 1 1/2 1/2 0 0 25
0 𝒔𝟐 0 4 -1 1 0 50
There is no positive 𝑐𝑗 −
0 𝒔𝟑 0 2 -1 0 1 40
𝑧𝑗 for any non-basic
variable. No variable can 𝑧𝑗 40 20 20 0 0 1000
enter. Algorithm 𝑐𝑗 − 𝑧𝑗 0 -10 -20 0 0
terminates.
14-10-2023 Deepti Mohan | Goa Institute of Management
 Iteration 1:
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2
Basic feasible solution: 𝑠1 = 50 , 𝑠2 = 100, 𝑠3 = 90. 𝑍 = 0
𝑥1 will enter the set of basic variables in the next iteration.
𝑠1 will leave the set of basic variables in the next iteration.

Iteration 2:
Basic variables: 𝑥1 , 𝑠2 , 𝑠3
Non-basic variables: s1 , 𝑥2
Basic feasible solution: 𝑥1 = 25 , 𝑠2 = 50, 𝑠3 = 40. 𝑍 =
1000
No variable can enter. Algorithm terminates. Optimal
solution is obtained in iteration 2.

14-10-2023 Deepti Mohan | Goa Institute of Management

Simplex Method – Example 2
Solve the following LPP using Simplex method
Min Z = x1 + x2 - 4x3
Subjected to the constraints (St)
x1 + x2 + 2x3 ≤ 9
x1 + x2 - x3 ≤ 2
-x1 + x2 + x3≤ 4
& x1, x2, x3 ≥0

14-10-2023 Deepti Mohan | Goa Institute of Management

Simplex Method – Example 2
Solve the following LPP using Simplex method
Min Z = x1 + x2 - 4x3 In Standard form:
Subjected to the constraints (St) 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
x1 + x2 + 2x3 ≤ 9
𝑠. 𝑡.
x1 + x2 - x3 ≤ 2 𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2
-x1 + x2 + x3≤ 4
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
& x1, x2, x3 ≥0 & 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒

Simplex Tableau 𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3

𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2
𝑐𝑗 is the objective function coefficient of variable j −𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
𝑥𝐵 is the set of basic variables. & 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑐𝐵 is the objective function coefficient of the basic variable

𝒄𝒋
Iteration 1: 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2 , 𝑥3
𝒔𝟏
𝒔𝟐
𝒔𝟑
𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒

Simplex Tableau 𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3

𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2
𝑐𝑗 is the objective function coefficient of variable j −𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
𝑥𝐵 is the set of basic variables. & 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑐𝐵 is the objective function coefficient of the basic variable

𝒄𝒋 -1 -1 4 0 0 0
Iteration 1: 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2 , 𝑥3
0 𝒔𝟏 1 1 2 1 0 0 9
0 𝒔𝟐 1 1 -1 0 1 0 2
0 𝒔𝟑 -1 1 1 0 0 1 4
𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒

Simplex Tableau 𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3

𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0

𝒄𝒋 -1 -1 4 0 0 0
Iteration 1: 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2 , 𝑥3
0 𝒔𝟏 1 1 2 1 0 0 9
0 𝒔𝟐 1 1 -1 0 1 0 2
Basic feasible solution:
0 𝒔𝟑 -1 1 1 0 0 1 4
𝑥1 = 0, 𝑥2 =0, 𝑥3 =0, 𝑠1 =
9 , 𝑠2 = 2, 𝑠3 = 4 𝑧𝑗 0 0 0 0 0 0 0
Z=0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒

Simplex Tableau 𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3

𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0

𝒄𝒋 -1 -1 4 0 0 0
Iteration 1: 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
Non-basic variables: 𝑥1 , 𝑥2 , 𝑥3
0 𝒔𝟏 1 1 2 1 0 0 9
0 𝒔𝟐 1 1 -1 0 1 0 2
Basic feasible solution:
0 𝒔𝟑 -1 1 1 0 0 1 4
𝑥1 = 0, 𝑥2 =0, 𝑥3 =0, 𝑠1 =
9 , 𝑠2 = 2, 𝑠3 = 4 𝑧𝑗 0 0 0 0 0 0 0
Z=0 𝒄𝒋 -𝑧𝑗 -1 -1 4 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒

Simplex Tableau 𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3

𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2
Iteration 1: −𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
Basic variables: 𝑠1 , 𝑠2 , 𝑠3
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
Non-basic variables: 𝑥1 , 𝑥2 , 𝑥3

𝒄𝒋 -1 -1 4 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS
𝑥3 will be the entering
variable 0 𝒔𝟏 1 1 2 1 0 0 9
0 𝒔𝟐 1 1 -1 0 1 0 2
0 𝒔𝟑 -1 1 1 0 0 1 4
𝑧𝑗 0 0 0 0 0 0 0
𝒄𝒋 -𝑧𝑗 -1 -1 4 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒

Simplex Tableau 𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3

𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2
Iteration 1: −𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
Basic variables: 𝑠1 , 𝑠2 , 𝑠3 & 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
Non-basic variables: 𝑥1 , 𝑥2 , 𝑥3

𝒄𝒋 -1 -1 4 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑥3 will be the entering
variable
𝑠3 will be the leaving 0 𝒔𝟏 1 1 2 1 0 0 9 4.5
variable 0 𝒔𝟐 1 1 -1 0 1 0 2 -
0 𝒔𝟑 -1 1 1 0 0 1 4 4
𝑧𝑗 0 0 0 0 0 0 0
𝒄𝒋 -𝑧𝑗 -1 -1 4 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 Simplex Tableau 𝒄𝒋 -1 -1 4 0 0 0
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 1 1 2 1 0 0 9 4.5
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
0 𝒔𝟐 1 1 -1 0 1 0 2 -
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
0 𝒔𝟑 -1 1 1 0 0 1 4 4
𝑧𝑗 0 0 0 0 0 0 0
Iteration 2: 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1 -1 4 0 0 0
-1 -1 4 0 0 0
Basic variables: 𝑠1 , 𝑠2 , 𝑥3
Non-basic variables: 𝑥1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

0 𝒔𝟏
0 𝒔𝟐
4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗
14-10-2023 𝒄𝒋Mohan
Deepti -𝑧𝑗 | Goa Institute of Management
 Simplex Tableau 𝒄𝒋 -1 -1 4 0 0 0
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 1 1 2 1 0 0 9 4.5
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
0 𝒔𝟐 1 1 -1 0 1 0 2 -
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
0 𝒔𝟑 -1 1 1 0 0 1 4 4
𝑧𝑗 0 0 0 0 0 0 0
Iteration 2: 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1 -1 4 0 0 0
-1 -1 4 0 0 0
Basic variables: 𝑠1 , 𝑠2 , 𝑥3
Non-basic variables: 𝑥1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

0 𝒔𝟏 0
New Row2= Old Row 2 + 0 𝒔𝟐 0 2 0 0 1 1 6
pivot row 4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗
14-10-2023 𝒄𝒋Mohan
Deepti -𝑧𝑗 | Goa Institute of Management
 Simplex Tableau 𝒄𝒋 -1 -1 4 0 0 0
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 1 1 2 1 0 0 9 4.5
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
0 𝒔𝟐 1 1 -1 0 1 0 2 -
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
0 𝒔𝟑 -1 1 1 0 0 1 4 4
𝑧𝑗 0 0 0 0 0 0 0
Iteration 2: 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1 -1 4 0 0 0
-1 -1 4 0 0 0
Basic variables: 𝑠1 , 𝑠2 , 𝑥3
Non-basic variables: 𝑥1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

0 𝒔𝟏 3 -1 0 1 0 -2 1
New Row 1= Old Row 1 – 0 𝒔𝟐 0 2 0 0 1 1 6
2*pivot row 4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗
14-10-2023 𝒄𝒋Mohan
Deepti -𝑧𝑗 | Goa Institute of Management
 Simplex Tableau 𝒄𝒋 -1 -1 4 0 0 0
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 1 1 2 1 0 0 9 4.5
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
0 𝒔𝟐 1 1 -1 0 1 0 2 -
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
0 𝒔𝟑 -1 1 1 0 0 1 4 4
𝑧𝑗 0 0 0 0 0 0 0
Iteration 2: 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1 -1 4 0 0 0
-1 -1 4 0 0 0
Basic variables: 𝑠1 , 𝑠2 , 𝑥3
Non-basic variables: 𝑥1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

Basic feasible solution:

𝑥1 = 0, 𝑥2 =0, 𝑥3 =4, 𝑠1 = 1 , 0 𝒔𝟏 3 -1 0 1 0 -2 1
𝑠2 = 6, 𝑠3 = 0 0 𝒔𝟐 0 2 0 0 1 1 6
Z=-16 (why?) 4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗 -4 4 4 0 0 4 16
14-10-2023 𝒄𝒋Mohan
Deepti -𝑧𝑗 | Goa Institute of Management
• Remember when the original problem is a minimization problem, we
have to reverse the sign of the Z value obtained from Simplex table to
get the minimum value of the objective function corresponding to the
original problem.
• Minimize Z = f is converted to Maximize Z=-f
• What we get is the value of –f, so multiply by -1 to get the optimal
value of f.

14-10-2023 Deepti Mohan | Goa Institute of Management

 Simplex Tableau 𝒄𝒋 -1 -1 4 0 0 0
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 1 1 2 1 0 0 9 4.5
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
0 𝒔𝟐 1 1 -1 0 1 0 2 -
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
0 𝒔𝟑 -1 1 1 0 0 1 4 4
𝑧𝑗 0 0 0 0 0 0 0
Iteration 2: 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1 -1 4 0 0 0
-1 -1 4 0 0 0
Basic variables: 𝑠1 , 𝑠2 , 𝑥3
Non-basic variables: 𝑥1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

Basic feasible solution:

𝑥1 = 0, 𝑥2 =0, 𝑥3 =4, 𝑠1 = 1 , 0 𝒔𝟏 3 -1 0 1 0 -2 1
𝑠2 = 6, 𝑠3 = 0 0 𝒔𝟐 0 2 0 0 1 1 6
Z=-16 4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗 -4 4 4 0 0 4 16
14-10-2023 𝒄𝒋Mohan
Deepti -𝑧𝑗 | Goa Institute of Management
 Simplex Tableau 𝒄𝒋 -1 -1 4 0 0 0
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9 0 𝒔𝟏 1 1 2 1 0 0 9 4.5
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4 0 𝒔𝟐 1 1 -1 0 1 0 2 -
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0 0 𝒔𝟑 -1 1 1 0 0 1 4 4
𝑧𝑗 0 0 0 0 0 0 0
Iteration 2: 𝒄𝒋 -𝑧𝒄𝑗 𝒋 -1
-1 -1
-1 44 00 00 00
Basic variables: 𝑠1 , 𝑠2 , 𝑥3
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Non-basic variables: 𝑥1 , 𝑥2 , 𝑠3

𝑥1 is the entering variable. 0 𝒔𝟏 3 -1 0 1 0 -2 1

0 𝒔𝟐 0 2 0 0 1 1 6
4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗 -4 4 4 0 0 4 16
𝒄𝒋 -𝑧𝑗 3 -5 0 0 0 -4
14-10-2023 Deepti Mohan | Goa Institute of Management
 Simplex Tableau 𝒄𝒋 -1 -1 4 0 0 0
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑠. 𝑡.
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9 0 𝒔𝟏 1 1 2 1 0 0 9 4.5
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4 0 𝒔𝟐 1 1 -1 0 1 0 2 -
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0 0 𝒔𝟑 -1 1 1 0 0 1 4 4
𝑧𝑗 0 0 0 0 0 0 0
Iteration 2: 𝒄𝒋 -𝑧𝒄𝑗 𝒋 -1
-1 -1
-1 44 00 00 00
Basic variables: 𝑠1 , 𝑠2 , 𝑥3
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Non-basic variables: 𝑥1 , 𝑥2 , 𝑠3

𝑥1 is the entering variable. 0 𝒔𝟏 3 -1 0 1 0 -2 1 1/3

𝑠1 is the leaving variable. 0 𝒔𝟐 0 2 0 0 1 1 6
4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗 -4 4 4 0 0 4 16
𝒄𝒋 -𝑧𝑗 3 -5 0 0 0 -4
14-10-2023 Deepti Mohan | Goa Institute of Management
 Simplex Tableau
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝒄𝒋 -1 -1 4 0 0 0
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡. 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 3 -1 0 1 0 -2 1 1/3
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0 0 𝒔𝟐 0 2 0 0 1 1 6
4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗 -4 4 4 0 0 4 16
Iteration 3:
Basic variables: 𝑥1 , 𝑠2 , 𝑥3 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1
3 -1
-5 4
0 0 0 0
-4
Non-basic variables: 𝑠1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

-1 𝒙𝟏 1 -1/3 0 1/3 0 -2/3 1/3

0 𝒔𝟐 0
4 𝒙𝟑 0
𝑧𝑗
14-10-2023 𝒄𝒋 -𝑧𝑗 | Goa Institute of Management
Deepti Mohan
 Simplex Tableau
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝒄𝒋 -1 -1 4 0 0 0
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡. 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 3 -1 0 1 0 -2 1 1/3
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0 0 𝒔𝟐 0 2 0 0 1 1 6
4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗 -4 4 4 0 0 4 16
Iteration 3:
Basic variables: 𝑥1 , 𝑠2 , 𝑥3 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1
3 -1
-5 4
0 0 0 0
-4
Non-basic variables: 𝑠1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

-1 𝒙𝟏 1 -1/3 0 1/3 0 -2/3 1/3

New Row2= Old Row 2 0 𝒔𝟐 0 2 0 0 1 1 6
4 𝒙𝟑 0
𝑧𝑗
14-10-2023 𝒄𝒋 -𝑧𝑗 | Goa Institute of Management
Deepti Mohan
 Simplex Tableau
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝒄𝒋 -1 -1 4 0 0 0
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡. 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 3 -1 0 1 0 -2 1 1/3
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0 0 𝒔𝟐 0 2 0 0 1 1 6
4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗 -4 4 4 0 0 4 16
Iteration 3:
Basic variables: 𝑥1 , 𝑠2 , 𝑥3 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1
3 -1
-5 4
0 0 0 0
-4
Non-basic variables: 𝑠1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

-1 𝒙𝟏 1 -1/3 0 1/3 0 -2/3 1/3

New Row 3= Old Row 3 + 0 𝒔𝟐 0 2 0 0 1 1 6
pivot row/3 4 𝒙𝟑 0 2/3 1 1/3 0 1/3 13/3
𝑧𝑗
14-10-2023 𝒄𝒋 -𝑧𝑗 | Goa Institute of Management
Deepti Mohan
 Simplex Tableau
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝒄𝒋 -1 -1 4 0 0 0
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡. 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 3 -1 0 1 0 -2 1 1/3
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0 0 𝒔𝟐 0 2 0 0 1 1 6
4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗 -4 4 4 0 0 4 16
Iteration 3:
Basic variables: 𝑥1 , 𝑠2 , 𝑥3 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1
3 -1
-5 4
0 0 0 0
-4
Non-basic variables: 𝑠1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

Basic feasible solution:

-1 𝒙𝟏 1 -1/3 0 1/3 0 -2/3 1/3
𝑥1 = 1/3, 𝑥2 =0, 𝑥3 =13/3,
𝑠1 = 0 , 𝑠2 = 6, 𝑠3 = 0 0 𝒔𝟐 0 2 0 0 1 1 6
Z=-17 4 𝒙𝟑 0 2/3 1 1/3 0 1/3 13/3
𝑧𝑗 -1 3 4 1 0 2 17
14-10-2023 𝒄𝒋 -𝑧𝑗 | Goa Institute of Management
Deepti Mohan
 Simplex Tableau
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝒄𝒋 -1 -1 4 0 0 0
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡. 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 3 -1 0 1 0 -2 1 1/3
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0 0 𝒔𝟐 0 2 0 0 1 1 6
4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗 -4 4 4 0 0 4 16
Iteration 3:
Basic variables: 𝑥1 , 𝑠2 , 𝑥3 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1
3 -1
-5 4
0 0 0 0
-4
Non-basic variables: 𝑠1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

Basic feasible solution:

-1 𝒙𝟏 1 -1/3 0 1/3 0 -2/3 1/3
𝑥1 = 1/3, 𝑥2 =0, 𝑥3 =13/3,
𝑠1 = 0 , 𝑠2 = 6, 𝑠3 = 0 0 𝒔𝟐 0 2 0 0 1 1 6
Z=-17 4 𝒙𝟑 0 2/3 1 1/3 0 1/3 13/3
𝑧𝑗 -1 3 4 1 0 2 17
14-10-2023 𝒄𝒋|-𝑧Goa
Deepti Mohan -2
𝑗 Institute of Management -4 0 -1 0 -2
 Simplex Tableau
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝒄𝒋 -1 -1 4 0 0 0
𝑍 = −𝑥1 − 𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3
𝑠. 𝑡. 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 9
𝑥1 + 𝑥2 − 𝑥3 + 𝑠2 = 2 0 𝒔𝟏 3 -1 0 1 0 -2 1 1/3
−𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 4
& 𝑥1, 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0 0 𝒔𝟐 0 2 0 0 1 1 6
4 𝒙𝟑 -1 1 1 0 0 1 4
𝑧𝑗 -4 4 4 0 0 4 16
Iteration 3:
Basic variables: 𝑥1 , 𝑠2 , 𝑥3 𝒄𝒋 -𝑧𝑗𝒄𝒋 -1
3 -1
-5 4
0 0 0 0
-4
Non-basic variables: 𝑠1 , 𝑥2 , 𝑠3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

Basic feasible solution:

-1 𝒙𝟏 1 -1/3 0 1/3 0 -2/3 1/3
𝑥1 = 1/3, 𝑥2 =0, 𝑥3 =13/3,
𝑠1 = 0 , 𝑠2 = 6, 𝑠3 = 0 0 𝒔𝟐 0 2 0 0 1 1 6
Z*=-17 (why?) 4 𝒙𝟑 0 2/3 1 1/3 0 1/3 13/3
No entering variable
𝑧𝑗 -1 3 4 1 0 2 17
14-10-2023 𝒄𝒋|-𝑧Goa
Deepti Mohan -2
𝑗 Institute of Management -4 0 -1 0 -2
Simplex Method – Example 3
MAX Z = x1 - 3x2 + 2x3
subject to
3x1 - x2 + 2x3 <= 7
-2x1 + 4x2 <= 12
-4x1 + 3x2 + 8x3 <= 10
and x1,x2,x3 >= 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 Standard Form:
MAX Z = x1 - 3x2 + 2x3 𝑀𝑎𝑥 𝑍 = 𝑥1 − 3𝑥2 + 2𝑥3 + 0𝑆1 + 0𝑆2 + 0𝑆3
𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜
subject to
3𝑥1 − 𝑥2 + 2𝑥3 + 𝑆1 = 7
3x1 - x2 + 2x3 <= 7
− 2𝑥1 + 4𝑥2 + 𝑆2 = 12
-2x1 + 4x2 <= 12
− 4𝑥1 + 3𝑥2 + 8𝑥3 + 𝑆3 = 10
-4x1 + 3x2 + 8x3 <= 10
𝑎𝑛𝑑 𝑥1, 𝑥2, 𝑥3, 𝑆1, 𝑆2, 𝑆3 ≥ 0
and x1,x2,x3 >= 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝒄𝒋
• Iteration 1:
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
• Solution?
• Entering 𝒔𝟏
variable =?
Leaving 𝒔𝟐
variable =? 𝒔𝟑
𝑧𝑗
𝑐𝑗 -𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

• Entering variable =x3, Leaving variable =S3
𝒄𝒋 1 -3 2 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

0 𝒔𝟏 3 -1 2 1 0 0 7 3.5
0 𝒔𝟐 -2 4 0 0 1 0 12 -
0 𝒔𝟑 -4 3 8 0 0 1 10 1.25
𝑧𝑗 0 0 0 0 0 0
𝑐𝑗 -𝑧𝑗 1 -3 2 0 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝒄𝒋 1 -3 2 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

Iteration 1 0 𝒔𝟏 3 -1 2 1 0 0 7 3.5
Z=0 0 𝒔𝟐 -2 4 0 0 1 0 12 -
Entering variable =x3
Leaving variable =s3 0 𝒔𝟑 -4 3 8 0 0 1 10 1.25
𝑧𝑗 0 0 0 0 0 0
𝑐𝑗𝒄-𝑧
𝒋𝑗 1 -3 2 0 0 0
Iteration 2 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Solution?
Entering variable =?
𝒔𝟏 0
Leaving variable =?
𝒔𝟐 0
New row 3 should be
such that we should 𝒙𝟑 1
get 1 in place of the 𝑧𝑗
pivot element in the
new table 𝑐𝑗 -𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝒄𝒋 1 -3 2 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

Iteration 1
Z=0 0 𝒔𝟏 3 -1 2 1 0 0 7 3.5
Entering variable =x3 0 𝒔𝟐 -2 4 0 0 1 0 12 -
Leaving variable =s3 0 𝒔𝟑 -4 3 8 0 0 1 10 1.25
𝑧𝑗 0 0 0 0 0 0 0
𝑐𝑗𝒄-𝑧
𝒋𝑗 1 -3 2 0 0 0
Iteration 2 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Z=2.5
Entering variable =x1 0 𝒔𝟏 4 -1.75 0 1 0 -0.25 4.5 1.125
Leaving variable =s1
0 𝒔𝟐 -2 4 0 0 1 0 12 -
Pivot row = old row 3
New row 3 = 1/8*old row 3 2 𝒙𝟑 -0.5 0.375 1 0 0 0.125 1.25 -
New row 2 = old row 2 𝑧𝑗 -1 0.75 2 0 0 0.25 2.5
New row 1 = old row 1- 𝑐𝑗 -𝑧𝑗 2 -3.75 0 0 0 -0.25
1/4*pivot row

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝒄𝒋 1 -3 2 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

Iteration 1
Z=0 0 𝒔𝟏 3 -1 2 1 0 0 7 3.5
Entering variable =x3 0 𝒔𝟐 -2 4 0 0 1 0 12 -
Leaving variable =s3 0 𝒔𝟑 -4 3 8 0 0 1 10 1.25
𝑧𝑗 0 0 0 0 0 0 0
𝑐𝑗𝒄-𝑧
𝒋𝑗 1 -3 2 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio

0 𝒔𝟏 4 -1.75 0 1 0 -0.25 4.5 1.125

Iteration 2
Z=2.5 0 𝒔𝟐 -2 4 0 0 1 0 12 -
Entering variable =x1 2 𝒙𝟑 -0.5 0.375 1 0 0 0.125 1.25 -
Leaving variable =s1 𝑧𝑗 -1 0.75 2 0 0 0.25 2.5
𝑐𝑗 -𝑧𝑗 2 -3.75 0 0 0 -0.25

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝒄𝒋 1 -3 2 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Iteration 2
Z=2.5
Entering variable =x1 0 𝒔𝟏 4 -1.75 0 1 0 -0.25 4.5 1.125
Leaving variable =s1 0 𝒔𝟐 -2 4 0 0 1 0 12 -
2 𝒙𝟑 -0.5 0.375 1 0 0 0.125 1.25 -
𝑧𝑗 -1 0.75 2 0 0 0.25 2.5
𝑐𝑗𝒄-𝑧
𝒋𝑗 2 -3.75 0 0 0 -0.25
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Iteration 3
Solution? 1 𝒙𝟏 1
Entering variable =?
Leaving variable =? 0 𝒔𝟐 0
2 𝒙𝟑 0
𝑧𝑗
𝑐𝑗 -𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝒄𝒋 1 -3 2 0 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Iteration 2
Z=2.5
Entering variable =x1 0 𝒔𝟏 4 -1.75 0 1 0 -0.25 4.5 1.125
Leaving variable =s1 0 𝒔𝟐 -2 4 0 0 1 0 12 -
2 𝒙𝟑 -0.5 0.375 1 0 0 0.125 1.25 -
𝑧𝑗 -1 0.75 2 0 0 0.25 2.5
𝑐𝑗𝒄-𝑧
𝒋𝑗 2 -3.75 0 0 0 -0.25
Iteration 3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
Z*=4.75

Pivot row = old row 1 1 𝒙𝟏 - 1.125

1 -0.4375 0 0.25 0
New row 1 = 1/4*old row 1 0.0625
New row 2 = old row 2 + ½ 0 𝒔𝟐 0 3.125 0 0.5 1 -0.125 14.25
* pivot row
2 𝒙𝟑 1.812
New row 3 = old row 3+- 0 0.1562 1 0.125 0 0.0938
5
1/8*pivot row
𝑧𝑗 1 -0.125 2 0.5 0 0.125 4.75
𝑐 -𝑧 0 -2.875 0 -0.5 0 -0.125
14-10-2023 Deepti𝑗 Mohan
𝑗 | Goa Institute of Management
Simplex Method – Example 4
Min Z = 2x1 - x2 + 3x3
subject to
x1 + x2 + 2x3 ≤ 5
2x1 + 3x2 + 4x3 ≤ 12
& x1, x2, x3 ≥0

14-10-2023 Deepti Mohan | Goa Institute of Management

Simplex Method – Example 4
Min Z = 2x1 - x2 + 3x3
Max Z = -2x1 + x2 - 3x3
subject to
subject to
x1 + x2 + 2x3 ≤ 5
x1 + x2 + 2x3 + s1 =5
2x1 + 3x2 + 4x3 ≤ 12
2x1 + 3x2 + 4x3 + s2 =
& x1, x2, x3 ≥0 12
& x1, x2, x3, s1, s2 ≥0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝒄𝒋 -2 1 -3 0 0

Max Z = -2x1 + x2 - 3x3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 RHS Ratio

subject to
0 𝒔𝟏
x1 + x2 + 2x3 + s1 =5
0 𝒔𝟐
2x1 + 3x2 + 4x3 + s2 = 12
𝑧𝑗
& x1, x2, x3, s1, s2 ≥0
𝑐𝑗 -𝑧𝑗

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝒄𝒋 -2 1 -3 0 0

Max Z = -2x1 + x2 - 3x3 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 RHS Ratio

subject to
0 𝒔𝟏 1 1 2 1 0 5 5
x1 + x2 + 2x3 + s1 =5
0 𝒔𝟐 2 3 4 0 1 12 4
2x1 + 3x2 + 4x3 + s2 = 12
𝑧𝑗 0 0 0 0 0 0
& x1, x2, x3, s1, s2 ≥0
𝑐𝑗 -𝑧𝑗 -2 1 -3 0 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝒄𝒋 -2 1 -3 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 RHS Ratio

0 𝒔𝟏 1 1 2 1 0 5 5
0 𝒔𝟐 2 3 4 0 1 12 4
Max Z = -2x1 + x2 - 3x3 𝑧𝑗 0 0 0 0 0 0
subject to 𝑐𝑗 -𝑧𝑗 -2 1 -3 0 0
x1 + x2 + 2x3 + s1 =5 𝒄𝒋 -2 1 -3 0 0
2x1 + 3x2 + 4x3 + s2 = 12 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 RHS Ratio
& x1, x2, x3, s1, s2 ≥0
0 𝒔𝟏 1/3 0 2/3 1 -1/3 1
1 𝒙𝟐 2/3 1 4/3 0 1/3 4
X1=0, x2=4, x3=0, s1=1, s2=0
𝑧𝑗 2/3 1 4/3 0 1/3 4
Z*=-4 𝑐𝑗 -𝑧𝑗 -8/3 0 -13/3 0 -1/3

14-10-2023 Deepti Mohan | Goa Institute of Management

Formula to find the multiplier for pivot row to
produce a new row
• Find the pivot element p (this is the element at the intersection of the
column corresponding to the entering variable and the row
corresponding to the leaving variable).
• To get the new row corresponding to the pivot row, simply divide the
old pivot row by p.
• New row corresponding to pivot row = (1/p)* pivot row
• To get any other row j of the new table, do
New row j = old row j – k/p*pivot row
where k is the element in the old row j corresponding to the entering variable.

14-10-2023 Deepti Mohan | Goa Institute of Management

Example 1 𝒄𝒋 -4 -1 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 RHS Ratio

In this example, -4 𝒙𝟏 1 1/3 𝑘1 0 0 1 3

Pivot row = old row 2 0 𝑠1 0 5/3 𝑝 1 0 1 3/5
pivot element p=5/3 0 𝑠2 0 5/3 𝑘3 0 1 2 6/5

New row 2 = (1/p)* pivot row = (3/5) *pivot row 𝑧𝑗 -4 -4/3 0 0

𝒄𝒋𝑗
𝑐𝑗 -𝑧 0-4 -1
1/3 00 0
New row 1 = old row 1 – 𝑘1 /p * pivot row 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 RHS Ratio
𝑘1 /p=(1/3)/(5/3)=(1/5)
New row 1 = old row 1 – (1/5)* pivot row
-4 𝒙𝟏 0
New row 3 = old row 3 – 𝑘3 /p * pivot row
-1 𝒙𝟐 1
𝑘3 /p=(5/3)/(5/3)=1
New row 3 = old row 3 –pivot row 0 𝒔𝟐 0
𝑧𝑗
𝑐𝑗 -𝑧𝑗
14-10-2023 Deepti Mohan | Goa Institute of Management
Example 1 𝒄𝒋 -4 -1 0 0
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 RHS Ratio

In this example, -4 𝒙𝟏 1 1/3 𝑘1 0 0 1 3

Pivot row = old row 2 0 𝑠1 0 5/3 𝑝 1 0 1 3/5
pivot element p=5/3 0 𝑠2 0 5/3 𝑘3 0 1 2 6/5

New row 2 = (1/p)* pivot row = (3/5) *pivot row 𝑧𝑗

𝑐𝒄𝑗𝒋-𝑧𝑗 -4 -1 0 0
New row 1 = old row 1 – 𝑘1 /p * pivot row 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 RHS Ratio
𝑘1 /p=(1/3)/(5/3)=(1/5)
New row 1 = old row 1 – (1/5)* pivot row
-4 𝒙𝟏 1 0 -1/5 1 3/5
New row 3 = old row 3 – 𝑘3 /p * pivot row
-1 𝒙𝟐 0 1 3/5 0 3/5
𝑘3 /p=(5/3)/(5/3)=1
New row 3 = old row 3 –pivot row 0 𝒔𝟐 0 0 1 0 1
𝑧𝑗
𝑐𝑗 -𝑧𝑗
14-10-2023 Deepti Mohan | Goa Institute of Management
 𝒄𝒋 -4 -1 0 0 - -M
M

Example 2 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒖 𝒔 𝒂𝟏 𝒂𝟐 RHS Ratio

In this example, -M 𝒂𝟏 3 𝑝 1 0 0 1 0 3 1
Pivot row = old row 1 -M 𝒂𝟐 4 𝑘2 3 -1 0 0 1 6 1.5
pivot element p=3 0 𝒔 1 𝑘3 2 0 1 0 0 3 3
New row 1 = (1/p)* pivot row = (1/3) *pivot row

New row 2 = old row 2 – 𝑘2 /p * pivot row 𝒄𝒋 -4 -1 0 0 - -M

𝑘2 /p=(4)/(3)=(4/3) M
New row 2 = old row 2 – (4/3)* pivot row 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒖 𝒔 𝒂𝟏 𝒂𝟐 RHS Ratio

New row 3 = old row 3 – 𝑘3 /p * pivot row -4 𝒙𝟏 1

𝑘3 /p=(1)/(3)=1/3
New row 3 = old row 3 –(1/3)*pivot row -M 𝒂𝟐 0
0 𝒔 0

14-10-2023 Deepti Mohan | Goa Institute of Management

 𝒄𝒋 -4 -1 0 0 -M -M
𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒖 𝒔 𝒂𝟏 𝒂𝟐 RHS Ratio
Example 2 -M 𝒂𝟏 3 𝑝 1 0 0 1 0 3 1
In this example, -M 𝒂𝟐 4 𝑘2 3 -1 0 0 1 6 1.5
Pivot row = old row 1
0 𝒔 1 𝑘3 2 0 1 0 0 3 3
pivot element p=3

New row 1 = (1/p)* pivot row = (1/3) *pivot row

New row 2 = old row 2 – 𝑘2 /p * pivot row 𝒄𝒋 -4 -1 0 0 -M -M

𝑘2 /p=(4)/(3)=(4/3) 𝒄𝑩 𝒙𝑩 𝒙𝟏 𝒙𝟐 𝒖 𝒔 𝒂𝟏 𝒂𝟐 RHS Ratio
New row 2 = old row 2 – (4/3)* pivot row
-4 𝒙𝟏 1 1/3 0 0 1/3 0 1
New row 3 = old row 3 – 𝑘3 /p * pivot row
𝑘3 /p=(1)/(3)=1/3 -M 𝒂𝟐 0 5/3 -1 0 -4/3 1 2
New row 3 = old row 3 –(1/3)*pivot row 0 𝒔 0 5/3 0 1 -1/3 0 2

14-10-2023 Deepti Mohan | Goa Institute of Management

14-10-2023 Deepti Mohan | Goa Institute of Management