Метод Фурье — Моцкина

Метод Фурье — Моцкина используются для исследования существования решений системы линейных неравенств.

Такая система задаёт выпуклый многогранник, поэтому метод используется в выпуклой геометрии, а также в теории линейного программирования.

Впервые метод исключения переменных описал Фурье в 1827 году, в 1936 году его переоткрыл американо-израильский математик Шаблон:Iw.

Пример

Пусть задана система неравенств с тремя переменными:

$\{\begin{array}{c}2x-5y+4z⩽10\\ 3x-6y+3z⩽9\\ -x+5y-2z⩽-7\\ -3x+2y+6z⩽12\end{array}$

Для исключения переменной $x$, все неравенства можно записать через эту перменную:

$\{\begin{array}{c}x⩽\frac{10+5y-4z}{2}\\ x⩽\frac{9+6y-3z}{3}\\ x⩾7+5y-2z\\ x⩾\frac{-12+2y+6z}{3}\end{array}$

Соответственно правая сторона каждого неравенства со знаком $⩽$ должна быть не меньшей, чем правая сторона неравенства со знаком $⩾$. Получаются 4 неравенства от 2 переменных:

$\{\begin{array}{c}7+5y-2z⩽\frac{10+5y-4z}{2}\\ 7+5y-2z⩽\frac{9+6y-3z}{3}\\ \frac{-12+2y+6z}{3}⩽\frac{10+5y-4z}{2}\\ \frac{-12+2y+6z}{3}⩽\frac{9+6y-3z}{3}\end{array}$