home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / numanal / 3343 < prev    next >
Encoding:
Text File  |  1992-11-18  |  1.5 KB  |  40 lines
  1. Newsgroups: sci.math.num-analysis
  2. Path: sparky!uunet!caen!takriti
  3. From: takriti@engin.umich.edu (samer Takriti)
  4. Subject: Re: question: how to show that a set of linear inequalities is consistent?
  5. Message-ID: <w5F=_V=@engin.umich.edu>
  6. Date: Wed, 18 Nov 92 12:57:21 EST
  7. Organization: University of Michigan Engineering, Ann Arbor
  8. References: <batra.722077145@beagle>
  9. Nntp-Posting-Host: ephedra.engin.umich.edu
  10. Lines: 28
  11.  
  12. In article <batra.722077145@beagle> batra@boulder.Colorado.EDU (sajeev batra) writes:
  13. >hi,
  14. >
  15. >I have a large set of  linear inequalities (with about a 20 unknowns)
  16. >and I am about to use linear programming to solve for them.
  17. >Is there an algorithm that will tell me that my set is consistent or
  18. >inconsistent?  Also, I need to know specifically which inequalities
  19. >contradict each other.  How do I go about doing this?  Any suggestions?
  20. >Please post or email.
  21. >
  22. >Thank YoO,
  23. >sajeev
  24. >batra@cs.colorado.edu
  25. >
  26.  
  27. Phase I of the simplex method tells you which inequalities are inconsistent
  28. with the system. Assume that you have a system of the form:
  29. A x = b, b >=0
  30.   x >= 0
  31. (Your system can be transformed into this format easily)
  32. Now add artificial variables to the previous system:
  33. A x + y = b
  34.   x,  y >= 0
  35. Note that y=b >=0 is a solution to the previous system. This is your starting
  36. solution. Minimize y1+y2+... If the solution is y1=y2=...=0 then the previous
  37. system (Ax=b, x>=0) has a solution. Otherwise, any constraint with yi<>0 is
  38. incosistent with the system.
  39. -Samer
  40.