One possibility would be to use exact values. If instead you work with finite precision, make sure the input is of high precision and contains no machine numbers. And make sure the result likewise is of high precision. Anything else would be an indication that LinearProgramming was using machine arithmetic which is not going to react well to an extreme level of scale differences.
