M C S D 11 3 3 O p e r a t i o n s R e s e a r c h & O p t i m i z a t i o n

CHAPTER 3:
SIMPLEX METHOD

nzah@utm.my-20232024(S1)

UTM JOHOR BAHRU

Introduction
The Simplex Method

§ The graphical method of solving linear programming problems is useful only for
problems involving two decision variables and relatively few problem constraints.
§ What happens when we need more decision variables and more problem
constraints?
§ We use an algebraic method called the simplex method, which was developed by
George B. DANTZIG (1914-2005) in 1947 while on assignment with the U.S. Department
of the air force.

2
Standard Maximization Problems in Standard Form

A linear programming problem is said to be a standard maximization problem in

standard form if its mathematical model is of the following form:
Maximize Z= 4X1 + 6X2 + 2X3
Subject to:
2X1 + 5x2 < 6
X1+ 9X2 - 7X3 < 8
4X1 - 10X2 + 2X3 > 3
X1 > 0, X2 > 0

3
 Slack Variable

§ A mathematical representation of surplus resources.” In real life

problems, it’s unlikely that all resources will be used completely, so
there usually are unused resources.
§ Slack variables represent the unused resources between the left-hand
side and right-hand side of each inequality.

4
 Slack Variable

§ The difference between the Right-Hand Side (R.H.S) and Left-Hand Side (L.H.S) of the (inequality ≤)
constraint thus yields the unused or slack amount of the resource.
R.H.S - L.H.S = slack or unused amount
§ To convert the (inequality ≤) to an equation (=), a non-negative slack variable is added to the
left-hand side of the constraint.
§ Example of Reddy Mikks model:
Constraint of raw material M1,
(L.H.S) 6X1 + 4X2 ≤ 24 (R.H.S)
Let, S1 be the slack or unused amount of raw material M1,
(L.H.S) 6X1 + 4X2 + S1 = 24 (R.H.S)
.: S1 ≥ 0 (non-negative slack variable)
or 24 - (6X1 + 4X2 ) = S1

5
 Surplus Variable

§ The difference between the Left-Hand Side (L.H.S) and Right-Hand Side (R.H.S) of the (inequality ≥)
constraint thus yields the surplus or extra amount of the resource.
L.H.S - R.H.S = surplus or extra amount
§ To convert the (inequality ≥) to an equation (=), a non-negative surplus variable is subtracted from
the left-hand side of the constraint.
§ Example:
(L.H.S) 5X1 + 7X2 ≥ 30 (R.H.S)
Let, S2 be the surplus or extra amount,
(L.H.S) 5X1 + 7X2 - S2 = 30 (R.H.S)
.: S2 ≥ 0 (non-negative surplus variable)
or (5X1 + 7X2 )- 30 = S2

6
Basic and Non-basic Variables

§ Basic variables are selected arbitrarily with the restriction that there be as many basic
variables as there are equations. The remaining variables are non-basic variables.
𝑥! + 2𝑥" + 𝑠! = 32
3𝑥! + 4𝑥" + 𝑠" = 84
§ This system has two equations, we can select any two of the four variables as basic
variables. The remaining two variables are then non-basic variables.
§ A solution found by setting the two non-basic variables equal to 0 and solving for the
two basic variables is a basic solution. If a basic solution has no negative values, it is a
basic feasible solution.
8
Steps to Solve LP problem using Simplex Method
To solve a linear programming problem in standard form, use the following steps.
1) Convert each inequality in the set of constraints to an equation by adding slack variables.
2) Create the initial simplex tableau.
3) Select the pivot column. (The column with the “most negative value” element in the last row.)
4) Select the pivot row. (The row with the smallest non-negative result when the last element in the row is
divided by the corresponding in the pivot column.)
5) Use elementary row operations calculate new values for the pivot row so that the pivot is 1 (Divide every
number in the row by the pivot number.)
6) Use elementary row operations to make all numbers in the pivot column equal to 0 except for the pivot
number. If all entries in the bottom row are zero or positive, this the final tableau. If not, go back to step 3.
7) If you obtain a final tableau, then the linear programming problem has a maximum solution, which is given
by the entry in the lower-right corner of the tableau.

9
 Pivot

Pivot Column: The column of the tableau representing the variable to be entered
into the solution mix.

Pivot Row: The row of the tableau representing the variable to be replaced in the
solution mix.

Pivot Number: The element in both the pivot column and the pivot row.

10
 Simplex Tableau

§ Most real-world problems are too complex to solve graphically. They have too many
corners to evaluate, and the algebraic solutions are lengthy.

§ A simplex tableau is a way to systematically evaluate variable mixes in order to find

the best one.

11
Simplex Tableau

Initial Simplex Tableau

All Variables Solution

Basic Variables Coefficients

12
 Example

The Cannon Hill furniture Company produces tables and chairs. Each table takes four
hours of labour from the carpentry department and two hours of labour from the
finishing department. Each chair requires three hours of carpentry and one hour of
finishing. During the current week, 240 hours of carpentry time are available and 100
hours of finishing time. Each table produced gives a profit of $70 and each chair a profit
of $50. How many chairs and tables should be made?

13
Example - Solution

Informations

Resource Tables (𝑋! ) Chairs (𝑋" ) Constraints

Carpentry (hr) 4 3 240

Finishing (hr) 2 1 100
Unit Profit $70 $50

Maximize Z= 70X1 + 50X2

Subject to:
4X1 + 3X2 < 240
2X1+ X2 < 100
X1 > 0, X2 > 0

14
 Example - Solution

§ The 1st step of the simplex method requires that each inequality be converted into an
equation.
§ The ”less than or equal to” inequalities are converted to equations by including slack
variables.
§ Suppose carpentry hours and finishing hours remain unused in a week.
§ The constraints become;
4𝑋1 + 3 𝑋2 + 𝑆! = 240 𝑜𝑟 4𝑋1 + 3 𝑋2 + 𝑆! + 0𝑆" = 240
2𝑋1 + 𝑋2 + 𝑆" = 100 𝑜𝑟 2𝑋1 + 𝑋2 + 0𝑆! + 𝑆" = 100
§ As unused hours result in no profit, the slack variables can be included in the objective
function with zero coefficients:
Z = 70𝑋1 + 50𝑋2 + 0𝑆! + 0𝑆"
Z − 70𝑋1 − 50𝑋2 − 0𝑆! − 0𝑆" = 0
15
 Example - Solution

The problem can now be considered as solving a system of 3 linear equations involving
the 5 variables; 𝑋1, 𝑋2, 𝑆1, 𝑆2, Z in such a way that Z has the maximum value;

4𝑋1 + 3 𝑋2 + 𝑆! + 0𝑆" = 240

2𝑋1 + 𝑋2 + 0𝑆! + 𝑆" = 100
Z − 70𝑋1 − 50𝑋2 − 0𝑆! − 0𝑆" = 0
Now, the system of linear equations can be written in matrix form or as a 3x6
augmented matrix.

16
 Example - Solution

§ The 2nd step:

Basic Right-Hand
𝑋! 𝑋" 𝑆! 𝑆" Z
Variables Side

𝑆! 4 3 1 0 0 240
𝑆" 2 1 0 1 0 100
Z -70 -50 0 0 1 0

The tableau represents the initial solution:

𝑋1 = 0; 𝑋2 = 0; 𝑆! = 240; 𝑆" = 100; 𝑍 = 0

The slack variables 𝑆! and 𝑆" form the initial solution mix. The initial solution assumes that all available hours
are unused. i.e. The slack variables take the largest possible values.

17
 Example - Solution

§ Variables in the solution mix are called basic variables.

§ Each basic variables has a column consisting of all 0’s except for a single 1.
§ All variables not in the solution mix take the value 0.
§ The simplex process, a basic variable in the solution mix is replaced by another variable
previously not in the solution mix.
§ The value of the replaced variable is set to 0.

18
 Example - Solution
§ The 3rd step:
Select the pivot column (determine which variable to enter the solution mix). Choose the
column with the “most negative” element in the objective function row.

Right-Hand
Basic 𝑋! 𝑋" 𝑆! 𝑆" Z
Side
Variables
𝑆! 4 3 1 0 0 240
𝑆" 2 1 0 1 0 100
Z -70 -50 0 0 1 0

Pivot Column
§ X1 should enter the solution mix because each unit of X1 (a table) contributes a profit of
$70 compared with only $50 for each unit of X1 (a chair).

19
 Example - Solution
§ The 4th step:
Select the pivot row (determine which variable to replace in the solution mix). The pivot
row is the row with the smallest non-negative result. Divide the last element in each row by
the corresponding element in the pivot column.
Enter
Right-Hand
Basic 𝑋! 𝑋" 𝑆! 𝑆" Z
Side
Variables
𝑆! 4 3 1 0 0 (240/4) = 60
Exit 𝑆" 2 1 0 1 0 (100/2) = 50
Z -70 -50 0 0 1 0

Pivot Row
Pivot Number Pivot Column

20
 Example - Solution
S2 should be replaced by X1 in the solution mix. 60 tables can be made with 240 unused
carpentry hours but only 50 tables can be made with 100 finishing hours. Therefore, we
decide to make 50 tables. Now calculate new values for the pivot row. Divide every
number in the row by the pivot number.

Right-Hand
Basic 𝑋! 𝑋" 𝑆! 𝑆" Z
Side
Variables
𝑆! 4 3 1 0 0 60
𝑋! 1 1/2 0 1/2 0 50
Z -70 -50 0 0 1 0

21
Example - Solution
Use row operations to make all numbers in the pivot column equal to 0 except
for the pivot number which remains as 1.

Basic 𝑋! 𝑋" 𝑆! 𝑆" Z Right-Hand Side

Variables
𝑆! 0 1 1 -2 0 40 −4×𝑅" + 𝑅!
𝑋! 1 1/2 0 1/2 0 50
Z 0 -15 0 35 1 3500 70×𝑅" + 𝑅&

If 50 tables are made, then the unused carpentry hours are reduced by 200 hours
(4 h/table multiplied by 50 tables); the value changes from 240 hours to 40 hours.
Making 50 tables results in the profit being increased by $3500; the value changes from $0
to $3500.

22
Example - Solution
Now repeat the steps until there are no negative numbers in the last row.
Select the new pivot column. X2 should enter the solution mix.
Select the new pivot row. S1 should be replaced by X2 in the solution mix.
Enter

Basic 𝑋! 𝑋" 𝑆! 𝑆" Z Right-Hand Side

Variables
Exit 𝑆! 0 1 1 -2 0 40
𝑋! 1 1/2 0 1/2 0 50
Z 0 -15 0 35 1 3500
Pivot Row
New Pivot Column

Pivot Number

23
Example - Solution
Calculate new values for the pivot row. As the pivot number is already 1,
there is no need to calculate new values for the pivot row.
Use row operations to make all numbers in the pivot column equal to
except for the pivot number.

Basic 𝑋! 𝑋" 𝑆! 𝑆" Z Right-Hand Side

Variables
𝑋" 0 1 1 -2 0 40
1
𝑋! 1 0 -1/2 3/2 0 30 − ×𝑅! + 𝑅"
2
Z 0 0 15 5 1 4100 15×𝑅! + 𝑅&

If 40 chairs are made, then the number of tables are reduced by 20 tables (1/2 table/chair
multiplied by 40 chairs); the value changes from 50 tables to 30 tables. The replacement of 20
tables by 40 chairs results in the profit being increased by $600; the value changes from $3500 to
$4100.

24
Example - Solution
Result:

As the last row contains no negative numbers, this solution gives the maximum value of Z.
This simplex tableau represents the optimal solution to the LP problem and is interpreted
as:
𝑋1 = 30 𝑇𝑎𝑏𝑙𝑒𝑠 ; 𝑋2 = 40(𝐶ℎ𝑎𝑖𝑟𝑠); 𝑆! = 0; 𝑆" = 0; Z = $4100 (Profit)

25
Exercise
A farmer owns a 100-acre farm and plans to plant at most three crops. The seed for
crops A, B, and C costs $40, $20, and $30 per acre, respectively. A maximum of $3200
can be spent on seed. Crops A, B, and C require 1, 2, and 1 workdays per acre,
respectively, and there are maximum of 160 workdays available. If the farmer can
make a profit of $100 per acre on crop A, $300 per acre on crop B, and $200 per acre
on crop C, how many acres of each crop should be planted to maximize profit?

26