Lesson 5:

Solving LP Maximization Problem:

Simplex Method
• The graphical method 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)
 Expected Learning Outcomes

1. Identify and set up a linear program in

standard maximization form
2. Use the simplex method to solve the
maximization problem
3. Identify the optimal solution to the original
maximization problem
 Maximization Problems in Standard
Form
A linear programming problem is said to be a
maximization problem in standard form if its
mathematical model is of the following form:
Maximize the objective function

Subject to problem constraints of the form

With non-negative constraints

 Slack Variables

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.
 Basic and Nonbasic 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.

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.
 Basic and Nonbasic 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.
 SIMPLEX METHOD

Step-1
Write the Step 4
Step 2 Are there Step-5
standard
Are there any positive Select the
maximization any Step-3 elements in pivot
problem in negative Select the pivot element
standard form, indicators the column and
introduce slack in the pivot above the perform
variables to form bottom column dashed the pivot
the initial system, row? line?
operation
and write the
initial tableau.

STOP
STOP The linear programming problem has
The optimal solution has been found. no optimal solution

Simplex algorithm for standard maximization problems

 To solve an LP problem in standard form,
we follow the following steps.
1. Convert each inequality in the set of constraints to an
equation by adding slack variables.
2. Create the initial simplex table.
3. Find the pivot number
– determine the pivot column.
(The column with the “most negative value” element in
the last row.)
– determine the pivot row.
(The row with the smallest non-negative result when
the last element in the row is divided by the
corresponding number in the pivot column.)
4. Use elementary row operations
– to make all numbers in the pivot column equal to 0
except for the pivot number which must be equal to 1.
5. If all entries in the bottom row are zero or positive, the
simplex table is the optimal table. If not, repeat step 3.
6. If you obtain an optimal simplex table, then the linear
programming problem has an optimal solution.
 Pivot

• Pivot Column:
– The column of the table contains the variable to be
entered into the solution mix.
• Pivot Row:
– The row of the table contains the variable to be
replaced in the solution mix.
• Pivot Number:
– The element in both the pivot column and the pivot
row.(intersection}
 Simplex Table

• 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 table is a way to systematically
evaluate variable mixes in order to find the best
one.
 EXAMPLE 1
LP problem by Simplex method
The XYZ furniture Company produces tables and chairs.
Each table takes four hours of labor from the carpentry
department and two hours of labor 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 P70 and each chair a
profit of P50.
To maximize profit, how many chairs and tables should be
made?
 STEP 1

Given information about XYZ Company

Resource Tables(X₁) Chairs ( X₂) Constraints
Carpentry (hr) 4 3 240

Finishing (hr) 2 1 100

Unit Profit 70 50

Objective Function: Maximize

Carpentry Constraint:
Finishing Constraint:
Non-negativity conditions:
• The first step of the simplex method requires that each
inequality be converted into an equation.
• ”less than or equal to” inequalities are converted to
equations by adding slack variables.
• Let s₁ be the carpentry hours slack variable and
• s₂ be the finishing hours slack variable .
• The constraints become;

or
• As unused hours or slack result in no profit, the slack
variables are included in the objective function with zero
coefficients:

• The problem can now be considered as solving a system of

3 linear equations involving the 5 variables
• Now, the system of linear equations can be written in matrix
form or as a 3x6 augmented matrix.

• The initial simplex table is;

Basic Right
x1 x2 S1 S2 P
Variables Hand Side
S1 4 3 1 0 0 240
S2 2 1 0 1 0 100
P -70 -50 0 0 1 0
STEP 2

Initial Simplex table

Basic Right Hand

x1 x2 S1 S2 P
Variables Side
S1 4 3 1 0 0 240
S2 2 1 0 1 0 100
P -70 -50 0 0 1 0

• The initial simplex table gives the initial solution;

 STEP 3
• Determine the pivot number
– First choose the pivot column. (The column with the
“most negative value” element in the last row.)

Basic Right hand

x1 x2 S1 S2 P
Variables side
S1 4 3 1 0 0 240
S2 2 1 0 1 0 100
P -70 -50 0 0 1 0

Pivot column

• Note that there are 2 negative values in the last row and the
most negative is -70, thus, the pivot column is column X₁
STEP 3 con’t
– Next choose the pivot row.
• divide the last element in each row by the corresponding
element in the pivot column.
• the pivot row is the row with the smallest non-negative result.

Basic Right hand

x1 x2 S1 S2 P side
Variables
S1 4 3 1 0 0 240
S2 2 1 0 1 0 100
P -70 -50 0 0 1 0

Pivot row
Pivot column
 STEP 3 con’t
• The entering variable now is x₁ and the leaving variable is s₂
• The pivot number is 2

Enter x₁

Basic Right hand

x1 x2 S1 S2 P side
Variables
S1 4 3 1 0 0 240
Exit s₂ S2 2 1 0 1 0 100
P -70 -50 0 0 1 0

Pivot column Pivot row

Pivot number
STEP 4
Use elementary row operations to
– make all numbers in the pivot column equal to 0 except for the
pivot number which must be equal to 1, that is,

– transform to using matrix row operations.

– Strat with with the pivot always

Basic Right
x1 x2 S1 S2 P hand side
Variables
S1 4 3 1 0 0 240
S2 2 1 0 1 0 100
P -70 -50 0 0 1 0
Step 4 con’t
• To change the pivot 2 to 1, we perform the row operation
(1/2)R₂ .

Right
Basic
x1 x2 S1 S2 P hand
Variables
side
S1 4 3 1 0 0 240
x1 2 1 0 1 0 100
P -70 -50 0 0 1 0

• Computation for row 2 values of the above table is shown

in the next slide
 Note :
• : R₂ here is the row 2 of the table in slide 22

•½ (2 1 0 1 0 100) = 1 ½ 0 ½ 0 50

this is new row 2 of the table

in slide 25
Step 4 con’t
The result is shown below
Basic Right
x1 x2 S1 S2 P
Variables hand side
S1 4 3 1 0 0 240
x1 1 1/2 0 1/2 0 50
P -70 -50 0 0 1 0

• To change the number 4 to 0, we perform the row

operation -4R₂+R₁.
• To change -70 to 0, we perform the row operation
70R₂+R₃.
• R₁, R₂ and R₃ here are the 1st , 2nd and 3rd rows of the
simplex table above
• Computations are shown in the next slide
-4(1 ½ 0 ½ 0 50) = -4 -2 0 -2 0 -200
+ 4 3 1 0 0 240
0 1 1 -2 0 40 this is now the
new R1 of the table in slide 27

70(1 ½ 0 ½ 0 50) = 70 35 0 35 0 3500

+ -70 -50 0 0 1 0
0 -15 0 35 1 3500 this is now
the new R3 0f the table in Slide 27
Step 4 con’t
•The result is shown in the simplex table below after
performing the 3 row operations
•This table is the 2nd simplex table,
•gives the 2nd solution : S₁ = 40, S₂ = 0, X₁ = 50, X₂ = 0 and P
= 3,500.
•Notice that P increased from P = 0(see initial solution, slide
17 ) to P = 3,500.

Basic Right hand

x1 x2 S1 S2 P
Variables side
S1 0 1 1 -2 0 40
x1 1 1/2 0 1/2 0 50
P 0 -15 0 35 1 3500
Step 4 con’t

2nd Simplex table

Basic Right hand

x1 x2 S1 S2 P
Variables side
S1 0 1 1 -2 0 40
x1 1 1/2 0 1/2 0 50
P 0 -15 0 35 1 3500
• Note that in the 2nd simplex table, not all entries in the
bottom row are zero or positive, thus, the 2nd simplex table
is not the optimal simplex table and the 2nd solution is not
the optimal solution.
• To find the optimal solution, repeat step 3 until there
are no negative numbers in the last row.
 Repeat step 3
•Select the new pivot column. x2 should enter into the solution
mix.
•Select the new pivot row. S1 should be replaced by x2 in the
solution mix.
Enter

Right
Basic
x1 x2 S1 S2 P hand
Variables
side
Exit S1 0 1 1 -2 0 40
x1 1 1/2 0 1/2 0 50
P 0 -15 0 35 1 3500

New Pivot New pivot row

New pivot
number column
 – make all numbers in the pivot column equal to 0 except
for the pivot number which must be equal to 1, that is,

– transform to using matrix row operations.

– Again start with the pivot

Basic Right hand

x1 x2 S1 S2 P
Variables side
S1 0 1 1 -2 0 40
x1 1 1/2 0 1/2 0 50
P 0 -15 0 35 1 3500
• As the pivot number is already 1, there is no need to
calculate new values for the pivot row.
• Use row operation -1/2 R₁ + R₂ to change ½ to 0 and
• Use row operation 15R₁ + R₃ to change -15 to 0

Basic Right hand

x1 x2 S1 S2 P
Variables side
S1 0 1 1 -2 0 40
x1 1 1/2 0 1/2 0 50
P 0 -15 0 35 1 3500
 Note:
• :

•-1/2(0 1 1 -2 0 40) =0 -1/2 -1/2 1 0 -20

+1 ½ 0 ½ 0 50
1 0 -1/2 3/2 0 30 :

•15(0 1 1 -2 0 40) = 0 15 15 -30 0 600

+ 0 -15 0 35 1 3500
0 0 15 5 1 4100
• The result is shown in the simplex table below after
performing the 2 row operations
• This table is the 3rd simplex table, which gives the 3rd
solution : S₁ = 0, S₂ = 0, X₁ = 30, X₂ = 40 and P = 4,100.
• Notice that P increased from P = 3,500(see 2nd solution,
slide 26 ) to P = 4,100.

Basic Right hand

x1 x2 S1 S2 P
Variables side
x2 0 1 1 -2 0 40
x1 1 0 -1/2 3/2 0 30
P 0 0 15 5 1 4100
 3rd Simplex Table

Basic Right hand

x1 x2 S1 S2 P
Variables side
x2 0 1 1 -2 0 40
x1 1 0 -1/2 3/2 0 30
P 0 0 15 5 1 4100

• As the last row of the 3rd simplex table contains no negative

numbers, the 3rd table is the optimal simplex atable.
• The solution gives the maximum value of P.
 The Optimal simplex Table

This optimal simplex table gives the optimal

solution to the XYZ LP problem:

and profit of P = 4100

The optimal solution is to make 30 tables and 40
chairs for a maximum profit of P4,100
 Challenge!
Try these problems for practice Solve by Simplex method

1. Maximize P = 50X₁ + 100X₂ +150X₃

Subject to: 2X₁ + 2X₂ ≤ 200
3X₃ ≤ 150
4X₁ + 4X₃ ≤ 600
X₁,X₂,X₃ ≥ 0
2. 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?