Page 252 -

232 CHAPTER 5 LINEAR PROGRAMMING: THE SIMPLEX METHOD

A basic feasible solution Is this solution feasible in terms of the real HighTech problem? No, it is not. It
containing one or more does not satisfy the constraint 4 combined total production requirement of 25 units.
artificial variables at
positive values is not We must make an important distinction between a basic feasible solution for the
feasible for the real tableau form and a feasible solution for the real problem. A basic feasible solution
problem. for the tableau form of a linear programming problem is not always a feasible
solution for the real problem.
The reason for creating the tableau form is to obtain the initial basic feasible
solution that is required to start the Simplex method. So, we see that whenever it is
necessary to introduce artificial variables, the initial simplex solution will not in
general be feasible for the real problem. This situation is not as difficult as it might
seem, however, because the only time we must have a feasible solution for the real
problem is at the last iteration of the Simplex method. So, devising a way to
guarantee that any artificial variable would be eliminated from the basic feasible
solution before the optimal solution is reached would eliminate the difficulty.
The way in which we guarantee that artificial variables will be eliminated before
the optimal solution is reached is to assign each artificial variable a very large cost in
the objective function. For example, in the modified HighTech problem, we could
assign a very large negative number (such as -100 000) as the profit coefficient for
artificial variable a 4 . So, if this variable is in the basis, it will substantially reduce
profits. As a result, this variable will be eliminated from the basis as soon as possible,
which is precisely what we want to happen.
As an alternative to picking a large negative number such as 100 000 for the profit
coefficient, we will denote the profit coefficient of each artificial variable by M.Here
it is assumed that M represents a very large number – in other words, a number of
large magnitude and hence, the letter M. This notation will make it easier to keep
track of the elements of the simplex tableau that depend on the profit coefficients of
the artificial variables. Using M as the profit coefficient for artificial variable a 4 in
the modified HighTech problem, we can write the objective function for the tableau
form of the problem as follows:
Max 50x 1 þ 40x 2 þ 0s 1 þ 0s 2 þ 0s 3 þ 0s 4 Ma 4
The initial simplex tableau for the problem is shown here.

x 1 x 2 s 1 s 2 s 3 s 4 a 4
Basis c B 50 40 0 0 0 0 M

s 1 0 3 5 1 0 0 0 0 150
s 2 0 0 1 0 1 0 0 0 20
s 3 0 8 5 0 0 1 0 0 300
a 4 M *1 1 0 0 0 1 1 25
M M 0 0 0 M M 25M
z j
50 + M 40 + M 0 0 0 M 0
c j – z j

This tableau corresponds to the solution s 1 ¼ 150, s 2 ¼ 20, s 3 ¼ 300, a 4 ¼ 25 and
x 1 ¼ x 2 ¼ s 4 ¼ 0.Interms of the simplex tableau,thissolution isa basicfeasiblesolution
because all the variables are greater than or equal to zero, and n m ¼ 7 4 ¼ 3of
the variables are equal to zero.
Since c 1 z 1 ¼ 50 + M is the largest value in the net evaluation row, we see
that x 1 will become a basic variable during the first iteration of the Simplex

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.