Page 256 -

236 CHAPTER 5 LINEAR PROGRAMMING: THE SIMPLEX METHOD

Summary of the Steps to Create Tableau Form

Step 1. If the original formulation of the linear programming problem contains
one or more constraints with negative right-hand side values, multiply
each of these constraints by 1. Multiplying by 1 will change the
direction of the inequalities. This step will provide an equivalent linear
programme with nonnegative right-hand side values.
Step 2. For constraints, add a slack variable to obtain an equality constraint.
The coefficient of the slack variable in the objective function is assigned a
value of zero. It provides the tableau form for the constraint, and the
slack variable becomes one of the basic variables in the initial basic
feasible solution.
Step 3. For constraints, subtract a surplus variable to obtain an equality
constraint, and then add an artificial variable to obtain the tableau form.
The coefficient of the surplus variable in the objective function is assigned
a value of zero. The coefficient of the artificial variable in the objective
function is assigned a value of M. The artificial variable becomes one of
the basic variables in the initial basic feasible solution.
Step 4. For equality constraints, add an artificial variable to obtain the tableau
form. The coefficient of the artificial variable in the objective function is
assigned a value of M. The artificial variable becomes one of the basic
variables in the initial basic feasible solution.
To obtain some practise in applying these steps, convert the following example
problem into tableau form, and then set up the initial simplex tableau:

Max 6x 1 þ 3x 2 þ 4x 3 þ 1x 4
s:t:
2x 1 0:5x 2 þ 1x 3 6x 4 ¼ 60
þ 1x 3 þ 0:6667x 4 20
1x 1
1x 2 5x 3 50
x 1 ; x 2 ; x 3 ; x 4 0

To eliminate the negative right-hand side values in constraints 1 and 3, we apply
step 1. Multiplying both constraints by 1, we obtain the following equivalent linear
programme:

Max 6x 1 þ 3x 2 þ 4x 3 þ 1x 4
s:t:
þ 6x 4 ¼ 60
2x 1 þ 0:5x 2 1x 3
1x 1 þ 1x 3 þ 0:6667x 4 20
1x 2 þ 5x 3 50
x 1 ; x 2 ; x 3 ; x 4 0

Note that the direction of the inequality in constraint 3 has been reversed as a
result of multiplying the constraint by 1. By applying step 4 for constraint 1, step 2
for constraint 2 and step 3 for constraint 3, we obtain the following tableau form:
Max 6x 1 þ 3x 2 þ 4x 3 þ 1x 4 þ 0s 2 þ 0s 3 Ma 1 Ma 3
s:t:
2x 1 þ 0:5x 2 1x 3 þ 6x 4 þ 1a 1 ¼ 60
1x 1 þ 1x 3 þ 0:6667x 4 þ 1s 2 ¼ 20
þ 1a 3 ¼ 50
1x 2 þ 5x 3 1s 3
x 1 ; x 2 ; x 3 ; x 4 ; s 1 ; s 2 ; a 1 ; a 2 0

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.