Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: LP question
Replies: 2   Last Post: Jun 6, 2013 4:30 AM

 Messages: [ Previous | Next ]
 RGVickson@shaw.ca Posts: 1,677 Registered: 12/1/07
Re: LP question
Posted: Jun 6, 2013 4:30 AM

On Monday, June 3, 2013 7:06:33 PM UTC-7, 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 absent---but we have assumed that problem (the original one) has a strictly larger max.

Date Subject Author
6/3/13 analyst41@hotmail.com
6/4/13 Peter Spellucci
6/6/13 RGVickson@shaw.ca