Fourier-Motzkin elimináció

algorithm

Scope: Adott $Q\in {\mathbb{R}}^{k\times n}$ és $b\in {\mathbb{R}}^k$. Az algoritmus eldönti, hogy létezik-e $x\in {\mathbb{R}}^n$ úgy, hogy $Qx\le b$.

Procedure.: $Q\to Q^{\prime }$ úgy, hogy $Q^{\prime }$-ben kevesebb nem csupa $0$ oszlop van.
lépés:

1. Minden sort osszuk le az első nem csupa $0$ oszlop első elemének az abszolút értékével.
2. Legyenek $I_{+},I_{-},I_0$ azon sorok halmazai, melyekre az első nem nulla elem $1,-1,0$.
3. $\forall (s_{+},s_{-})\in I_{+}\times I_{-}$ legyen $s^{\prime }=s_{+}+s_{-}$, tehát összeadjuk a két sort.
4. Ezeket a $s^{\prime }$ sorokat rakjuk bele egy új $Q^{\prime }$ mátrixba.
5. Változtatás nélkül rakjuk még hozzá $I_0$ sorait is $Q^{\prime }$ mátrixhoz.

Ezek a lépések után létrehoztunk egy új $Q^{\prime }$ mátrixot úgy, hogy kevesebb nem csupa $0$ oszlopa van.
Továbbá, ha $x\in {\mathbb{R}}^n$ kielégítette a $Qx\le b$ egyenlőtlenséget, akkor $\exists x^{\prime }$ úgy, hogy $Q^{\prime }{x}^{\prime }\le b^{\prime }$.

Dependencies:

• LP feladat