quasi
Posts:
12,049
Registered:
7/15/05


Re: Specialized Linear Program
Posted:
Apr 25, 2013 10:23 PM


analyst41 wrote: > >Max sum over j, c(j).x(j) >St > sum over j, a(i,j).x(j) <= b(i) for i = 1,2,..m. > x(j) >= 0 for j = 1,2,...n. > >All a's,b's and c's are >= 0. > >This LP has the property that x feasible implies x' feasible >whenever 0 <= x'(j) <= x(j) for all j. > >Are these problems any easier than general LPs?
Not as far as I can see.
The only difference is that you have a known vertex of the feasible region, namely the origin, and that the feasible region is entirely in the first orthant.
Given any LP with a known vertex of the feasible region, a change of coordinates can be used to achieve another LP in the form you specify above.
quasi

