Operational Research I

(Simplex Method)

Dr B. E. Owusu

February 4, 2025
The Simplex Method

The use of the simplex method to solve an LP problem requires

that the problem be converted into its standard form. The standard
form of the LP problem should have the following characteristics:
1 All the constraints should be expressed as equations by adding
slack or surplus and/or artificial variables.
2 The right-hand side of each constraint should be made
non-negative (if not). This is done by multiplying both sides
of the resulting constraint by −1.
3 The objective function should be of the maximization type.

Dr B. E. Owusu Operational Research I

The standard form of the LP problem is expressed as:
Optimize (Max or Min)

Z = c1 x1 + c2 x2 + · · · + cn xn + 0s1 + 0s2 + · · · + 0sm

Subject to the linear constraints:

a11 x1 + a12 x2 + · · · + a1n xn + s1 = b1 ,

a21 x1 + a22 x2 + · · · + a2n xn + s2 = b2 ,
..
.
am1 x1 + am2 x2 + · · · + amn xn + sm = bm ,

and
x1 , x2 , . . . , xn , s1 , s2 , . . . , sm ≥ 0.

Dr B. E. Owusu Operational Research I

This standard form of the LP problem can also be expressed in the
compact form as follows:
Optimize (Max or Min)
n
X m
X
Z= cj xj + 0si
j=1 i=1

(Objective function)
Subject to the linear constraints:
n
X
aij xj + si = bi , i = 1, 2, . . . , m
j=1

(Constraints)
And
xj , si ≥ 0, for all i and j
(Non-negativity conditions)
Dr B. E. Owusu Operational Research I
Algorithm
Step 1: Formulation of the Mathematical Model

1 Formulate the LP model by converting inequalities into

equalities using slack or surplus variables.
2 Convert a minimization problem to maximization using:

Minimize Z = −Maximize Z ∗ where Z ∗ = −Z .

3 Ensure all bi values are positive; multiply constraints with

bi < 0 by −1 if needed.
4 Add slack, surplus, or artificial variables and assign them a
zero cost in the objective function.
5 Replace unrestricted variables with the difference of two
non-negative variables.

Dr B. E. Owusu Operational Research I

Step 2: Set Up the Initial Solution

Create the initial simplex table with all variables, constraints,

and the objective function.
Identify the identity matrix (slack variable columns) to
represent the initial basic solution.
Basic variables (xB ) are calculated using xB = B −1 b, where B
is the identity matrix.

Dr B. E. Owusu Operational Research I

 Basic Variables Variables
Coeff (cB ) B V (b = xB ) x1 x2 ··· xn s1 s
cB1 s1 xB1 = b1 a11 a12 ··· a1n 1
cB2 s2 xB2 = b2 a21 a22 ··· a2n 0
.. .. .. .. .. .. .. ..
. . . . . . . .
cBm sm xBm = bm am1 am2 ··· amn 0
Z = ΣcBi xBi z1 z2 ··· zn 0
cj − zj c1 − z1 c2 − z2 ··· cn − zn 0
Table: Initial Simplex Table

Dr B. E. Owusu Operational Research I

Step 3: Test for Optimality

Calculate cj − zj for all non-basic variables:

X
cj − zj = cj − (cB × aij ).

Optimality conditions:
If cj − zj ≤ 0 for all j: Solution is optimal.
If cj − zj > 0 but all elements in that column are ≤ 0: Solution
is unbounded.
If cj − zj > 0: Improvement is possible.

Dr B. E. Owusu Operational Research I

Step 4: Select the Pivot Column and Row

Pivot Column: Select the column with the largest cj − zj > 0.

bi
Pivot Row: Compute the ratio aij for all aij > 0 and choose
the row with the smallest ratio.
The intersection of the pivot row and column is the pivot
element.

Dr B. E. Owusu Operational Research I

Step 5: Perform Pivoting

Make the pivot element 1 by dividing the pivot row by the

pivot element.
Perform row operations to make all other elements in the
pivot column 0.

Dr B. E. Owusu Operational Research I

Step 6: Update the Table

Replace the leaving variable with the entering variable.

Recalculate cB , xB , and cj − zj .

Dr B. E. Owusu Operational Research I

Step 7: Repeat Until Optimality

Repeat steps 3–6 until all cj − zj ≤ 0.

Read the optimal solution from the final simplex table.

Dr B. E. Owusu Operational Research I

Key Terms

Basic Variables: Variables in the solution with non-zero

values.
Non-Basic Variables: Variables not in the solution (x = 0).
Degeneracy: Occurs when one or more basic variables have a
value of zero.

Dr B. E. Owusu Operational Research I

Example 1

Let x1 and x2 be the number of chairs and tables to be produced

by the manufacturer using available resources of timber and labor.
Maximize:
Z = 6x1 + 8x2
Subject to:
30x1 + 20x2 ≤ 300
5x1 + 10x2 ≤ 110
x1 ≥ 0, x2 ≥ 0

Dr B. E. Owusu Operational Research I

Introducing the slack variables s1 and s2 , the problem can be
restated as:
Maximize:
Z = 6x1 + 8x2 + 0s1 + 0s2
Subject to:
30x1 + 20x2 + s1 = 300
5x1 + 10x2 + s2 = 110
x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0
where x1 and x2 are the decision variables, and s1 and s2 are slack
variables.

Dr B. E. Owusu Operational Research I

It can be simplified in a tabular form as below:

CB Basis x1 x2 s1 s2 RHS
0 s1 30 20 1 0 300
0 s2 5 10 0 1 110
Cj 6 8 0 0
Zj
Cj - Zj

Dr B. E. Owusu Operational Research I

1 Maximization problems are used for profit, and minimization
problems are used for cost.
2 The CB column contains the contributions per unit for the
basic variables s1 and s2 . A zero indicates that the
contributions per unit are zero because no profits are made
from unused raw materials or labor.
3 The second column, the basis, contains the variables in the
solution that are used to determine the total contribution. In
the initial solution, no products are made.
4 The starting solution will have zero contribution towards profit
since no units of chairs or tables are manufactured. This is
represented in the CB-th row for the column under RHS.
5 Since no units are manufactured, the first solution is:

x1 = 0, x2 = 0, s1 = 300, s2 = 110

Dr B. E. Owusu Operational Research I

Table II

CB Basis x1 x2 s1 s2 RHS θ
0 s1 30 20 1 0 300 15
0 s2 5 10 0 1 110 11 →
Cj 6 8 0 0
Zj 0 0 0 0 0
Cj − Zj 6 8↑ 0 0

Dr B. E. Owusu Operational Research I

Table III

CB Basis x1x 2 s1 s2 RHS θ

0 s1 200 1 −2 80 4 →
1 1
8 x2 2 1 0 10 11 22
Cj 6 8 0 0
8
Zj 4 8 0 10 88
8
Cj − Z j 2 → 0 0 − 10

Dr B. E. Owusu Operational Research I

Table Final IV

CB Basis x1 x2 s1 s2 RHS
1 1
6 x1 1 0 20 − 10 4
1 3
8 x2 0 1 − 40 20 9
Cj 6 8 0 0
1 6
Zj 6 8 10 10 96
1 6
Cj − Z j 0 0 − 10 − 10

x1 = 4, x2 = 9

Objective function = 6x1 + 8x2 = 6(4) + 8(9) = 24 + 72 = 96

Dr B. E. Owusu Operational Research I

Example 2

Minimize:
Z = x1 − 3x2 + 3x3
Subject to:
3x1 − x2 + 2x3 ≤ 7,
2x1 + 4x2 ≥ −12,
−4x1 + 3x2 + 8x3 ≤ 10,
x1 , x2 , x3 ≥ 0.

Dr B. E. Owusu Operational Research I

Standard Form

Minimize:
Z = x1 − 3x2 + 3x3 + 0s1 + 0s2 + 0s3
Subject to:
3x1 − x2 + 2x3 + s1 = 7,
−2x1 − 4x2 + s2 = 12,
−4x1 + 3x2 + 8x3 + s3 = 10,
x1 , x2 , x3 , s1 , s2 , s3 ≥ 0.
The initial feasible solution is:

x1 = 0, x2 = 0, x3 = 0, s1 = 7, s2 = 12, s3 = 10.

Dr B. E. Owusu Operational Research I

Table I

Table: Simplex Tableau I: Initial Step

CB Basis x1 x2 x3 s1 s2 s3 RHS θi
0 s1 3 −1 2 1 0 0 7 −7
0 s2 −2 −4 0 0 1 0 12 −3
10
0 s3 −4 3 8 0 0 1 10 3 →
Cj 1 −3 3 0 0 0
Zj 0 0 0 0 0 0 0
Cj − Z j 1 −3 ↑ 3 0 0 0

Dr B. E. Owusu Operational Research I

Table II

Table: Simplex Tableau II

CB Basis x1 x2 x3 s1 s2 s3 RHS θi
5 14
0 s1 3 0 3 1 0 13 31
3
31
5→
0 s2 − 22
3 0 32
3 0 1 3 4 76
3
76
− 22
−3 x2 − 34 1 8
3 0 0 1
3
10
3 − 10
4
Cj 1 −3 3 0 0 0
Zj 4 −3 −8 0 0 0 −10
Cj − Zj −3 ↑ 0 8 0 0 1

Dr B. E. Owusu Operational Research I

Table III

Table: Simplex Tableau III: Final Step

CB Basis x1 x2 x3 s1 s2 s3 RHS θi
14 3 1 31
1 x1 1 0 5 5 0 5 5 −
86 22 34 434
0 s2 0 0 15 15 1 15 15 −
52 4 4 74
−3 x2 0 1 15 15 0 15 15 −
Cj 1 −3 3 0 0 0 −10
Zj 1 −3 − 525 − 59 0 − 35 − 43 5
67 9 3
Cj − Z j 0 0 5 5 0 5 − 38 5

Optimal solution is reached for Cj − Zj ≥ 0.

x1 = 31 74
5 , x2 = 15 , x3 = 0.  
31 74
Z = x1 − 3x2 + 3x3 = 5 −3 15 + 3(0) = − 43
5 .
Dr B. E. Owusu Operational Research I
Example 3
Maximize:
Z = 5x1 − 3x2
Subject to:
x1 + x2 ≤ 2,
5x1 + 2x2 ≤ 10,
3x1 + 8x2 ≤ 12,
x1 , x2 ≥ 0.
Maximize:
Z = 5x1 − 3x2 + 0s1 + 0s2 + 0s3
Subject to:
x1 + x2 + s1 = 2,
5x1 + 2x2 + s2 = 10,
3x1 + 8x2 + s3 = 12,
x1 , x2 , s1 , s2 , s3 ≥ 0.
The initial feasible solution is: Operational Research I
Dr B. E. Owusu
Table I

Ci Basis x1 x2 s1 s2 s3 RHS θi
0 s1 1 1 1 0 0 2 2→
0 s2 5 2 0 1 0 10 2
0 s3 3 8 0 0 1 12 4
Cj 5 3 0 0 0
Zj 0 0 0 0 0
Cj − Zj 5↑ 3 0 0 0
Table: Simplex Tableau I - Initial Step

Dr B. E. Owusu Operational Research I

Table II

Ci Basis x1 x2 s1 s2 s3 RHS
5 x1 1 1 1 0 0 2
0 s2 0 −3 −5 1 0 0
0 s3 0 5 −3 0 1 6
Cj 5 3 0 0 0
Zj 5 5 5 0 0 10
Cj − Zj 0 −2 −5 0 0
The optimal solution is reached for Cj − Zj ≤ 0:

x1 = 2, x2 = 0.

Z = 5x1 + 3x2 = 5(2) + 3(0) = 10.

Dr B. E. Owusu Operational Research I

Simplex Algorithm(Minimization Case)

In certain cases, it is difficult to obtain an initial basic feasible

solution of the given LP problem. Such cases arise:
(i.) when the constraints are of the leq type,
n
X
aij Xj ≤ bi , Xj ≥ 0 (1)
j=1

and value of few right-hand side constants is negative [i.e.

bi < 0]. After adding the non-negative slack variable
si (i = 1, 2, · · · , m), the initial solution so obtained will be
si = −bi for a particular resource, i. This solution is not
feasible because it does not satisfy non-negativity conditions
of slack variables (i.e. si ≥ 0).

Dr B. E. Owusu Operational Research I

(ii.) when the constraints are of the ≥ type,
n
X
aij Xj ≥ bi , Xj ≥ 0 (2)
j=1

After adding surplus (negative slack) variable si , the initial

solution so obtained will be −si = bi or si = −bi
n
X
aij Xj − si = bi , Xj ≥ 0, si ≥ 0 (3)
j=1

This solution is not feasible because it does not satisfy

non-negativity conditions of surplus variables (i.e. si ≥ 0). In such
a case, artificial variables, Ai (i = 1, 2, · · · , m) are added to get an
initial basic feasible solution.

Dr B. E. Owusu Operational Research I

The resulting system of equations then becomes:
n
X
aij Xj − si + Ai = bi , Xj , si , Ai ≥ 0, i = 1, 2, · · · , m (4)
j=1

These are m simultaneous equations with (n + m + m)

variables (n decision variables, m artificial variables and m
surplus variables). An initial basic feasible solution of LP
problem with such constraints can be obtained by equating
(n + 2m − m) = (n + m) variables equal to zero.
Thus the new solution to the given LP problem is:
Ai = bi (i = 1, 2, · · · , m), which is not the solution to the
original system of equations because the two systems of
equations are not equivalent. Thus, to get back to the original
problem, artificial variables must be removed from the optimal
solution.

Dr B. E. Owusu Operational Research I

Two-Phase Method

In the first phase of this method, the sum of the artificial

variables is minimized subject to the given constraints in order
to get a basic feasible solution of the LP problem.
The second phase minimizes the original objective function
starting with the basic feasible solution obtained at the end of
the first phase.
Since the solution of the LP problem is completed in two
phases, this method is called the two-phase method.

Dr B. E. Owusu Operational Research I

Steps: Phase I

1 (a) If all the constraints in the given LP problem are ‘less than
or equal to’ (≤)) type, then Phase II can be directly used to
solve the problem. Otherwise, the necessary number of
surplus and artificial variables are added to convert constraints
into equality constraints (b) ) If the given LP problem is of
minimization, then convert it to the maximization type by the
usual method.
2 Assign zero coefficient to each of the decision variables (xj )
and to the surplus variables; and assign - 1 coefficient to each
of the artificial variables. This yields the following auxiliary LP
problem.
m
∗
X
MazimizeZ = (−1)Ai (5)
i=1

Dr B. E. Owusu Operational Research I

subject to the constraints

m
X
aij xj + Ai = bi , i = 1, 2, · · · , m
i=1

and

xj , Aj ≥ 0

3 Apply the simplex algorithm to solve this auxiliary LP

problem. The following three cases may arise at optimality:

Dr B. E. Owusu Operational Research I

(a) Max Z ∗ = 0 and at least one artificial variable is present in
the basis with positive value. This means that no feasible
solution exists for the original LP problem.
(b) Max Z ∗ = 0 and no artificial variable is present in the basis.
This means that only decision variables (xj′ s) are present in
the basis and hence proceed to Phase II to obtain an optimal
basic feasible solution on the original LP problem.
(c) Max Z ∗ = 0 and at least one artificial variable is present in
the basis at zero value. This means that a feasible solution to
the auxiliary LP problem is also a feasible solution to the
original LP problem. In order to arrive at the basic feasible
solution, proceed directly to Phase II or else eliminate the
artificial basic variable and then proceed to Phase II.

Dr B. E. Owusu Operational Research I

Phase II

4 Assign actual coefficients to the variables in the objective

function and zero coefficient to the artificial variables which
appear at zero value in the basis at the end of Phase I. The
last simplex table of Phase I can be used as the initial simplex
table for Phase II. Then apply the usual simplex algorithm to
the modified simplex table in order to get the optimal solution
to the original problem. Artificial variables that do not appear
in the basis may be removed.

Dr B. E. Owusu Operational Research I

Example

Use the two-phase simplex method to solve the following LP

problem:
Minimize
Z = x1 + x2
Subject to the constraints

2x1 + x2 ≥ 4,
x1 + 7x2 ≥ 7,
x1 , x2 ≥ 0.

Dr B. E. Owusu Operational Research I

Solution

Converting the given LP problem objective function into the

maximization form and then adding surplus variables s1 and s2 and
artificial variables A1 and A2 in the constraints, the problem
becomes:
Maximize
Z ∗ = −x1 − x2
Subject to the constraints

2x1 + x2 − s1 + A1 = 4,
x1 + 7x2 − s2 + A2 = 7,
x1 , x2 , s1 , s2 , A1 , A2 ≥ 0.

where Z ∗ = −Z .

Dr B. E. Owusu Operational Research I

Phase I: This phase starts by considering the following auxiliary
LP problem:
Maximize
Z ∗ = −A1 − A2
Subject to the constraints

2x1 + x2 − s1 + A1 = 4,
x1 + 7x2 − s2 + A2 = 7,
x1 , x2 , s1 , s2 , A1 , A2 ≥ 0.

Dr B. E. Owusu Operational Research I

 Basic Coefficient Basic x1 x2 s1 s2 A1 A2 RHS(b)
Variables (cB ) (B)
A1 −1 A1 2 1 −1 0 1 0 4
A2 −1 A2 1 7 0 −1 0 1 7
Cj 0 0 0 0 −1 −1
Z∗ −3 −8 1 1 −1 −1 −11
zj −3 −8 1 1 −1 −1
cj − zj 3 8 −1 −1 0 0

Dr B. E. Owusu Operational Research I

 Basic Coeff(cB ) Basic x1 x2 s1 s2 A1 A2 RHS(b)
Variables (B)
13
A1 −1 A1 7 0 −1 17 1 − 71 3
1
x2 0 x2 7 1 0 − 71 0 1
7 1
Cj 0 0 0 0 −1 −1
Z∗ − 137 0 1 − 71 −1 17 −3
zj − 137 0 1 − 71 −1 17
13
cj − zj 7 0 −1 17 0 − 78

Dr B. E. Owusu Operational Research I

 cB B x1 x2 s1 s2 A∗1 A∗2 Value
0 s2 13 0 -7 1 7 -1 21
0 x2 2 1 -1 0 1 0 4
Cj 0 0 0 0 -1 -1
z∗ = 0 0 0 0 0 -1 -1 0
cj − zj 0 0 0 0 -1 -1

Dr B. E. Owusu Operational Research I

Phase II

Cb β x1 x2 s1 s2 RHS θ
21
0 s2 13 0 -7 1 21 13
4
-1 x2 2 1 -1 0 4 2
Cj -1 -1 0 0
Zj -2 -1 1 0 -2
cj − zj 1 0 -1 0

Dr B. E. Owusu Operational Research I

 Cb β x1 x2 s1 s2 RHS
7 1 21
0 x1 1 0 − 13 13 13
1 2 10
-1 x2 0 1 13 − 13 13
Cj -1 -1 0 0
6 1
Zj -1 -1 13 13 − 31
13
6 1
cj − zj 0 0 − 13 − 13

Dr B. E. Owusu Operational Research I