Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: LP question
Posted:
Jun 6, 2013 4:30 AM


On Monday, June 3, 2013 7:06:33 PM UTC7, anal...@hotmail.com wrote: > You have an LP L0 that asks for > > > > Max c.x > > x in S0, where S0 is defined by all x satifying > > > > Ax = b > > x >= 0. > > > > Let the optimum value for L0 be z0. > > > > Let z be the optimum value for LP L that says > > > > Max cx > > x in S, > > > > when S = intersection of S0 with a single constraint (b1 is a scalar) > > a1.x <= b1. > > > > Is it true that if z is strictly less than z0 then the additional > > constraint would be tight for all optimal soultions of LP L?
Yes, because if it were not tight at an optimal solution, we would have an optimal solution to the problem with the new constraint absentbut we have assumed that problem (the original one) has a strictly larger max.



