An important advantage of converting a given linear program into the standard form of the Simplex method is that it allows us to read out an associated basic feasible solution with literally no effort. In other words, it allows us to immediately begin the application of the Simplex algorithm. Indeed, one of the primary reasons for selecting the previous problem as our first example is precisely that by adding slack variables, we immediately arrive at an equivalent problem that is in the standard form.

For other linear programs, we may not be as "lucky." Specifically, we need to figure out how to deal with constraints that, as given, are in the "³" format or in the equality format. In the former case, we need to find a way to convert it into an equality with a nonnegative right-hand-side constant, as required by the standard from. In the latter case, we need to find out whether or not the given equality contains a candidate basic variable, i.e., a variable that has a coefficient of 1 and appears in that equation only.

Apart from issues related to setting up different types of constraints, we also need to figure out how to deal with problems where some of the variables are not required to be nonnegative. For example, in the production planning problem formulated in an earlier section, it may be desirable not to constrain the ending-inventory variables to be nonnegative, so as to accommodate scenarios where backlogging is allowed. Such variables are said to be unrestricted in sign. Since the Simplex algorithm assumes that all variables are nonnegative, we need to develop a mechanism for dealing with unrestricted (and other types of) variables.

In this section, we will go through a variety of linear programs that require some form of additional processing. As noted above, these involve the handling of, e.g., various constraint types, unrestricted variables, minimization objective functions, and so on.

We will begin with the description of an initialization procedure that is known as the big-M method. This method is designed to convert a given linear program, with constraints of all types, into the standard form. Thus, the procedure prepares a problem for the application of the standard Simplex algorithm. This will be given at the next link.

Initialization: The Big-M Formulation

If we call the linear program formulated in the big-M method the artificial problem, then the feasible set of the original linear program (even when it is empty) is a subset of the feasible set of this artificial problem. The starting point of the big-M method is a basic solution that is feasible to the artificial problem. This solution allows us to start the Simplex algorithm expeditiously, but it is not a feasible solution to the original problem. Our goal is to iterate toward solutions that are inside the original feasible set, assuming that it is not empty. Conceptually, this is visualized in Figure LP-7 below.

To accomplish this goal, we designed an artificial objective function that is an aggregation of two functional parts, of which one is a copy of the original objective function and the other is a "penalty function" associated with the artificial variables. The magnitude of the penalty, M, needs to be chosen to ensure that the contribution to this aggregate objective function from the second part, whenever it is positive, always outweighs that from the first part, for any solution. This requirement is rather strong; and furthermore, in a computer implementation of the big-M method, it is difficult to tell a priori how big an M is sufficient.

To circumvent this difficulty, we will describe, at the next link, a slightly modified version of the big-M method, called the two-phase method. The basic idea behind this modified method is to separate the task of iterating toward the original feasible set from that of finding an optimal solution within that set. Doing so will allow us to avoid the difficulty with choosing a value for M. As we will see, the two-phase method also have the side benefit of having simpler arithmetic.

Initialization: The Two-Phase Formulation

The two-phase, or the big-M, method is designed to handle constraints of different types. At the next link, we discuss how to handle variables of different types.

Unrestricted and Other Variable Types

Finally, at the next link, we will discuss three special situations that may occur in the course of the Simplex iterations. These are: degeneracy, unboundedness, and multiple optimal solutions.

Special Situations in the Simplex algorithm

The discussion at this link refers to several figures. To view these figures, click on the following titles: Figure LP-8, Figure LP-9, Figure LP-10.

Assignment No. 4

Chapter 4: 4.5-4, 4.5-8, 4.6-8, and 4.6-19.

I recommend that you use the Interactive OR Routines to solve these problems.