Operations Research

LECTURE 5
Simplex Method of
Linear Programming
Simplex Method of Linear Programming
Under 'graphical solutions' in linear programming (LP) the objective function obviously should have
not more than two decision variables. If the decision variables are more than two, the 'cartesian
plane' cannot accommodate them. Therefore, a most popular and widely used analysis called
'SIMPLEX METHOD', is used.
This method provides an algorithm (a procedure that is iterative) that is based on fundamental
theorems of linear programming. It helps in moving from one basic feasible solution to another in a
prescribed manner such that the value of the objective function is improved. This procedure of
jumping from one vertex to another vertex is repeated.

Slack Variables and Artificial Variables

In the simplex method for solving linear programming problems, slack variables and artificial
variables play important roles in transforming the problem into a standard form and guiding the
algorithm toward an optimal solution.

Slack Variables:
Slack variables are introduced to convert inequality constraints into equality constraints in the
standard form of a linear programming problem. They represent the surplus or slack in each
inequality constraint. A surplus slack variable is added for ‘greater than or equal to’ constraints,
while a deficit slack variable is added for ‘less than or equal to’ constraints.

Example:
Consider the following linear programming problem:
Maximize 𝑍 = 3𝑥! + 4𝑥"
Subject to
2𝑥! + 3𝑥" ≤ 6
4𝑥! + 2𝑥" ≥ 8
𝑥! ,𝑥" ≥ 0
To convert the inequality constraints to equality constraints, we introduce slack variables:
Let's define 𝑠! and 𝑠" as the slack variables for the first and second constraints, respectively.
The constraints become
2𝑥! + 3𝑥" + 𝑠! = 6
4𝑥! + 2𝑥" − 𝑠" = 8

Now the problem is in standard form with equality constraints.

2
Artificial Variables:
Artificial variables are introduced when solving linear programming problems using the simplex
method to handle situations where the initial basic feasible solution is not obvious. They help guide
the algorithm toward finding an initial feasible solution.
Example:
Consider the following linear programming problem:
Minimize 𝑍 = 2𝑥! + 3𝑥"
Subject to
3𝑥! + 2𝑥" ≤ 5
4𝑥! + 3𝑥" ≥ 6
𝑥! , 𝑥" ≥ 0

To convert the inequality constraints to equality constraints, we introduce artificial variables:

Let 𝑎! and 𝑎" be the artificial variables for the first and second constraints, respectively.
The constraints become
3𝑥! + 2𝑥" + 𝑎! = 5
4𝑥! + 3𝑥" − 𝑎" = 6

When we apply the simplex method, we treat the artificial variables as part of the initial basis. The
goal is to minimize the sum of artificial variables to achieve a feasible solution. Ideally, in the
process of optimizing the artificial variables, they will be reduced to zero, and we will be left with
the original problem.

Note: It's important to note that if any artificial variable remains non-zero in the optimal table, it
indicates that the original problem is infeasible.

Both slack and artificial variables are essential tools in transforming and solving linear
programming problems using the simplex method, ensuring that the algorithm can find optimal
solutions or detect infeasibility efficiently.

Steps to solve the Simplex Method:

1. Convert the inequalities into equalities by adding slack variables, surplus variables, or artificial
variables, as the case may be.

2. Identify the coefficient of equalities and put them into a matrix form AX = B. Where ‘A’
represents a matrix of coefficients, ‘X’ represents a vector of unknown quantities and B
represents a vector of constants, leading to AX = B [This is according to the system of
equations].

3
3. Tabulate the data into the first iteration of the Simplex method.

Basic 𝒄𝒃 𝒙𝒃 𝒚𝟏 𝒚𝟐 𝒔𝟏 𝒔𝟐 Minimum Ratio

(BV) 𝑿𝑩𝒊 /𝒀𝒊𝒋 ; 𝒀𝒊𝒋 > 0
Variable

S1
S2

𝑍)
𝐶)

𝑍) − 𝐶)

A. Cj is the coefficient of unknown quantities in the objective function.

𝑍) = 𝛴𝐶*+,+) (Multiples and additions of coefficients in the table, i.e., 𝐶*! × 𝑦!! + 𝐶*" × 𝑦!"

B. Identify the Key or Pivotal column with the minimum element of 𝑍) − 𝐶) denoted as 'KC'
throughout the problems in the lecture.

C. Find the 'Minimum Ratio' i.e., 𝑋*+ /𝑌+) .

D. Identify the key row with the minimum element in a minimum ratio column. The key row is
denoted as 'KP'.

E. Identify the key element at the intersecting point of the key column and key row, which is
put into a box throughout the problems in the lecture.

4. Reinstate the entries to the next iteration of the simplex method.

A. The pivotal row is to be adjusted by making the key element '1' and dividing the other
elements in the row by the same number.
B. The key column must be adjusted such that the other elements other than key elements
should be made zero.
C. The same multiple should be used for other elements in the row to adjust the rest of Notes
the elements. But, the adjusted key row elements should be used for deducting out from the
earlier iteration row.
D. The same iteration is continued until the values of 𝑍) − 𝐶) become either '0' or positive.

5. Find the 'Z' value given by 𝑐. , 𝑥. .

4
Finding an initial basic feasible solution
Finding an initial basic feasible solution is an essential step in solving linear programming problems
using the simplex method. An initial basic feasible solution serves as the starting point for the
iterative process of improving the objective function value by moving along the edges of the
feasible region.

There are a few methods to obtain an initial basic feasible solution, and I'll describe two
common approaches:
§ The corner point method and
§ The two-phase method

Corner Point method:

In this method, you identify a corner point (vertex) of the feasible region that satisfies all
constraints and serves as a basic feasible solution.
Steps:
1. Plot the constraints on a graph to visualize the feasible region.

2. Identify the vertices (corners) of this region.

3. Evaluate the objective function at each vertex.

4. Choose the vertex that maximizes (or minimizes) the objective function as the initial basic
feasible solution.

Example:
Consider the following linear programming problem:
Maximize 𝑍 = 3𝑥! + 5𝑥"
Subject to
2𝑥! + 𝑥" ≤ 10
𝑥! + 3𝑥" ≤ 18
𝑥! , 𝑥" ≥ 0

The feasible region is bounded by the intersection of the constraint lines. The vertices of this region
are (0, 0), (5, 0), (6, 2), and (0, 6). You can evaluate the objective function at each vertex to find the
optimal initial solution. In this case, the corner point (6, 2) maximizes the objective function, so (6, 2)
is the initial basic feasible solution.

5
Two-Phase method:
The two-phase method is used when it's difficult to identify a feasible solution immediately. It
involves adding artificial variables to create a feasible tableau, followed by optimizing the artificial
variables to eliminate them and get a feasible solution.
Steps:
5. Convert the inequalities to equalities by introducing slack or surplus variables.

6. Introduce artificial variables to create an auxiliary problem.

7. Optimize the artificial variables to obtain a feasible solution.

8. Once the artificial variables are eliminated, you'll have an initial basic feasible solution for
the original problem.

Example:
Consider the following linear programming problem:
Maximize 𝑍 = 4𝑥! + 3𝑥"
Subject to
3𝑥! + 2𝑥" ≤ 6
2𝑥! + 3𝑥" ≥ 9
𝑥! , 𝑥" ≥ 0
To create an initial feasible solution, introduce artificial variables:
3𝑥! + 2𝑥" + 𝑎! = 6
2𝑥! + 3𝑥" − 𝑎" = 9

Now, set the artificial variables 𝑎! and 𝑎" as basic variables and the others as non-basic variables.
Perform row operations to make the artificial variables equal to zero while minimizing their
coefficients. After optimizing, you will end up with a tableau that satisfies the original constraints
with a feasible solution.
Once you have an initial basic feasible solution, you can apply the simplex method iteratively to
improve the solution and find the optimal solution that maximizes (or minimizes) the objective
function.

Numerical Example 1:
Maximize Z = 5𝑥! + 3𝑥" (Subject to constraints)
𝑥! + 𝑥" ≤ 2
5𝑥! + 2𝑥" ≤ 10
3𝑥! + 8𝑥" ≤ 12
Where 𝑥! , 𝑥" ≥ 0 ( Non - negativity constraints)

6
Solution:
Step 1: Conversion of inequalities into equalities adding slack variable
𝑥! + 𝑥" + 𝑥/ = 2
5𝑥! + 2𝑥" + 𝑥0 = 10
3𝑥! + 8𝑥" + 𝑥1 = 12
Where, 𝑥/ , 𝑥0 and 𝑥1 are slack variables.

Step 2: Fit the data into the matrix form AX = B

Step 3: Fit the data into the first iteration of the Simplex method

BV 𝑪𝑩 𝑿𝑩 𝒀𝟏 𝒀𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑 Min. Ratio

𝑺𝟏 0 2 1 1 1 0 0 2/1=2(KR)

𝑺𝟐 0 10 5 2 0 1 0 10/5=2

𝑺𝟑 0 12 3 8 0 0 1 12/3=4

𝑍) 0 0
𝐶) 5 3

𝑍) − 𝐶) -5 -3

(↑KC)

Z = 𝑪𝑩 𝑿𝑩
= (𝟎 × 𝟐) + (𝟎 × 𝟏𝟎) + (𝟎 × 𝟏𝟐)
=0

7
Step 4: Fit the data into second iteration of Simplex method

BV 𝑪𝑩 𝑿𝑩 𝒀𝟏 𝒀𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑 Min. Ratio

𝒀𝟏 5 2/1=2 1/1=1 1/1=1 - - - -

𝑺𝟐 0 10-2(5) =0 5-1(5)=0 2-1(5)=-3 - - - -

𝑺𝟑 0 12-2(3)=6 3-1(3) = 8-1(3)=5 - - - -

0

𝑍) 5 5
𝐶) 5 3

𝑍) − 𝐶) 0 2

Z = 𝑪𝑩 𝑿𝑩
= (𝟓 × 𝟐) + (𝟎 × 𝟏𝟎) + (𝟎 × 𝟔)
= 10
Therefore, Maximum value of ‘Z’=10

Numerical Example 2:
Maximize Z = 2𝑥! + 3𝑥" (Subject to constraints)
𝑥! + 𝑥" ≤ 1
3𝑥! + 𝑥" ≤ 4
Where 𝑥! , 𝑥" ≥ 0 (Non - negativity constraints)

Solution 2:
Step 1: Conversion of inequalities into equalities by adding slack variables.
𝑥! + 𝑥" + 𝑥/ = 1
3𝑥! + 𝑥" + 𝑥0 = 4
Where, 𝑥/ , 𝑥0 are slack variables.

Step 2: Identify the coefficients

8
Step 3: First iteration of Simplex Method.

BV 𝑪𝑩 𝑿𝑩 𝒀𝟏 𝒀𝟐 𝑺𝟏 𝑺𝟐 Min. Ratio

𝑆! 0 1 1 1 1 0 1/1=1(KR)

𝑆" 0 4 3 1 0 1 4/1=4

𝑍) 0 0
𝐶) 2 3

𝑍) − 𝐶) -2 -3

(↑KC)
Z = 𝑪𝑩 𝑿𝑩
= (𝟎 + 𝟎 + 𝟎)
=0

Step 4: Second iteration of Simplex Method.

BV 𝑪𝑩 𝑿𝑩 𝒀𝟏 𝒀𝟐 𝑺𝟏 𝑺𝟐 Min. Ratio

𝑌! 3 1/1=1 1/1=1 1/1=1 - - -

𝑆" 0 4-1(1)=3 3-1(1)=2 1-1(1)=0 - - -

𝑍) 3 3
𝐶) 2 3

𝑍) − 𝐶) 1 0

Z = 𝑪𝑩 𝑿𝑩
= (𝟑 ∗ 𝟏) + (𝟎 ∗ 𝟑)
=3
Therefore, Maximum value of ‘Z’ = 3

9
Conclusion –
The simplex method, both for the minimization and the maximization LP problem, may be
summarized through a flow chart shown

Practice Questions:
Question 1:
Max Z = 3𝑥! + 2𝑥"
Subject to
𝑥! + 𝑥" ≤ 4
𝑥! − 𝑥" ≤ 2
And 𝑥! , 𝑥" ≥ 0

Question 2:
Max Z = 5𝑥! + 3𝑥"
Subject to
5𝑥! + 2𝑥" ≤ 10
3𝑥! + 8𝑥" ≤ 12
And 𝑥! , 𝑥" ≥ 0

10
Question 3:
Max Z = 3𝑥! + 2𝑥" + 5𝑥/
Subject to
𝑥! + 2𝑥" + 𝑥/ ≤ 430
3𝑥! + 2𝑥/ ≤ 460
𝑥! + 4𝑥/ ≤ 420
And 𝑥! , 𝑥" , 𝑥/ ≥ 0

Reference:
§ Hillier, F. S., & Lieberman, G. J. (2013). Introduction to operations research. New York, NY: McGraw-Hill.
§ Winston, W. L. (2014). Operations research: Applications and algorithms. Boston, MA: Cengage Learning.
§ Taha, H. A. (2016). Operations research: An introduction. Upper Saddle River, NJ: Pearson.

11