Violations of the Standard Form

What do we do if our linear programming problem does not comply with the requirements of the "standard form"?

Well, we do not panic!

Of course, if you insist you can panic, but there is really no need for that. The good news is that it is easy to handle violations of the standard form. The general strategy is to transform a problem that is a non-standard form into an equivalent problem that is in a standard form. By equivalent we mean that the two problems have the same set of feasible solutions, the same set of optimal solutions, and the same optimal value for the objective function. Thus, by solving the equivalent problem (having a standard form) we recover a solution to the original problem (having a non-standard form).

We shall now see how each of the possible violations of the standard form is handled. So recall that the standard form requires the following:

There are consequently three types of violations:

Since the third violations has two cases ( a "=" type constraint or a ">=" type constraint), there are altogether four violations to examine.

Violation # 1: Negative right-hand side coefficient

This is the easiest violation: all we have to do is multiply the offending constraint by -1, observing that if the constraint is not an "=" type, multiplication by -1 will reverse the direction of the inequality (from "<=" to ">=" and vice versa.)

In case you have forgotten about the rules for multiplication of equalities and inequalities by -1, you may wish to experiment with the following example.

Original constraint

 3x1 2x2 4x3 - 6

Equivalent constraint

 3x1 2x2 4x3   6

You certainly have observed that by fixing this type of violation we may cause a different violation. In particular, this fix will transform a kosher "<=" constraint into an non-kosher ">=" constraint. So, do not panic. As promised, we shall shortly examine a fix for the third type of violation

Violation # 2: A decision variable is not required to be non-negative

To handle this violation we call upon a very old trick: any number (positive or negative) can be expressed as the difference of two non-negative numbers. For example, x=-4 can be expressed as v-w, where say v=6 and w=10.

So all we have to do to handle a variable that is not restricted in sign is to replace it (in the objective function and the functional constraint) by the difference of two new decision variables that are required to be non-negtive.

For example, consider the following problem:

max z = 3x1 + 4x2 + 5x3
s.t.
2x1 + 5x2 + 3x3<= 10
3x1 + 2x2 + 7x3<= 20
x2 >= 0

Two decision variables (namey x1 and x3) are not subject to the non-negativity constraint. So we replace each of them by the difference of two new decision variables. The result is as follows:

max z = 3(x'1 - x"1) + 4x2 + 5(x'3 - x"3)
s.t.
2(x'1 - x"1)+ 5x2 + 3(x'3 - x"3)<= 10
3(x'1 - x"1) + 2x2 + 7(x'3 - x"3)<= 20
x'1,x"1,x2,x'3,x"3 >= 0

There are now five decision variables.

We shall refer to such variables as URS (short for Un Restricted Sign).

Violation # 3: A functional constraint is not a "<=" type

We distinguish here between two cases, namely

  • A >= constraint
  • A = constraint

We deal with the first by transforming it into a equivalent =" constraint which will then be handled by the trick we use to handle this type of constraints.

The details are simple: we subtract a decision variable, called surplus variable from the left-hand side of a >=" constraint, subject this variable to the non-negativity constraint and rewrite the constraint as a =" constraint.

To illustrate how little trick works, consider the following functional constraint:

3x1 + 2x2 + 7x3 >= 20

Then, this constraint is equivalent to

3x1 + 2x2 + 7x3 - x4 = 20 , ( x4 >= 0)

in that they both have the same set of feasible solutions with regard to original decision variables (x1,x2,x3). In other words, (x1,x2,x3) is feasible with respect to the origianl constraint if and only if (x1,x2,x3,x4) is feasible with regard to the = constaint, where

x4 = 20 - 3x1 - 2x2 - 7x3

Make sure that you understand why it is necessary to subject x4 to the non-negative constraint.

So far so good! Our last task is to deal with " = " type of constraints.

Recall that the Simplex Method requires a problem is a canonical form. Thus, our " = " constaint will need a basic variable to represent it in the basis. For this reason, we do here exactly what we did for "standard" (" <= " ) constraints, namely we add to the left-hand side of the constraint a decision variable. For example, consider the constraint

x1 + 3x2 + 7x3 - x4 = 25

We thus introduce a new decision variable, x5, and designate it as the representative of this constraint in the basis. The resulting constraint will thus be as follows:

x1 + 3x2 + 7x3 - x4 + x5 = 25

You may wonder, perhaps why we need to introduce x5, into the picture given that the constraint has other variables. Why do'nt we let say x1 represent this constraint in the basis?

This is a very good question (thank you!). The answer goes like this. If it is indeed possible to designate one of the original variables as a representative of a = constraint in the initial basis then it is not necessary to introduce a surplus variable for this constraint.

The difficulty is that it is not always easy to identify such a representative because the original variables typically appear in more than one constraint.

There is one major difficulty, however, with the above scheme: The the original = constraint is equivalent to the constraint resulting from the introduction of the additional decision variable only if the additional variable is equal to zero. Thus it is more appropriate to rewrite the above example as follows:

x1 + 3x2 + 7x3 - x4 = 25
x1 + 3x2 + 7x3 - x4 + x5 = 25 , ( x5 = 0)

This important observation implies that in the course of the Simplex Procedure we shall have to take out of the basis all the additional variables representing equality constraints in the initial basis. These variables are therefore viewed as temporary constructs. Appropriately they are called artificial variables.

We therefore need a method for taking all the artificial variables out of the basis whenever this is possible. This qualification is merely a reminder that if the problem is not feasible, namely if the constraints cannot be satisfied, then it is impossible to take all the artificial variables out of the basis.

But before we address this issue, let us summarise the modelling aspect of the discussion. Here is then the recipe for handling violations of the standard form:

Violation

Remedy

Negative right-hand side coefficient

Multiply the offending constraint by -1

URS variable

Replace the offending variable by the difference of two new variables that are subject to the non-negativity constraint

" >= " constraint

Rewrite the offending constraint as an " = " constraint through the introduction of a surplace variable

" = " constraint

Add an artificial variable to the offending constaint and use it (temporarily) as a basic variable for the constraint

Let us now see how this recipe works in the context of the following little example:

x1 + 3x2 + 7x3 > = 25
-3x1 - 2x2 + 7x3 = - 5
2x1 + x2 + 4x3 < = 10
   x2,x3 >= 0

The first constraint is fixed by the introduction of a surplus variable (to make it an = constraint) and an artificial variable to (to construct the canonical form). Thus, its modified form is as follows:

x1 + 3x2 + 7x3 - x4 + x5 = 25

The second constraint is multiplied by -1 (to handle the negative RHS) and then an artificial variable is introduced to construct the canonical form. The end result is as follows:

3x1 + 2x2 - 7x3 + x6 = 5

The third constraint is in the standard form so we just add a slack variable.

2x1 + x2 + 4x3 + x7 = 10

Finally, x1 is URS, so we replace it everywhere in the functional constraints by the difference of two non-negative variables. The result is then as follows:

x'1 - x"1 + 3x2 + 7x3 - x4 + x5 = 25
3x'1 - 3x1 + 2x2 - 7x3 + x6 = 5
2x1 - 2x1 + x2 + 4x3 + x7 = 10
   x'1,x"1,x2,x3,x4,x5,x6,x7 >= 0

Or, equivalently, in a more military format

 x1 -  x2 + 3x3 + 7x4 - x5 + x6 = 25
3x1 - 3x2 + 2x3 - 7x4 + x7 =  5
2x1 - 2x2 +  x3 + 4x4 + x8 = 10
xj>= 0 , j=1,...,8

The initial basis consists then of (x6,x7,x8)

As a rule, we always name (index) the slack, surplus and artificial variables in such a manner that initial basis consists of the last m decision variables (m = number of functional constraints). That is, the mxm identity matrix representing the initial basis consists of the last m columns of the left-hand side coefficients of the canonical form.

In a tabular form, the coefficients of the functional constraints will appear as follows:

x1 x2 x3 x4 x5 x6 x7 x8 RHS
1 -1 3 7 -1 1     25
3 -3 2 -7     1    5
2 -2 1 4       1 10

One more thing.

Because of the special role that artificial variables play in the canonical form, it is useful introduce a convention for identifyng them in the canonical form and in the simplex tableau.

This can be done on a variety of ways. For example, we can underline them, eg x3. This way we can easily identify all the articifial variables of a given formulation. For instance, consider the tableau representation of the previous example:

x1 x2 x3 x4 x5 x6 x7 x8 RHS
1 -1 3 7 -1 1     25
3 -3 2 -7     1    5
2 -2 1 4       1 10

You are cordially invited to use our facility to polish your skills in handling violations of the standard form. You supply the constraints in their natural form and the facility will generate the canonical, including a report on the violations and the they way they are handled.


Alternatively, you may wish to read the material we have on the 2-Phase Method. This method is commonly used to handle artificial variables. It attempts to take these variables out of the basis. If this cannot be done, the method reports that the problem is infeasible.

Contributed by

© The University of Melbourne 1994-2000.
Disclaimer and Copyright Information.
Conditions of use.
Date created: January 15, 2000
Date last modified: February 15, 2000
Authorised by: Moshe Sniedovich
Maintained by: Moshe Sniedovich, Department of Mathematics and Statistics.
Email: m.sniedovich@ms.unimelb.edu.au