Page 291 -

DUALITY 271

Min 6x 1 þ 2x 2
s:t:
5x 1 1x 2 13
3x 1 þ 7x 2 9
x 1 ; x 2 0
The dual is the following maximization problem in canonical form:

Max 13u 1 þ 9u 2
s:t:
5u 1 þ 3u 2 6
1u 1 þ 7u 2 2
u 1 ; u 2 0

Although we could state a special set of rules for converting each type of primal
Try Problem 13 for problem into its associated dual, we believe it is easier to first convert any primal
practise in finding the problem into an equivalent problem in canonical form. Then, we follow the proce-
dual of a minimization
problem in canonical dures already established for finding the dual of a maximization or minimization
form. problem in canonical form.
Let us illustrate the procedure for finding the dual of any linear programming
problem by finding the dual of the following minimization problem:
Min 2x 1 3x 2
s:t:
1x 1 þ 2x 2 12
4x 1 2x 2 3
6x 1 1x 2 ¼ 10
x 1 ; x 2 0

For this minimization problem, we obtain the canonical form by converting all
constraints to greater-than-or-equal-to form. The necessary steps are as follows:

Step 1. Convert the first constraint to greater-than-or-equal-to form by
multiplying both sides of the inequality by ( 1). Doing so yields:
x 1 2x 2 12

Step 2. Constraint 3 is an equality constraint. For an equality constraint, we first
create two inequalities: one with form, the other with form. Doing
so yields:

6x 1 1x 2 10
6x 1 1x 2 10

Then, we multiply the constraint by ( 1) to get two constraints.
6x 1 1x 2 10
6x 1 þ 1x 2 10

Now the original primal problem has been restated in the following
equivalent form:

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.