MA224: Lecture 14

MA224: Lecture 14
Feng Chen
Apr 15,2014
1
Where Can We Read Dual Variables?
Read dual variables from row zero.
Generally, simplex method starts from the following table.
x −OBJ
r(x) c
0
xB A
b
(1)
Note that here I use r(x) to denote the checking number corresponding to variable x.
After pivoting process, we have
xB
xN
T
r(x) 0 · · · 0 cN − cTB B −1 N
xB Im×m
B −1 N
−OBJ
−cTB B −1 b
B −1 b
(2)
T B −1 )e = −y .
For a nonbasic variable , such as xNk , if cNk = 0, and Nk = eq , then rxnk = −(CB
q
q
Here, yq is the q-th dual variable. This means we can read the value of yq from the entry related
to xNk in the checking row after pivoting process.
Read dual variables from checking row zero after Big-M method has been used.
Recall that for Big-M method, we introduce artificial variables xa with constraint coeﬃcients
of unit vector eTi = (0, · · · , 0, 1, 0, · · · , 0) (the i-th entry is 1). Suppose artificial variable xa corresponding to a unit vector eu . Because ca = −M (for standard max LP). Therefore, r(xa ) =
ca − cTB B −1 eu = ca − y T eu = −M − yu . This implies that yu = −M − ra . (r(xa ) is the value related
to variable xa in checking row 0).
According to the similar analysis, you can obtain the optimal dual variables (cTB B −1 ) from
the optimal table for primal LP, while we use Big − M method to solve standard min LP, or use
two-phase method to solve standard max or min LP.
1
2
Complimentary Slackness
Consider LP PLP and its dual, DLP.
P LP )max cT x
s.t. Ax ≤ b
x≥0
DLP )min y T b
s.t. y T A ≥ cT
y≥0
Suppose A ∈ Rm×n . We can convert above two programs to be standard by introducing slack
variables s ∈ Rm to PLP, and excess variables, e ∈ Rn to DLP. i.e.,
P LP )max cT x
s.t. Ax + Is = b
x≥0
DLP )min y T b
s.t. y T A − Ie = cT
y≥0
Now we have the following complimentary slackness property for primal LP and its dual.
Theorem 1 (Complimentary Slackness) y T s = 0, and xT e = 0
Proof: If si is basic variable, si might not zero. However, because r(si ) = c(si )−y T ei = c(si )−yi =
0, and c(si ) = 0, yi = 0 claims. This means y T s = 0.
If si is nonbasic variable, si = 0 although we may have r(si ) > 0. We still claim y T s = 0.
Use the same logic, we can easily prove xT e = 0. Details are omitted for brevity.
Corresponding to an optimal solution, si = 0 implies the constraint is tight (no slackness), and
such constraint is called a binding constraint. When trying to find an optimal solution, the
binding constraint can be also understood as the factor that the solution is more dependent on. If
you change it, the optimal solution will have to change. In contrast, the non-binding constraint
doesn’t aﬀect the optimal solution and can be changed without changing the solution.
3
Exercises
Problem 1 Prove the complimentary relation of xT e = 0 in details.
Problem 2
max 5x1 + 12x2 + 4x3
s.t. x1 + 2x2 + x3 ≤ 10
2x1 − x2 + 3x3 = 8
x1 , x2 , x3 ≥ 0
2
By introducing slack variable s1 for the first constraint, and artificial variable xa for the second
constraint. We use the big-M method with xa , and solve the big-M linear program with the following
optimal Tableau.
x1 x2 x3
obj row 0 0 − 35
x2
0 1 − 15
7
x1
1 0
5
s1
− 29
5
2
5
2
5
2
5
xa
−M
− 15
2
5
−OBJ
−54 54
12
5
26
5
Please get the optimal dual variables using the relations as shown complimentary slackness. (Do
not solve the dual linear program by simplex method)
Problem 3 Solve the dual of the following problem, then find its optimal solution from the solution
of the dual. Does the solution of the dual oﬀer computational advantages over solving the primal
directly?
min 5x1 + 6x2 + 3x3
s.t. 5x1 + 5x2 + 3x3 ≥ 50
x1 + x2 − x3 ≥ 20
7x1 + 6x2 − 9x3 ≥ 30
5x1 + 5x2 + 5x3 ≥ 35
2x1 + 4x2 − 15x3 ≥ 10
12x1 + 10x2 ≥ 90
x1 − 10x3 ≥ 20
x1 , x2 , x3 ≥ 0
3

Download Report