Си/Си++ Поиск минимума кусочно-линейной функции

[Маришка_Курносова]

Задано n линейных функций:
y1=A1*x + B1;
y2=A2*x + B2;
…;
Yn=An*x + Bn;
Найти минимум «верхнюю огибающей» этих функций, то есть кусочно-линейной функции
Y(x) = max(Ai*x +Bi) -> min. Под max i. а под min х

Указание: Можно от произвольной точки двигаться точкам излома огибающей в сторону её убывания

Сама мало понимаю как это должно происходить.

P.S. буду благодарна за подсказки к решению или готовые варианты ответов, даже если не на Си. Заранее спасибо. Ребят, если можно, поскорее, пожалуйста.

[vlad_light]

сплайны только начал изучать...
Значит максимум и минимум - это числа? Если да - то алгоритм такой:
Yi(X) = Ki*Xi + Bi; Xi є [Xj,X(j+1)]
1)k<0 => max(Y) = Y(Xj);
2)k>0 => max(Y) = Y(X(j+1))
для минимума - аналогично.

Входные данные:
2-мерный массив чисел {(Ki, Bi) | i є {1, 2, ... , n} }
1-мерный массив разбития отрезка X={X1, X2, ... , Xn}
на отрезки: [A=X1, X2], [X2, X3], ... , [X(n-1), Xn=B]

[coinkrsk]

Если не учитывать пару кривых случаев, то верхняя огибающая - выпуклая вниз кусочно-линейная функция ака ямка Надо найти минимум. Самое простое - подсмотреть идею. Откуда? Как в большинстве задач оптимизации - либо из биологии, либо из физики. Тут чистая физика. Идея такая: берем самую крутую прямую(наибольший коэффициент углового наклона (a_max)) которая, очевидно, будет правым краем нашей "ямки". И пускаем по ней шарик. Куда покатится шарик? Правильно, по антиградиенту, те в сторону наибольшего убывания. Понятно, что скатится шарик на дно ямки, его- то мы и ищем. Осталость определить когда нужно менять прямые по которым катиться. Смотрим на примере для первой линии: смотрим все пересечения (1, 2 и 3). Берем либо самое правое (наибольший х) либо самое верхнее (наибольший у) кому как больше нравиться функции линейные – результат не изменится – это точка номер 1. Меняем линию и катимся по другой. Продолжаем в том же духе пока линия не будет наклонена отрицательно(a<=0), тут стоп, шарик не покатится вверх. Ответ – последняя точка пересечения.

[sult9191]

coinkrsk а как можно организовать переход от одной линии на другую в программе?

Сообщение от coinkrsk

Если не учитывать пару кривых случаев, то верхняя огибающая - выпуклая вниз кусочно-линейная функция ака ямка Надо найти минимум. Самое простое - подсмотреть идею. Откуда? Как в большинстве задач оптимизации - либо из биологии, либо из физики. Тут чистая физика. Идея такая: берем самую крутую прямую(наибольший коэффициент углового наклона (a_max)) которая, очевидно, будет правым краем нашей "ямки". И пускаем по ней шарик. Куда покатится шарик? Правильно, по антиградиенту, те в сторону наибольшего убывания. Понятно, что скатится шарик на дно ямки, его- то мы и ищем. Осталость определить когда нужно менять прямые по которым катиться. Смотрим на примере для первой линии: смотрим все пересечения (1, 2 и 3). Берем либо самое правое (наибольший х) либо самое верхнее (наибольший у) кому как больше нравиться функции линейные – результат не изменится – это точка номер 1. Меняем линию и катимся по другой. Продолжаем в том же духе пока линия не будет наклонена отрицательно(a<=0), тут стоп, шарик не покатится вверх. Ответ – последняя точка пересечения.

а как можно организовать переход от одной линии на другую в программе?

[coinkrsk]

Просто. Или сложно. Как хотите.

P.S. Чем конкретнее вопрос, тем конкретнее ответ.