Transcript 0 - Dalton State College

INTRODUCTION TO OPERATIONS
RESEARCH
Duality Theory
DUALITY THEORY




Every linear programming problem has associated
with it another linear programming problem called
the dual
Major application of duality theory is in the
interpretation and implementation of sensitivity
analysis.
Original linear programming problem will be referred
to as the primal problem and a dual problem will be
introduced.
Will assume that primal problem is in standard
form.
PRIMAL PROBLEM
Maximize
Z = c 1x 1 + … + c nx n
Maximize
Z = cx
Subject to.
a11x1 + … + a1nxn ≤ b1
Subject to
Ax ≤ b
x≥0
am1x1 + … + amnxn ≤ bm
x1 ≤ 0, …, xn ≤ 0
SETTING UP THE DUAL PROBLEM
Primal Problem
Max
Subject to
and





Z = cx
Ax ≤ b
x≥0
Dual Problem
Min
Subject to
and
W = yb
yA ≥ c
y≥0
Coefficients in the objective function of the primal problem are the right-hand
sides of the functional constraints in the dual problem
Right-hand sides of the functional constraints in the primal problem are the
coefficients in the objective function of the dual problem
Coefficients of a variable in the functional constraints of the primal problem
are the coefficients in a functional constraint of a dual problem
Parameters for functional constraints in either problem are the coefficients of
a variable in the other problem
Coefficients in the objective function of either problem are the right-hand sides
for the other problem
DUAL PROBLEM
Primal/Dual Problems for Wyndor Glass Co.
Primal Problem
Maximize
Z = 3x1 + 5x2
Subject to.
x1
≤4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
Dual Problem
Minimize
W = 4y1 + 12y2 + 18y3
Subject to.
y1
+ 3y3 ≥ 3
2y2 + 2y3 ≥ 5
DUAL PROBLEM
Primal/Dual Problems for Wyndor Glass Co
Matrix form:
Max
 x1 
Z  3 5  
x 2 
1 0 
4 
0 2  x1   12

 x   
2

3 2 
18
Min
W   y1 y2
 y1
y2
4 


y3  12
18
1 0 


y3  0 2  3 5
3 2 
PRIMAL-DUAL RELATIONSHIPS

Weak Duality Property



Strong Duality Property



If x is a feasible solution for the primal problem and y is a
feasible solution for the dual problem, then cx ≤ yb.
Wyndor Glass Co. Example: x1 = 3, x2 = 3, then Z = 24, y1 = 1,
y2 = 1, y3 = 2, then W = 52
If x* is an optimal solution for the primal problem and y* is an
optimal solution for the dual problem, then cx* = y*b.
Wyndor Glass Co. Example: x1 = 3, x2 = 3, then Z = 24, y1 = 1,
y2 = 1, y3 = 2, then W = 52
Symmetry Property

The dual of the dual problem is the primal problem
PRIMAL-DUAL RELATIONSHIPS

Complementary Solutions Property





At each iteration, the simplex method simultaneously identifies a CPF
solution x for the primal problem and a complementary solution y for the
dual problem where cx = yb.
If x is not optimal for the primal problem, then y is not feasible for the dual
problem
Wyndor Glass Co. Example: x1 = 0, x2 = 6, then Z = 30, y1 = 0, y2 = 5/2,
y3 = 0, then W = 30.
This is feasible for primal problem but violates constraint in dual problem
Complementary Optimal Solutions Property


At the final iteration, the simplex method simultaneously identifies an
optimal solution for the x* primal problem and a complementary optimal
solution y* for the dual problem cx* = y*b.
The y* contains the shadow prices for the primal problem
DUALITY THEOREM



If one problem has feasible solutions and a bounded
objective function (optimal solution), then so does the
other problem and both the weak and strong duality
properties are applicable
If one problem has feasible solutions and an unbounded
objective function (no optimal solution), then the other
problem has no feasible solutions.
If one problem has no feasible solutions, then the other
problem has either no feasible solutions or an
unbounded objective function.
ECONOMIC INTERPRETATION
Variable
xj
cj
Z
bi
aij
yi
W
Description
Level of activity j
Unit profit from activity j
Total profit from all activities
Amount of resource i available
Amount of resource i consumed by each unit
of activity j
Shadow price for resource I
Value of Z