338 ACTIVITY 16:



Math 438 ACTIVITY 18: Duality in linear programming

WHY: Duality (interchange of roles for certain objects) is an idea that shows up in a number of mathematical situations. In linear programming, it relates two problems in such a way that the solution to one gives the solution to the other, which may be of great interest if one is easier to solve [in particular, if artificial variables are not needed for one of the problems] . The results also give important information useful for "what–if" decision–making based on the optimal solution of a problem.

LEARNING OBJECTIVES:

1. Discover how to set up the dual of a linear programming problem.

2. Discover how to read the solution to the dual problem from the final simplex tableau of the primal problem [and vice versa].

3. Understand the interpretation of the variables in the dual problem.

VOCABULARY:

Dual Problem

The dual to an LP problem in standard form [minimize CTX subject to AX = b, X ≥ 0] is the LP problem

maximize bTY subject to ATY ≤ C.

[Note the coefficients of the objective swap roles with the constants of the constraints, "minimize" becomes "maximize" , we get "≤" inequalities and we transpose the matrix – we do not have a Y ≥ 0 condition – to put the dual into standard form will require some changes in variables to recover this condition.

If we put the dual problem into standard form and take its dual, we get the original problem – the "primal" problem – back again – “The dual of the dual is the primal”]

Symmetric Primal Problem

A symmetric primal problem is an LP problem of the form minimize CTX subject to AX ≥ b, X ≥ 0

[Minimize, with ≥ constraints]

Symmetric Dual Problem

A symmetric dual problem has the form maximize bTY subject to ATY ≤ C, Y ≥ 0

[Maximize with ≤ constraints]

[Note – the dual of a symmetric primal problem is a symmetric dual – and the dual of a symmetric dual is a symmetric primal. In these cases the X ≥ 0 ( Y ≥0) condition is retained]

Weak Duality Theorem

If both the primal and dual problems [notation as in the definition] are feasible then

bTY ≤ CTX for all X ≥ 0 such that AX = b and for all Y such that ATY ≤ C.

[All feasible values (values from feasible solutions – not the actual solutions) for the objective of the dual [the “maximize”] are less than or equal to all feasible values for the objective of the primal [the “minimize”] – so the problems cannot be unbounded]

Corollary to the Weak Duality Theorem

If there is an optimal solution for the primal problem [primal problem is feasible and bounded] then there is an optimal solution to its dual and the respective objective function values of these two solutions are equal.

Duality Theorem

If P represents the original LP problem and D represents its dual problem then:

1. if either P or D has an optimal solution, then both have optimal solutions and min CTX = max bTY.

2. if P is unbounded then D is infeasible.

3. if D is unbounded then P is infeasible.

4. both P and D can be infeasible.

CRITERIA:

1. Quality of the answers to the Critical Thinking Questions.

2. Accuracy of the answers to the Furnco problem.

METHODOLOGY for using the dual:

1. Put problem in Standard Form As usual – change to "minimize" if necessary, add slack or surplus variables as needed, clean up variables (unrestricted or negative) to have the form : Min CTX where AX = b, X ≥ 0.

2. Determine C, b, A, AT Identify the coefficients of the objective function C and of the constraints A and the right hand sides of the constraints b.

3. Write the Dual Problem Write the dual problem: maximize bTY subject to ATY ≤ C. and adjust/replace/add variables as necessary to regain the Y ≥ 0 condition

4. Check Work Find the dual form of the dual problem (requires standard form) and check that it is the primal.

5. Solve Primal or Dual Use the Simplex Method to solve the easier of the two forms to solve.

6. Add new bottom row Add a row to the simplex tableau in which the objective function coefficients are added to the existing bottom row [as in the SIMPLEX program]

7. Read Dual Solution The solution of the dual (whichever you didn't solve) consists of the entries in the new tableau row under the original identity matrix (under the B–1 matrix in the final tableau)

RESOURCES:

1. Section 3.6: Strategic Mathematics, especially example 3.23.

2. The setup and solution to the Furnco problem (last class)

3. 30 minutes

PLAN:

1. Look over the mode and answer the Critical Thinking Questions.

2. Set up and solve the dual of the Furnco problem

MODEL :

1. Put in Standard Form Add slack or surplus variables to put a problem in the form: Min CTX where AX = b, X ≥ 0.

Standard form:

minimize –2x1 + x2 – 3x3 minimize –2x1 + x2 – 3x3

subj to: x1 – x2 + 4x3 ≤ 1 subj to: x1 – x2 + 4x3 + x4 = 1

2x1 + x2 – x3 ≤ 10 2x1 + x2 – x3 + x5 = 10

–x1 + x2 – x3 ≤ 8 –x1 + x2 – x3 + x6 = 8

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 xi ≥ 0 for all i

2. Determine C, b, A, AT Identify the coefficients of the objective function C and of the constraints A and the right hand sides of the constraints b.

C T = [–2 1 –3 0 0 0] bT = [1 10 8] A = [pic] AT = [pic]

3. Write the Dual Problem State the dual problem in the form maximize bTY subject to ATY ≤ C.

[There is a y–variable for each constraint on the x's and a constraint on the y's for each x–variable. The right–hand sides of the primal constraints give the dual objective coefficients, and the primal objective coefficients give the dual right–hand sides.]

maximize y1 + 10y2 + 8y3

subj. to: y1 + 2y2 – y3 ≤ –2

–y1 + y2 + y3 ≤ 1

4y1 – y2 – y3 ≤ –3

y1 ≤ 0

y2 ≤ 0

y3 ≤ 0

4. Check Work Find the dual form of the dual problem and check that it is the primal.

The dual of the dual is obtained by putting the dual in standard form and applying the duality process. We first make the variables in the dual non–negative by replacing each by its negative (keeping the same name – “New yi = – Old yi”). We also multiply the inequalities with negative right hand sides by –1 (as usual) to get:

Standard Form

maximize – y1 – 10y2 – 8y3 minimize y1 + 10y2 + 8y3

subj to: y1 + 2y2 – y3 ≥ 2 subj to: y1 + 2y2 – y3 – y4 = 2

y1 – y2 – y3 ≤ 1 y1 – y2 – y3 + y5 = 1

4y1 – y2 – y3 ≥ 3 4y1 – y2 – y3 – y6 = 3

yi ≥ 0 yi ≥ 0

[Notice that solving this would require artificial variables in the first and third constraints]

We now apply the duality process to the standard form of the dual problem above to get:

–maximize 2x1 + x2 + 3x3

subject to x1 + x2 + 4x3 ≤ 1 Since x1 and x3 are ≥ 0 and x2 is ≤ 0

2x1 – x2 – x3 ≤ 10 we can change the sign of x2 [as before – make up a “New x2“ equal to “– Old x2“]

–x1 – x2 – x3 ≤ 8 Mechanically, we replace x2 with – x2 everywhere in the problem.

–x1 ≤ 0 The resulting problem is exactly the one we started with – as claimed. .

x2 ≤ 0

–x3 ≤ 0

5. Solve Primal or Dual Use the Simplex Method to solve the easier of the two forms to solve.

The primal is easier to solve since no artificial variables are needed. Then first and last tableaus are as follows:

[pic] [pic]

6. Form z Vector Add objective function coefficients to the bottom row of the final solution tableau.

new row: = [–2 1 –5 –1.33 –.33 0]

7. Read Dual Solution Read the coordinates of the solution to the dual (of the solved problem – in this case it really is the dual of our original problem] under the columns which were the identity columns in original Phase II tableau.

The identity columns of the original tableau correspond to the slack variables x4, x5, and x6. Thus the solution to the dual problem is y1 = –1.33, y2 = –.33, y3 = 0, (thus y4, y5, y6 are non–basic) and z = –4.67.

DISCUSSION:

Step 1. Put in Standard Form

In order to solve a problem using the simplex method we must replace the constraint inequalities by equalities. This is what is done by converting the problem to standard form. Doing this increases the dimension of the feasible region, but there is a 1–1 correspondence between the extreme points of the original feasible region and those of the new feasible region. Thus, solutions to the problem in standard form yield solutions to the original problem.

Step 2. Determine C, b, A, AT

We need these vectors and matrices to form the dual problem. Recall that C is the vector of objective function coefficients, b is the vector of right hand sides of the constraints, A is the matrix of coefficients of the constraints of the standard form of the problem.

Step 3. Write the Dual Problem

It is easy to write the dual problem from the standard form of the primal problem. The coefficients of the dual variables in the objective function are the right hand sides of the primal constraints. thus there are as many dual variables as there are primal constraints. The dual constraints are formed using the matrix AT as the dual constraint coefficient matrix. All the dual constraints are of the form ≤ and the right hand sides of the dual constraints are the coefficients of the primal objective function. Thus, there are as many dual constraints as there are variables in the standard form of the primal problem.

Step 4. Check Work

The best way to check that you have completed the duality process correctly is to perform the duality process on the dual problem after converting it to standard form. You should get the original problem back again. This is inherent in all duality situations: the dual of the dual is the original problem.

Step 5. Solve Primal or Dual

One of the advantages of determining the dual of a linear programming problem is that it may be easier to solve than the original problem. If you anticipate having to add artificial variables to solve a problem, it may be that the dual form is solvable without needing artificial variables. This is always true when the two problems are in symmetric primal and symmetric dual forms. Whichever form you choose to solve, you must apply the simplex method to obtain the solution.

Step 6. Form added row to tableau

Because the solution of the dual problem is the vector CBTB–1 and the bottom row of the final solution tableau is CBTB–1A – CT, we can compute CBTB–1 by adding the coefficients of objective function variables to the bottom row of the final solution tableau. This vector, denoted z = CBTB–1A, is the next to last row in each tableau from the Simplex program. The elements of z which correspond to the identity columns in the initial tableau will be the solutions to the dual problem. Why? If you have a two–phase problem, you have to compute the overall B–1 (B2–1 B1–1= and compute CBTB–1 directly to get the solution to the dual of the original problem. You can't read it off the final tableau.

Step 7. Read Dual Solution

See the discussion of the last step to see how to read the dual solution from the final solution tableau. In some cases the values read are actually the negatives of the true dual solutions. This situation occurs when the original problem was in maximize form. When in doubt, simply compute CBTB–1 directly.

In general, if a constraint is a "≤" constraint, representing a limitation on a resource to be used (in making a profit) the corresponding dual variable represents the price per unit that a buyer would have to offer to buy the resource (from the person using it. The buyer – the dual player – would like to keep this small) – the unit value (in context) of the resource. For a "≥" constraint (a requirement of a minimum level to be achieved) the corresponding dual variable indicates the benefit per unit to the buyer (who would like to see this larger).

EXERCISE:

Write the dual of the Furnco problem, identify the necessary matrices and vectors and write the solution of the dual problem from the printed SIMPLEX solution – do not re–do the work of solution.

CRITICAL THINKING QUESTIONS:

1. In model I, if x4, x5, and x6 were actual problem variables with objective function coefficients of 1, –2, 3, what would the dual problem be?

2. Why do we read the dual solution from the components of z corresponding to identity columns in the original tableau?

3. If we rewrite the objective function in Model 1 as –max 2x1 – x2 + 3x3 then the problem is in symmetric dual form. Verify that its symmetric primal form is equal to the dual we computed in step 3 of Model 1.

4. Why does it make sense that the variable y2 – which represents the amount that Furnco's buyer is willing to pay for labor – has a value of 0?

5. Which was the most difficult step in the methodology to understand? Can you reword it and its discussion to make it clearer?

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

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

Google Online Preview   Download