The Dual Problem
Another special class of linear programming problems we
encounter in practical applications is characterized by the
following conditions:
1. The objective function is to be minimized.
2. All the variables involved are nonnegative.
3. All other linear constraints may be written so that the
expression involving the variables is greater than or
equal to a nonnegative constant.
Such problems are called standard minimization
problems.
The Dual Problem
In solving this kind of linear programming problem, it
helps to note that each maximization problem is associated
with a minimization problem, and vice versa.
The given problem is called the primal problem, and the
related problem is called the dual problem.
Finding Dual of a LP problem
Primal Dual
Maximization Minimization
Minimization Maximization
ith variable ith constraint
jth constraint jth variable
Inequality sign of ith Constraint:
xi > 0 if dual is maximization
if dual is minimization
…contd. to next slide
Finding Dual of a LP problem…contd.
Primal Dual
ith variable unrestricted ith constraint with = sign
jth constraint with = sign jth variable unrestricted
RHS of jth constraint Cost coefficient associated with jth
variable in the objective function
Cost coefficient associated
with ith variable in the RHS of ith constraint constraints
objective function
Refer class notes for pictorial representation of all the operations
Example
Write the dual problem associated with this problem:
Minimize C 6x 8 y
subject to 40 x 10 y 2400
10 x 15 y 2100 Primal
Problem
5 x 15 y 1500
x, y 0
We first write down a tableau for the primal problem:
x y Constant
40 10 2400
10 15 2100
5 15 1500
6 8
Example
x y Constant
40 10 2400
10 15 2100
5 15 1500
6 8
Next, we interchange the columns and rows of the tableau
and head the three columns of the resulting array with the
three variables u, v, and w, obtaining
u v w Constant
40 10 5 6
10 15 15 8
2400 2100 1500
Example
u v w Constant
40 10 5 6
10 15 15 8
2400 2100 1500
Consider the resulting tableau as if it were the initial
simplex tableau for a standard maximization problem.
From it we can reconstruct the required dual problem:
Maximize P 2400u 2100v 1500w
subject to 40u 10v 5w 6 Dual
10u 15v 15w 8 Problem
u, v , w 0
Theorem 1
The Fundamental Theorem of Duality
A primal problem has a solution if and only if the
corresponding dual problem has a solution.
Furthermore, if a solution exists, then:
a. The objective functions of both the primal and
the dual problem attain the same optimal value.
b. The optimal solution to the primal problem
appears under the slack variables in the last row
of the final simplex tableau associated with the
dual problem.
Example
Complete the solution of the problem from our last example:
Maximize P 2400u 2100v 1500w
subject to 40u 10v 5w 6 Dual
10u 15v 15w 8 Problem
u, v , w 0
Example
Solution
The dual problem associated with the given primal
problem is a standard maximization problem.
Thus, we can proceed with the simplex method.
First, we introduce to the system of equations the slack
variables x and y, and restate the inequalities as equations,
obtaining
40u 10v 5w x 6
10u 15v 15w y 8
2400u 2100v 1500 w P0
Example
Solution
Next, we transcribe the coefficients of the system of
equations
40u 10v 5w x 6
10u 15v 15w y 8
2400u 2100v 1500w P0
into an initial simplex tableau:
u v w x y P Constant
40 10 5 1 0 0 6
10 15 15 0 1 0 8
–2400 –2100 –1500 0 0 1 0
Example
Solution
Continue with the simplex iterative method until a final
tableau is obtained with the solution for the problem:
u v w x y P Constant
1 0 –3/20 3/100 –1/50 0 1/50
0 1 11/10 –1/50 2/25 0 13/25
0 0 450 30 120 1 1140
Solution for the
primal problem
The fundamental theorem of duality tells us that the
solution to the primal problem is x = 30 and y = 120, with a
minimum value for C of 1140.
Write the dual problem anf then solve it.
Min z = 2x1 + x2
s.t.
3x1 + x2 ≥ 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 3
xi ≥ 0
Example
Primal Dual
min 7 x1 x2 5 x3 max 10 y1 6 y2
s.t. x1 x2 3 x3 10 s.t. y1 5 y2 7
5 x1 2 x2 x3 6 y1 2 y2 1
x1 , x2 , x3 0 3 y1 y2 5
y1 , y2 0
Example
Primal Dual
min 7 x1 x2 5 x3 max 10 y1 6 y2
s.t. x1 x2 3 x3 10 s.t. y1 5 y2 7
5 x1 2 x2 x3 6 y1 2 y2 1
x1 , x2 , x3 0 3 y1 y2 5
y1 , y2 0
x=(7/4,0,11/4) and y=(2,1) are feasible solutions
7*7/4 + 0 + 5*11/4 = 10*2 + 6*1 = 26
Thus, x and y are optimal
