The trick is to use only non-negative variables for the equations. (That's considered OK in linear programming. Though you may consider it cheating.) By the way, linear programming over rational numbers is in P.