Page 286 -

266 CHAPTER 6 SIMPLEX-BASED SENSITIVITY ANALYSIS AND DUALITY

6.2 Duality

Every linear programming problem has an associated linear programming problem
called the dual problem. Referring to the original formulation of the linear pro-
gramming problem as the primal problem, we will see how the primal can be
converted into its corresponding dual. Then we will solve the dual linear program-
George B. Dantzig and ming problem and interpret the results. A fundamental property of the primal–dual
Alex Orden presented relationship is that the optimal solution to either the primal or the dual problem also
their paper at a provides the optimal solution to the other. In cases where the primal and the dual
symposium in 1951
‘A duality theorem based problems differ in terms of computational difficulty, we can choose the easier
on the Simplex method’. problem to solve.
Let us return to the HighTech Industries problem. The original formulation – the
primal problem – is as follows:
Max 50x 1 þ 40x 2
s:t:
3x 1 þ 5x 2 150 Assembly time
1x 2 20 UltraPortable display
8x 1 þ 5x 2 300 Warehouse space
x 1 ; x 2 0

A maximization problem with all less-than-or-equal-to constraints and non-
negativity requirements for the variables is said to be in canonical form. For a
maximization problem in canonical form, such as the HighTech Industries prob-
lem, the conversion to the associated dual linear programme is relatively
easy. Let us state the dual of the HighTech problem and then identify the steps
taken to make the primal–dual conversion. The HighTech dual problem is as
follows:
Min 150u 1 þ 20u 2 þ 300u 3
s:t:
3u 1 þ 8u 3 50
5u 1 þ 1u 2 þ 5u 3 40
u 1 ; u 2 ; u 3 0
This canonical form for a minimization problem is a minimization problem with all
greater-than-or-equal-to constraints and nonnegativity requirements for the varia-
bles. So, the dual of a maximization problem in canonical form is a minimization
problem in canonical form. The variables u 1 , u 2 and u 3 are referred to as dual
variables.
With the preceding example in mind, we make the following general statements
about the dual of a maximization problem in canonical form.
1 The dual is a minimization problem in canonical form.
2 When the primal has n decision variables (n ¼ 2 in the HighTech problem),
the dual will have n constraints. The first constraint of the dual is associated
with variable x 1 in the primal, the second constraint in the dual is associated
with variable x 2 in the primal and so on.
3 When the primal has m constraints (m ¼ 3 in the HighTech problem), the
dual will have m decision variables. Dual variable u 1 is associated with the first
primal constraint, dual variable u 2 is associated with the second primal
constraint and so on.

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.