DUALITY THEORY:ADAPTING TO OTHER PRIMAL FORMS

ADAPTING TO OTHER PRIMAL FORMS

Thus far it has been assumed that the model for the primal problem is in our standard form. However, we indicated at the beginning of the chapter that any linear programming problem, whether in our standard form or not, possesses a dual problem. Therefore, this section focuses on how the dual problem changes for other primal forms.

Each nonstandard form was discussed in Sec. 4.6, and we pointed out how it is possible to convert each one to an equivalent standard form if so desired. These conversions are summarized in Table 6.12. Hence, you always have the option of converting any model to our standard form and then constructing its dual problem in the usual way. To illus- trate, we do this for our standard dual problem (it must have a dual also) in Table 6.13. Note that what we end up with is just our standard primal problem! Since any pair of pri- mal and dual problems can be converted to these forms, this fact implies that the dual of the dual problem always is the primal problem. Therefore, for any primal problem and its dual problem, all relationships between them must be symmetric. This is just the sym- metry property already stated in Sec. 6.1 (without proof ), but now Table 6.13 demon- strates why it holds.

One consequence of the symmetry property is that all the statements made earlier in the chapter about the relationships of the dual problem to the primal problem also hold in reverse.

Another consequence is that it is immaterial which problem is called the primal and which is called the dual. In practice, you might see a linear programming problem fit- ting our standard form being referred to as the dual problem. The convention is that the model formulated to fit the actual problem is called the primal problem, regardless of its form.

Our illustration of how to construct the dual problem for a nonstandard primal problem did not involve either equality constraints or variables unconstrained in sign. Actu- ally, for these two forms, a shortcut is available. It is possible to show (see Probs. 6.4-7 and 6.4-2a) that an equality constraint in the primal problem should be treated just like a ::: constraint in constructing the dual problem except that the nonnegativity constraint for the corresponding dual variable should be deleted (i.e., this variable is unconstrained in sign). By the symmetry property, deleting a nonnegativity constraint in the primal prob- lem affects the dual problem only by changing the corresponding inequality constraint to an equality constraint.

Another shortcut involves functional constraints in > form for a maximization problem. The straightforward (but longer) approach would begin by converting each such con- straint to ::: form Constructing the dual problem in the usual way then gives -aij as the coefficient of yi in functional constraint j (which has > form) and a coefficient of -bi in the objec- tive function (which is to be minimized), where yi also has a nonnegativity constraint yi > 0. Now suppose we define a new variable yi' = -yi. The changes caused by ex- pressing the dual problem in terms of yi' instead of yi are that (1) the coefficients of the variable become aij for functional constraint j and bi for the objective function and (2) the constraint on the variable becomes yi' : : : 0 (a nonpositivity constraint). The shortcut is to use yi' instead of yi as a dual variable so that the parameters in the orig- inal constraint (aij and bi) immediately become the coefficients of this variable in the dual problem.

Here is a useful mnemonic device for remembering what the forms of dual constraints should be. With a maximization problem, it might seem sensible for a functional constraint to be in ::: form, slightly odd to be in = form, and somewhat bizarre to be in > form. Similarly, for a minimization problem, it might seem sensible to be in > form, slightly odd to be in = form, and somewhat bizarre to be in ::: form. For the constraint on an individ- ual variable in either kind of problem, it might seem sensible to have a nonnegativity con- straint, somewhat odd to have no constraint (so the variable is unconstrained in sign), and quite bizarre for the variable to be restricted to be less than or equal to zero. Now recall the correspondence between entities in the primal and dual problems indicated in Table 6.3; namely, functional constraint i in one problem corresponds to variable i in the other prob- lem, and vice versa. The sensible-odd-bizarre method, or SOB method for short, says that the form of a functional constraint or the constraint on a variable in the dual problem should be sensible, odd, or bizarre, depending on whether the form for the corresponding entity in the primal problem is sensible, odd, or bizarre. Here is a summary.

The SOB Method for Determining the Form of Constraints in the Dual.3

1. Formulate the primal problem in either maximization form or minimization form, and then the dual problem automatically will be in the other form.

2. Label the different forms of functional constraints and of constraints on individual vari- ables in the primal problem as being sensible, odd, or bizarre according to Table 6.14. The labeling of the functional constraints depends on whether the problem is a maximization problem (use the second column) or a minimization problem (use the third column).

3. For each constraint on an individual variable in the dual problem, use the form that has the same label as for the functional constraint in the primal problem that corre- sponds to this dual variable (as indicated by Table 6.3).

4. For each functional constraint in the dual problem, use the form that has the same la- bel as for the constraint on the corresponding individual variable in the primal prob- lem (as indicated by Table 6.3).

The arrows between the second and third columns of Table 6.14 spell out the corre- spondence between the forms of constraints in the primal and dual. Note that the corre- spondence always is between a functional constraint in one problem and a constraint on an individual variable in the other problem. Since the primal problem can be either a max- imization or minimization problem, where the dual then will be of the opposite type, the second column of the table gives the form for whichever is the maximization problem and the third column gives the form for the other problem (a minimization problem).

To illustrate, consider the radiation therapy example presented at the beginning of Sec. 3.4. To show the conversion in both directions in Table 6.14, we begin with the max- imization form of this model as the primal problem, before using the (original) mini- mization form.

The primal problem in maximization form is shown on the left side of Table 6.15. By using the second column of Table 6.14 to represent this problem, the arrows in this table indicate the form of the dual problem in the third column. These same arrows are used in Table 6.15 to show the resulting dual problem. (Because of these arrows, we have placed the functional constraints last in the dual problem rather than in their usual top position.)

3This particular mnemonic device (and a related one) for remembering what the forms of the dual constraints should be has been suggested by Arthur T. Benjamin, a mathematics professor at Harvey Mudd College. An in- teresting and wonderfully bizarre fact about Professor Benjamin himself is that he is one of the world’s great human calculators who can perform such feats as quickly multiplying six-digit numbers in his head. For a further discussion and derivation of the SOB method, see A. T. Benjamin: “Sensible Rules for Remembering Duals — The S-O-B Method,” SIAM Review, 37(1): 85–87, 1995.

Beside each constraint in both problems, we have inserted (in parentheses) an S, O, or B to label the form as sensible, odd, or bizarre. As prescribed by the SOB method, the label for each dual constraint always is the same as for the corresponding primal constraint.

However, there was no need (other than for illustrative purposes) to convert the pri- mal problem to maximization form. Using the original minimization form, the equivalent primal problem is shown on the left side of Table 6.16. Now we use the third column of Table 6.14 to represent this primal problem, where the arrows indicate the form of the dual problem in the second column. These same arrows in Table 6.16 show the resulting dual problem on the right side. Again, the labels on the constraints show the application of the SOB method.

Just as the primal problems in Tables 6.15 and 6.16 are equivalent, the two dual problems also are completely equivalent. The key to recognizing this equivalency lies in the fact that the variables in each version of the dual problem are the negative of those in the other version (y1'= -y1, y2'= -y2, y3 = -y3'). Therefore, for each version, if the vari- ables in the other version are used instead, and if both the objective function and the constraints are multiplied through by -1, then the other version is obtained. (Problem 6.4-5 asks you to verify this.)

If you would like to see another example of using the SOB method to construct a dual problem, one is given in the Solved Examples section of the book’s website.

If the simplex method is to be applied to either a primal or a dual problem that has any variables constrained to be nonpositive (for example, y3' : : : 0 in the dual problem of Table 6.15), this variable may be replaced by its nonnegative counterpart (for example, y3 = -y3').

When artificial variables are used to help the simplex method solve a primal problem, the duality interpretation of row 0 of the simplex tableau is the following: Since ar- tificial variables play the role of slack variables, their coefficients in row 0 now provide the values of the corresponding dual variables in the complementary basic solution for the dual problem. Since artificial variables are used to replace the real problem with a more convenient artificial problem, this dual problem actually is the dual of the artificial prob- lem. However, after all the artificial variables become nonbasic, we are back to the real primal and dual problems. With the two-phase method, the artificial variables would need to be retained in phase 2 in order to read off the complete dual solution from row 0. With the Big M method, since M has been added initially to the coefficient of each artificial variable in row 0, the current value of each corresponding dual variable is the current co- efficient of this artificial variable minus M.

For example, look at row 0 in the final simplex tableau for the radiation therapy example, given at the bottom of Table 4.12. After M is subtracted from the coefficients of the artificial variables x 4 and x 6, the optimal solution for the corresponding dual problem given in Table 6.15 is read from the coefficients of x3, x 4, and x 6 as (y1, y2, y3') = (0.5, -1.1, 0). As usual, the surplus variables for the two functional constraints are read from the coefficients of x1 and x2 as z1 - c1 = 0 and z2 - c2 = 0.