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

Метод Фурье — Моцкина (также известный как метод исключения Фурье — Моцкина, метод проекций Фурье — Моцкина) — это алгоритм в линейной алгебре и теории линейных неравенств, предназначенный для исключения переменных из системы линейных неравенств. Метод позволяет последовательно исключать одну переменную за другой, преобразуя исходную систему в эквивалентную систему с меньшим числом переменных, что в конечном итоге может привести к определению совместности системы или нахождению её решения. Назван в честь французского математика Жана Батиста Жозефа Фурье и американского математика Теодора Моцкина.

¶История

Метод был впервые предложен Жаном Батистом Жозефом Фурье в 1826 году в его работе «Решение отдельных вопросов, связанных с неравенствами». Фурье разработал метод для решения задач, возникающих в механике и физике, где требовалось находить допустимые области параметров. Однако его работа оставалась малоизвестной в течение длительного времени.

В 1936 году американский математик Теодор Моцкин независимо переоткрыл и формализовал этот метод. Моцкин, работавший в области линейного программирования и теории оптимизации, применил его для анализа систем линейных неравенств, возникающих в экономических моделях. В 1950-х годах метод получил широкое распространение в связи с развитием вычислительной техники и линейного программирования, так как он позволял решать задачи, связанные с нахождением допустимых решений в многомерных пространствах.

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

Метод Фурье — Моцкина основан на идее последовательного исключения переменных из системы линейных неравенств. Пусть дана система из \(m\) линейных неравенств с \(n\) переменными:

\[ a_{i1}x_1 + a_{i2}x_2 + \ldots + a_{in}x_n \leq b_i, \quad i = 1, \ldots, m. \]

Для исключения переменной \(x_k\) (например, \(x_1\)) все неравенства делятся на три группы:

Неравенства, в которых коэффициент при \(x_k\) положительный (\(a_{ik} > 0\)): их можно переписать в виде \(x_k \leq \text{линейная комбинация остальных переменных}\).
Неравенства, в которых коэффициент при \(x_k\) отрицательный (\(a_{ik} < 0\)): их можно переписать в виде \(x_k \geq \text{линейная комбинация остальных переменных}\).
Неравенства, в которых коэффициент при \(x_k\) равен нулю: они не зависят от \(x_k\) и остаются без изменений.

Затем для каждой пары неравенств из первой и второй групп (верхняя и нижняя границы для \(x_k\)) составляется новое неравенство, которое не содержит \(x_k\). Например, если есть неравенство \(x_k \leq L\) и \(x_k \geq U\), то из них следует \(U \leq L\). Полученная система неравенств, не содержащая \(x_k\), эквивалентна исходной в том смысле, что если существует решение исходной системы, то существует и решение новой системы, и наоборот.

Процесс повторяется для каждой переменной, пока не останется система с одной переменной или не будет установлена несовместность (например, получено противоречие вида \(0 \leq -1\)).

¶Пример

Рассмотрим систему неравенств:

\[ \begin{cases} x_1 + x_2 \leq 3, \\ x_1 - x_2 \leq 1, \\

x_1 + x_2 \leq 0, \\
x_1 - x_2 \leq -1.

\end{cases} \]

Исключим переменную \(x_1\). Для этого перепишем неравенства в виде:

Из первого: \(x_1 \leq 3 - x_2\).
Из второго: \(x_1 \leq 1 + x_2\).
Из третьего: \(-x_1 \leq -x_2 \Rightarrow x_1 \geq x_2\).
Из четвёртого: \(-x_1 \leq -1 + x_2 \Rightarrow x_1 \geq 1 - x_2\).

Теперь, комбинируя верхние и нижние границы, получаем:

\(x_2 \leq 3 - x_2 \Rightarrow 2x_2 \leq 3 \Rightarrow x_2 \leq 1.5\).
\(x_2 \leq 1 + x_2 \Rightarrow 0 \leq 1\) (всегда истинно).
\(1 - x_2 \leq 3 - x_2 \Rightarrow 1 \leq 3\) (всегда истинно).
\(1 - x_2 \leq 1 + x_2 \Rightarrow -2x_2 \leq 0 \Rightarrow x_2 \geq 0\).

Таким образом, после исключения \(x_1\) получаем систему: \(0 \leq x_2 \leq 1.5\). Это означает, что исходная система совместна, и \(x_2\) может принимать любое значение в этом интервале, а \(x_1\) определяется соответствующими границами.

¶Применение

Метод Фурье — Моцкина находит применение в различных областях:

Линейное программирование: используется для проверки совместности системы ограничений и для нахождения допустимых решений в задачах оптимизации.
Вычислительная геометрия: применяется для построения выпуклых многогранников и анализа их свойств, например, для определения вершин и рёбер.
Теория управления: используется для анализа систем линейных неравенств, описывающих ограничения на состояния и управления.
Экономика и исследование операций: применяется для моделирования и решения задач распределения ресурсов и планирования.
Анализ данных и машинное обучение: используется в методах опорных векторов (SVM) для нахождения разделяющих гиперплоскостей.

¶Ограничения и сложность

Основным недостатком метода Фурье — Моцкина является его экспоненциальная сложность. При исключении каждой переменной количество неравенств может увеличиваться квадратично, что в худшем случае приводит к \(O(2^n)\) неравенств для системы с \(n\) переменными. Это делает метод непрактичным для больших систем, особенно в задачах с десятками и сотнями переменных.

Для преодоления этого ограничения разработаны более эффективные алгоритмы, такие как симплекс-метод для линейного программирования и методы внутренней точки. Однако метод Фурье — Моцкина остаётся важным теоретическим инструментом, особенно в задачах, где требуется аналитическое решение или анализ структуры многогранников.

¶Связь с другими методами

Метод Фурье — Моцкина является аналогом метода исключения Гаусса для систем линейных неравенств. В то время как метод Гаусса позволяет решать системы линейных уравнений, метод Фурье — Моцкина решает системы линейных неравенств. Также метод тесно связан с понятием проекции многогранника: исключение переменной эквивалентно проекции многогранника на подпространство меньшей размерности.

¶Интересные факты

Метод Фурье — Моцкина иногда называют «методом исключения Фурье», хотя вклад Моцкина был значительным, так как он формализовал алгоритм и показал его связь с линейным программированием.
Теодор Моцкин также известен своими работами в области теории чисел и комбинаторики, в частности, он ввёл понятие «моцкиновских чисел», которые описывают количество путей на решётке.
Метод может быть использован для нахождения всех вершин многогранника, заданного системой неравенств, хотя это требует дополнительных вычислительных затрат.

¶Источники

Fourier, J. B. J. (1826). «Solution d’une question particulière du calcul des inégalités». Bulletin des Sciences Mathématiques, Astronomiques, Physiques et Chimiques.
Motzkin, T. S. (1936). «Beiträge zur Theorie der linearen Ungleichungen». Dissertation, Universität Basel.
Schrijver, A. (1986). Theory of Linear and Integer Programming. John Wiley & Sons.
Ziegler, G. M. (1995). Lectures on Polytopes. Springer-Verlag.