傅里葉 - 莫茨金消元法的英文名：Fourier-Motzkin Elimination，簡稱 FME 算法，它是一種用于從線性不等式中消除變量的數(shù)學(xué)方法。

它的命名源自于在 1827 年和 1936 年獨(dú)立發(fā)現(xiàn)該算法的 Joseph Fourier 和 Theodore Motzkin 的姓氏。

1. 展示

從線性不等式中消除一組變量，是指通過將關(guān)系式中的若干個(gè)元素有限次地變換，消去其中的某些元素，從而解決問題的一種方法。

如果線性不等式中的所有變量都被消除，那么我們會得到一個(gè)常不等式。因?yàn)楫?dāng)且僅當(dāng)原不等式有解時(shí)，消元后的不等式才為真，消除所有變量可用于檢測不等式系統(tǒng)是否有解。

考慮一個(gè)含 n 個(gè)不等式的系統(tǒng)S，有從到的r個(gè)變量，其中為要消除的變量。根據(jù)系數(shù)的符號（正、負(fù)或空）， S中的線性不等式可以分為三類：

（1）形式為的不等式，對于范圍從 1 到 （ 為這種不等式的數(shù)量）的 j，用表示； 

（2）形式為的不等式，對于范圍從 1 到 （ 為這種不等式的數(shù)量）的 j，用表示；

（3）不包含的不等式，設(shè)它們構(gòu)成的不等式組為?。

因此原系統(tǒng)等價(jià)于

消元包括產(chǎn)生一個(gè)等價(jià)于的系統(tǒng)。顯然，這個(gè)公式等價(jià)于

不等式

等價(jià)于對于且，所有個(gè)不等式構(gòu)成的不等式組。

因此，我們將原系統(tǒng)S轉(zhuǎn)換為另一個(gè)消掉的系統(tǒng)，這個(gè)系統(tǒng)有個(gè)不等式。特別地，如果，那么新系統(tǒng)不等式的個(gè)數(shù)為。

2. 例題

考慮以下不等式系統(tǒng)：

為了消除 x，我們可以根據(jù) x 改寫不等式：

這樣我們得到兩個(gè)≤不等式和兩個(gè)≥等式；如果每個(gè)≤不等式的右側(cè)至少是每個(gè)≥不等式的右側(cè)，則系統(tǒng)有一個(gè)解。我們有2X2這樣的組合：

現(xiàn)在我們有了一個(gè)新的少了一個(gè)變量不等式系統(tǒng)。

3. 時(shí)間復(fù)雜度

在 n 個(gè)不等式上消元可以最多得到個(gè)不等式，因此連續(xù)運(yùn)行 d 步可以得到最多的雙指數(shù)復(fù)雜度。這是由于算法產(chǎn)生了許多不必要的約束（其他約束隱含的約束）。必要約束的數(shù)量以單一指數(shù)增長。

可以使用線性規(guī)劃 (Linear Programming, LP) 檢測不必要的約束。

4. 應(yīng)用

信息論的可實(shí)現(xiàn)性證明保證了存在性能良好的編碼方案的條件。這些條件通常使用線性不等式系統(tǒng)描述。系統(tǒng)的變量包括傳輸速率和附加輔助速率。通常，人們旨在僅根據(jù)問題的參數(shù)（即傳輸速率）來描述通信的基本限制，因此述輔助率需要消除上。而我們正是通過傅立葉 - 莫茨金消元法來做到這一點(diǎn)的。

5. 實(shí)現(xiàn)

在編程語言中，Racket，一種基于 Lisp 的多范式編程語言在 fme - Fourier-Motzkin Elimination for Integer Systems) 中對 FME 算法做了簡單函數(shù)代數(shù)實(shí)現(xiàn)。