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

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

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

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

Пример

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

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

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

${\begin{cases}x\leqslant {\frac {10+5y-4z}{2}}\\x\leqslant {\frac {9+6y-3z}{3}}\\x\geqslant 7+5y-2z\\x\geqslant {\frac {-12+2y+6z}{3}}\\\end{cases}}$

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

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