DUALITY THEORY:THE ESSENCE OF DUALITY THEORY

THE ESSENCE OF DUALITY THEORY

Given our standard form for the primal problem at the left (perhaps after conversion from another form), its dual problem has the form shown to the right.

Thus, with the primal problem in maximization form, the dual problem is in minimization form instead. Furthermore, the dual problem uses exactly the same parameters as the primal problem, but in different locations, as summarized below.

1. The coefficients in the objective function of the primal problem are the right-hand sides

of the functional constraints in the dual problem.

2. The right-hand sides of the functional constraints in the primal problem are the coef- ficients in the objective function of the dual problem.

3. The coefficients of a variable in the functional constraints of the primal problem are the coefficients in a functional constraint of the dual problem.

To highlight the comparison, now look at these same two problems in matrix notation (as introduced at the beginning of Sec. 5.2), where c and y = [y1, y2, . . . , ym] are row vec- tors but b and x are column vectors.

To illustrate, the primal and dual problems for the Wyndor Glass Co. example of Sec. 3.1 are shown in Table 6.1 in both algebraic and matrix form.

The primal-dual table for linear programming (Table 6.2) also helps to highlight the correspondence between the two problems. It shows all the linear programming pa- rameters (the aij, bi, and cj) and how they are used to construct the two problems. All the headings for the primal problem are horizontal, whereas the headings for the dual prob- lem are read by turning the book sideways. For the primal problem, each column (ex- cept the right-side column) gives the coefficients of a single variable in the respective constraints and then in the objective function, whereas each row (except the bottom one) gives the parameters for a single contraint. For the dual problem, each row (except the right-side row) gives the coefficients of a single variable in the respective constraints and then in the objective function, whereas each column (except the rightmost one) gives the parameters for a single constraint. In addition, the right-side column gives the right-hand sides for the primal problem and the objective function coefficients for the dual problem,

whereas the bottom row gives the objective function coefficients for the primal problem and the right-hand sides for the dual problem.

Consequently, we now have the following general relationships between the primal and dual problems.

1. The parameters for a (functional) constraint in either problem are the coefficients of a

variable in the other problem.

2. The coefficients in the objective function of either problem are the right-hand sides for the other problem.

Thus, there is a direct correspondence between these entities in the two problems, as sum- marized in Table 6.3. These correspondences are a key to some of the applications of du- ality theory, including sensitivity analysis.

The Solved Examples section of the book’s website provides another example of us- ing the primal-dual table to construct the dual problem for a linear programming model.

Origin of the Dual Problem

Duality theory is based directly on the fundamental insight (particularly with regard to row 0) presented in Sec. 5.3. To see why, we continue to use the notation introduced in Table 5.9 for row 0 of the final tableau, except for replacing Z* by W* and dropping the asterisks from z* and y* when referring to any tableau. Thus, at any given iteration of the simplex method for the primal problem, the current numbers in row 0 are denoted as shown in the (partial) tableau given in Table 6.4. For the coefficients of x1, x2, . . . , xn, recall that z = (z1, z2, . . . , zn) denotes the vector that the simplex method added to the vector of initial coefficients, -c, in the process of reaching the current tableau. (Do not confuse z with the value of the objective function Z.) Similarly, since the initial coeffi- cients of xn+1, xn+2, . . . , xn+m in row 0 all are 0, y = ( y1, y2, . . . , ym) denotes the vec- tor that the simplex method has added to these coefficients. Also recall [see Eq. (1) in the statement of the fundamental insight in Sec. 5.3] that the fundamental insight led to the following relationships between these quantities and the parameters of the original model:

To illustrate these relationships with the Wyndor example, the first equation gives W = 4y1 + 12y2 + 18y3, which is just the objective function for the dual problem shown in the upper right-hand box of Table 6.1. The second set of equations give z1 = y1 + 3y3 and z2 = 2y2 + 2y3, which are the left-hand sides of the functional constraints for this dual problem. Thus, by subtracting the right-hand sides of these > constraints (c1 = 3 and c2 = 5), (z1 - c1) and (z2 - c2) can be interpreted as being the surplus variables for these functional constraints.

The remaining key is to express what the simplex method tries to accomplish (according to the optimality test) in terms of these symbols. Specifically, it seeks a set of basic variables, and the corresponding BF solution, such that all coefficients in row 0 are non- negative. It then stops with this optimal solution. Using the notation in Table 6.4, this goal is expressed symbolically as follows:

Condition for Optimality:

zj - cj > 0 for j = 1, 2, . . . , n,

yi > 0 for i = 1, 2, . . . , m.

After we substitute the preceding expression for zj, the condition for optimality says that the simplex method can be interpreted as seeking values for y1, y2, . . . , ym such that

But, except for lacking an objective for W, this problem is precisely the dual problem! To complete the formulation, let us now explore what the missing objective should be.

Since W is just the current value of Z, and since the objective for the primal problem is to maximize Z, a natural first reaction is that W should be maximized also. However, this is not correct for the following rather subtle reason: The only feasible solutions for this new problem are those that satisfy the condition for optimality for the primal problem. Therefore, it is only the optimal solution for the primal problem that corresponds to a feasible solution for this new problem. As a consequence, the optimal value of Z in the primal problem is the minimum feasible value of W in the new problem, so W should be minimized. (The full justification for this conclusion is provided by the relationships we de- velop in Sec. 6.3.) Adding this objective of minimizing W gives the complete dual problem.

Consequently, the dual problem may be viewed as a restatement in linear programming terms of the goal of the simplex method, namely, to reach a solution for the primal problem that satisfies the optimality test. Before this goal has been reached, the corresponding y in row 0 (coefficients of slack variables) of the current tableau must be in- feasible for the dual problem. However, after the goal is reached, the corresponding y must be an optimal solution (labeled y*) for the dual problem, because it is a feasible solution that attains the minimum feasible value of W. This optimal solution ( y1*, y2*, . . . , ym*) provides for the primal problem the shadow prices that were described in Sec. 4.7. Fur- thermore, this optimal W is just the optimal value of Z, so the optimal objective function values are equal for the two problems. This fact also implies that cx ::: yb for any x and y that are feasible for the primal and dual problems, respectively.

To illustrate, the left-hand side of Table 6.5 shows row 0 for the respective iterations when the simplex method is applied to the Wyndor Glass Co. example. In each case, row 0 is partitioned into three parts: the coefficients of the decision variables (x1, x2), the coefficients of the slack variables (x3, x4, x5), and the right-hand side (value of Z ). Since the coefficients of the slack variables give the corresponding values of the dual variables ( y1, y2, y3), each row 0 identifies a corresponding solution for the dual problem, as shown in the y1, y2, and y3 columns of Table 6.5. To interpret the next two columns, recall that (z1 - c1) and (z2 - c2) are the surplus variables for the functional constraints in the dual problem, so the full dual problem after augmenting with these surplus variables is

Thus, a negative value for either surplus variable indicates that the corresponding constraint is violated. Also included in the rightmost column of the table is the calculated value of the dual objective function W = 4y1 + 12y2 + 18y3.

As displayed in Table 6.4, all these quantities to the right of row 0 in Table 6.5 already are identified by row 0 without requiring any new calculations. In particular, note in Table 6.5 how each number obtained for the dual problem already appears in row 0 in the spot indicated by Table 6.4.

For the initial row 0, Table 6.5 shows that the corresponding dual solution (y1, y2, y3) = (0, 0, 0) is infeasible because both surplus variables are negative. The first iteration succeeds in eliminating one of these negative values, but not the other. After two it- erations, the optimality test is satisfied for the primal problem because all the dual variables and surplus variables are nonnegative. This dual solution (y , y , y ) = (0, 3, 1) is optimal (as could be verified by applying the simplex method directly to the dual problem), so the optimal value of Z and W is Z * = 36 = W *.

Now let us summarize the newly discovered key relationships between the primal and dual problems.

Weak duality property: If x is a feasible solution for the primal problem and y is a feasible solution for the dual problem, then cx ::: yb.

For example, for the Wyndor Glass Co. problem, one feasible solution is x1 = 3, x2 = 3, which yields Z = cx = 24, and one feasible solution for the dual problem is y1 = 1, y2 = 1, y3 = 2, which yields a larger objective function value W = yb = 52. These are just sample feasible solutions for the two problems. For any such pair of feasible solutions, this inequality must hold because the maximum feasible value of Z = cx (36) equals the min- imum feasible value of the dual objective function W = yb, which is our next property.

Strong duality property: If x* is an optimal solution for the primal problem and y* is an optimal solution for the dual problem, then

cx* = y*b.

Thus, these two properties imply that cx < yb for feasible solutions if one or both of them are not optimal for their respective problems, whereas equality holds when both are optimal.

The weak duality property describes the relationship between any pair of solutions for the primal and dual problems where both solutions are feasible for their respective problems. At each iteration, the simplex method finds a specific pair of solutions for the two problems, where the primal solution is feasible but the dual solution is not feasible (except at the final iteration). Our next property describes this situation and the relation- ship between this pair of solutions.

Complementary solutions property: At each iteration, the simplex method si- multaneously identifies a CPF solution x for the primal problem and a comple- mentary solution y for the dual problem (found in row 0, the coefficients of the slack variables), where

cx = yb.

If x is not optimal for the primal problem, then y is not feasible for the dual problem.

To illustrate, after one iteration for the Wyndor Glass Co. problem, x1 = 0, x2 = 6, and

5

y1 = 0, y2 = , y

= 0, with cx = 30 = yb. This x is feasible for the primal problem, but

2 3

this y is not feasible for the dual problem (since it violates the constraint, y1 + 3y3 > 3).

The complementary solutions property also holds at the final iteration of the simplex

method, where an optimal solution is found for the primal problem. However, more can be said about the complementary solution y in this case, as presented in the next property.

Complementary optimal solutions property: At the final iteration, the simplex method simultaneously identifies an optimal solution x* for the primal problem and a complementary optimal solution y* for the dual problem (found in row 0, the coefficients of the slack variables), where are the shadow prices for the primal problem.

For the example, the final iteration yields

We shall take a closer look at some of these properties in Sec. 6.3. There you will see that the complementary solutions property can be extended considerably further. In partic- ular, after slack and surplus variables are introduced to augment the respective problems, every basic solution in the primal problem has a complementary basic solution in the dual problem. We already have noted that the simplex method identifies the values of the sur- plus variables for the dual problem as zj - cj in Table 6.4. This result then leads to an ad- ditional complementary slackness property that relates the basic variables in one problem to the nonbasic variables in the other (Tables 6.7 and 6.8), but more about that later.

In Sec. 6.4, after describing how to construct the dual problem when the primal prob- lem is not in our standard form, we discuss another very useful property, which is sum- marized as follows:

Symmetry property: For any primal problem and its dual problem, all relation- ships between them must be symmetric because the dual of this dual problem is this primal problem.

Therefore, all the preceding properties hold regardless of which of the two problems is labeled as the primal problem. (The direction of the inequality for the weak duality prop- erty does require that the primal problem be expressed or reexpressed in maximization form and the dual problem in minimization form.) Consequently, the simplex method can be applied to either problem, and it simultaneously will identify complementary solutions (ultimately a complementary optimal solution) for the other problem.

So far, we have focused on the relationships between feasible or optimal solutions in the primal problem and corresponding solutions in the dual problem. However, it is pos- sible that the primal (or dual) problem either has no feasible solutions or has feasible so- lutions but no optimal solution (because the objective function is unbounded). Our final property summarizes the primal-dual relationships under all these possibilities.

Duality theorem: The following are the only possible relationships between the primal and dual problems.

1. If one problem has feasible solutions and a bounded objective function (and so has an optimal solution), then so does the other problem, so both the weak and strong duality properties are applicable.

2. If one problem has feasible solutions and an unbounded objective function (and so no optimal solution), then the other problem has no feasible solutions.

3. If one problem has no feasible solutions, then the other problem has either no feasible solutions or an unbounded objective function.

Applications

As we have just implied, one important application of duality theory is that the dual prob- lem can be solved directly by the simplex method in order to identify an optimal solution for the primal problem. We discussed in Sec. 4.8 that the number of functional constraints affects the computational effort of the simplex method far more than the number of vari- ables does. If m > n, so that the dual problem has fewer functional constraints (n) than the primal problem (m), then applying the simplex method directly to the dual problem instead of the primal problem probably will achieve a substantial reduction in computa- tional effort.

The weak and strong duality properties describe key relationships between the primal and dual problems. One useful application is for evaluating a proposed solution for the pri- mal problem. For example, suppose that x is a feasible solution that has been proposed for implementation and that a feasible solution y has been found by inspection for the dual

problem such that cx = yb. In this case, x must be optimal without the simplex method even being applied! Even if cx < yb, then yb still provides an upper bound on the optimal value of Z, so if yb - cx is small, intangible factors favoring x may lead to its selection without further ado.

One of the key applications of the complementary solutions property is its use in the dual simplex method presented in Sec. 8.1. This algorithm operates on the primal problem exactly as if the simplex method were being applied simultaneously to the dual problem, which can be done because of this property. Because the roles of row 0 and the right side in the simplex tableau have been reversed, the dual simplex method re- quires that row 0 begin and remain nonnegative while the right side begins with some negative values (subsequent iterations strive to reach a nonnegative right side). Conse- quently, this algorithm occasionally is used because it is more convenient to set up the initial tableau in this form than in the form required by the simplex method. Further- more, it frequently is used for reoptimization (discussed in Sec. 4.7), because changes in the original model lead to the revised final tableau fitting this form. This situation is common for certain types of sensitivity analysis, as you will see in the next chapter.

In general terms, duality theory plays a central role in sensitivity analysis. This role is the topic of Sec. 6.5.

Another important application is its use in the economic interpretation of the dual prob- lem and the resulting insights for analyzing the primal problem. You already have seen one example when we discussed shadow prices in Sec. 4.7. Section 6.2 describes how this in- terpretation extends to the entire dual problem and then to the simplex method.