1

Simplex Method
The simplex method attempts to move from one Basic Feasible Solution to
a better Basic Feasible Solution until the optimum is found.

Problem Example
A Company manufactures three products A, B, and C using three resources,
R1, R2, and R3. The following table gives the availability of the resources, their
usage by the three products, and the profits per unit.
Resource requirements per unit
Resource A B C Availability
R1 2 1 3 42
R2 2 1 2 40
R3 1 .5 1 45
profits per unit 24 22 45
a. Formulate the problem as a linear program
b. Find the optimum solution using simplex method
c. From the optimum solution determine the status of each resource.
 2

Solution
a. Formulate the problem as a linear program
Decision variables (Unknowns):
𝒙𝟏 = Number of units of product 𝐴
𝒙𝟐 = Number of units of product 𝐵
𝒙𝟑 = Number of units of product 𝐶
The complete model is
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 24𝑥1 + 22𝑥2 + 45𝑥3
Subject to
− Resource R1: 2𝑥1 + 𝑥2 + 3𝑥3 ≤ 42
− Resource R2: 2𝑥1 + 𝑥2 + 2𝑥3 ≤ 40
1
− Resource R3: 𝑥1 + 𝑥2 + 𝑥3 ≤ 45
2

𝑥1 , 𝑥2 , 𝑥3 ≥ 0
b. Find the optimum solution using simplex method
Step 1: Converting inequalities into equations with nonnegative right-hand side
• In (≤) constraints,
− The right-hand side represents the limit on the availability of a resource
− The left-hand side represents the usage of this limited resource by the activities
(variables) of the model.
− The difference between the right-hand side and the left-hand side of the (≤)
constraint thus yields the unused or slack amount of the resource.
• To convert a (≤)-inequality to an equation, a nonnegative slack variable is added
to the left-hand side of the constraint.
• In our example, the constraint associated with the use of resource R1 is given as:
2𝑥1 + 𝑥2 + 3𝑥3 ≤ 42
• Defining 𝑠1 as the slack or unused amount of R1, the constraint can be converted
to the following equation:
2𝑥1 + 𝑥2 + 3𝑥3 + 𝑠1 = 42
 3

Thus, the constraints are expressed in equation form as:

− Resource R1: 2𝑥1 + 𝑥2 + 3𝑥3 + 𝑠1 = 42
− Resource R2: 2𝑥1 + 𝑥2 + 2𝑥3 + 𝑠2 = 40
1
− Resource R3: 𝑥1 + 𝑥2 + 𝑥3 + 𝑠3 = 45
2

𝑥1 , 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
Step 2: Converting objective function into objective equation
𝑧 = 24𝑥1 + 22𝑥2 + 45𝑥3
𝑧 − 24𝑥1 − 22𝑥2 − 45𝑥3 = 0
Step 3: Prepare starting simplex table (starting basic feasible solution)
The starting simplex table can be represented as follows:

All model variables Objective equation coefficients

Basic 𝒛 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 Solution

Basic variables
𝒛 1 −24 −22 −45 0 0 0 0 𝑧 row

𝒔𝟏 0 2 1 3 1 0 0 42 𝑠1 row

𝒔𝟐 0 2 1 2 0 1 0 40 𝑠2 row
1
𝒔𝟑 0 1 2
1 0 0 1 45 𝑠3 row

Unit columns Right-hand-side values

Constraints coefficients

Note that:
− Basic variables are listed in the leftmost Basic column and their values in the
rightmost Solution column
− Nonbasic variables (those not listed in the Basic column) always equal zero.
− Basic variables that listed in the Basic column must have a unit column (column
with intersection element equals one, and all other elements equal zero)
 4

The design of the table specifies the set of basic and nonbasic variables as well as
provides the solution associated with the starting iteration as follows:

Basic variables Nonbasic (zero) variables

𝒔𝟏 = 42 units 𝒙𝟏 = 0 units

𝒔𝟐 = 40 units 𝒙𝟐 = 0 units

𝒔𝟑 = 45 units 𝒙𝟑 = 0 units

𝒛 = $0

Note that:
− The solution is considered a Basic Feasible Solution if it satisfies two requirements:
1. In a set of 𝒎 equations and 𝒏 variables (𝒎 < 𝒏), and we set 𝒏 − 𝒎 variables
equal to zero, the remaining variables must have a unit column.
2. All variables have nonnegative values.
Regarding our example, in the previous starting simplex table, this table represents a
Basic Feasible Solution because:
1. We have a set of 𝟑 equations (𝑅1, 𝑅2, 𝑅3) and 6 variables 𝑥1 , 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 and
we set 𝟑 variables (𝟔 − 𝟑) equal to zero (Nonbasic variables) 𝑥1 , 𝑥2 , 𝑥3 , the
remaining variables (Basic variables) 𝑠1 , 𝑠2 , 𝑠3 have a unit column
2. All variables have nonnegative values
− The maximum number of Basic Solutions is:
𝑛
𝑛!
𝐶𝑚 =
𝑚! × (𝑛 − 𝑚)!
Regarding our example, we have a set of 𝟑 equations (𝒎) and 6 variables (𝒏). Thus,
the maximum number of Basic Solutions is:
6!
𝐶36 =
3! × (6 − 3)!
6! 6×5×4×3×2×1
= = = 20
3! × 3! 3 × 2 × 1 × 3 × 2 × 1
 5

Step 4: Optimality test

• In the maximization models,
𝑧 − row

Does not include negative coefficients includes negative coefficients

The solution is the optimum The solution is not the optimum

Stop Improve solution (Step 5)

• Regarding our example, z-row includes negative coefficients (−24, −22, −45),
thus, the optimum solution is not reached at this iteration, and there is possibility
for improvement
Step 5: Improve solution
A. Select an entering variable using the optimality condition (Pivot Column):
The Rule: The entering variable in a maximization problem is the nonbasic
variable having the most negative coefficient in the z-row. The entering variable
column is identified as the pivot column
• Regarding our example, the entering variable is (𝒙𝟑 ) because it has the most
negative coefficient in the z-row(−45).
∴ 𝒙𝟑 column is the pivot column.
B. Select an leaving variable using the feasibility condition (Pivot Row):
The Rule: The leaving variable is the basic variable associated with the minimum
nonnegative ratio (The ratios of the solution column values to the corresponding
coefficients under the entering variable). The leaving variable row is identified as
the pivot row
• Regarding our example, the mechanics of determining the leaving variable
from the simplex table calls for computing the ratios of solution column values
to the corresponding coefficients under the entering variable (𝒙𝟑 ) as the
following table shows:
 6

Basic Entering (𝒙𝟑 ) Solution Ratio

42
𝒔𝟏 3 42 𝑥3 = = 14 ← minimum
3
40
𝒔𝟐 2 40 𝑥3 = = 20
2
45
𝒔𝟑 1 45 𝑥3 = = 45
1

Conclusion: 𝒔𝟏 leaves the basic solution and new value of 𝒙𝟑 is 14

∴ 𝒙𝟑 row is the pivot row

A Very Important Note:
The minimum nonnegative ratio refers to the maximum number of units that can be
entered from the nonbasic variable to keep the feasibility of the solution
C. Determine the Pivot element:
The Rule: The pivot element is the intersection of the pivot column and the pivot
row
• Regarding our example, the pivot element is (𝟑)

− The following table is a restatement of the starting table with its pivot row and
column highlighted:
Pivot
column

Basic 𝒛 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 Solution

𝒛 1 −24 −22 −45 0 0 0 0

Leave ← 𝒔𝟏 0 2 1 3 1 0 0 42 Pivot row

𝒔𝟐 0 2 1 2 0 1 0 40
1
𝒔𝟑 0 1 2
1 0 0 1 45
Pivot element ↑
Enter
 7

D. Determine the new basic solution by using row operations:

The row operations needed to produce the new basic solution include two types.
1. Pivot row
a. Replace the leaving variable in the Basic column with the entering variable.
b. New pivot row = Current pivot row ÷ Pivot element
2. All other rows, including (z)
New Row = Current row − (Its pivot column coefficient × New pivot row)
These computations are applied to the preceding table in the following manner:
1. Replace (𝒔𝟏 ) in the Basic column with(𝒙𝟑 )
2. New pivot row (𝒙𝟑 ) = Current pivot row (𝒔𝟏 ) ÷ Pivot element (𝟑)

𝒛 → 0 ÷ 3 = 0
2
𝒙𝟏 → 2 ÷ 3 =
3
1
𝒙𝟐 → 1 ÷ 3 =
3

𝒙𝟑 → 3 ÷ 3 = 1
1
𝒔𝟏 → 1 ÷ 3 =
3

𝒔𝟐 → 0 ÷ 3 = 0

𝒔𝟑 → 0 ÷ 3 = 0
𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧 → 42 ÷ 3 = 14
 8

3. New 𝒛 row = Current 𝒛 row − (−45 × New 𝒙𝟑 row)

𝒛 → 1 − (−45 × 0) = 1
2
𝒙𝟏 → −24 − (−45 × 3) = 6
1
𝒙𝟐 → −22 − (−45 × 3) = −7

𝒙𝟑 → −45 − (−45 × 1) = 0
1
𝒔𝟏 → 0 − (−45 × 3) = 15

𝒔𝟐 → 0 − (−45 × 0) = 0

𝒔𝟑 → 0 − (−45 × 0) = 0
𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧 → 0 − (−45 × 14) = 630

4. New 𝒔𝟐 row = Current 𝒔𝟐 row − (2 × New 𝒙𝟑 row)

𝒛 → 0 − (2 × 0) = 0
2 2
𝒙𝟏 → 2 − (2 × 3) =
3
1 1
𝒙𝟐 → 1 − (2 × 3) =
3

𝒙𝟑 → 2 − (2 × 1) = 0
1 2
𝒔𝟏 → 0 − (2 × 3) = −
3

𝒔𝟐 → 1 − (2 × 0) = 1

𝒔𝟑 → 0 − (2 × 0) = 0
𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧 → 40 − (2 × 14) = 12
 9

5. New 𝒔𝟑 row = Current 𝒔𝟑 row − (1 × New 𝒙𝟑 row)

𝒛 → 0 − (1 × 0) = 0
2 1
𝒙𝟏 → 1 − (1 × 3) =
3
1 1 1
𝒙𝟐 → 2
− (1 × 3) =
6

𝒙𝟑 → 1 − (1 × 1) = 0
1 1
𝒔𝟏 → 0 − (1 × 3) = −
3

𝒔𝟐 → 0 − (1 × 0) = 0

𝒔𝟑 → 1 − (1 × 0) = 1
𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧 → 45 − (1 × 14) = 31

∴ These computations produce the following table:

Pivot
column

Basic 𝒛 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 Solution

𝒛 1 6 −7 0 15 0 0 630
2 1 1
𝒙𝟑 0 3 3
1 3
0 0 14
2 1 2
Leave ← 𝒔𝟐 0 3 3
0 −
3
1 0 12 Pivot row
1 1 1
𝒔𝟑 0 3 6
0 −
3
0 1 31
↑
Enter
 10

Observe that the new table has the same properties as the starting table. When we
set the new nonbasic variables 𝒙𝟏 , 𝒙𝟐 , and 𝒔𝟏 to zero, the Solution column
automatically yields the new basic solution (𝒙𝟑 = 𝟏𝟒, 𝒔𝟐 = 𝟏𝟐, 𝒔𝟑 = 𝟑𝟏) as follows:

Basic variables Nonbasic (zero) variables

𝒙𝟑 = 14 units 𝒙𝟏 = 0 units

𝒔𝟐 = 12 units 𝒙𝟐 = 0 units

𝒔𝟑 = 31 units 𝒔𝟏 = 0 units

𝒛 = $630

In the last table, the optimality condition shows that (𝒙𝟐 ) is the entering variable. The
feasibility condition produces the following:

Basic Entering (𝒙𝟐 ) Solution Ratio

1 1
𝒙𝟑 14 𝑥2 = 14 ÷ = 42
3 3
1 1
𝒔𝟐 12 𝑥2 = 12 ÷ = 36 ← minimum
3 3
1 1
𝒔𝟑 31 𝑥2 = 31 ÷ = 186
6 6

Conclusion: 𝒔𝟐 leaves the basic solution and new value of 𝒙𝟐 is 36

 11

Replacing 𝒔𝟐 in the Basic column with entering 𝒙𝟐 , the following row operations are
applied:
𝟏
1. New pivot row (𝒙𝟐 ) = Current pivot row (𝒔𝟐 ) ÷ Pivot element ( )
𝟑

1
𝒛 → 0 ÷
3
= 0
2 1
𝒙𝟏 → 3
÷
3
= 2
1 1
𝒙𝟐 → 3
÷
3
= 1
1
𝒙𝟑 → 0 ÷
3
= 0
2 1
𝒔𝟏 → −
3
÷
3
= −2
1
𝒔𝟐 → 1 ÷
3
= 3
1
𝒔𝟑 → 0 ÷
3
= 0
1
𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧 → 12 ÷ = 36
3

2. New 𝒛 row = Current 𝒛 row − (−7 × New 𝒙𝟐 row)

𝒛 → 1 − (−7 × 0) = 1

𝒙𝟏 → 6 − (−7 × 2) = 20

𝒙𝟐 → −7 − (−7 × 1) = 0

𝒙𝟑 → 0 − (−7 × 0) = 0

𝒔𝟏 → 15 − (−7 × −2) = 1

𝒔𝟐 → 0 − (−7 × 3) = 21

𝒔𝟑 → 0 − (−7 × 0) = 0
𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧 → 630 − (−7 × 36) = 882
 12

1
3. New 𝒙𝟑 row = Current 𝒙𝟑 row − ( × New 𝒙𝟐 row)
3

1
𝒛 → 0 − (3 × 0) = 0
2 1
𝒙𝟏 → 3
− (3 × 2) = 0
1 1
𝒙𝟐 → 3
− (3 × 1) = 0
1
𝒙𝟑 → 1 − (3 × 0) = 1
1 1
𝒔𝟏 → 3
− (3 × −2) = 1
1
𝒔𝟐 → 0 − (3 × 3) = −1
1
𝒔𝟑 → 0 − (3 × 0) = 0
1
𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧 → 14 − (3 × 36) = 2

1
4. New 𝒔𝟑 row = Current 𝒔𝟑 row − ( × New 𝒙𝟐 row)
6

1
𝒛 → 0 − (6 × 0) = 0
1 1
𝒙𝟏 → 3
− (6 × 2) = 0
1 1
𝒙𝟐 → 6
− (6 × 1) = 0
1
𝒙𝟑 → 0 − (6 × 0) = 0
1 1
𝒔𝟏 → −
3
− (6 × −2) = 0
1 1
𝒔𝟐 → 0 − (6 × 3) = −
2
1
𝒔𝟑 → 1 − (6 × 0) = 1
1
𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧 → 31 − (6 × 36) = 25
 13

∴ These computations produce the following table:

Basic 𝒛 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟏 𝒔𝟐 𝒔𝟑 Solution

𝒛 1 20 0 0 1 21 0 882

𝒙𝟑 0 0 0 1 1 −1 0 2

𝒙𝟐 0 2 1 0 −2 3 0 36
1
𝒔𝟑 0 0 0 0 0 −
2
1 25

When we set the new nonbasic variables 𝒙𝟏 , 𝒔𝟏 , and 𝒔𝟐 to zero, the Solution column
automatically yields the new basic solution (𝒙𝟑 = 𝟐, 𝒙𝟐 = 𝟑𝟔, 𝒔𝟑 = 𝟐𝟓) as follows:

Basic variables Nonbasic (zero) variables

𝒙𝟑 = 2 units 𝒙𝟏 = 0 units

𝒙𝟐 = 36 units 𝒔𝟏 = 0 units

𝒔𝟑 = 25 units 𝒔𝟐 = 0 units

𝒛 = $882

Based on the optimality condition, none of the z-row coefficients are negative. Hence,
the last table is optimal.
 14

The optimum solution can be read from the simplex table in the following manner:
The optimal values of the variables in the Basic column are given in the right-hand-
side Solution column and can be interpreted as

Decision variable Optimum value Recommendation

Not to produce any units of a

𝒙𝟏 0
product

𝒙𝟐 36 Produce 36 units of product B

𝒙𝟑 2 Produce 2 units of product C

𝒛 882 Total profit is $882

Note that:
You can verify that the values (s1 = 0, s2 = 0, s3 = 25) are consistent with the given
values of x1 , x2 , and x3 by substituting out the values of x1 , x2 , and x3 in the
constraints.
c. From the optimum solution determine the status of each resource.
The solution also gives the status of the resources. A resource is designated as
scarce if the activities (variables) of the model use the resource completely.
Otherwise, the resource is abundant.
This information is secured from the optimum table by checking the value of the
slack variable associated with the constraint representing the resource.
If the slack value is zero, the resource is used completely and, hence, is classified
as scarce. Otherwise, a positive slack indicates that the resource is abundant. The
following table classifies the constraints of the model:

Resource Slack value Status

R1 𝒔𝟏 = 0 Scarce
R2 𝒔𝟐 = 0 Scarce
R3 𝒔𝟑 = 25 Abundant
15
 16

A Very Important Note:

When a nonbasic variable enters the solution it can either increase or decrease the
values of the basic variables including (z) or leave it unchanged, depending on the
parameters of the entering nonbasic variable (The intersection between the entering
nonbasic variable column and the basic variable row) as follows:

The parameter of the entering nonbasic variable

Negative Positive Zero

Entering nonbasic Entering nonbasic Entering nonbasic

variable by one unit will variable by one unit will variable by one unit
Increase the value of Decrease the value of will Not cause a
the basic variable by the the basic variable by the change in the value
parameter value parameter value of basic variable

Example:
The following table represents a starting simplex iteration. All variables are
nonnegative. The table is not optimal for a maximization problem.

Basic 𝒛 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 𝒔𝟒 Solution

𝒛 1 −5 −4 0 0 0 0 0

𝒔𝟏 0 6 4 1 0 0 0 24

𝒔𝟐 0 1 2 0 1 0 0 6

𝒔𝟑 0 −1 1 0 0 1 0 1

𝒔𝟒 0 0 1 0 0 0 1 2
↑
Enter

Determine the effect of entering 𝒙𝟏 by one unit on the values of 𝒛, 𝒔𝟏 , 𝒔𝟐 , 𝒔𝟑 , 𝒔𝟒 , 𝒂𝒏𝒅 𝒙𝟐

 17

Solution
The effect of entering 𝒙𝟏 by one unit on the values of:

𝒛 → Will increase the value of 𝒛 by 5 units because the parameter of 𝒙𝟏 is negative

𝒔𝟏 → Will decrease the value of 𝒔𝟏 by 6 units because the parameter of 𝒙𝟏 is positive

𝒔𝟐 → Will decrease the value of 𝒔𝟐 by 1 unit because the parameter of 𝒙𝟏 is positive

𝒔𝟑 → Will increase the value of 𝒔𝟑 by 1 unit because the parameter of 𝒙𝟏 is negative

𝒔𝟒 → Will not cause a change in the value 𝒔𝟒 because the parameter of 𝒙𝟏 is zero

𝒙𝟐 → Will not cause a change in the value 𝒙𝟐 because 𝒙𝟐 is a nonbasic variable

 18

Unsolved problem
1. A company produces two products on two machines. A unit of product 1
requires 2 hours on machine 1 and 1 hour on machine 2. For product 2, a
unit requires 1 hour on machine 1 and 3 hours on machine 2. The profits
per unit of products 1 and 2 are $30 and $20, respectively. The total daily
processing time available for each machine is 8 hours.
a. Formulate the problem as a linear program.
b. Find the optimum solution using simplex method.
c. From the optimum solution determine the status of each resource.

2. Reddy Mikks produces both interior and exterior paints from two raw
materials, Ml and M2. The following table provides the basic data of the
problem:

a. Formulate the problem as a linear program.

b. Find the optimum solution using simplex method.
c. From the optimum solution determine the status of each resource.