Linear programming problem

Hendrik

New member
Joined
Nov 28, 2014
Messages
8
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.
 
Top