About Artificial Variables in Linear Programming (LP)

Another frequently asked question by students is related to use of artificial variables
while preparing the initial basic feasible solution table. The common flow of discussion
forces the student to think in a logical way as he has been thinking about slack and surplus
variables but the artificial variables can not be considered in the same logical category as
the previous two.

Just to recall, slack and surplus variables are used in LP to convert inequality constraints
to that of equality. If the constraint is of <= type, we add a slack variable to the left
hand side expression to make it equal to the right hand side value. It has some meaning. If
we write a constraint related to a raw material in a product mix problem, the left hand side
expression gives the raw material consumption while the r.h.s. value is the availabilty of
that raw material. The consumption has to be less than or equal to the availability, it can
not be more. And so the constraint is of <= type. The value of the slack variable is the
difference between the availability and the consumption. So at any stage it gives the
quantity of raw material unused.

Similarly, when the constraint is of >= type, we subtarct a surplus variable from the l.h.s.
expression to make it equal to the r.h.s. value. Why should such type of constraint arise in
real life situation? May be that the production of a product has to be more than a given
quantity because this much is needed by a very important customer. Or may be that intake of
a combination of items by human body has to be more than a prescribed quantity to keep the
body healthy. You can understand that here again the surplus variable has some meaning and
it's value gives an idea as to how much surplus one has produced or how much surplus one has
eaten.

Coming to the artificial variables, they don't have such meaning. Here, suddenly you have to
reduce your understanding capability. Don't try to find much meaning. Artificial variables
are not there to make out much meaning. They are used to get an initial basic variable from
the constraints while preparing the initial basic feasible solution table. Constraints of >=
type and = type don't provide any basic variable. So, artificial variable is added
arbitrarily to get the basic variable. And also a heavy penalty is associated for this
misdeed so that these variables are pushed out of the basis. Values of these variables don't
make much sense because they should go out of the basis and never come back. But if they
remain in the optimal basis then you have to say that there is no feasible solution to the
given LP. This conclusion depends just on the presence of the articial variable in the basis
of the optimal table, it doesn't change with it's value.