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

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

$Ax⩽b,$

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

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

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

Опис методу

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

$a_{i1}{x}_1+\dots +a_{ij}{x}_j+\dots +a_{in}{x}_n⩽b_i,i=1,\dots ,m,$

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

$Ax⩽b,$

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

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

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

$x_n⩽b{\text{'}}_j-a{\text{'}}_{j1}{x}_1-\dots -a{\text{'}}_{jn-1}{x}_{n-1}=f_j(x_1,\dots ,x_{n-1}),$

де $a{\text{'}}_{jk}=\frac{a_{jk}}{a_{jn}},k=1,\dots ,n-1,b{\text{'}}_j=\frac{b_j}{a_{jn}},$ а $f_j(x_1,\dots ,x_{n-1})$ позначає відповідну афінну функцію. Аналогічно для $i\in I_n^{-}$:

$x_n⩾b{\text{'}}_i-a{\text{'}}_{i1}{x}_1-\dots -a{\text{'}}_{in-1}{x}_{n-1}=g_i(x_1,\dots ,x_{n-1}),$

де $a{\text{'}}_{ik}=\frac{a_{ik}}{a_{in}},k=1,\dots ,n-1,b{\text{'}}_i=\frac{b_i}{a_{in}},$ а $g_j(x_1,\dots ,x_{n-1})$ позначає відповідну афінну функцію.

Нехай також для $k\in I_n^0$ позначено $h_k(x_1,\dots ,x_{n-1})=a_{k1}{x}_1+\dots +a_{in-1}{x}_{n-1}-b_k.$ Загалом із цими позначеннями можна записати систему нерівностей у виді:

$\{\begin{array}{c}{x}_n⩽f_j(x_1,\dots ,x_{n-1}),\mathrm{\forall }j\in I_n^{+}\\ g_i(x_1,\dots ,x_{n-1})⩽x_n,\mathrm{\forall }i\in I_n^{-}\\ h_k(x_1,\dots ,x_{n-1})⩽0,\mathrm{\forall }k\in I_n^0\end{array}.$

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

$\{\begin{array}{c}{g}_i(x_1,\dots ,x_{n-1})⩽f_j(x_1,\dots ,x_{n-1}),\mathrm{\forall }i\in I_n^{-},j\in I_n^{+}\\ h_k(x_1,\dots ,x_{n-1})⩽0,\mathrm{\forall }k\in I_n^0\end{array}.$

Якщо $x_1,\dots ,x_n$ є розв'язком початкової системи, то очевидно $x_1,\dots ,x_{n-1}$ є розв'язком нової системи. Навпаки, якщо нова система має розв'язок $x_1,\dots ,x_{n-1}$, то $\underset{i\in I_n^{-}}{\max }{g}_i(x_1,\dots ,x_{n-1})⩽\underset{j\in I_n^{+}}{\min }{f}_j(x_1,\dots ,x_{n-1})$ і для кожного $x_n,$ що задовольняє нерівності:

$\underset{i\in I_n^{-}}{\max }{g}_i(x_1,\dots ,x_{n-1})⩽x_n⩽\underset{j\in I_n^{+}}{\min }{f}_j(x_1,\dots ,x_{n-1})$

$x_1,\dots ,x_n$ є розв'язком початкової системи. Зокрема система лінійних нерівностей має хоча б один розв'язок тоді і лише тоді коли хоча б один розв'язок має система одержана виключенням змінної методом Фур'є — Моцкіна.

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

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

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

Елементи нових матриці і вектора можна записати із формул вище. Для цього нехай $|I_n^{+}|=m_1,|I_n^{-}|=m_2,|I_n^0|=m_3,$ де $m_1+m_2+m_3=m.$ Якщо $m_1=m$ або $m_2=m$ то нова система нерівностей буде порожньою і будь-який набір чисел $x_1,\dots ,x_{n-1}$ буде її розв'язкам. Тоді для початкової системи $x_1,\dots ,x_n$ буде розв'язком, якщо $\max g_i(x_1,\dots ,x_{n-1})⩽x_n$ чи в залежності від умов, $x_n⩽\min f_j(x_1,\dots ,x_{n-1}).$ Тому можна припустити $m_1⩾1,m_2⩾1,m_3⩾0.$

Нехай $i_1<i_2<\dots <i_{m_1}$ є індексами із множини $I_n^{+}$, $j_1<j_2<\dots <j_{m_2}$ є індексами із множини $I_n^{-}$, а $k_1<k_2<\dots <k_{m_3}$є індексами із множини $I_n^0.$ Кожен рядок нової матриці $A^{\prime }$ відповідає або парі індексів $i_t\in I_n^{-},j_s\in I_n^{+}$ або індексу $k_r\in I_n^0.$ Для визначеності нехай парі індексів $(i_t,j_s)$ відповідає $(t-1)\cdot m_2+s$ -ий рядок матриці, а індексу $k_r$ — рядок номер $m_1\cdot m_2+r.$

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

$a{\text{'}}_{m_1{m}_2+r,l}=a_{k_r,l},b{\text{'}}_{m_1{m}_2+r}=b_{k_r},k_r\in I_n^0,l\in \{1,\dots ,n-1\}.$

Для пари індексів $(i_t,j_s)$ відповідні елементи одержуються із нерівності $g_{i_t}(x_1,\dots ,x_{n-1})⩽f_{j_s}(x_1,\dots ,x_{n-1}):$

$a{\text{'}}_{(t-1)\cdot m_2+s,l}=\frac{a_{j_s,l}}{a_{j_s,n}}-\frac{a_{i_t,l}}{a_{i_t,n}},b{\text{'}}_{(t-1)\cdot m_2+s}=\frac{b_{j_s}}{a_{j_s,n}}-\frac{b_{i_t}}{a_{i_t,n}},i_t\in I_n^{-},j_s\in I_n^{+},l\in \{1,\dots ,n-1\}.$

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

$T_{n}Ax⩽T_{n}b,$

де $T_n$ є матрицею розмірності $(m_1\cdot m_2+m_3)\times m$ для якої у $(t-1)\cdot m_2+s$ -ому рядку (що, як і вище відповідає впорядкованій парі індексів $(i_t,j_s)$, де $i_t\in I_n^{-},j_s\in I_n^{+}$) ненульовими є тільки елементи у $i_t$-ому і $j_s$-ому стовпцях, які є рівними $\frac{1}{a_{i_t,n}}$ і $-\frac{1}{a_{j_s,n}}$ відповідно. Останній стовпець матриці $T_{n}A$ є нульовим.

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

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

Приклад

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

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

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

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

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

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

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

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

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

1. $Ax\le b,x\in {ℝ}^n,$
2. $c^{T}A=0,c^{T}b<0,c\in {ℝ}^m,c⩾0.$

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

1. $Ax=b,x⩾0,x\in {ℝ}^n$
2. $c^{T}A⩽0,c^{T}b>0c\in {ℝ}^m.$

Див. також

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

Література

• Komei Fukuda. Lecture: Polyhedral Computation, Spring 2016.
• Шаблон:Cite book