The Simplex Method and Sensitivity Analysis



LP Sensitivity Analysis*

The previous courses provided two types of methods for solving LP problems (i.e. finding an optimal solution and the related optimal value of the objective function):

1. The graphical method which is applicable to problems with two variables (and with at most three variables).

2. The simplex methods for solving general LP problems.

Remark. The simplex methods computations are particularly tedious, repetitive, and boring. Once you have learned how the simplex methods work (and it is important that you do understand the concepts and the mathematical foundations of the simplex methods presented in Courses 2&3), computers with carry out the tedious work and you will not need to solve an LP manually.

*) This course is mainly based on Chapter 3 in Taha (2007), and Chapters 3 & 4 in Hillier and Liebermann (2005).

This course focuses on LP sensitivity analysis based on the optimal solution found via both types of methods. With sensitivity analysis we can ascertain the impact of the uncertainty regarding the parameters’ values on the quality of the optimum solution and related information. In LP the parameters (input data) of the model can change within certain limits preserving the optimality of the solution or some other parameters determined by the optimal solution.

With an optimal solution of an LP problem additional economic information can be derived, namely the related dual prices of resources and the reduced (imputed) costs of activities.

• The dual or shadow price of a resource is the technical name of the unit worth of that resource. The unit worth of a resource is the change in the optimal objective value per unit change in the availability of a resource. Knowing the range of a certain resource which keeps the dual price of that resource unchanged provides support for scientific decision making.

• The reduced cost is defined as

Reduced cost per unit = Cost of consumed resources per unit − Revenue per unit.

It is used to evaluate the “attractiveness” of a “product” from the standpoint of optimization which depends on the relative values of the revenue per unit and the cost of the resources consumed by one unit.

Sensitivity analysis deals with determining:

• the dual prices (corresponding to the optimal solution) and the conditions regarding the changes in the availability of the resources that will keep the current dual prices valid;

• the reduced costs (corresponding to the optimal solution) and the conditions regarding changes in coefficients of the objective function that will keep the current optimal solution (point) unchanged.

All software packages provide information for sensitivity analysis. The material in this course also stresses the interpretation of each iteration in terms of the solution of the original problem, to make you able to read and interpret the output reports provided by commercial software. It also explains how simplex based sensitivity analysis is used to provide important economic interpretations about the optimum solution, including the dual (or shadow) prices and the reduced costs.

To explain the basics of sensitivity analysis we start with graphical solution and then extend to the general LP problem using the simplex tableau results.

• Graphical sensitivity analysis uses the graphical solution to determine:

i) The dual prices (of resources) and their feasibility (conditions and) ranges (that keep the dual prices unchanged). The current value of the objective function and the current optimum point will change owing to the change in the parameters, but their new values can be easily computing based on the current optimal solution.

ii) The optimality (conditions and) ranges of the unit prices that keep the optimal solution (point) unchanged. The current value of the objective function will change owing to the change in its parameters, but the new value can be easily computing based on the current optimal solution.

• Algebraic sensitivity analysis uses (the z-row in) the optimal tableau to determine the dual prices and the reduced costs, and by recomputing the optimal simplex tableau with the modified right-hand side (or the modified coefficients of the objective function) in terms of deviations from the original data determines:

i) The feasibility (conditions and) ranges for the resources that assure that the dual prices associated with the optimal solution remain valid. The current value of the objective function and the current optimum point will change owing to the change in the parameters, but their new values can be easily computing based on their expression in terms of the current deviations of the parameters, found in the recomputed optimal simplex tableau.

ii) The optimality conditions and the optimality ranges for the unit costs that will keep an optimal solution unchanged. The current value of the objective function will change owing to the change in its parameters, but its new value can be easily computing based on (its row in) the recomputed optimal simplex tableau.

In this course we rewrite the primal basic form of a LP problem (formula (3) in Courses 2&3) and use its related (primal) tableau. This approach provides better motivation for the name “basic variables”, illustrates that the use of the label “−1” in Courses 2&3 is merely a convention, and is more convenient for the pivot operations and the scope of sensitivity analysis.

Two cases will be considered for sensitivity analysis:

1. Sensitivity of the optimum solution to changes in the availability of the resources (right-hand side of the constraints).

2. Sensitivity of the optimum solution to changes in unit profit or unit cost (coefficients of the objective function).

(I) Graphical Sensitivity Analysis

• Changes in the availability of a resource will move the line corresponding to its constraint parallel to itself. The dual price for a certain resource remains valid for changes (increases or decreases) in the resource that move the line corresponding to its constraint parallel to itself to any point on the line segment corresponding to the other resource constraint related to the optimum solution (corner point). The extreme points of this segment line determine the range of applicability of the given dual price. We call such a range the feasibility range for (the dual price corresponding to) a certain resource.

The dual prices and their feasibility range, determined by using an optimal solution of an LP problem, allow making economic decisions about that problem (when variants of changes in resources are considered).

Example 3.6-1 in JOBCO.pdf illustrates:

1) The computation of the dual price and of the feasibility range of a resource.

2) How the computed dual prices and their feasibility range allow making economic decisions about this LP problem.

• Changes in revenue units (i.e. objective-function coefficients) will change the slope of z. However, the optimum solution will remain in the same corner point so long as the line of the objective function lies between the lines corresponding to the two constraints that define the optimum point. This means that there is a range for the coefficients of the objective function that will keep the optimum solution unchanged at the optimum corner point. If we write z = c1x1 + c2x2 we can obtain the range for c1/c2 by using the data of the lines that contain the optimum point. Furthermore, we can determine the optimality range for c1(c2) by fixing the value for c2(c1). The computation of the optimality range for the unit costs and how the computed optimality ranges can be used for making economic decisions on LP problems are also illustrated for the JOBCO model.

(II) Sensitivity Analysis using the Primal Simplex Method

We start with introducing an equivalent representation for the primal basic form: we write the objective equation as z − ∑cixi = 0, and the constraints equations as ∑aijxj + si = bi, where si denotes the corresponding slack variable.

The primal tableau corresponding to the above basic form will have:

• Its first column is labeled with z; it is followed by columns labeled with the nonbasic variables (as in the previous representation); then we place the columns labeled by the basic variables; the last column, labeled “Solution” (or RHS), contains the constants terms (from the objective function and the right-hand side of the constraint equations).

• The first row is labeled (in the left side) by the objective function (referred to as the z-row), and the other rows are labeled (also in the left side) by the basic variables.

Using this new approach, the simplex algorithm can be reformulated as follows:

Step 1. Determine a starting basic feasible solution (LP problems in which all the constraints are (≤) with nonnegative right-hand sides offer a convenient all-slack starting feasible solution).

Step 2. Select an entering variable using the optimality condition (based on the z-row).

Optimality condition. The entering variable in a maximization (minimization) problem is the nonbasic variable having the most negative (positive) coefficient in the z-row. Ties are broken arbitrarily (or using Bland’s rule). The optimum is reached at the iteration where all the z-row coefficients of the nonbasic variables are nonnegative (nonpositive).

STOP if there is no entering variable; the (last) solution is optimal. Otherwise, go to Step 3.

Step 3. Select a leaving variable using the feasibility condition.

Feasibility condition. For both maximization and minimization problems, the leaving variable is the basic variable associated with the smallest nonnegative ratio (with strictly positive denominator). Ties are broken arbitrarily (or using Bland’s rule).

Step 4. Determine a new basic solution by using the appropriate Gauss-Jordan computations. Go to Step 2.

Gauss-Jordan row operations:

1. Pivot row

a. Replace the (label of the) leaving variable in the Basic column with the (label of the) entering variable.

b. New pivot row = Current pivot row ÷ Pivot element.

2. All other rows, including z

New row = (Current row) − (pivot column coefficient) × (New pivot row).

We use the Reddy Mikks model (Example 3.3-1 in ExSimplex.pdf) to illustrate the new approach.

Changes in the Right-Hand Side

1. Determination of Dual Prices

The z-row in the optimal simplex tableau for a LP problem with ≤ constraints yields directly the dual prices as the coefficients of the slack variables. (For ≥ constraints, the same idea remains applicable except that the dual price will assume the opposite sign of that associated with the ≤ constraint. As for the case where the constraint is an equation, the determination of the dual price from the optimal simplex tableau requires somewhat involved calculations as will be shown in Course 5.)

2. Determination of the Feasibility Conditions and Ranges

To determine the feasibility ranges in a LP problem with all ≤ constraints, we introduce in the right-hand sides of the constraints additional variables Di for changes (positive or negative) in the resources. Then we compute the optimum simplex tableau for this new problem, and derive the conditions that will keep the solution feasible – that is the right-hand side of the optimum tableau remains nonnegative. The individual feasibility ranges result from changing the resources one at a time.

We illustrates the procedure to obtain the dual prices and the feasibility (conditions and) ranges (that keep the dual prices unchanged) using the TOYCO model (Example 3.6-2 in TOYCO1.pdf).

The above results can be summarized as follows:

__________________________________________

1. The dual prices remain valid so long as the changes Di, i= 1, …, m, in the right-hand sides of the constraints satisfy all the feasibility conditions when the changes are simultaneous or fall within the feasibility ranges when the changes are made individually.

2. For other situations where the dual prices are not valid because the simultaneous feasibility conditions are not satisfied or because the individual feasibility ranges are violated, the recourse is to either re-solve the problem with the new values of Di or apply the post-optimal analysis presented in Course 5.

_______________________________________________

Available LP packages usually present this information as standard output. Practically, none provide the case of simultaneous conditions, presumably because its display is cumbersome, particularly for large LP problems.

Changes in the Objective Function

1. Determination of Reduced Costs

The reduced costs can be read in the optimal simplex tableau (z-equation coefficients).

With the given definition of the reduced cost we can now see that an unprofitable variable can be made profitable in two ways:

1. By increasing the unit revenue.

2. By decreasing the unit cost of consumed resources.

In most real-life situations, the price per unit may not be a viable option because its value is dictated by market conditions. The real option then is to reduce the consumption of resources, perhaps by making the production process more efficient.

2. Determination of the Optimality Conditions and Ranges

To determine the conditions that will keep an optimal solution unchanged (in a maximization problem), called the optimality conditions, we introduce additional variables di for the changes (increases or decreases) in unit revenues of the coefficients in the objective function. Then we generate the simplex tableaus using the same sequence of entering and leaving variables as in the original model. The new optimal tableau is exactly the same as the original optimal tableau except that the reduced costs (z-equation coefficients) have changed. This means that changes in the objective-function coefficients can affect the optimality of the problem only.

A convenient way for computing the new reduced costs is to add a new top row and a new leftmost column to the optimal tableau:

• the entries in the top row are the changes dj associated with each variable;

• the entries in the leftmost column are 1 in the z-row and the associated dj in the row of each basic variable (keep in mind that dj = 0 for the slack variables).

Now, to compute the new reduced cost for each variable (or the value of z), multiply the elements of its column by the corresponding elements in the leftmost column, add them up, and subtract the top-row element from the sum.

Note that the application of these computations to the basic variables will always produce a zero reduced cost, a proven theoretical result.

The optimality conditions corresponding to nonbasic variables (in a maximization problem) are obtained by the nonnegativity of the corresponding new reduced costs (z-equation coefficients). These conditions should be satisfied simultaneously to maintain the optimality of the current optimum.

Remark. The only difference in the minimization case is that the reduced costs (z-equation coefficients) must be ≤ 0 to maintain optimality.

The general optimality conditions can be used to determine the individual optimality ranges for di by one at a time changes.

We illustrate the above procedure by using the TOYCO model (TOYCO2.pdf).

The above results can be summarized as follows:

___________________________________________

1. The optimal values of the variables remain unchanged so long as the changes dj, j = 1, …, n, in the objective function coefficients satisfy all the optimality conditions when the changes are simultaneous or fall within the optimality ranges when a change is made individually.

2. For further situations where the simultaneous optimality conditions are not satisfied or the individual ranges are violated, the recourse is to either resolve the problem with the new values of dj or apply the post-optimal analysis presented in Course 5.

___________________________________________

(III) Sensitivity Analysis with Solver

Click Solve in Solver parameters dialogue box.

↓

The new dialogue box Solver results will give you the opportunity to request further details about the solution, including the important sensitivity analysis report (click Sensitivity).

↓

The report will be stored in a separate Excel sheet, as shown by the choices on the bottom of the screen. You can then click Sensitivity Report 1 to view the results.

The output includes:

1. The reduced cost.

2. The shadow (dual) price.

3. The optimality (feasibility) ranges for the changes dj and Di.

To illustrate the Excel Solver sensitivity analysis we use the report for the TOYCO model (in SA_Solver.pdf)

Solution for Homework Week 1 (SpecialCases.pdf)

1. Degeneracy (Problem 1)

2. Alternative optima (Problem 2)

3. Unbounded solutions (Problem 3)

4. Nonexisting (or infeasible) solutions (Problem 4).

Degeneracy

In the application of the feasibility condition of the simplex method, a tie for the minimum ratio may occur and can be broken arbitrarily. When this happens, at least one basic variable will be zero in the next iteration and the new solution is said to be degenerate. In the graphical solution of Problem 1 three lines pass through the optimum point x1 = 0, x2 =2. Because this is a two-dimensional problem, the point is overdetermined and one of the constraints (x1 + 4x2 ≤ 8) is redundant.

From the theoretical standpoint degeneracy has two implications:

• The phenomenon of cycling or circling.

• The solution may be temporarily degenerate. Note that two consecutive iterations (though differing in the basic-nonbasic categorization of the variables) yield identical values for all the variables and the objective value. The computation should not be stopped at the iteration where degeneracy first appears.

From the practical point of view, degeneracy reveals that the model has at least one redundant constraint. In practice, the mere knowledge that some resources are superfluous can be valuable during the implementation of the solution. The information may also lead to discovering irregularities in the construction of the model. Unfortunately, there are no efficient computational techniques for identifying the redundant constraints directly from the tableau.

Alternative Optima

When the objective function is “parallel” to a non-redundant binding constraint (i.e. a constraint that is satisfied as an equation at the optimal solution), the objective function can assume the same optimal value at more than on solution point, thus giving rise to alternative optima. Problem 2 shows that there is an infinite number of optimal solutions (the lines z = 2x1 + x2 and that corresponding to the constraint x1 + 2x2 ≤ 5 are parallel); it also demonstrates the practical significance of encountering such solutions.

In practice, alternative optima are useful because we can choose from many solutions without experiencing deterioration in the objective value.

Unbounded Solution

In some LP models, the values of the variables may be increased indefinitely without violating any of the constraints – meaning that the solution space is unbounded in at least one variable. As a result, the objective value may increase (maximization case) or decrease (in the minimization case) indefinitely. Unboundedness points to the possibility that the model is poorly constructed. The most likely irregularity in such models is that one or more non-redundant constraints have not been accounted for, and the parameters (constants) of some constraints may not have been estimated correctly. In the simplex method unboundedness can be recognized when there is no leaving variable (all the denominators of the ratios of the feasibility conditions are negative or zero). In the graphical solution of Problem 3 the solution space is unbounded in the direction of x2, and the value of z can be increased indefinitely.

Infeasible Solution

LP models with inconsistent constraints have no feasible solution. We notice that this situation can never occur if all the constraints are of the type ≤ with nonnegative right-hand sides because the slack variables provide a feasible solution. For other types of constraints we use artificial variables. Although the artificial variables are penalized in the objective function to force them to zero at the optimum, this can occur only if the model has a feasible space. Otherwise, at least one artificial variable will be positive in the final (optimum) iteration. From the practical point of view, an infeasible space points to the possibility that the model is not correctly formulated. The graphical solution of Problem 4 illustrates such a situation.

More about the Artificial Starting Solution

The procedure for “ill-behaved” LPs with (=) and (≥) constrained is to use artificial variables that play the role of slacks at the first iteration, and then dispose of them legitimately at a later iteration. Two closely related methods are introduced here: the M-method and two-phase method.

M-Method

The M-method starts with the LP equation form. In any equation i which does not have a slack variable (or a variable that can play the role of a slack) we introduce an artificial variable Ri. Then, a starting basic solution is obtained (similar to the convenient all-slack basic solution). However, because the artificial variables are not part of the original LP model, they are assigned a very high penalty in the objective function, thus forcing them (eventually) to equal 0 in the optimum solution. This will always be the case if the problem has a feasible solution.

Penalty rule for artificial variables. Given M, a sufficiently large positive value (mathematically, M → ∞), the artificial variable objective coefficient equals −M in maximization problems and M in minimization problems.

From the standpoint of solving the problem on the computer, M must assume a numeric value. What value of M should we use? The answer depends on the data of the original LP. M should be large relative to the actual objective coefficients of the model, but should not be too large because potential severe round-off errors can result when very large values are manipulated with much smaller values (that may impair the accuracy of the simplex calculations). Chosen M, before proceeding with the simplex method computations, we need to make the z-row consistent with the rest of the tableau by substituting out the artificial variables in the z-row using the appropriate constraint equations.

The application of the M-Method is illustrated using Example 3.4-1 in M-Method.pdf.

Two-Phase Method

Phase I. Put the problem in equation form, and add the necessary artificial variables to the constraints (exactly as in the M-method) to secure a starting basic solution. Next, find a basic solution of the resulting equations that, regardless of whether the LP is maximization or minimization, always minimizes the sum of the artificial variables. If the minimum value of the sum is positive, the LP problem has no feasible solution, which ends the process (recall that a positive artificial variable signifies that an original constraint is not satisfied). Otherwise, proceed to Phase II.

Phase II. Use the feasible solution from Phase I as a starting basic feasible solution of the original problem.

We illustrate the Two-phases method using Example 3.4-2 in Two_Phases.pdf.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download