Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 4 ] |
|
Автор | Сообщение | |
---|---|---|
Somebody |
|
|
Возникла такая задача: [math]\min_{w_1, \dots, w_k} \{ x_1 + \dots + x_n\},[/math] (1) [math]\sum_{i=1}^{n} {\boldsymbol{w}}{\boldsymbol{a_{i,j}}^T}x_i=b_j,[/math] (2) [math]{\boldsymbol{D}}\boldsymbol{w}>\boldsymbol{d}.[/math] (3) Здесь жирными символами обозначены вектора и матрицы. При этом группа условий (2) однозначно задаёт [math]x[/math], то есть существует единственное решение СЛАУ [math]\boldsymbol{Q}\boldsymbol{x}=\boldsymbol{b},[/math] где каждый элемент матрицы [math]q_{i,j}[/math] есть некоторая линейная комбинация элементов [math]\{w_1, \dots, w_k\}[/math]: [math]q_{i,j}={\boldsymbol{w}}{\boldsymbol{a_{i,j}}^T}.[/math] Очевидно, что [math]\boldsymbol{x}=\boldsymbol{Q}^{-1}\boldsymbol{b}[/math] и можно задавать целевую функцию в виде [math]\boldsymbol{Q}^{-1}\boldsymbol{b}\boldsymbol{1},[/math] где [math]\boldsymbol{1}[/math] есть единичный столбец. Но как оптимизировать это дальше точными методами не знаю. С другой стороны можно рассмотреть [math]{x_1, \dots, x_n,}[/math] в качестве переменных и величин и производить минимизацию и по ним, но тогда условия (2) уже не будет линейным. Получается уже квадратичное программирование (в общем случае это NP задачи), а хотелось свести эту задачу к чему-то более простому с точки зрения вычислений. Буду благодарен за любую информацию и идеи. |
||
Вернуться к началу | ||
Somebody |
|
|
Здравствуйте.
Возникла такая задача: [math]\min_{w_1, \dots, w_k} \{ x_1 + \dots + x_n\},[/math] (1) [math]\sum_{i=1}^{n} {\boldsymbol{w}}{\boldsymbol{a_{i,j}}^T}x_i=b_j,[/math] (2) [math]{\boldsymbol{D}}\boldsymbol{w}>\boldsymbol{d}.[/math] (3) Здесь жирными символами обозначены вектора и матрицы. При этом группа условий (2) однозначно задаёт [math]x[/math], то есть существует единственное решение СЛАУ [math]\boldsymbol{Q}\boldsymbol{x}=\boldsymbol{b},[/math] где каждый элемент матрицы [math]q_{i,j}[/math] есть некоторая линейная комбинация элементов [math]\{w_1, \dots, w_k\}[/math]: [math]q_{i,j}={\boldsymbol{w}}{\boldsymbol{a_{i,j}}^T}.[/math] Очевидно, что [math]\boldsymbol{x}=\boldsymbol{Q}^{-1}\boldsymbol{b}[/math] и можно задавать целевую функцию в виде [math]\boldsymbol{Q}^{-1}\boldsymbol{b}\boldsymbol{1},[/math] где [math]\boldsymbol{1}[/math] есть единичный столбец. Но как оптимизировать это дальше точными методами не знаю. С другой стороны можно рассмотреть [math]{x_1, \dots, x_n,}[/math] в качестве переменных и величин и производить минимизацию и по ним, но тогда условия (2) уже не будет линейным. Получается уже квадратичное программирование (в общем случае это NP задачи), а хотелось свести эту задачу к чему-то более простому с точки зрения вычислений. Буду благодарен за любую информацию и идеи. |
||
Вернуться к началу | ||
searcher |
|
|
Somebody писал(а): С другой стороны можно рассмотреть x1,…,xn, в качестве переменных и величин и производить минимизацию и по ним, но тогда условия (2) уже не будет линейным. Правильно. Somebody писал(а): Получается уже квадратичное программирование Неправильно. Получается задача нелинейного программирования. |
||
Вернуться к началу | ||
Somebody |
|
|
searcher писал(а): Somebody писал(а): Получается уже квадратичное программирование Неправильно. Получается задача нелинейного программирования. Задача с квадратичными ограничениями и линейной целевой функцией (QCLP). Да, можно рассмотреть и в общем случае в виде задачи нелинейной оптимизации, но хотелось свести её во что-то более красивое. Возможно, что метод множителей Лагранжа что-то тогда и даст, но пока не пытался его использовать. |
||
Вернуться к началу | ||
[ Сообщений: 4 ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 9 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |