Известна ли такая постановка задачи линейного прогр-ия ?

[ishak]

Положим вектор целевой функции единичным.Для единичного вектора целевой функции f0
и заданных ограничениях найдем решение х задачи линейного программирования(ЗЛП).
Найденный х будет являться решением ЗЛП для некоторого подпространства векторов
целевой функции. Очевидно,что существует такой единичный вектор f1 ,принадлежащий
этому подпростанству, при котором целевая функция при заданном х достигает своего максимума. Другими словами, f1 есть "ближайший" вектор к полученному решению х.
Процесс решения ЗЛП есть нахождение х и f1 при заданном начальном f0.
К сожалению ,нигде не нашел такой постановки задачи ЗЛП и методов решения для f1.
Буду благодарен за ссылки и комментарии.

[maxal]

Попробую переформулировать в матрично-векторной форме.
Пусть матрица $A$ и вектор $b$ фиксированы.
Определим функцию $f(c)=\max c^T x$ при ограничениях $Ax\geq b$, $x\geq 0.$

Пусть $c_0$ - это некоторые единичный вектор. Найдем вектор $x_0\geq 0$ такой, что $f(c_0)=c_0^T x_0,$ $Ax_0\geq b.$
Пусть $C = \{ c : |c|=1\ \mbox{и}\ f(c) = c^T x_0 \}.$ Требуется найти такой вектор $c_1\in C$, что $\max_{c\in C} f(c) = f(c_1).$

Так?

[ishak]

Давайте по-другому.
Определена функция $f(c,x)=c^Tx$, при ограничениях $Ax<=b,x>=0$, $c^Tc=1$.
Найдем такой $x_0$, что $f(c_0,x_0)=max f(c_0,x)$. Тогда вектору $x_0$ соответствует множество векторов $C$, для каждого члена $c_k$ этого множества $f(c_k,x_0)=max f(c_k,x)$. Или $C = \{ c^Tc=1 \mbox{ и}\ f(c,x_0)=max f(c,x) \}.$
Требуется найти $c_1$ , при условии $c_1 \in C $ , такой что $ f(c_1,x_0)=max f(c,x_0) \}.$

Рассмотрим 2-мерный случай.Проведем оси $X1$ и $X2$.
Ограничения-неравенства заданы двумя пересекающимися прямыми, т.е. определена матрица $A(2,2)$ и вектор $b$ . Для вектора $c_0$ точка пересечения прямых( вектор $x_0$ ) определяет максимум функции $f(c_0,x)$ .Теперь определим $C$.
Из начала координат проведем два вектора-строки матрицы $A(2,2)$ . Очевидно, что они ортональны соответствующим прямым.Эти два вектора ограничивают множество векторов $C$ , для которых $x_0$ есть решение ЗЛП. Вектор $c_0$ принадлежит этому множеству С , иначе задача не ограничена и $x_0$ не является решением ЗЛП.
Если $x_0$ принадлежит $C$ , то $c_1$ коллинеарен $x_0$.
Если $x_0$ не принадлежит $C$, то $c_1$ коллинеарен "ближайшему" вектору-строке.

[maxal]

ishak писал(а):

Давайте по-другому.

Дык это то же самое, что я написал.

В этой задаче имеет смысл прежде всего перейти к дуальной задаче, т.е. от
$\left\{\begin{array}{l}\max c^T x\\ Ax \leq b\\ x\geq 0\end{array}\right.$
к
$\left\{\begin{array}{l}\min b^T y\\ A^T y \geq c\\ y\geq 0\end{array}\right.$

Мы знаем, что максимум в исходной задаче достигается на векторе $x_0$, поэтому мы можем считать, что $b^T y = c^T x_0$. Задача превращается в отыскание максимума
$\left\{\begin{array}{l}\max c^T x_0\\ A^T y - c \geq 0\\ b^T y = c^T x_0\\ y\geq 0\\ c^T c = 1\end{array}\right.$
где неизвестными являются векторы $y$ и $c$. К сожалению, последнее условие не является линейным, поэтому средствами линейного программирования эту задачу не решить. Придется привлекать методы квадратичного программирования.

[maxal]

Алгоритм решения похожей задачи описан в статье:
Shang-Wang Chang. "A Programming Problem with a Linear Objective Function Having the Quadratic Constraints of the Form $\frac{1}{2}x' x + p' x \leq r$". Management Science, Vol. 23, No. 3. (Nov., 1976), pp. 324-331.

[ishak]

Спасибо за ответ и ссылку.
Теперь о $c^Tc=1$ :

maxal писал(а):

К сожалению, последнее условие не является линейным, поэтому средствами линейного программирования эту задачу не решить. Придется привлекать методы квадратичного программирования.

Не хотелось бы.
Нелинейности исчезают, если линейные ограничения введены и для $x$ и для $c$ в постановке задачи :
$\left\{\begin{array}{l}\max c^T x\\ Ax \leq b\\ x\geq 0\\ Dc \leq v\\ c\geq 0\end{array}\right.$
Придется ли тогда привлекать методы квадратичного программирования ?

[maxal]

ishak писал(а):

Придется ли тогда привлекать методы квадратичного программирования ?

Ну если в качестве ответа нужен именно единичный вектор - то возникает квадратичное ограничение. Если такого требования нет или если единичность рассматривать не в евклидовой норме, а например в норме $l_1$, то получится ЗЛП.

[ishak]

Требование единичности снимается.
Фраза "получится ЗЛП" означает , что квадратичные методы не нужны и для решения подходит симплекс-метод ?

[maxal]

Ну да. Решайте следующую ЗЛП относительно $c$ и $y$:
$\left\{\begin{array}{l}\max c^T x_0\\ A^T y - c \geq 0\\ b^T y = c^T x_0\\ y\geq 0\\ Dc\leq v\\ c\geq 0\end{array}\right.$
Найденный c - и будет искомым.

[ishak]

Согласен.
Если Вы согласны , рассмотрим уже другую задачу, где не задается $c_0$ и не ищется $x_0$.
Просто задана линейная функция и линейные ограничения для каждого из аргументов.
$\left\{\begin{array}{l}\max c^T x\\ Ax \leq b\\ x\geq 0\\ Dc \leq v\\ c\geq 0\end{array}\right.$
Сводится ли эта задача к классической ЗЛП ?
Придется ли привлекать методы квадратичного программирования для решения этой задачи ?

[Vassil]

Если неизвестные в Вашей задачи все $x_i$ и все $c_i$, то очевидно, что задача нелинейная, более конкретно - квадратическая, так как целевая функция содержит члены, которые --- произведения двух неизвестных. Ограничения --- линейны.

[ishak]

Спасибо.