Проверка ограниченности многогранника линейной системы

[_nobody]

Добрый день.

Пусть задана задача линейного программирования, например, в канонической форме (матричная запись):
$c^Tx\to \max$\\ Ax=b$ \\ x\ge 0$
Или задана в более общем виде
$c^Tx\to \max \\ A_1x=b_1 \\ A_2x\le b_2 \\ x\ge 0$

Как можно быстро проверить, ограничен ли многогранник, который образован системой ограничений?
Есть ли для этого какие-то результаты (желательно не как результат работы симплекс-метода)? Если да, то где об этом можно почитать?

Заранее благодарен.

[iifat]

Подозреваю, никак. Более того, симплекс-метод даст ограниченность/неограниченность в одном направлении; про другие он ничего не скажет. Можно построить куб и провести $2^n$ вычислений по симпрекс-методу, конечно...

[svv]

Я совершенно не знаком с линейным программированием.
Правильно ли я понимаю, что переменные $x_1,..., x_n$ не должны принимать отрицательных значений?

[_nobody]

svv,
да, условие $x\ge 0$ как раз означает, что каждый элемент в векторе $x$ должен быть неотрицательным.

[svv]

Второй вопрос. Правильно ли, что каждое из неравенств, входящих в $A_2x\leqslant b_2$, запрещает «дальнюю» половину пространства, в которой не лежит начало координат, а допускает «ближнюю», в которой начало координат находится?

(Т.е., например, вот так $x_1+x_2+x_3+x_4\leqslant 1$ бывает, а вот так $x_1+x_2+x_3+x_4\geqslant 1$ нет.)

[_nobody]

svv,
а это уже зависит от направления (знаков). Например, может получиться так, что многогранник (пусть он ограничен) вообще не касается координатных осей, т.е. как бы подвешен — как раз за счет того, что есть неравенства, которые его смещают от осей в "положительном" направлении, а другие ограничивают его от ухода в бесконечность (ограничивается гранями, заданными неравенствами).
В общем, любое неравенство $Cx\ge d$ всегда сводится к виду $-Cx\le -d$.

P.S. Если что, задача линейного программирования в форме неравенств всегда сводима к каноническому виду путем введения по дополнительной переменной для каждого неравенства, так что при желании достаточно рассматривать систему с ограничениями-равенствами.

[iifat]

svv в сообщении #839157 писал(а):

Я совершенно не знаком с линейным программированием

Что, правда?
На всякий случай: для решения симплекс-методом задача приводится к каноническому виду:

_nobody в сообщении #838962 писал(а):

$\begin{cases}c^Tx\to \max\\Ax=b\\x\ge 0\end{cases}$

С помощью добавления переменных. Если, например, нас интересуют положительные и отрицательные значения кой-нить переменной, для неё вводятся две дополнительных неотрицательных: $x_i=x'_i-x''_i$. Неравенства преобразуются в равенства: $x_1+x_2 \geqslant 3$ преобразуется в $x_1+x_2-x_3=3$

-- 21.03.2014, 13:45 --

В принципе, надо посмотреть теорию. Возможно, например, максимум функции $\sum \left |x_i\right |$ на выпуклом многограннике будет достигаться на вершине. Тогда можно попробовать модифицировать симплекс-метод — в конце концов, это просто перебор вершин многогранника. Тогда, по крайней мере, хватит одного прогона.

-- 21.03.2014, 13:48 --

Так и не смог модуль закрыть.

[svv]

Хорошо, что все неравенства можно свести к $\mathbf x\geqslant 0$. Пусть они уже сведены. Парочка очевидных вещей.

У нас есть условия $A\mathbf x=\mathbf b$. Выясняем, существует ли хоть одно решение $\mathbf x=\mathbf a\geqslant 0$ (уж это-то теория наверняка умеет). Допустим, существует. Тогда любое другое можно представить в виде $\mathbf x=\mathbf a+\mathbf y$, где $\mathbf y=\sum\limits_i c_i \mathbf y_i$. Здесь набор векторов $\mathbf y_i$, $i=1..k$ — фундаментальная система решений однородной системы $A\mathbf y=0$. Тогда вопрос об ограниченности многогранника сводится к такому:
Существует ли набор коэффициентов $c_i$, при котором линейная комбинация $\sum\limits_i c_i \mathbf y_i\geqslant 0$ ?

(Оффтоп)

Условия $A\mathbf x=\mathbf b$ определяют $k$-мерную плоскость, а любой касательный к ней вектор имеет вид $\mathbf y=\sum\limits_i c_i \mathbf y_i$. Двигаясь из точки $\mathbf a$ в этой плоскости по лучу $\mathbf x=\mathbf a+t\mathbf y$, $t\geqslant 0$, мы не наткнемся ни на одну из гиперплоскостей $x_i=0$, если все координаты вектора $\mathbf y$ неотрицательны, и тогда многогранник неограничен. В противном случае какую-то гиперплоскость $x_i=0$ пересечём обязательно, тогда многогранник ограничен.

Другая переформулировка: многогранник ограничен, если задача $A\mathbf x=0$, $\mathbf x\geqslant 0$ имеет только тривиальное решение $\mathbf x=0$. Неограничен в противном случае.

-- Пт мар 21, 2014 22:09:56 --

iifat в сообщении #839169 писал(а):

Что, правда?

Честное пионерское. Также я ничего не понимаю в теории групп, теории чисел... да мало ли ещё разделов в математике.

[iifat]

svv в сообщении #839501 писал(а):

Условия $A\mathbf x=\mathbf b$ определяют $k$-мерную плоскость

О! Спасибо, не заметил. А ведь и правда, по сути, пересечение плоскости с "первым квадрантом". Тогда необходимо проверить, что эта плоскость пересекается со всеми осями в положительных точках! Решаем n систем, получающихся из нашей подстановкой нулей вместо всех переменных кроме одной. Если все решения существуют и положительны, область ограничена. Иначе — нет.
Подозреваю, это примерно то, что вы и писали.

[svv]

Точно!

(Оффтоп)

Тоже думал, как его назвать — квадрант, октант... По аналогии с мультиполем —мультант? $2^n$-ант? Первый — в любом случае.

[_nobody]

Я правильно понимаю, что для ограниченности необходимо и достаточно, чтобы $\operatorname{rank}(A)=n$, где $n$ — число переменных?
В частности, верно для невырожденных квадратных матриц размерности $n\times n$.

[svv]

Нет, от ранга $r=\operatorname{rank}A$ зависит размерность $k$ плоскости, которую составляют решения $\mathbf x$ системы $A\mathbf x=\mathbf b$.

$\bullet$ Пусть система совместна (ранг $r$ основной матрицы равен рангу расширенной).
Тогда при ранге $r$ размерность будет $k=n-r$.
$\bullet$ Пусть, далее, все уравнения независимы, ни одно не является следствием остальных.
Тогда ранг $r=m$, т.е. количеству уравнений.

Если уравнений $>n$, то обязательно будут зависимые, мы этот случай исключили.
Если уравнений $n$, то будет единственное решение, точка. Размерность равна нулю.
Если уравнений $n-1$, то будет прямая решений. Размерность равна $1$.
...
Если уравнений $1$, то будет гиперплоскость решений, размерности $n-1$.

Это всё еще без учета ограничений $\mathbf x\geqslant 0$

Ну, а ограниченность многогранника зависит не от ранга матрицы $r$, т.е. размерности $k$ плоскости решений, а от расположения плоскости относительно системы координат. Наглядно — от того, как она сдвинута-повернута. Если хоть один её касательный вектор $\mathbf y$ имеет все неотрицательные координаты, многогранник неограничен: двигаясь по этому направлению, мы никогда не встретим никакую координатную гиперплоскость $x_i=0$.

[_nobody]

svv
Разве сформулированное Вами суждение «система $Ax=0$ имеет только решение $x=0$» ($x\in\mathbb{R}^n$) не эквивалетно утверждению «$ \operatorname{rank}(A)=n$», т.е. когда после приведения к диагональному виду методом Гаусса получаем $A\sim \begin{pmatrix}E_{n\times n} \\ 0\end{pmatrix}$, где $E_{n\times n} $ — единичная матрица размерности $n$ (нулевая подматрица может быть и нулевой размерности)?

[svv]

Нет, там же вся хитрость в маленьком и почти незаметном уточнении $\mathbf x\geqslant 0$. Разберем на примере $n=3,\quad r=m=1, \quad k=2$. Геометрическое место точек $\mathbf x$ — решений системы $A\mathbf x=\mathbf b$ — плоскость в трехмерном пространстве.

Поясню, как работает та переформулировка. Отбрасываем $\mathbf b$, получаем систему $A\mathbf x=0$. Соответствующая плоскость теперь проходит через начало координат. Но пока про ограниченность многогранника ещё ничего нельзя сказать.

Пожалуйста, представьте один из нижних углов Вашей комнаты — это начало координат. От него идут три ребра (два «стена-пол» и одно «стена-стена») — пусть это положительные половины координатных осей. Все три координаты любой точки комнаты (в том числе точно на стене и точно на полу) неотрицательны.

Проведём через угол плоскость. Возможны два различных случая:
1) Плоскость вообще не проходит через комнату, она находится вне её, пересечение только в начале координат. Такому при $\mathbf b\geqslant 0$ соответствует ограниченность многогранника.
2) Плоскость проходит через комнату (хотя бы даже совпадая со стеной или полом). Такому при $\mathbf b\geqslant 0$ соответствует неограниченность многогранника.

[_nobody]

Тогда встает вопрос — как проверить, что система $Ax=0$ если и имеет нетривиальные решения, то только те, где хотя бы одна компонента решения отрицательна? Только путем явного нахождения фундаментальной системы решений (после диагонализации матрицы $A\sim \begin{pmatrix}E_n & A_{12} \\ \mathbb{O}& \mathbb{O}\end{pmatrix}$ проверяем, чтобы в каждом столбце подматрицы $A_{12}$ был хотя бы один положительный элемент — тогда в ФСР все решения вне первого ортанта)?

Но условие $ \operatorname{rank}(A)=n$ ведь является достаточным, но не необходимым, так?

——————————

Видимо, я опять ошибаюсь по поводу ФСР: $Ax=0$ может иметь либо одно тривиальное решение, либо бесконечное множество решений, посему каждое решение должно быть с минимум одной отрицательной компонентой, а при построении ФСР обычно свободные переменные поочередно полагаются равными 1 при остальных нулевых, но в этом случае не исключена ситуация, когда при некотором наборе значений свободных переменных все равно получится решение с неотрицательными компонентами...
Поэтому если $y_1,...,y_r$ — фундаментальная система решений, то необходим критерий, утверждающий, что при любом наборе коэффициентов $\lambda_1,\ldots,\lambda_r$ решение $\sum\limits_{i=1}^r \lambda_iy_i$ всегда имеет хотя бы одну отрицательную координату.