В математике метод Фурье-Моцкина используются для исследования существования решений системы линейных неравенств ${\displaystyle Ax\leqslant b}$ , где матрица ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ , а ${\displaystyle b\in \mathbb {R} ^{m}}$ .

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

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

Описание метода

Пример

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

В статье не хватает ссылок на источники (см. рекомендации по поиску ). Информация должна быть проверяема , иначе она может быть удалена. Вы можете статью, добавив ссылки на авторитетные источники в виде сносок . ( 20 февраля 2023 )

На эту статью не ссылаются другие статьи Википедии . Пожалуйста, установите ссылки в соответствии с принятыми рекомендациями . ( 9 марта 2022 )