y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0
IE5001
4
LP Duality: Dakota Example
• The first dual constraint is associated with desks, the second dual constraint with tables, and the third dual constraint with chairs
Primal Problem (or Dual Problem) Maximize z Constraint i form = form ≥ form Variable xj xj ≥ 0 xj unrestricted in sign xj 0
Dual Problem (or Primal Problem)
• Thus, the solution to the Dakota dual will yield optimal
prices for lumber, finishing hours, and carpentry hours
IE5001
7Байду номын сангаас
LP Duality: Shadow Prices
• In summary, when the primal is a normal maximization problem, the dual variables are related to the value of resources available to the decision maker
• Then
• The dual LP is a minimization problem
• A dual variable is defined for each of the m primal constraints and is required to be nonnegative
• A dual constraint is defined for each of the n primal variables and is of “≥” type
Primal Variables
Right-hand
Variables
x1
…
xj
…
xn
y1
a11
…
a1j
…
a1n
y2
a21
…
a2j
…
a2n
…
……………
Side
b1 b2 …
…
……………
…
ym
am1
…
amj
…
amn
bm
c1
…
cj
…
cn
1st Dual
jth Dual
nth Dual
Dual
Constraint
2x1 + 1.5x2 + 0.5x3 ≤ 8
x2
≤5
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
• The dual problem is
(lumber constraint) (finishing constraint) (carpentry constraint) (table demand constraint)
• The decision variable y1 is associated with lumber, y2 with finishing hours, y3 with carpentry hours and y4 with table demands
• Suppose an entrepreneur wants to purchase all of Dakota’s resources. The entrepreneur must determine the price he or she is willing to pay for a unit of each of Dakota’s resources
desk that could be sold for $60. Since the entrepreneur is
offering 8y1 + 4y2 + 2y3 for the resources used to produce a desk, he or she must chose the y variables to satisfy:
• For this pair of LPs, the original LP is called the primal problem, while the other LP is called the dual problem
• Knowledge of the dual problem also provides interesting economic insights
min w = 48y1 + 20y2 + 8y3 + 5y4
s.t.
8y1 + 4y2 + 2y3 ≥ 60 (desk constraint)
6y1 + 2y2 + 1.5y3 + y4 ≥ 30 (table constraint)
y1 + 1.5y2 + 0.5y3 ≥ 20 (chair constraint)
• Objective coefficients of the dual LP are given by RHS of primal constraints
IE5001
10
LP Duality
Let x = (x1, x2,…, xn)T, y = (y1, y2,…, ym)T, c = (c1, c2,…, cn)T, b = (b1, b2,…, bm)T ,
• In setting the resource prices, the prices must be high enough to induce Dakota to sell. They must be nonnegative
IE5001
6
LP Duality: Dakota Example
• The entrepreneur must offer Dakota at least $60 for a
a11 a12 ... a1n
A


a21
a22
...
a2n


am1
am2
...
amn

Primal LP :
Dual LP :
Max z cT x
Min w bT y
s.t. Ax b
s.t. yT A cT
IE5001
x0
y0 11
LP Duality
8y1 + 4y2 + 2y3 ≥ 60
• Similar reasoning shows that at least $30 must be paid
for the resources used to produce a table. Thus the y
variables must satisfy: 6y1 + 2y2 + 1.5y3 + y4 ≥ 30
combination of resources that includes 8 board feet of
lumber, 4 finishing hours, and 2 carpentry hours because
Dakota could, if it wished, use the resources to produce a
min
w b1 y1 b2 y2 ... bm ym
s.t.
a11 y1 a21 y2 ... am1 ym c1
a12 y1 a22 y2 ... am2 ym c2
a1n y1 a2n y2 ... amn ym cn
IE5001
Minimize w
Variable yi
↔
yi ≥ 0
↔
yi unrestricted in sign
↔
yi 0
Constraint j
↔
≥ form
↔
= form
↔
form
IE5001
12
LP Duality: Example
• Consider the following LP
Linear Programming Duality
LP Duality
• For each LP, we can define another LP directly or systematically such that for this pair of LPs, the optimal solution of one LP automatically yields the optimal solution of the other LP
• For this reason, dual variables are often referred to as resource shadow prices
IE5001
8
LP Duality
For every primal LP, we have an associated dual LP
Dual
Constraint
Constraint Objective
IE5001
9
LP Duality
• Assume that the primal LP is a maximization problem with all the constraints being of “” type and all decision variables are assumed to be nonnegative