🚀 go-pugleaf

In article <batra.722077145@beagle> batra@boulder.Colorado.EDU (sajeev batra) writes:
>hi,
>
>I have a large set of  linear inequalities (with about a 20 unknowns)
>and I am about to use linear programming to solve for them.
>Is there an algorithm that will tell me that my set is consistent or
>inconsistent?  Also, I need to know specifically which inequalities
>contradict each other.  How do I go about doing this?  Any suggestions?
>Please post or email.
>
>Thank YoO,
>sajeev
>batra@cs.colorado.edu
>

Phase I of the simplex method tells you which inequalities are inconsistent
with the system. Assume that you have a system of the form:
A x = b, b >=0
  x >= 0
(Your system can be transformed into this format easily)
Now add artificial variables to the previous system:
A x + y = b
  x,  y >= 0
Note that y=b >=0 is a solution to the previous system. This is your starting
solution. Minimize y1+y2+... If the solution is y1=y2=...=0 then the previous
system (Ax=b, x>=0) has a solution. Otherwise, any constraint with yi<>0 is
incosistent with the system.
-Samer