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

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

Ax\leqslant b,

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

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

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

Опис методу

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

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

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

Ax\leqslant b,

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

Геометрично така система нерівностей задає опуклий політоп. Метод Фур'є — Моцкіна дає змогу перейти від системи нерівностей із n невідомими до системи із n - 1 невідомою. Послідовно далі можна цю систему привести до системи із n - 2 невідомими і так далі. Щоправда при цьому кількість нерівностей збільшується. Після n кроків виключення змінних одержується система нерівностей без змінних, тобто система виду $0\leqslant c_{i},\ i=1,\ldots ,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}\leqslant b'_{j}-a'_{j1}x_{1}-\ldots -a'_{jn-1}x_{n-1}=f_{j}(x_{1},\ldots ,x_{n-1}),

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

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

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

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

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

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

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

Якщо $x_{1},\ldots ,x_{n}$ є розв'язком початкової системи, то очевидно $x_{1},\ldots ,x_{n-1}$ є розв'язком нової системи. Навпаки, якщо нова система має розв'язок $x_{1},\ldots ,x_{n-1}$ , то $\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})$ і для кожного $x_{n},$ що задовольняє нерівності:

\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})

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

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

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

A'x'\leqslant b',\quad

де матриця

A'=(a'_{ij})

має розмірність

(|I_{n}^{+}|\cdot |I_{n}^{-}|+|I_{n}^{0}|)\times (n-1)

, а

b'

є вектор-стовпцем із

|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},\ldots ,x_{n-1}$ буде її розв'язкам. Тоді для початкової системи $x_{1},\ldots ,x_{n}$ буде розв'язком, якщо $\max g_{i}(x_{1},\ldots ,x_{n-1})\leqslant x_{n}$ чи в залежності від умов, $x_{n}\leqslant \min f_{j}(x_{1},\ldots ,x_{n-1}).$ Тому можна припустити $m_{1}\geqslant 1,\ m_{2}\geqslant 1,\ m_{3}\geqslant 0.$

Нехай $i_{1}<i_{2}<\ldots <i_{m_{1}}$ є індексами із множини $I_{n}^{+}$ , $j_{1}<j_{2}<\ldots <j_{m_{2}}$ є індексами із множини $I_{n}^{-}$ , а $k_{1}<k_{2}<\ldots <k_{m_{3}}$ є індексами із множини $I_{n}^{0}.$ Кожен рядок нової матриці $A'$ відповідає або парі індексів $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'_{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\}.

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

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\}.

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

T_{n}Ax\leqslant 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}$ -ому стовпцях, які є рівними ${1 \over a_{i_{t},n}}$ і $-{1 \over a_{j_{s},n}}$ відповідно. Останній стовпець матриці $T_{n}A$ є нульовим.

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

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

Приклад

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки

↑ J.B.J. Fourier у: Analyse des travaux de l'Académie Royale des Sciences pendant l'année 1824, Partie mathématique, 1827.
↑ T.S. Motzkin: Beiträge zur Theorie der Linearen Ungleichungen.
↑ 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 978-0-471-98232-6.

[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.

[1]

[2]

[3]

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

Зміст