Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

29.4 Duality

We have proven that, under certain assumptions, SIMPLEX will terminate. We have not yet shown that it actually finds the optimal solution to a linear program, however. In order to do so, we introduce a powerful concept called linear-programming duality.

Duality is a very important property. In an optimization problem, the identification of a dual problem is almost always coupled with the discovery of a polynomial-time algorithm. Duality is also powerful in its ability to provide a proof that a solution is indeed optimal.

For example, suppose that, given an instance of a maximum-flow problem, we find a flow f of value |f|. How do we know whether f is a maximum flow? By the max-flow min-cut theorem (Theorem 26.7), if we can find a cut whose value is also |f|, then we have verified that f is indeed a maximum flow. This is an example of duality: given a maximization problem, we define a related minimization problem such that the two problems have the same optimal objective values.

Given a linear program in which the objective is to maximize, we shall describe how to formulate a dual linear program in which the objective is to minimize and whose optimal value is identical to that of the original linear program. When referring to dual linear programs, we call the original linear program the primal.

Given a primal linear program in standard form, as in (29.16)-(29.18), we define the dual linear program as

minimize

(29.86)

subject to

(29.87)

(29.88)

To form the dual, we change the maximization to a minimization, exchange the roles of the right-hand sides and the objective-function coefficients, and replace the less-than-or-equal-to by a greater-than-or-equal-to. Each of the m constraints in the primal has an associated variable y_i in the dual, and each of the n constraints in the dual has an associated variable x_j in the primal. For example, consider the linear program given in (29.56)-(29.60). The dual of this linear program is

minimize

(29.89)

subject to

(29.90)

(29.91)

(29.92)

(29.93)

We will show, in Theorem 29.10, that the optimal value of the dual linear program is always equal to the optimal value of the primal linear program. Further-more, the simplex algorithm actually implicitly solves both the primal and the dual linear programs simultaneously, thereby providing a proof of optimality.

We begin by demonstrating weak duality, which states that any feasible solution to the primal linear program has a value no greater than that of any feasible solution to the dual linear program.

Lemma 29.8: (Weak linear-programming duality

Let be any feasible solution to the primal linear program in (29.16)-(29.18) and let be any feasible solution to the dual linear program in (29.86)-(29.88). Then

Proof We have

Corollary 29.9

Let be a feasible solution to a primal linear program (A, b, c), and let be a feasible solution to the corresponding dual linear program. If

then and are optimal solutions to the primal and dual linear programs, respectively.

Proof By Lemma 29.8, the objective value of a feasible solution to the primal cannot exceed that of a feasible solution to the dual. The primal linear program is a maximization problem and the dual is a minimization problem. Thus, if feasible solutions and have the same objective value, neither can be improved.

Before proving that there always is a dual solution whose value is equal to that of an optimal primal solution, we describe how to find such a solution. When we ran the simplex algorithm on the linear program in (29.56)-(29.60), the final iteration yielded the slack form (29.75)-(29.78) with B = {1, 2, 4} and N = {3, 5, 6}. As we shall show below, the basic solution associated with the final slack form is an optimal solution to the linear program; an optimal solution to linear program (29.56)-(29.60) is therefore , with objective value (3 · 8) + (1 · 4) + (2 · 0) = 28. As we shall also show below, we can read off an optimal dual solution: the negatives of the coefficients of the primal objective function are the values of the dual variables. More precisely, suppose that the last slack form of the primal is

Then an optimal dual solution is to set

(29.94)

Thus, an optimal solution to the dual linear program defined in (29.89)-(29.93) is (since n + 1 = 4 ∈ B), , and . Evaluating the dual objective function (29.89), we obtain an objective value of (30 · 0) + (24 · (1/6)) + (36 · (2/3)) = 28, which confirms that the objective value of the primal is indeed equal to the objective value of the dual. Combining these calculations with Lemma 29.8, we have a proof that the optimal objective value of the primal linear program is 28. We now show that in general, an optimal solution to the dual, and a proof of the optimality of a solution to the primal, can be obtained in this manner.

Theorem 29.10: (Linear-programming duality)

Suppose that SIMPLEX returns values on the primal linear program (A, b, c). Let N and B denote the nonbasic and basic variables for the final slack form, let c′ denote the coefficients in the final slack form, and let be defined by equation (29.94). Then is an optimal solution to the primal linear program, is an optimal solution to the dual linear program, and

(29.95)

Proof By Corollary 29.9, if we can find feasible solutions and that satisfy equation (29.95), then and must be optimal primal and dual solutions. We shall now show that the solutions and described in the statement of the theorem satisfy equation (29.95).

Suppose that we run SIMPLEX on a primal linear program, as given in lines (29.16)-(29.18). The algorithm proceeds through a series of slack forms until it terminates with a final slack form with objective function

(29.96)

Since SIMPLEX terminated with a solution, by the condition in line 2 we know that

(29.97)

If we define

(29.98)

we can rewrite equation (29.96) as

(29.99)

For the basic solution associated with this final slack form, for all j ∈ N, and z = v′. Since all slack forms are equivalent, if we evaluate the original objective function on , we must obtain the same objective value, i.e.,

(29.100)

(29.101)

We shall now show that , defined by equation (29.94), is feasible for the dual linear program and that its objective value equals . Equation (29.100) says that the first and last slack forms, evaluated at , are equal. More generally, the equivalence of all slack forms implies that for any set of values x = (x₁, x₂, ..., x_n), we have

Therefore, for any set of values x, we have

so that

(29.102)

Applying Lemma 29.3 to equation (29.102), we obtain

(29.103)

(29.104)

By equation (29.103), we have that , and hence the objective value of the dual is equal to that of the primal (v′). It remains to show that the solution is feasible for the dual problem. From (29.97) and (29.98), we have that for all j = 1, 2, ..., n + m. Hence, for any i = 1, 2, ..., m, (29.104) implies that

which satisfies the constraints (29.87) of the dual. Finally, since for each j ∈ N ∪ B, when we set according to equation (29.94), we have that each , and so the nonnegativity constraints are satisfied as well.

We have shown that, given a feasible linear program, if INITIALIZE-SIMPLEX returns a feasible solution, and if SIMPLEX terminates without returning "unbounded," then the solution returned is indeed an optimal solution. We have also shown how to construct an optimal solution to the dual linear program.

Exercises 29.4-1

Formulate the dual of the linear program given in Exercise 29.3-4.

Exercises 29.4-2

Suppose that we have a linear program that is not in standard form. We could produce the dual by first converting it to standard form, and then taking the dual. It would be more convenient, however, to be able to produce the dual directly. Explain how, given an arbitrary linear program, we can directly take the dual of that linear program.

Exercises 29.4-3

Write down the dual of the maximum-flow linear program, as given in lines (29.47)-(29.50). Explain how to interpret this formulation as a minimum-cut problem.

Exercises 29.4-4

Write down the dual of the minimum-cost-flow linear program, as given in lines (29.51)-(29.55). Explain how to interpret this problem in terms of graphs and flows.

Exercises 29.4-5

Show that the dual of the dual of a linear program is the primal linear program.

Exercises 29.4-6

Which result from Chapter 26 can be interpreted as weak duality for the maximum-flow problem?