University of Liverpool – Question 1: (0 points)
Duality is an idea that exists in many areas of mathematics. It generally refers to pairing a mathematical object with a related one that is, in some sense, ‘the other way round’.
One advantage of doing this is that thinking about the dual object can give us information about the original object. In a way, it is providing us with a different viewpoint from which to consider a problem.
The dual of a linear program LP will be another linear program DP. We will use different letters though, with the following conventions, to show which program we are thinking of as a dual program.
Copyright By PowCoder代写 加微信 powcoder
That is, we always write xixi, for i=1,…,mi=1,…,m, and yjyj, for j=1…,nj=1…,n. Let
x=(x1⋮xm),y=(y1⋮yn),c=(c1⋮cm),b=(b1⋮bn),A=(aj,i),z=cTx,w=bTy. x=⎛⎝⎜⎜x1⋮xm⎞⎠⎟⎟,c=⎛⎝⎜⎜c1⋮cm⎞⎠⎟⎟,Az=cTx,y=⎛⎝⎜⎜y1⋮yn⎞⎠⎟⎟,b=⎛⎝⎜⎜b1⋮bn⎞⎠⎟⎟,=(aj,i),w=bTy. Then for the linear program
LP=max{cTx:Ax≤b,x≥0},
LP=max{cTx:Ax≤b,x≥0},
there exists a dual program
DP=min{bTy:ATy≥c,y≥0}
DP=min{bTy:ATy≥c,y≥0}
with several important properties.
Notice that this definition refers to LP before we add any slack, surplus or artificial variables. It is helpful here to also write a more informal description of creating the dual program.
The dual program is a minimisation problem, whereas the original program is a maximisation problem.
Create one yjyj for each of the xx-constraints. Create a new yy-constraint for each xixi.
The coefficient of yjyj in the yy-constraint is the coefficient of xixi in the xx-constraint corresponding to yjyj.
The yy-constraint is a ≥≥ constraint, whereas the xx-constraints are all ≤≤ constraints.
The constant in the yy-constraint is the coefficient of xixi in the xx-objective function.
The coefficient of yjyj in the yy-objective function is the constant in the xx-constraint corresponding to yjyj.
Recall the spring factory LP: maximise z=63×1+113×2
original linear program:
dual program:
maximise z=63×1+113×2
subject to 8×1+15×2≤400,×1+x2≤30,×1+2×2≤50,×1,x2≥0. 8×1+15x2x1+x2x1+2x2x1,x2≤400,≤30,≤50,≥0. The dual linear program is
minimise w=400y1+30y2+50y3
minimise w=400y1+30y2+50y3
subject to 8y1+y2+y3≥6315y1+y2+2y3≥113y1,y2,y3≥0. 8y1+y2+y315y1+y2+2y3y1,y2,y3≥63≥113≥0.
Question 2: (0 points)
Proposition (The Weak Duality Property):
If ˆxx^ is a feasible solution to LP and ˆyy^ is a feasible solution to DP, then ˆz=cTˆx≤bTˆy=ˆw.
z^=cTx^≤bTy^=w^.
Since ˆxx^ is feasible for LP, its components satisfy m∑i=1aj,i⋅ˆxi≤bj,j=1,…,n. ∑i=1maj,i⋅x^i≤bj,j=1,…,n.
Hence, since ˆyj≥0y^j≥0 for all jj, (m∑i=1aj,i⋅ˆxi)ˆyj≤bj⋅ˆyj,j=1,…,n, (∑i=1maj,i⋅x^i)y^j≤bj⋅y^j,j=1,…,n,
n∑j=1(m∑i=1aj,i⋅ˆxi⋅ˆyj)≤n∑j=1(bj⋅ˆyj)=bTˆy. ∑j=1n(∑i=1maj,i⋅x^i⋅y^j)≤∑j=1n(bj⋅y^j)=bTy^.
On the other hand, since ˆyy^ is feasible for DP its components satisfy n∑j=1aj,i⋅ˆyj≥ci,i=1,…,m,
∑j=1naj,i⋅y^j≥ci,i=1,…,m,
from which we can similarly deduce that m∑i=1n∑j=1aj,i⋅ˆxi⋅ˆyj≥m∑i=1ci⋅ˆxi=cTˆx. ∑i=1m∑j=1naj,i⋅x^i⋅y^j≥∑i=1mci⋅x^i=cTx^.
Combining these inequalities give the required result.
Now, as xx varies we are trying to increase z=z(x)z=z(x), which has an upper bound of w=w(y)w=w(y); and as yy varies we are trying to reduce w=w(y)w=w(y), which has a lower bound of z=z(x)z=z(x). Since this holds for all feasible xx and yy we immediately get the following result:
Corollary (The Optimality Property):
Let ˆxx^ be a feasible solution for LP with ˆz=z(ˆx)z^=z(x^). Also let ˆyy^ be a feasible solution for DP with ˆw=w(ˆy)w^=w(y^).
If ˆz=ˆwz^=w^ then ˆxx^ is an optimal solution for LP and ˆyy^ is an optimal solution for DP. The Weak Duality Property also tells us the following.
Corollary:
If LP is unbounded then DP has no feasible solution. Similarly, if DP is unbounded then LP has no feasible solution.
Note that this statement gives two implications; the converse statements are not true in general. Consider the linear program
maximise: z=2×1+7×2
maximise: z=2×1+7×2
subject to
−x1+x2≤3,×2≤5,×1,x2≥0. −x1+x2x2x1,x2≤3,≤5,≥0.
We can draw the feasible region in this case.
We can see immediately that the feasible region is unbounded. For any value of x1≥2×1≥2, the point (x1,5)(x1,5) is in the feasible region. At this point, the value of the objective function is
z=2×1+35≥x1.
z=2×1+35≥x1.
The linear program is therefore unbounded, as it has solutions that are arbitratily large. From Weak Duality we can therefore conclude that the dual linear program is infeasible. The dual program is
minimise: w=3y1+5y2
minimise: w=3y1+5y2
subject to
−y1≥2,y1+y2≥7,y1,y2≥0.
−y1y1+y2y1,y2≥2,≥7,≥0.
We can see that there are no feasible solutions to this as no value of y1y1 can satisfy the constraints.
Question 3: (0 points)
As we have just said, it is not true that if either LP or DP is infeasible then the other is necessarily unbounded; it is also possible for neither LP nor DP to be feasible.
On the other hand, we are about to prove that it is not possible for one to have an optimal solution and the other not be feasible. We first need to state a technical proposition, which may be readily checked from the definition of a dual linear program.
Proposition:
Let LP be a linear program with dual DP. The dual of DP is LP.
Theorem (Strong Duality Property):
The linear program LP has an optimal solution z⋆z⋆ if and only if the dual program DP has an optimal solution w⋆w⋆. In this case, we have z⋆=w⋆z⋆=w⋆.
Let x⋆x⋆ be an optimal solution of LP with z⋆=z(x⋆)z⋆=z(x⋆), and let y⋆jy⋆j, for j=1,…,nj=1,…,n, be the shadow prices for this optimal solution. Recall (from last week) that
z⋆=n∑j=1bj⋅y⋆j
z⋆=∑j=1nbj⋅y⋆j
̄ci=−ci+n∑j=1aj,i⋅y⋆j
c ̄i=−ci+∑j=1naj,i⋅y⋆j
for i=1,…,m, where ̄ci is the reduced cost of the decision variable xi.
For an optimal solution to LP, the reduced costs for decision variables are non-negative. That is ̄ci≥0, which yields:
n∑j=1aj,i⋅y⋆j≥ci,i=1,…,m;y⋆i≥0.
These are exactly the constraints for DP and so y⋆=(y⋆1,…,y⋆n)T is a feasible solution for DP. The value of the objective function w of DP at the feasible point y⋆ is bTy⋆, so z(x⋆)=n∑j=1bj⋅y⋆j=w(y⋆).
Hence by the Optimality Property, y⋆ is an optimal solution to DP with w⋆=w(y⋆)=z⋆.
We can prove the converse implication by applying this one to DP and its dual program LP.
Question 4: (0 points)
Recall that, in the proof of the Weak Duality Property, we derived the inequality
cTˆx=m∑i=1ci⋅ˆxi≤m∑i=1n∑j=1aj,i⋅ˆxi⋅ˆyj≤n∑j=1bj⋅ˆyj=bTˆy,
which holds for any feasible solutions x of LP and y of DP.
Strong duality tells us that this inequality becomes equality in the case of optimal solutions x⋆,y⋆. Hence, we can take one of these equalities and rearrange:
m∑i=1n∑j=1aj,i⋅x⋆i⋅y⋆j=n∑j=1bj⋅y⋆i−n∑j=1bj⋅y⋆j+n∑j=1m∑i=1aj,i⋅x⋆i⋅y⋆j=0n∑j=1(−bj+m∑i=1aj,i⋅x⋆i)y⋆j=0. Notice that each term
−bj+m∑i=1aj,i⋅x⋆i≤0
(by the structural constraints in LP), and that each y⋆j≥0 (by the non-negativity constraints of the
Hence the only way the whole sum over j can be equal to zero is if each summand is equal to zero.
That is, for all j=1,…,n, we have
(m∑i=1aj,i⋅x⋆i−bj)y⋆j=0,
and a similar argument shows that, for all i=1,…,m,
(n∑j=1aj,iy⋆j−ci)x⋆i=0.
These two equations are called the Complementary Slackness conditions, and give us the following properties.
Proposition (Complementary Slackness Properties):
Suppose LP has an optimal solution at x⋆ and its dual DP has an optimal solution at y⋆. If y⋆j>0 then ∑mi=1aj,i⋅x⋆i=bj;
i.e. if the jth variable in the optimal solution to DP is non-zero then the jth constraint in the optimal solutions to LP has no slack (it is binding).
If ∑mi=1aj,i⋅x⋆i
If ∑nj=1aj,i⋅y⋆j