please explain it. thx so much!!! Consider the primal linear programming problem
ID: 3531353 • Letter: P
Question
please explain it.
thx so much!!!
Consider the primal linear programming problem Suppose this problem and its dual are feasible, and let lambda denote a known optimal solution to the dual. If the k throw of the matrix A and the kth element of the right-hand side b are multiplied by , determine an optimal solution w to the dual of this modified problem. Suppose that, in the original primal, we add mu times the kth equation to the rth equation. What is a solution w to the corresponding dual problem? Suppose, in the original primal, we add mu times kth row of .A to the cost vector c. What is a solution to the corresponding dual problem?Explanation / Answer
1. If the kth row of A and th element of b are multiplied by some mu not equal to zero,
the constraints actually do not change , so the optimal solution of the primal do not change
and hence the optimal value also do not change
let the transformed b obtained by the transformation be d...... let d(i) represent the i th element of d
we know that lamda' * b = the optimal value
hence, now we have w' * d = optimal value(same as above) (since in the dual, objective function = y'b)
so, consider w* = lambda with the kth value divided by k ,
for this, we have the same optimal value for the dual and hence this is the optimal solution of this problem
2. By adding mu times the th equation to the rth equation also , the primal does not change , it is equivalent and hence the optimal value does not change
so again we have ,
lamda' * b = the optimal value
hence, now we have w' * d = optimal value(same as above)
here , transformed b has all elements same except the rth elemnt which is modified to mu*b(k) + b(r) = d(r)
consider, w(i) = lambda(i) for all values except r and k
we have, lambda(k)* b(k) + lambda(r)*b(r) = w(k)*d(k) + w(r)*d(r)
==> lambda(k)* b(k) + lambda(r)*b(r) = w(k)*b(k) + w(r)*(b(r)+mu*b(k))
so w(r) = lambda(r) & w(k) = lambda(k) / (1+mu)
hence this gives the same optimal value
3. so , the dual now is minimize, b'y
such that A'y = l where l is the transformed c i.e. l(i) = c(i) + mu*A(k,i)
the kk th column of A' has the same elements as A(k,i)
consider , the new dual optimal solution as w(i) = lambda(i) for all i except k
and w(k) = lambda(k)+ mu
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.