Метод Фур'є — Моцкіна

У математиці метод виключення змінних Фур'є — Моцкіна використовується для дослідження існування розв'язків системи лінійних нерівностей:

${\displaystyle Ax\leqslant b,}$

де ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ є матрицею, а ${\displaystyle b\in \mathbb {R} ^{m}}$.

Оскільки така система задає опуклий політоп, то метод має застосування у опуклій геометрії і також у математичній теорії лінійного програмування.

Вперше метод виключення змінних для нерівностей описав Жан Батист Жозеф Фур'є у 1827 році, у 1936 році його повторно відкрив математик ^[en].

Опис методу

Нехай задано m лінійних нерівностей від n змінних виду:

${\displaystyle a_{i1}x_{1}+\ldots +a_{ij}x_{j}+\ldots +a_{in}x_{n}\leqslant b_{i},\quad i=1,\ldots ,m,}$

де всі ${\displaystyle a_{ij}}$ і ${\displaystyle b_{i}}$ є дійсними числами. У матричній формі ця система нерівностей записується як:

${\displaystyle Ax\leqslant b,}$

де ${\displaystyle A=(a_{ij})}$ є матрицею відповідних коефіцієнтів, а ${\displaystyle b=(b_{i})}$ — вектор-стовпець правих частин нерівностей.

Геометрично така система нерівностей задає опуклий політоп. Метод Фур'є — Моцкіна дає змогу перейти від системи нерівностей із n невідомими до системи із n - 1 невідомою. Послідовно далі можна цю систему привести до системи із n - 2 невідомими і так далі. Щоправда при цьому кількість нерівностей збільшується. Після n кроків виключення змінних одержується система нерівностей без змінних, тобто система виду ${\displaystyle 0\leqslant c_{i},\ i=1,\ldots ,N.}$ Початкова система має розв'язки тоді і тільки тоді коли остання система нерівностей є справедливою, тобто всі ${\displaystyle c_{i}}$ є справді невід'ємними.

Для виключення змінної ${\displaystyle x_{n}}$ із описаної вище системи нерівностей, нехай ${\displaystyle I_{n}^{+}}$ позначає множину індексів i для яких ${\displaystyle a_{in}>0,}$ ${\displaystyle I_{n}^{-}}$ позначає множину індексів i для яких ${\displaystyle a_{in}<0}$ і ${\displaystyle I_{n}^{0}}$ позначає множину індексів i для яких ${\displaystyle a_{in}=0.}$ Для кожного ${\displaystyle j\in I_{n}^{+}}$ можна записати:

${\displaystyle x_{n}\leqslant b'_{j}-a'_{j1}x_{1}-\ldots -a'_{jn-1}x_{n-1}=f_{j}(x_{1},\ldots ,x_{n-1}),}$

де ${\displaystyle a'_{jk}={a_{jk} \over a_{jn}},\ k=1,\ldots ,n-1,\ b'_{j}={b_{j} \over a_{jn}},}$ а ${\displaystyle f_{j}(x_{1},\ldots ,x_{n-1})}$ позначає відповідну афінну функцію. Аналогічно для ${\displaystyle i\in I_{n}^{-}}$:

${\displaystyle x_{n}\geqslant b'_{i}-a'_{i1}x_{1}-\ldots -a'_{in-1}x_{n-1}=g_{i}(x_{1},\ldots ,x_{n-1}),}$

де ${\displaystyle a'_{ik}={a_{ik} \over a_{in}},\ k=1,\ldots ,n-1,\ b'_{i}={b_{i} \over a_{in}},}$ а ${\displaystyle g_{j}(x_{1},\ldots ,x_{n-1})}$ позначає відповідну афінну функцію.

Нехай також для ${\displaystyle k\in I_{n}^{0}}$ позначено ${\displaystyle h_{k}(x_{1},\ldots ,x_{n-1})=a_{k1}x_{1}+\ldots +a_{in-1}x_{n-1}-b_{k}.}$ Загалом із цими позначеннями можна записати систему нерівностей у виді:

${\displaystyle {\begin{cases}x_{n}\leqslant f_{j}(x_{1},\ldots ,x_{n-1}),\quad \forall j\in I_{n}^{+}\\g_{i}(x_{1},\ldots ,x_{n-1})\leqslant x_{n},\quad \forall i\in I_{n}^{-}\\h_{k}(x_{1},\ldots ,x_{n-1})\leqslant 0,\quad \forall k\in I_{n}^{0}\end{cases}}.}$

Метод виключення змінних полягає у заміні цієї системи системою ${\displaystyle |I_{n}^{+}|\cdot |I_{n}^{-}|+|I_{n}^{0}|}$ нерівностей виду:

${\displaystyle {\begin{cases}g_{i}(x_{1},\ldots ,x_{n-1})\leqslant f_{j}(x_{1},\ldots ,x_{n-1}),\quad \forall \ i\in I_{n}^{-},\ j\in I_{n}^{+}\\h_{k}(x_{1},\ldots ,x_{n-1})\leqslant 0,\quad \forall k\in I_{n}^{0}\end{cases}}.}$

Якщо ${\displaystyle x_{1},\ldots ,x_{n}}$ є розв'язком початкової системи, то очевидно ${\displaystyle x_{1},\ldots ,x_{n-1}}$ є розв'язком нової системи. Навпаки, якщо нова система має розв'язок ${\displaystyle x_{1},\ldots ,x_{n-1}}$, то ${\displaystyle \max _{i\in I_{n}^{-}}g_{i}(x_{1},\ldots ,x_{n-1})\leqslant \min _{j\in I_{n}^{+}}f_{j}(x_{1},\ldots ,x_{n-1})}$ і для кожного ${\displaystyle x_{n},}$ що задовольняє нерівності:

${\displaystyle \max _{i\in I_{n}^{-}}g_{i}(x_{1},\ldots ,x_{n-1})\leqslant x_{n}\leqslant \min _{j\in I_{n}^{+}}f_{j}(x_{1},\ldots ,x_{n-1})}$

${\displaystyle x_{1},\ldots ,x_{n}}$ є розв'язком початкової системи. Зокрема система лінійних нерівностей має хоча б один розв'язок тоді і лише тоді коли хоча б один розв'язок має система одержана виключенням змінної методом Фур'є — Моцкіна.

Матричний запис нової системи рівнянь

Для початкової системи нерівностей ${\displaystyle Ax\leqslant b}$ із матрицею розмірності ${\displaystyle m\times n}$ застосуванням методу Фур'є — Моцкіна одержується система нерівностей яку перенесенням змінних у ліву сторону і вільних членів у праву сторону можна записати у матричній формі:

${\displaystyle A'x'\leqslant b',\quad }$де матриця ${\displaystyle A'=(a'_{ij})}$ має розмірність ${\displaystyle (|I_{n}^{+}|\cdot |I_{n}^{-}|+|I_{n}^{0}|)\times (n-1)}$, а ${\displaystyle b'}$ є вектор-стовпцем із ${\displaystyle |I_{n}^{+}|\cdot |I_{n}^{-}|+|I_{n}^{0}|}$ елементами.

Елементи нових матриці і вектора можна записати із формул вище. Для цього нехай ${\displaystyle |I_{n}^{+}|=m_{1},\ |I_{n}^{-}|=m_{2},\ |I_{n}^{0}|=m_{3},}$ де ${\displaystyle m_{1}+m_{2}+m_{3}=m.}$ Якщо ${\displaystyle m_{1}=m}$ або ${\displaystyle m_{2}=m}$ то нова система нерівностей буде порожньою і будь-який набір чисел ${\displaystyle x_{1},\ldots ,x_{n-1}}$ буде її розв'язкам. Тоді для початкової системи ${\displaystyle x_{1},\ldots ,x_{n}}$ буде розв'язком, якщо ${\displaystyle \max g_{i}(x_{1},\ldots ,x_{n-1})\leqslant x_{n}}$ чи в залежності від умов, ${\displaystyle x_{n}\leqslant \min f_{j}(x_{1},\ldots ,x_{n-1}).}$ Тому можна припустити ${\displaystyle m_{1}\geqslant 1,\ m_{2}\geqslant 1,\ m_{3}\geqslant 0.}$

Нехай ${\displaystyle i_{1}<i_{2}<\ldots <i_{m_{1}}}$ є індексами із множини ${\displaystyle I_{n}^{+}}$, ${\displaystyle j_{1}<j_{2}<\ldots <j_{m_{2}}}$ є індексами із множини ${\displaystyle I_{n}^{-}}$, а ${\displaystyle k_{1}<k_{2}<\ldots <k_{m_{3}}}$є індексами із множини ${\displaystyle I_{n}^{0}.}$ Кожен рядок нової матриці ${\displaystyle A'}$ відповідає або парі індексів ${\displaystyle i_{t}\in I_{n}^{-},\ j_{s}\in I_{n}^{+}}$ або індексу ${\displaystyle k_{r}\in I_{n}^{0}.}$ Для визначеності нехай парі індексів ${\displaystyle (i_{t},\ j_{s})}$ відповідає ${\displaystyle (t-1)\cdot m_{2}+s}$ -ий рядок матриці, а індексу ${\displaystyle k_{r}}$ — рядок номер ${\displaystyle m_{1}\cdot m_{2}+r.}$

Для індексів із множини ${\displaystyle I_{n}^{0}}$ коефіцієнти нових матриці і вектора є рівними відповідним коефіцієнтам початкових:

${\displaystyle a'_{m_{1}m_{2}+r,l}=a_{k_{r},l},\ b'_{m_{1}m_{2}+r}=b_{k_{r}},\quad k_{r}\in I_{n}^{0},\ l\in \{1,\ldots ,n-1\}.}$

Для пари індексів ${\displaystyle (i_{t},\ j_{s})}$ відповідні елементи одержуються із нерівності ${\displaystyle g_{i_{t}}(x_{1},\ldots ,x_{n-1})\leqslant f_{j_{s}}(x_{1},\ldots ,x_{n-1}):}$

${\displaystyle a'_{(t-1)\cdot m_{2}+s,l}={a_{j_{s},l} \over a_{j_{s},n}}-{a_{i_{t},l} \over a_{i_{t},n}},\ b'_{(t-1)\cdot m_{2}+s}={b_{j_{s}} \over a_{j_{s},n}}-{b_{i_{t}} \over a_{i_{t},n}},\quad i_{t}\in I_{n}^{-},\ j_{s}\in I_{n}^{+},\ l\in \{1,\ldots ,n-1\}.}$

Систему нерівностей одержану застосуванням методу Фур'є — Моцкіна до останньої змінної можна також записати як

${\displaystyle T_{n}Ax\leqslant T_{n}b,}$

де ${\displaystyle T_{n}}$ є матрицею розмірності ${\displaystyle (m_{1}\cdot m_{2}+m_{3})\times m}$ для якої у ${\displaystyle (t-1)\cdot m_{2}+s}$ -ому рядку (що, як і вище відповідає впорядкованій парі індексів ${\displaystyle (i_{t},\ j_{s})}$, де ${\displaystyle i_{t}\in I_{n}^{-},\ j_{s}\in I_{n}^{+}}$) ненульовими є тільки елементи у ${\displaystyle i_{t}}$-ому і ${\displaystyle j_{s}}$-ому стовпцях, які є рівними ${\displaystyle {1 \over a_{i_{t},n}}}$ і ${\displaystyle -{1 \over a_{j_{s},n}}}$ відповідно. Останній стовпець матриці ${\displaystyle T_{n}A}$ є нульовим.

На наступному кроці методом Фур'є — Моцкіна можна виключити змінну ${\displaystyle x_{n-1}.}$ Результат зновуж можна записати як ${\displaystyle T_{n-1}T_{n}Ax\leqslant T_{n-1}T_{n}b,}$ для деякої матриці ${\displaystyle T_{n-1}.}$ Після n кроків і виключення усіх змінних остаточно одержується система ${\displaystyle TAx\leqslant Tb,}$ де ${\displaystyle T=T_{1}T_{2}\ldots T_{n},}$ для матриць ${\displaystyle T_{i}}$ які на кожному етапі визначаються, як і вище.

Добуток ${\displaystyle TA}$ є нульовою матрицею і після n кроків система нерівностей має вид ${\displaystyle 0\leqslant Tb.}$ Зокрема початкова система нерівностей має розв'язок тоді і тільки тоді коли всі елементи вектора ${\displaystyle Tb}$ є невід'ємними.

Приклад

Нехай задано систему нерівностей із трьома змінними:

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

Для виключення змінної 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}}}$

Відповідно права сторона кожної нерівності зі знаком "≤" має бути не меншою, ніж права сторона нерівності зі знаком "≥". Загалом одержуються 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}}\geqslant {\frac {10+5y-4z}{2}}\\{\frac {-12+2y+6z}{3}}\geqslant {\frac {9+6y-3z}{3}}\\\end{cases}}}$

Застосування

Складність алгоритму

Після застосування одного кроку методу Фур'є — Моцкіна до системи із ${\displaystyle m}$ нерівностей може бути одержано щонайбільше ${\displaystyle m^{2}/4}$ нерівностей, відповідно після ${\displaystyle n}$ кроків одержується щонайбільше ${\displaystyle 4(m/4)^{2^{n}}}$ нерівностей, тобто кількість зростає як подвійне експоненціювання. Причиною цього є величезна кількість залежних нерівностей, які випливають з інших. Тому простий метод Фур'є — Моцкіна на практиці не використовується. Кількість незалежних нерівностей зростає експоненційно. Залежні нерівності можна виявляти за допомогою лінійного програмування.

Також метод має численні теоретичні застосування.

Лема Фаркаша і пов'язані твердження

Метод Фур'є — Моцкіна можна використати для доведення багатьох альтернативних тверджень, які стверджують, що з деяких двох систем лінійних рівнянь та нерівностей розв'язок має одна і тільки одна.

Одне із таких тверджень, яке є варіантом леми Фаркаша відразу випливає із матричного запису результатів застосування метод Фур'є — Моцкіна. Вище була отримана матиця ${\displaystyle T}$ така, що після ${\displaystyle n}$ послідовних кроків метод Фур'є — Моцкіна одержується система нерівностей ${\displaystyle TAx\leqslant Tb}$ і добуток ${\displaystyle TA}$ є нульовою матрицею. Також із властивостей методу ця система має хоч один розв'язок тоді і тільки тоді коли хоч один розв'язок має початкова система ${\displaystyle Ax\leqslant b,}$ а матриця ${\displaystyle T}$ є невід'ємною (оскільки вона є добутком невід'ємних матриць ${\displaystyle T_{i}}$) . Тому, якщо система ${\displaystyle Ax\leqslant b}$ не має розв'язку то нерівності${\displaystyle 0\leqslant Tb}$ не всі виконуються тобто існує рядок матриці ${\displaystyle T}$ добуток якого на вектор ${\displaystyle b}$ є від'ємним. Іншими словами існує вектор стовпець ${\displaystyle c}$ розмірності ${\displaystyle m}$ із невід'ємними компонентами, що ${\displaystyle c^{T}A=0}$ і ${\displaystyle c^{T}b<0}$. Натомість якщо система ${\displaystyle Ax\leqslant b}$ має розв'язки, то із ${\displaystyle c^{T}A=0}$ випливає ${\displaystyle c^{T}b\geqslant 0.}$ Відповідно із двох систем нижче має розв'язок одна і тільки одна:

1. ${\displaystyle Ax\leq b,\quad x\in \mathbb {R} ^{n},}$
2. ${\displaystyle c^{T}A=0,\quad c^{T}b<0,\quad c\in \mathbb {R} ^{m},\quad c\geqslant 0.}$

Звідси, як вказано у статті лема Фаркаша можна одержати і стандартну лему Фаркаша, яка стверджує, що із двох систем нижче має розв'язок одна і тільки одна:

1. ${\displaystyle Ax=b,\quad x\geqslant 0,\quad x\in \mathbb {R} ^{n}}$
2. ${\displaystyle c^{T}A\leqslant 0,\quad c^{T}b>0\quad c\in \mathbb {R} ^{m}.}$

Див. також

• Лема Фаркаша
• Політоп

Примітки

1. J.B.J. Fourier у: Analyse des travaux de l'Académie Royale des Sciences pendant l'année 1824, Partie mathématique, 1827.
2. T.S. Motzkin: Beiträge zur Theorie der Linearen Ungleichungen.
3. David Monniaux, Quantifier elimination by lazy model enumeration [ 20 вересня 2021 у Wayback Machine.], Computer aided verification (CAV) 2010.

Література

• Komei Fukuda. Lecture: Polyhedral Computation, Spring 2016.
• Schrijver, Alexander (1998). Theory of Linear and Integer Programming. John Wiley & sons. с. 155–156. ISBN .