2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение23.03.2014, 16:29 
Заслуженный участник


23/07/08
10626
Crna Gora
_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.

 Профиль  
                  
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение23.03.2014, 17:13 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение23.03.2014, 17:22 


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

 Профиль  
                  
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение23.03.2014, 19:30 


01/04/11
29
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$?

 Профиль  
                  
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение23.03.2014, 23:27 
Заслуженный участник


23/07/08
10626
Crna Gora
Если $\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, Вам понятны такие наглядные пояснения, или Вам ближе формальные рассуждения?

 Профиль  
                  
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение24.03.2014, 00:02 


01/04/11
29
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$, то многогранник неограничен, в противном случае ограничен.
?


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

 Профиль  
                  
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение24.03.2014, 00:24 
Заслуженный участник


16/02/13
4105
Владивосток
_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$. Если многогранник ограничен, то и сумма координат точек ограничена; если неограничен, то, поскольку все координаты неотрицательны, сумма неограничена и факт этот вскроет симлекс-метод.

 Профиль  
                  
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение24.03.2014, 01:00 


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

 Профиль  
                  
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение24.03.2014, 01:10 
Заслуженный участник


23/07/08
10626
Crna Gora
_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$ в качестве критерия неограниченности использовать нельзя.

 Профиль  
                  
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение25.03.2014, 01:20 
Заслуженный участник


23/07/08
10626
Crna Gora
Н. В. Черникова, “Алгоритм для нахождения общей формулы неотрицательных решений системы линейных уравнений”, Журнал вычислительной математики и математической физики, 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.

 Профиль  
                  
 
 Re: Проверка ограниченности многогранника линейной системы
Сообщение26.03.2014, 23:22 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group