Algorithm Example

Step 1 Convert the system of Maximize: P=2 x +5 y

inequalities (constraints) to Subject to 2 x+ y ≤ 5
equation using slack variables. x +2 y ≥ 4
x , y ≥0
Adding slack variables, s and t
2 x+ y + s=5
x +2 y +t=4
Step 2 Set the objective function equal −2 x−5 y+ P=0
to zero.
Step 3 Construct an initial simplex Active x y s t P
tableau and label the active or variable
basic variables. Active variables s
s 2 1 1 0 0 5
are the columns that only
t 1 2 0 1 0 4
contain one and zeroes. Each
P −2 −5 0 0 1 0
inequality constraint appears in
its own row. Write the objective
function as the bottom row.
Step 4 Select the pivot column. This is Active x y s t P
the column with the most variable
negative number on the left side s
s 2 1 1 0 0 5
of the bottom row.
t 1 2 0 1 0 4
P −2 −5 0 0 1 0
Step 5 Select the pivot row. Divide Active x y s t P Ratio
each entry in the constant variables
s 2 1 1 0 0 5 5
column by the corresponding =5
1
positive entry in the pivot t 1 2 0 1 0 4 4
=2
column. The smallest positive 2
P −2 −5 0 0 1 0
ratio indicates the pivot row.

Step 5 Select the pivot element, which Active x y s t P Ratio

is the entry in the pivot column variables
s 2 1 1 0 0 5 5
and pivot row. The pivot must =5
1
be positive. It can’t be zero.
 t 1 2 0 1 0 4 4
=2
2
P −2 −5 0 0 1 0

Step 7 Perform row operations to make Active x y s t P

the pivot element equal to 1 and variables
s 2 1 1 0 0 5
the remaining elements in the
t 1 1 0 1 0 2
pivot column equal to zero.
2 2
P −2 −5 0 0 1 0

Replace exiting variable with

entering variable.
1
R2 → R2
2

New active variables would be y . So, y is entering

variable and t is exiting variable.

x y s t P
Active
variables
Step 8 Active x y s t P
s 3 0 1 −1 0 3
variables
2 2
1 1 0 1 s 3 0 1 −1 0 3
y 0 2
2 2 2
Repeat the2 process by
1 0 0 5 y 1 1 0 1 0 2
P 1 10
identifying the most negative 2 2
2 2
entry in the last row. P 1 0 0 5 1 10
2 2
Once the left side of last row is R1 → R1−R 2
all non-negative, the solution
can be found. The value of
s=3 ,t=0
each active variables is equal to R3 → R3 +5 R2
the right most entry in the row.
y=2, x=0
All inactive variables equal
zero. P=10

∴The maximum of P is 10 at (0,2).

Simplex Method

Step 1: Formulate the problem. 

Let x  = The number of “Darling” pineapple jam

y = The number of “Honey” pineapple jam

The problem is formulated the same way as we did in Graphical Method.

Maximise: P=10 x +12 y (objective function)

Subject to: 0.4 x +0.6 y ≤ 480 (pineapple constraint: 480kg available)
0.8 x +0.6 y ≤ 810 (sugar constraint: 810kg available)
x , y ≥0 (non-negativity conditions)

Step 2: Convert the system inequalities (constraints) into equations by adding one
slack variable for each inequality.

0.4 x +0.6 y + s=480

0.8 x +0.6 y +t=810

Step 3: Set the objective function equal to zero.

−10 x−12 y+ P=0

After adding the slack variables, our problem reads

Objective function:  −10 x 1−12 x 2 + P=0

Subject to constraints: 0.4 x +0.6 y + s=480

0.8 s+0.6 y +t=810

x , y ≥0

Step 4: Construct the initial simplex tableau as follows.

x y s t P
s 0.4 0.6 1 0 0 480
t 0.8 0.6 0 1 0 810
 P −10 −12 0 0 1 0

If we arbitrarily choose  x=0 and y=0 we get s=480 , t=810∧P=0.

Step 5: Select the pivot column.

x y s t P
s 0.4 0.6 1 0 0 480
t 0.8 0.6 0 1 0 810
P −10 −12 0 0 1 0

Step 6: Select the pivot row.

x y s t P Ratio
s 0.4 0.6 1 0 0 480 480
=800
0.6
t 0.8 0.6 0 1 0 810 810
=1350
0.6
P −10 −12 0 0 1 0

Step 7: Select the pivot element.

x y s t P Ratio
s 0.4 0.6 1 0 0 480 480
=800
0.6
t 0.8 0.6 0 1 0 810 810
=1350
0.6
P −10 −12 0 0 1 0

Step 8: Perform row operations to make the pivot equal to 1 and the remaining
elements in the pivot column equal to zero.
R1
x y s t P R1 →
0.6
s 2 1 5 0 0 800
3 3
t 0.8 0.6 0 1 0 810
P −10 −12 0 0 1 0

Replace exiting variable, t with entering variable, y .

x y s t P
 s 2 1 5 0 0 800
3 3
y 2 0 −1 1 0 330
5
P −2 0 20 0 1 9600

By arbitrarily choosing  x=0  and  s=0, we obtain  y=800 ,t=330 ,∧P=9600 .

Step 9: Repeat the process by identifying the most negative entry in the last row. It
indicates the pivot row. Calculate the ratio to select pivot column. Then, select the
pivot element.

x y s t P Ratio
s 2 1 5 0 0 800 2
800 ÷ =1200
3 3 3
y 2 0 −1 1 0 330 2
330 ÷ =825
5 5
P −2 0 20 0 1 9600

x y s t P
s 2 1 5 0 0 800
3 3 5
y 1 0 −5 5 0 825 R2 → R2
2
2 2
P −2 0 20 0 1 9600

Replace exiting variable, y with entering variable, x .

x y s t P 3
R1 → R1− R 2
2
s 0 1 10 −2 0 250
3 3
x 1 0 −5 5 0 825 R3 → R3 +2 R2
2 2
P 0 0 15 5 1 11250

We no longer have negative entries in the bottom row, therefore we are finished.

Step 10: Read off the answers.

We look at the columns that have a 1 and all other entries zeros. Since the columns  s and t
are not such columns, we arbitrarily choose s=0 and t=0 , and we get
x=825 , y=250∧P=11250 . Therefore, the maximum of P is 11250 at (825, 250), which
means the manufacturer should make 825 “Darling” pineapple jams and 250 “Honey”
pineapple jams to maximize their profit to RM 11 250.