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

[svv]

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

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

Когда $\operatorname{rank}A=n$, это тривиальный случай, это фактически вообще не задача линейного программирования. Здесь надо просто решить систему $A\mathbf x=\mathbf b$ с квадратной невырожденной матрицей, у нее будет единственное решение. Далее либо оно удовлетворяет условиям $\mathbf x\geqslant 0$, и тогда невозможно найти ни лучше, ни хуже, ибо нет выбора. Либо не удовлетворяет, тогда задача не имеет решений.

Вот картинка к менее тривиальному случаю $r=\operatorname{rank}A=1, n=3$.

Здесь на рисунке а) изображен ограниченный многогранник размерности $k=n-r=2$ при $\mathbf b\neq 0$, который находится на некоторой плоскости. Полагая $\mathbf b=0$, мы сдвигаем плоскость параллельно самой себе так, чтобы она прошла через начало координат, рисунок б) Тогда единственная точка пересечения с «комнатой» — начало координат, отмечено розовым. У любого решения (синие векторы) некоторые координаты отрицательные.

Другой случай на рисунке в). Ранги те же, но многогранник неограничен. Сдвигая плоскость параллельно, чтобы она проходила через начало координат, получим, как на рисунке г), ситуацию, когда часть плоскости находится в «комнате». Соответственно, некоторые решения имеют все неотрицательные координаты, одно из них изображено синим вектором.

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

как проверить

По поводу хорошего алгоритма надо подумать, я хотел только показать геометрическую интерпретацию (хотя она может вдохновить и натолкнуть) и её связь с чисто алгебраическими условиями неограниченности.
См. советы iifat.

[iifat]

Не стоит, я там фигню написал. Заворожила меня эта ваша "плоскость".
Возьмём, к примеру, трёхмерное пространство. Если $\operatorname{rank}A=1$, то у нас плоскость и можно найти её пересечение с тремя координатными осями; если $\operatorname{rank}A=2$, то это прямая, и надо найти её пересечение с координатными плоскостями. Их должно быть две. в обоих случаях мы, собственно, находим все вершины многогранника. Подозреваю, при обобщении задачи тенденция сохранится, а это посложнее собственно симплекс-метода.

[_nobody]

Проблема симплекс-метода еще в том, что он может найти оптимальное решение, не задев "бесконечность", т.е. его работа не гарантирует, что всегда будет обнаружена неограниченность области допустимых решений.

[_nobody]

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

Тогда любое другое можно представить в виде $\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$ ?

Вопрос: почему для всех возможных коэффициентов требуется $\sum\limits_i c_i \mathbf y_i\geqslant 0$, а не $a+\sum\limits_i c_i \mathbf y_i\geqslant 0 \Leftrightarrow \sum\limits_i c_i \mathbf y_i\geqslant -a$?

[svv]

Если $\mathbf a\geqslant 0$ — некоторое решение системы $A\mathbf x=\mathbf b$, то любое другое можно представить в виде $\mathbf x=\mathbf a+\mathbf y$, где $\mathbf y$ — решение однородной системы $A\mathbf x=0$. Общее решение неоднородной системы есть сумма частного решения неоднородной системы и общего решения однородной системы.

Если $\mathbf y$ — решение однородной системы, то $t\mathbf y$ тоже, поэтому решение системы $A\mathbf x=\mathbf b$ можно записать и так: $\mathbf x=\mathbf a+t\mathbf y$. Такая форма нацелена на то, чтобы зафиксировать $\mathbf a$ и $\mathbf y$, а менять $t$ (причем $t\geqslant 0$). Это даёт луч с началом в $\mathbf a$ и направляющим вектором $\mathbf y$. Луч лежит в $k$-мерной плоскости решений, о которой я говорил ранее.

Будем отождествлять точки и их радиус-векторы. Назовём хорошим вектор (или точку), у которого все координаты неотрицательны, а плохим — у которого есть отрицательные.

Если многогранник неограничен, то существует лежащий в плоскости многогранника луч, состоящий только из хороших векторов. Если многогранник ограничен, то некоторая часть луча может быть хорошей, но начиная с некоторого $t$ его векторы будут плохими.

Если вектор $\mathbf a$ хороший (а я этого требую), вопрос неограниченности многогранника определяется хорошестью вектора $\mathbf y$, но не $\mathbf a+\mathbf y$. Ведь неотрицательность координат $\mathbf a$ и $\mathbf y$ гарантирует неотрицательность координат $\mathbf a+t\mathbf y$ при $t\geqslant 0$. А неотрицательность координат $\mathbf a$ и $\mathbf a+\mathbf y$ ничего не гарантирует (см. ниже левую картинку).
Зато если координаты $\mathbf y$ строго положительны, то даже при плохом исходном векторе $\mathbf a$ многогранник будет неограниченным! (см. ниже правую картинку)

Взгляните на картинки.
На левой изображена ситуация, когда $\mathbf a$ хороший, а $\mathbf y$ плохой. Многогранник ограничен.
На правой изображена ситуация, когда $\mathbf a$ плохой, а $\mathbf y$ хороший. Многогранник неограничен.
Розовым изображено множество решений неоднородной системы. Нарисовано несколько линейных комбинаций вида $\mathbf a+t\mathbf y$ (при $t=0, 0.5, 1, 1.5...$, примерно). Хорошие линейные комбинации изображены синим, плохие красным. Серым изображена плохая область, где хотя бы одна координата отрицательна.

Видно, что:
при плохом $\mathbf y$ для достаточно большого $t$ сумма $\mathbf a+t\mathbf y$ будет плохой; и тот факт, что сумма $\mathbf a+\mathbf y$ (при $t=1$) хорошая, ничего не значит;
при хорошем $\mathbf y$ для достаточно большого $t$ сумма $\mathbf a+t\mathbf y$ будет хорошей.

_nobody, Вам понятны такие наглядные пояснения, или Вам ближе формальные рассуждения?

[_nobody]

svv
спасибо за пояснения!

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

_nobody, Вам понятны такие наглядные пояснения (под наглядностью понимается не только что-либо графическое, но и всё что угодно, способствующее пониманию), или Вам ближе формальные рассуждения?

Вообще я приверженец формализма с наглядным обоснованием, так что как Вам удобнее.

Стоит на всякий случай добавить, что рисунок приведен для плоского случая, т.е. пространства $\mathbb{R}^2$.

Вот на рисунке приведен пример, когда ФСР состоит из одного вектора $y$. Но, например, на левом изображении видно, что при любом $t$, даже отрицательном, вектор $ty$ будет иметь отрицательную координату, т.е. условие $ty\ge 0$ не выполняется никогда, но при этом "многогранник" ограничен, а на правом рисунке как раз противоложное — возможно выполнение $ty\ge 0$, но область неограничена. Поэтому вопрос для меня открыт:

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

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

Тогда любое другое можно представить в виде $\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$ ?

Вопрос: почему для всех возможных коэффициентов требуется $\sum\limits_i c_i \mathbf y_i\geqslant 0$, а не $a+\sum\limits_i c_i \mathbf y_i\geqslant 0 \Leftrightarrow \sum\limits_i c_i \mathbf y_i\geqslant -a$?

А о соображении, откуда берется условие, уже было сформировано (а точнее: было сформировано, потом забылось — посему и вопрос возник, а сейчас снова вспомнилось ), как возможность продолжить n-мерный фундаментальный вектор насколько угодно далеко, вследствие чего и возникает неограниченность...

————————————————————
Или я просто наоборот представляю конечное утверждение?
На самом деле должно быть так:
Если существует набор коэффициентов $(\lambda_1,\ldots,\lambda_r)\in\mathbb{R}^r$ такой, что $\sum\limits_{i=1}^r \lambda_i y_i> 0$, то многогранник неограничен, в противном случае ограничен.
?


По всей видимости, так. В общем, вопрос лишь в способе выяснения, как это проверять для конкретных числовых матриц линейной системы.

[iifat]

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

почему для всех возможных коэффициентов требуется $\sum\limits_i c_i \mathbf y_i\geqslant 0$, а не $a+\sum\limits_i c_i \mathbf y_i\geqslant 0 \Leftrightarrow \sum\limits_i c_i \mathbf y_i\geqslant -a$?

Да потому ж, что нам надо умножить $\sum\limits_i c_i \mathbf y_i\geqslant 0$ на произвольную положительную величину и всё равно получить точку внутри нашего многогранника.
В общем, ещё подумав, прихожу к способу: решаем задачу с нашими ограничениями и целевой функцией $\sum x_i\to max$. Если многогранник ограничен, то и сумма координат точек ограничена; если неограничен, то, поскольку все координаты неотрицательны, сумма неограничена и факт этот вскроет симлекс-метод.

[_nobody]

iifat
Спасибо!
Интересно, есть ли более шустрые методы.

[svv]

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

На самом деле должно быть так:
Если существует набор коэффициентов $(\lambda_1,\ldots,\lambda_r)\in\mathbb{R}^r$ такой, что $\sum\limits_{i=1}^r \lambda_i y_i> 0$, то многогранник неограничен, в противном случае ограничен.
?

Да. На всякий случай: здесь каждое $y_i$ означает один из векторов ФСР. Я поэтому обозначал их полужирным: $\mathbf y_i$. Индекс $i$ нумерует вектор в наборе, а не координату вектора.

Некоторые координаты вектора $\mathbf y=\sum \lambda_i \mathbf y_i$ могут быть и нулевыми. Если при этом остальные положительны, многогранник всё равно будет неограниченным. В принципе, это важный частный случай, он возможен, когда плоскость параллельна одной или нескольким координатным осям. Поэтому я писал $\geqslant 0$, хотя, понятно, «совсем нулевой вектор» $\mathbf y$ в качестве критерия неограниченности использовать нельзя.

[svv]

Н. В. Черникова, “Алгоритм для нахождения общей формулы неотрицательных решений системы линейных уравнений”, Журнал вычислительной математики и математической физики, 4:4 (1964), 733–738
http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=7684&option_lang=rus
Там есть ссылка на полный текст в pdf-формате.
И как раз для однородных систем.

-- Вт мар 25, 2014 00:46:10 --

Lloyd L. Dines. On Positive Solutions of a System of Linear Equations.

[_nobody]

svv,
спасибо! Интересный метод в русской статье.