OPERATION RESEARCH
ME354
OPERATION RESEARCH
Lecture -8
Solving a Simplex Method
NITK , Surathkal
OPERATION RESEARCH Linear Programming
Step 1. Formulation
Step 2. Solution
✓ Graphical solution
✓ Simplex Method
✓ Big M Method
✓ Dual Simplex Method
✓ Two Phase model
NITK , Surathkal
OPERATION RESEARCH Simplex Method
➢ An Overview of the Simplex Method
➢ Standard Form
➢ Tableau Form
➢ Setting Up the Initial Simplex Tableau
➢ Improving the Solution
➢ Calculating the Next Tableau
➢ Solving a Maximization/Minimization Problem
➢ Special Cases NITK , Surathkal
OPERATION RESEARCH Simplex Method
➢ Simplex method is an iterative procedure for solving LPP in a finite
number of steps.
➢ This method provides an algorithm which consists of moving from one
vertex of the region of feasible solution to another
➢ Simplex method is a popular algorithm for linear programming
➢ The name of the algorithm is derived from the concept of a simplex and
was suggested by T. S. Motzkin.
NITK , Surathkal
OPERATION RESEARCH Standard Form of LPP
NITK , Surathkal
OPERATION RESEARCH Slack and Surplus Variables
NITK , Surathkal
OPERATION RESEARCH Slack and Surplus Variables
NITK , Surathkal
OPERATION RESEARCH Slack and Surplus Variables
NITK , Surathkal
OPERATION RESEARCH Slack and Surplus Variables
NITK , Surathkal
OPERATION RESEARCH
Slack and surplus variables
Before the simplex algorithm can be used to solve a linear program, the problem
must be written in standard form.
a. Constraints of type (≤) : for each constraint i of this type, we add a slack
variable ei, such that ei is nonnegative.
Example: 3x1+2x2 ≤ 2 translates into 3x1+2x2+ S1 = 2 , S1 ≥ 0
b. Constraints of type (≥) : for each constraint i of this type, we add a surplus
variable ei, such that ei is nonnegative.
Example: 3x1+2x2 ≥ 2 translates into 3x1+2x2- S2 = 2 , S2 ≥ 0
NITK , Surathkal
OPERATION RESEARCH Basic and non‐basic variables
Consider a system of equations with n variables and m equations where n ≥ m
A basic solution for this system is obtained in the following way:
a) Set n-m variables equal to zero. These variables are called non‐basic variables
(N.B.V).
b) Solve the system for the m remaining variables. These variables are called basic
variables (B.V.)
c) The vector of variables obtained is called the basic solution (it contains both
basic and non‐basic variables).
NITK , Surathkal
OPERATION RESEARCH Examples
NITK , Surathkal
OPERATION RESEARCH Terminologies
NITK , Surathkal
OPERATION RESEARCH
How does Simplex Method Works
NITK , Surathkal
OPERATION RESEARCH
How does Simplex Method Works
NITK , Surathkal
OPERATION RESEARCH How does Simplex Method
Works
NITK , Surathkal
OPERATION RESEARCH Overview of the Simplex Method
➢ Steps Leading to the Simplex Method
Formulate Put In Put In Execute
Problem Standard Tableau Simplex
as LP Form Form Method
NITK , Surathkal
OPERATION RESEARCH Simplex Method-Procedure
➢ Step 1: Check whether the objective function of the given LPP is to be
maximized or minimized.
➢ If it is to be minimized then we convert it into a problem of
maximization by, Min Z = –Max (–Z)
➢ Step 2: Check whether all bi (i = 1, 2, …, m) are positive.
➢ If any one of bi is negative, then multiply the inequation of the
constraint by –1 so as to get all bi to be positive.
NITK , Surathkal
OPERATION RESEARCH Simplex Method
➢ Step 3: Express the problem in the standard form by introducing slack/surplus
variables to convert the inequality constraints into equations.
➢ Step 4: Obtain an initial basic feasible solution to the problem in the form
XB = B–1b and put it in the first column of the simplex table.
➢ Form the initial simplex table shown as follows:
NITK , Surathkal
OPERATION RESEARCH Simplex Method
➢ Step 5: Compute the net evaluations Zj – Cj by using the relation:
Zj – Cj = CB (aj – Cj)
➢ Examine the sign of Zj – Cj: Maximization Problem
(i) If all Zj – Cj ≤ 0, then the initial basic feasible solution XB is an optimum basic
feasible solution.
(ii) If at least one Zj – Cj > 0, then proceed to the next step as the solution is not
optimal.
NITK , Surathkal
OPERATION RESEARCH Simplex Method
➢ Step 6: To find the entering variable, i.e., key column.
➢ Step 7: To find the leaving variable or key row
➢ Step 8: Form a new basis by dropping the leaving variable and introducing the
entering variable along with the associated value under CB column.
➢ The leaving element is converted to unity by dividing the key equation by the
key element and all other elements in its column to zero by using the formula:
➢ Step 9: Repeat the procedure of Step (5) until either an optimum solution is
obtained or there is an indication of unbounded solution. NITK , Surathkal
Simplex Method -Steps
OPERATION RESEARCH
➢ Step 1: Standard Form.
➢ Step 2: Determine Slack Variables.
➢ Step 3: Setting up the Tableau.
➢ Step 4: Check Optimality.
➢ Step 5: Identify Pivot Variable.
➢ Step 6: Create the New Tableau. NITK , Surathkal
OPERATION RESEARCH Standard Form
NITK , Surathkal
Simplex Method -Steps
OPERATION RESEARCH
➢ Step 1: Standard Form.
➢ Step 2: Determine Slack Variables.
➢ Step 3: Setting up the Tableau.
➢ Step 4: Check Optimality.
➢ Step 5: Identify Pivot Variable.
➢ Step 6: Create the New Tableau. NITK , Surathkal
OPERATION RESEARCH
Setting up the Tableau
NITK , Surathkal
OPERATION RESEARCH
Setting up the Tableau
The green frame
corresponds to ZJ:
The pink frames
correspond to the
The blue frame corresponds to the constraints of (LP=). coefficients Cj
The grey frame corresponds to the value of the basic variables
The Red frame corresponds to the value of Z, i.e. the value of the objective function,
calculated as follows
NITK , Surathkal
Simplex Method -Steps
OPERATION RESEARCH
➢ Step 1: Standard Form.
➢ Step 2: Determine Slack Variables.
➢ Step 3: Setting up the Tableau.
➢ Step 4: Check Optimality.
➢ Step 5: Identify Pivot Variable.
➢ Step 6: Create the New Tableau. NITK , Surathkal
OPERATION RESEARCH
Check Optimality
➢ We stop when we reach the optimality criterion.
➢ The simplex algorithm stops when:
NITK , Surathkal
Simplex Method -Steps
OPERATION RESEARCH
➢ Step 1: Standard Form.
➢ Step 2: Determine Slack Variables.
➢ Step 3: Setting up the Tableau.
➢ Step 4: Check Optimality.
➢ Step 5: Identify Pivot Variable.
➢ Step 6: Create the New Tableau. NITK , Surathkal
