DUALITY THEORY:THE ROLE OF DUALITY THEORY IN SENSITIVITY ANALYSIS

THE ROLE OF DUALITY THEORY IN SENSITIVITY ANALYSIS

As described further in the next chapter, sensitivity analysis basically involves investigating the effect on the optimal solution if changes occur in the values of the model pa- rameters aij, bi, and cj. However, changing parameter values in the primal problem also changes the corresponding values in the dual problem. Therefore, you have your choice of which problem to use to investigate each change. Because of the primal-dual rela- tionships presented in Secs. 6.1 and 6.3 (especially the complementary basic solutions property), it is easy to move back and forth between the two problems as desired. In some cases, it is more convenient to analyze the dual problem directly in order to de- termine the complementary effect on the primal problem. We begin by considering two such cases.

Changes in the Coefficients of a Nonbasic Variable

Suppose that the changes made in the original model occur in the coefficients of a vari-ble that was nonbasic in the original optimal solution. What is the effect of these changes on this solution? Is it still feasible? Is it still optimal?

Because the variable involved is nonbasic (value of zero), changing its coefficients cannot affect the feasibility of the solution. Therefore, the open question in this case is whether it is still optimal. As Tables 6.10 and 6.11 indicate, an equivalent question is whether the complementary basic solution for the dual problem is still feasible after these changes are made. Since these changes affect the dual problem by changing only one constraint, this question can be answered simply by checking whether this complementary basic so- lution still satisfies this revised constraint.

We shall illustrate this case in the corresponding subsection of Sec. 7.2 after devel- oping a relevant example. The Solved Examples section of the book’s website also gives another example for both this case and the next one.

Introduction of a New Variable

As indicated in Table 6.6, the decision variables in the model typically represent the levels of the various activities under consideration. In some situations, these activities were selected from a larger group of possible activities, where the remaining activities were not included in the original model because they seemed less attractive. Or perhaps these other activities did not come to light until after the original model was formulated and solved. Either way, the key question is whether any of these previously unconsidered activities are sufficiently worthwhile to warrant initiation. In other words, would adding any of these activities to the model change the original optimal solution?

Adding another activity amounts to introducing a new variable, with the appropriate coefficients in the functional constraints and objective function, into the model. The only resulting change in the dual problem is to add a new constraint (see Table 6.3).

After these changes are made, would the original optimal solution, along with the new variable equal to zero (nonbasic), still be optimal for the primal problem? As for the preceding case, an equivalent question is whether the complementary basic solution for the dual problem is still feasible. And, as before, this question can be answered simply by checking whether this complementary basic solution satisfies one constraint, which in this case is the new constraint for the dual problem.

To illustrate, suppose for the Wyndor Glass Co. problem introduced in Sec. 3.1 that a possible third new product now is being considered for inclusion in the product line. Letting xnew represent the production rate for this product, we show the resulting revised model as follows:

After we introduced slack variables, the original optimal solution for this problem with- out xnew (given by Table 4.8) was (x1, x2, x3, x4, x5) = (2, 6, 2, 0, 0). Is this solution, along with xnew = 0, still optimal?

To answer this question, we need to check the complementary basic solution for the dualproblem. As indicated by the complementary optimal basic solutions property in Sec. 6.3, this solution is given in row 0 of the final simplex tableau for the primal problem, using the locations shown in Table 6.4 and illustrated in Table 6.5. Therefore, as given in both the bottom row of Table 6.5 and the sixth row of Table 6.9, the solution is (Alternatively, this complementary basic solution can be derived in the way that was illustrated in Sec. 6.3 for the complementary basic solution in the next-to-last row of Table 6.9.)

Since this solution was optimal for the original dual problem, it certainly satisfies the original dual constraints shown in Table 6.1. But does it satisfy this new dual constraint?

is satisfied, so this dual solution is still feasible (and thus still optimal). Consequently, the original primal solution (2, 6, 2, 0, 0), along with xnew = 0, is still optimal, so this third possible new product should not be added to the product line.

This approach also makes it very easy to conduct sensitivity analysis on the coefficients of the new variable added to the primal problem. By simply checking the new dual constraint, you can immediately see how far any of these parameter values can be changed before they affect the feasibility of the dual solution and so the optimality of the primal solution.

Other Applications

Already we have discussed two other key applications of duality theory to sensitivity analy- sis, namely, shadow prices and the dual simplex method. As described in Secs. 4.7 and 6.2, the optimal dual solution (y1*, y2*, . . . , ym*) provides the shadow prices for the respective resources that indicate how Z would change if (small) changes were made in the bi (the resource amounts). The resulting analysis will be illustrated in some detail in Sec. 7.2.

In more general terms, the economic interpretation of the dual problem and of the sim- plex method presented in Sec. 6.2 provides some useful insights for sensitivity analysis.

When we investigate the effect of changing the bi or the aij values (for basic variables), the original optimal solution may become a superoptimal basic solution (as de- fined in Table 6.10) instead. If we then want to reoptimize to identify the new optimal solution, the dual simplex method (discussed at the end of Secs. 6.1 and 6.3) should be applied, starting from this basic solution. (This important variant of the simplex method will be described in Sec. 8.1.)

We mentioned in Sec. 6.1 that sometimes it is more efficient to solve the dual prob- lem directly by the simplex method in order to identify an optimal solution for the pri- mal problem. When the solution has been found in this way, sensitivity analysis for the primal problem then is conducted by applying the procedure described in Sections 7.1 and 7.2 directly to the dual problem and then inferring the complementary effects on the primal problem (e.g., see Table 6.11). This approach to sensitivity analysis is rela- tively straightforward because of the close primal-dual relationships described in Secs. 6.1 and 6.3.