Hello,
I just cant figure out how to solve the following question:
Consider an LP problem of the form
max Z =cTx
s.t.
Ax ≤ b
x ≥ 0
Let y* be the optimal solution of the corresponding dual problem. Suppose that
b in the LP is replaced by a vector d and let x* be the optimal solution of this
modified LP. Show that:
cTx*≤dTy*
I know that the dual of the original LP is of the form
min W = bTy
s.t.
ATy ≥ c
y ≥ 0
And since x* and y* are optimal solutions the corresponding objective values
for the primal and dual are equal. Thus we have:
cTx2=bTy2 and dTy1=cTx1
where x1 and y1 (=y*) belong to the original problem and x2 (=x*) y2
to the modified problem.
But I dont know how to go on from here. I hope someone can help me out.
I just cant figure out how to solve the following question:
Consider an LP problem of the form
max Z =cTx
s.t.
Ax ≤ b
x ≥ 0
Let y* be the optimal solution of the corresponding dual problem. Suppose that
b in the LP is replaced by a vector d and let x* be the optimal solution of this
modified LP. Show that:
cTx*≤dTy*
I know that the dual of the original LP is of the form
min W = bTy
s.t.
ATy ≥ c
y ≥ 0
And since x* and y* are optimal solutions the corresponding objective values
for the primal and dual are equal. Thus we have:
cTx2=bTy2 and dTy1=cTx1
where x1 and y1 (=y*) belong to the original problem and x2 (=x*) y2
to the modified problem.
But I dont know how to go on from here. I hope someone can help me out.