Сделал замену переменных (x = n, y = n + m, X = N, Y = N + M) и продиференцировал. В итоге максимум достигается при n + m = (N + M) / 2. В случае четного N + M максимум функции равен 2 * N / (N + M)
Если N = M, делаем n = m = N / 2. Получается N / (N + N) + (N — N / 2) / (2 * N — N) = 1. Можно лучше?
если m = 0, f(n, m) = n / n + (N — n) / (N — n + M) > 1
Но это же означает, что максимум достигается на граничных условиях. Перебирая все границы можно получить, что максимольное существующее значение получается при n = 1, m = 0, и он равен (2 * N + M — 2) / (N + M — 1)
Попробуйте расписать все честно и посчитать, верхняя часть дроби
— 2 n^2 + (2 N + M — 2 m) n + mN — > max (можно разложить на множители и найти максимум относительно n)
Нижняя часть (n + m) ((N+M) — (n+m)), естественно минимизируется при n+m = (N+M), хотя здесь и возникает деление на 0. То есть если верхняя часть максимум, а нижняя минимум и эти значения согласуется, тогда есть ответ :) Естественно что максимум по очевидным причинам меньше 2
Вообще если зафиксировать к примеру m, то функция получается такая
f (n) = 2 — m/(n + m) — (M — m) / (-n + (N+M -m)), то есть искать надо минимум среди
m/(n+m) + (M — m) / ( -n + (N+M-m)) -> min
А потом среди минимумов параметров m, найти глобальный минимум.
Как я написал выше, это была «простая» задача из теории вероятностей: как можно разложить 100 черных и 100 белых шаров по двум корзинам, чтобы вероятность вытащить черный была максимальна. Хотел получить строгое формальное решение (плюс немного обобщил), но уперся в оптимизацию. Честно говоря, многое из матана позабывал, поэтому и задал вопрос.
Думал есть какое-нибудь красивое и простое аналитическое решение, вроде как метод коэффициентов лагранжа для линейных функций. Но и этого вполне хватит, спасибо за помощь.
Непонятно обобщение :) Расскажите с обобщением понятно, что если положить 100 черных в одну корзину и 100 белых в другую вероятность максимальная. Так же понятно если в одной корзине доминируют одни шары скажем с X%, то и вероятность вытащить их X% из этой корзины. Поэтому кладем по максимуму разные шары в разные корзины
Не понял ваш вывод. Разделять по максимуму — не оптимальный вариант.
Корзины после распределения шаров выбираются наугад. Далее, вытягивается наугад ОДИН шар. Формально, это будет так:
Ну, если максимум что мы можем выжать из n/(n+m) это 1, при m = 0. Идем дальше, (N-n)/(N-n + M-m) тут лучшим случаем будет тот, где разность M — m минимальна, то есть 1. Следовательно, при M = 1, m = 0, n = 1, N = INF, предел (N-n)/(N-n + M-m) равен единице, а значит максимум функции стремится к 2.
Спасибо, но тут два момента.
1 — N,M — некие константы. Мы решаем относительно них.
2 — неясно, почему вы оптимизируете два элемента в сумме по-отдельности; мы имеем право это делать?
От N и M ничего не зависит, т.к. оба слагаемых стремятся к максимуму (1) при неограниченном возрастании m и n, при условии неограниченного убывания m/n. Асимптотически максимум — 2.
Если областью определения было бы 0 < m < M и 0 < n < N, то решение было бы при m = [M/2], n = [N/2].
1, Ну тогда стояло условие поставить как: n <= N ^ m <= M ^ N, M > 0. А то немного сбивает с толку.
2. Я оптимизирую по частям, а не по отдельности, то есть сохраняю условия оптимизации первой части для второй и наоборот.
Ну при таком раскладе, можно пойти в лоб, и воспользоваться школьной математикой 9го класса, как вариант. Хотя решение и не самое удачное, наверное.
На самом деле частные производные тут совсем не помогут, условия поставлены не совсем корректно. При n +m -> 0 или n+m -> N+ M, получается любой бесконечно большое число. Так что тут задача в целочисленных ограничений, которые зачастую не имеют красивого решения.
Для целочисленных задач могу посоветовать построить графики в Mathematica или поискать для конкретных значений N, M экстремумы. Ну а вообще попытаться наложить больше ограничений на N, M.
Также можно посмотреть в сторону f (x, y) > или < f(x, y+1) и f (x +1, y) > или < f(x, y). Если функция монотонна (она квадратичная скорее всего будет 2 отрезка монотонности), то можно методом спуска определить целочисленный экстремум.
сдается мне, это не математика 9-го класса. По крайней мере, здесь есть ограничения, которые нужно учитывать. И максимум будет как раз на границе. Я было через коеффициенты лагранжа пошел, но что-то запутался… забыл матан :)
2 vics001,
Согласен, не совсем корректно поставил условия. Тут можно смело положить, что n > 0 (строго больше нуля) чтобы отрезать ассимптотическое приближение. В исходной задачи N=M=100, так что я здесь немного обобщил.
Раз пошла такая пьянка — это была «простая» задача из теории вероятностей: как можно разложить 100 черных и 100 белых шаров по двум корзинам, чтобы вероятность вытащить черный была максимальна. Хотел получить строгое формальное решение, но уперся в оптимизацию. Честно говоря, многое из матана позабывал, поэтому и задал вопрос.
