Chapter 5: Linear Programming: Simplex Method

Introduction

The concept of linear programming and its solution method “simplex” was first introduced by George Dantzig, the so-called father of linear programming. His research on the planning methods for the US Army Air Force was a game changer, as the method had great potential for dealing with difficult decision making problems by utilizing technological/computational advances.

The whole concept can be briefly explained by his own quote:

“Linear programing can be viewed as part of a great revolutionary development that has given mankind the ability to state general goals and to lay out a path of detailed decisions to be taken in order to ‘best’ achieve these goals when faced with practical situations of great complexity. Our tools for doing this are ways to formulate real-world problems in detailed mathematical terms (models), techniques for solving the models (algorithms), and engines for executing the steps of algorithms (computers and software).”

In a linear program, the optimum solution is at one of the corners of the feasible region, i.e., the solution space. Thus, all the solving methods utilize this geometric approach. The graphical solution of two-variable linear models was introduced in the previous chapter. A general procedure for solving linear models is the simplex method, which will be explained in this chapter. Although it is an algebraic method, the simplex algorithm has geometric fundamentals as well.

Transition From Graphical to Algebraic Solution

The first step of the simplex method is to transform the linear model into a system of equations consisting of functional constraints. Thus, the solution space is presented by m linear equations and n variables. If the numbers of the linear equations and the variables are equal, the system has only one solution. However, the majority of linear programs have a greater number of variables compared equations n>m. This yields an infinite number of solutions, which creates the solution space. A basic solution—whether it is feasible or not—is a corner point of the solution space. The corner points of system of equations are obtained by setting n – m number of variables equal to zero and solving the equations for the remaining m number of variables.

A slack or surplus is utilized to reconstruct a constraint to obtain equation format. A slack variable represents the remainder of an expendable resource and applies to less than or equal constraints. On the other hand, a surplus represents the excess amount of a restricted resource and applies to greater than or equal constraints.

If two corner-point feasible solutions are connected by a line segment, these cornerpoint feasible solutions are adjacent. Two corner-point feasible solutions are adjacent if all but one of their respective variables have the same value.

A corner-point feasible solution is the optimum cornerpoint feasible solution only if it has no adjacent cornerpoint feasible solutions with a more desirable Z value.

Before moving to the algebra of the simplex method, the key solution concepts of the method are summarized below:

• The method solely focuses on CPF solutions, i.e., BF solutions.
• It is an iterative algorithm.
• The preferred initial BF solution is the CPF solution at the origin, where all decision variables are set to zero.
• Optimality test subject changes from a BF solution to an adjacent one.
• The selection between the adjacent BF solutions is based on the improvement in Z.
• If there are many adjacent BF solutions that improve the Z, the one providing the largest improvement is selected.
• If none of the adjacent BF solutions improve Z, the current BF solution is optimal.

Based on the solution concepts stated above, the simplex method solves the problem.

Initialization: Point A (0, 0) is the first basic feasible solution.

Test for optimality: Point A is not optimal, as moving along on either side improves Z. Recall that the objective is to maximize Z, and thus, an improvement refers to an increase.

Iteration: Moving from point A to Q improves Z more than moving from point A to D. In other words, holding x2 constant at zero and increasing x1 improves Z more than holding x1 constant at zero and increasing x2, because in the objective function x1 has a greater coefficient than x2.

Test for optimality: None of the adjacent BF solutions (A or K) improve the value of Z.

Stop: Point D is the optimal BF solution for Program 4.1. Revisit Figure 5.3. and notice that the simplex method solves the program efficiently and with lesser effort than the complete calculation of CPF solutions.

The Algebra of Simplex Method

In the previous section, the constraints of the example Program 4.1. were transformed into equations. For such a model, BF solutions consist of four variables (x1, x2, s 1, s 2), whereas CPF solutions consist of two (x1, x2). Thus, a BF solution is an augmented form of a corresponding CPF solution, even though their graphical demonstrations are identical on a x1x2 - plane. This section focuses on finding the optimum BF solution.

Similar to the definition of adjacent CPF solutions, two BF solutions are adjacent if their basic variables are equal except one. As the basic and non-basic variables are interchangeable only with each other, two adjacent BF solutions have the same non-basic variables with a single exception. Inherently, all but one of their basic variables are the same. For instance, the BF solution A is adjacent to B, as one of their basic variables (s 1) match and the others (s 2, x2) do not. From a different perspective, the BF solution B can be obtained from A by leaving the basic variable s 2 in the non-basic variables set and moving x2 to the basic variables group. The simplex algorithm iteratively switches to the next BF solution that is adjacent to the previous BF solution until it reaches the optimum Z. The switching is done just as the explanation of obtaining the BF solution B from A.

Initialization: For the initial basic solution, s 1, s 2 are chosen to be basic variables and shown in bold face above. Thus, the initial BF solution is (0, 0, 30, 12), as the nonbasic variables are known to be zero. Notice that this solution can easily be obtained without any calculation, as each equation has one unique basic variable with a coefficient of 1. Before getting to the next step, the simplex method requires to convert the equations in this readable format in every iterative BF solution. Test for optimality: The objective for Program 4.1. is to maximize the function Z = 2x1 + x2. However, the initial BF solution (0, 0, 30, 12) has no basic variables that are in the function of Z. Thus, the value of Z is zero. It is obvious that switching a variable from basic to non-basic will improve the value of Z; x1 and x2 both have positive coefficients in the objective function. Determining the entering variable: The next is to decide entering variable from non-basic variables (x1, x2). As it mentioned earlier, the criteria is the rate of improvement of Z. The coefficients of the variables in the objective function refer to the effect of one unit increase of respective variable on the function output Z. Hence, these coefficients correspond to the rate of improvements of the respective variables in Z. According to the objective function of Program 4.1., increasing x1 from zero yields more than increasing x2 from zero. Thus, the entering variable is x1. Determining the leaving variable: Considering x1 is the new basic variable while x2 is still the nonbasic.

Among the non-basic constraints in Eq. (0.3), only s 1 has a negative coefficient. s 1 is the entering variable. Only Eq.(3.2) has a right-hand side value divided by the coefficient of x1.

Artificial variable ?2 becomes a non-basic variable and it has disappeared from the equations as it can be omitted.

Simplex Method in Tabular Form

The previous section was focused on representing the underlying logic of the simplex method by algebraic formulations. Once the method is understood, the remaining is a repetitive process. Nevertheless, it is burdensome to rewrite the whole system of equations and perform the required calculations in each iteration. This excessive effort is lessened by reforming the system of equations into a table that includes only the essential information. The first example of the previous section, the initial system of equations for Program 4.1., is presented in tabular form in Table 5.5. The tabular form on the righthand side of the Table 5.5. is called the simplex tableau, which includes a basic variables column (Z, s1, s2)— recall that Z in Eq.(0) acts as a basic variable—and the corresponding right-hand side values of the equations are given in the leftmost column (0, 30, 12). Since the nonbasic variables (x1, x2) are known to be zero, the initial BF solution (x1, x2, s1, s2) = (0, 0, 30, 12) and yields Z=0. The coefficients of the basic variables forming the identity matrix means that the simplex tableau is ready for the next step, the test of optimality.

Identity matrix of n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. An identity matrix is also called a unity matrix.

In the previous section, the leaving variable was determined from the right-hand side constant, which is divided by the coefficient of the entering variable. Here in the simplex tableau, the same process is done by a name called the minimum ratio test, which is given on the rightmost column. The minimum value means limiting the entering variable the most. The only possible leaving variables are s 1 and s 2, as Z is not a genuine basic variable. In fact, it only acts as one. Remember that the basic variable s 2 (row 3 for Eq. 2) does not limit x1. In the simplex tableau, this is implied by a negative coefficient in the pivotal column.

Before moving forward, the steps of determining the pivotal row are given below: 1. Take each positive coefficient in the pivotal column. 2. Divide each of these into the right-hand side constant for the corresponding row. 3. Identify the row that has the minimum ratio. 4. Pivotal row is the row that is identified in the previous step. The simplex method requires that each equation must have only one basic variable that does not appear in other equations. In the simplex tableau, this condition is satisfied by elementary row operations to obtain the identity matrix for the new set of basic-variables. The first operation is always dividing the pivot row by the pivot number. The following are elementary row operations with this new pivot row in order to form an identity matrix in the coefficients column for the new basic-variables.

The specific operations for the simplex tableau in Table 5.6. are listed 1. Divide the pivot row by the pivot number 2. Add the new pivot row to row 3 (Eq. 2) 3. Add two times the new pivot row to row 1(Eq. 0). After these operations above, dashed-line frames under the coefficients columns of Z, x and s2 forms a 3×3 identity matrix.

The value at the intersection of the pivotal column and row is called the pivotal number. It is alternatively called as pivot number or pivot element.