Оптимизационная задача

[alisa-lebovski]

Надо максимизировать по $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$, а постепенно. Но меня смущает, что это все интуитивные соображения, а не строгие. Вопрос в том, верны ли они вообще, если да, то как это доказать, а если нет, то как правильно.

[grizzly]

alisa-lebovski в сообщении #1265704 писал(а):

Но меня смущает, что это все интуитивные соображения, а не строгие.

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

[Markiyan Hirnyk]

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

[alisa-lebovski]

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)$ надо брать сначала побольше, а потом поменьше.

[Markiyan Hirnyk]

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

[grizzly]

alisa-lebovski в сообщении #1265831 писал(а):

поэтому $x(t)$ надо брать сначала побольше, а потом поменьше.

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

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

[alisa-lebovski]

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$. Меня смущает, что это интуитивное рассуждение, а не научное.

[grizzly]

alisa-lebovski в сообщении #1265848 писал(а):

Сами $g_1$ и $g_2$ удовлетворяют третьему условию

Тогда конечно. Простите, сегодня что-то у меня совсем плохо с телепатией

[Markiyan Hirnyk]

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

[alisa-lebovski]

Markiyan Hirnyk в сообщении #1265855 писал(а):

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

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

[Markiyan Hirnyk]

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

[grizzly]

alisa-lebovski в сообщении #1265848 писал(а):

Меня смущает, что это интуитивное рассуждение, а не научное.

Вы сможете доказать, что переход от $g_1$ к $g_2$ по константе может быть только в одном месте? В том смысле, что любой другой переход по константе будет хуже невозможен по услвоиям (upd).

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

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

[sup]

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]$ (и хотя бы в одной точке строго больше).

[alisa-lebovski]

sup, рассмотреть интегральную функцию было отличной идеей!

Для нее получается верхняя граница:

$$y(t)\le\min\left\{\int_0^t g_2(u)\,du,A-\int_t^1 g_1(u)\,du\right\}.$$

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

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