Kachian's algorithm is an algorithm that produces a numerical approximation
to an optimal solution to an LP. The LP would have to be expressed with
numerical coefficients.
I'm not aware of any general purpose algorithm for solving an LP with
symbolic coefficients. However, if the coefficients are rational numbers,
then it is possible to get an exact rational answer using the simplex
algorithm. This is implemented for example in Maple V.
There are also "sensitivity analysis" techniques for analyzing the optimal
solution to an LP to determine for what range of coefficients the solution
would remain optimal. It's possible that such techniques would be useful
here.
- Brian
Brian Borchers borchers@nmt.edu
Department of Mathematics http://www.nmt.edu/~borchers/
New Mexico Tech Phone: 505-835-5813
Socorro, NM 87801 FAX: 505-835-5366