Fourier-Motzkin Elimination
npm install fourier-motzkinFourier-Motzkin Elimination can be used to determine whether an arbitrary system of linear inequalities has solutions or not.
``
npm install fourier-motzkin
Let's say you have a linear system of inequalities:
First, you have to transform it, so now you have a single matrix:
Now simply run the elimination algorithm:
`js
var fme = require('fourier-motzkin');
var mx =
[[ 1, 1, 1, 1],
[-2, 1, -1, -1],
[-1, -4, 1, -2],
[-1, 0, 0, 0],
[ 0, -1, 0, 0],
[ 0, 0, -1, 0]];
console.log(fme(mx));
`
The algorithm has exponential complexity, but it works very well on smaller systems.
- Improve performance (remove those slow map/reduce calls, switch to faster Array` implementation)
- If the system is not solvable, provide proof (Farkas' lemma)
- If the system has one solution, find it
- etc
MIT