2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Оптимизационная задача
Сообщение16.11.2017, 09:08 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
Надо максимизировать по $x(t)$ интеграл
$$\int_0^1f(t)x(t)\,dt,$$
где $f(t)\ge 0$ --- убывающая функция, при условиях
1) $$\int_0^1x(t)\,dt=A>0,$$
2) $$0\le g_1(t)\le x(t)\le g_2(t),\quad \forall 0\le t\le 1,$$
3) $$0\le x(t_2)-x(t_1)\le B(t_2-t_1),\quad \forall 0\le t_1\le t_2\le 1,$$
где $A,B>0$ --- константы, $g_1,g_2$ --- функции.

Идея в том, что раз $f(t)$ убывает, то функцию $x(t)$ надо сделать сначала как можно больше, равной $g_2$, а потом как можно меньше, равной $g_1$, а точку переключения выбрать исходя из условия 1). Но тогда $x(t)$ получается разрывной, и не удовлетворяет условию 3). Можно сделать $x(t)$ сначала равной $g_2$, а потом как можно меньше, но в рамках условия 3), чтобы не сразу переключалась на $g_1$, а постепенно. Но меня смущает, что это все интуитивные соображения, а не строгие. Вопрос в том, верны ли они вообще, если да, то как это доказать, а если нет, то как правильно.

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 10:42 
Заслуженный участник
Аватара пользователя


09/09/14
6328
alisa-lebovski в сообщении #1265704 писал(а):
Но меня смущает, что это все интуитивные соображения, а не строгие.
У Вас $x(t)$ -- неубывающая функция. Мне кажется, что из Ваших же соображений следует, что, по возможности, её нужно пытаться сделать константой (если позволяют ограничения $g_i(t)$. А если не позволяют, то приблизить к константе, насколько позволяет коридор ограничений и коэффициент $B$.

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 11:28 


11/07/16
801
Попробуйте дискретизировать задачу, выбрав достаточно большое натуральное число $N$ и рассматривая последовательность $x(t_j),\,t_j:=j/N,\,j=0,...,N,$ заменяя интегралы интегральными суммами и учитывая условие 3). Для нахождения элементов последовательности надо решить задачу линейного программирования. Затем задаем функцию $x(t)$ на всем отрезке $[0,1]$, применяя сплайны (Полагаю, достаточно кубических сплайнов.). Все это механизировано в Мэйпле и Математике.

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 17:51 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
grizzly в сообщении #1265721 писал(а):
alisa-lebovski в сообщении #1265704 писал(а):
Но меня смущает, что это все интуитивные соображения, а не строгие.
У Вас $x(t)$ -- неубывающая функция. Мне кажется, что из Ваших же соображений следует, что, по возможности, её нужно пытаться сделать константой (если позволяют ограничения $g_i(t)$. А если не позволяют, то приблизить к константе, насколько позволяет коридор ограничений и коэффициент $B$.


На самом деле, $g_1$ и $g_2$ тоже неубывающие функции, причем $g_1(0)=g_2(0)=0$, $g_1(1)=g_2(1)=1.$

Зачем же делать $x(t)$ ближе к константе? Я рассуждаю так: $f(t)$ убывает, значит, сначала она принимает большие значения, потом меньшие. Чтобы максимизировать интеграл, большие значения надо брать с большим весом, а меньшие с меньшим, поэтому $x(t)$ надо брать сначала побольше, а потом поменьше.

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 19:03 


11/07/16
801
alisa-lebovskiОжидаю вашей реакции и на мое предложение (как принято среди цивилизованных людей).
Искренне,
Маркиян Гирнык

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 19:07 
Заслуженный участник
Аватара пользователя


09/09/14
6328
alisa-lebovski в сообщении #1265831 писал(а):
поэтому $x(t)$ надо брать сначала побольше, а потом поменьше.
Конечно. Но поскольку $x(t)$ возрастает, то это "сначала побольше" всегда меньше, чем "потом поменьше". В идеале константа. Но раз есть такие условия на $g_i(x)$, то константы, понятно, не будет, а будет, видимо, какая-то лесенка с ровными ступеньками и наклонами с коэффициентом $B$ от ступеньки к ступеньке. А как аналитически правильно расставить эти ступеньки, я не знаю. Вам ведь нужно какое-то аналитическое рассуждение? или численное решение?

Нужно ещё учитывать, что не при любых $A$ и $B$ удастся вместить $x(t)$ в заданный коридор.

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 19:13 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
Markiyan Hirnyk в сообщении #1265846 писал(а):
alisa-lebovskiОжидаю вашей реакции и на мое предложение (как принято среди цивилизованных людей).
Искренне,
Маркиян Гирнык


Дело в том, что мне бы хотелось найти аналитическое решение в общем случае, насколько это возможно, а не численное в конкретном.

-- Чт ноя 16, 2017 19:24:41 --

grizzly в сообщении #1265847 писал(а):
alisa-lebovski в сообщении #1265831 писал(а):
поэтому $x(t)$ надо брать сначала побольше, а потом поменьше.
Конечно. Но поскольку $x(t)$ возрастает, то это "сначала побольше" всегда меньше, чем "потом поменьше". В идеале константа. Но раз есть такие условия на $g_i(x)$, то константы, понятно, не будет, а будет, видимо, какая-то лесенка с ровными ступеньками и наклонами с коэффициентом $B$ от ступеньки к ступеньке. А как аналитически правильно расставить эти ступеньки, я не знаю. Вам ведь нужно какое-то аналитическое рассуждение? или численное решение?

Нужно ещё учитывать, что не при любых $A$ и $B$ удастся вместить $x(t)$ в заданный коридор.


Сами $g_1$ и $g_2$ удовлетворяют третьему условию, а $A$ лежит между интегралами от них от 0 до 1, с этим все в порядке. Так что есть такой вариант: до какого-то места $x(t)$ равно $g_2$, потом постоянная до пересечения с графиком $g_1$, и дальше $g_1$. Это я и имела в виду под "потом поменьше". Точка переключения с $g_2$ на константу определяется по первому условию из $A$. Меня смущает, что это интуитивное рассуждение, а не научное.

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 19:26 
Заслуженный участник
Аватара пользователя


09/09/14
6328
alisa-lebovski в сообщении #1265848 писал(а):
Сами $g_1$ и $g_2$ удовлетворяют третьему условию
Тогда конечно. Простите, сегодня что-то у меня совсем плохо с телепатией :D

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 19:31 


11/07/16
801
Вы не пробовали рассмотреть конкретные функции и постоянные, например, $f(x):=1-x$?

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 20:52 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
Markiyan Hirnyk в сообщении #1265855 писал(а):
Вы не пробовали рассмотреть конкретные функции и постоянные, например, $f(x):=1-x$?


Делать, как вы предлагаете, не умею. Я теоретик. Ищу аналитическое решение.

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 21:15 


11/07/16
801
Вам и предлагают попытаться найти "аналитическое решение" для простого конкретного случая, чтобы иметь модельный пример.

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение16.11.2017, 21:20 
Заслуженный участник
Аватара пользователя


09/09/14
6328
alisa-lebovski в сообщении #1265848 писал(а):
Меня смущает, что это интуитивное рассуждение, а не научное.
Вы сможете доказать, что переход от $g_1$ к $g_2$ по константе может быть только в одном месте? В том смысле, что любой другой переход по константе будет хуже невозможен по услвоиям (upd).

А потом доказать, что любой участок $x(t)$, который не лежит на одной из границ и не является константой, можно улучшить. Рассмотрите участок между точками $t_1$ и $t_2$ с подъёмом, менее крутым, чем для коэффициента $B$ и замените его на лесенку, у которой первый подъём максимально крут как можно дольше. Должно получиться.

Останется показать, что этим исчерпываются все нетривиальные варианты.

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение17.11.2017, 09:54 
Заслуженный участник


22/11/10
1183
alisa-lebovski в сообщении #1265704 писал(а):
Можно сделать $x(t)$ сначала равной $g_2$, а потом как можно меньше, но в рамках условия 3), чтобы не сразу переключалась на $g_1$, а постепенно. Но меня смущает, что это все интуитивные соображения, а не строгие. Вопрос в том, верны ли они вообще, если да, то как это доказать, а если нет, то как правильно.

Можно предложить такой подход. Обозначим
$$y(t) = \int \limits_0^t x(s) \, ds$$
$$h(t) = |f'(t)| = - f'(t).$$
Тогда
$$ J(y) = \int \limits_0^1 f(t)x(t) \, dt = f(1) y(1) + \int \limits_0^1 h(t)y(t) \, dt.$$
Надо найти максимум $J(y)$ при условиях
$$y(0) = 0, \quad y(1) = A, \quad g_1(t) \leqslant y'(t) \leqslant g_2(t), \quad 0 \leqslant y'' \leqslant  B.$$
Первое слагаемое в выражении для $J(y)$ фактически не зависит от $y$, а значит его можно "выкинуть". Остается интеграл. Пусть $y_1(t) \geqslant y_2(t)$. Тогда, очевидно, $J(y_1) \geqslant J(y_2)$. Если даны два допустимых управления $y_1(t), y_2(t)$, то напрашивается построить из них более оптимальное
$$y(t) = \max (y_1(t), y_2(t)).$$
Отсюда уже легко получить, что действительно надо выбирать оптимальное $y(t)$ максимально возможным ( с учетом роста и условия $y(1) = A$).

К сожалению, такой прямолинейный подход с максимумом не вполне корректен. Поскольку в точках переключения может нарушаться условие на вторую производную. Тем не менее, мне кажется, что на этом пути можно доказать, что оптимальное решение сначала двигается по "максимальной" кривой, а потом тормозит насколько может, чтобы вписаться в условие $y(1) = A$. Просто надо показать, что оптимальное решение не меньше любого допустимого на некотором отрезке $[0, t_0]$ (и хотя бы в одной точке строго больше).

 Профиль  
                  
 
 Re: Оптимизационная задача
Сообщение17.11.2017, 16:57 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
sup, рассмотреть интегральную функцию было отличной идеей!

Для нее получается верхняя граница:
$$y(t)\le\min\left\{\int_0^t g_2(u)\,du,A-\int_t^1 g_1(u)\,du\right\}.$$

Эта граница состоит из двух кусков, выпуклых внутрь, соединяющихся в одной точке, изломом наружу.
Максимальная выпуклая функция, "натягивающаяся" на границу снизу, должна совпадать с ней по краям, а в районе излома границы иметь прямой участок, касательный к обоим ее кускам в некоторых точках - он и соответствует участку постоянства $x(t)$.

Всем спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

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



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

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


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

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