Максимизировать функцию при ограничении

disepa

Как максимизировать ф-ю при ограничении (подскажите, где копать, а то все забыл).
g(n_1,...,n_m)=\sum_{i<j} n_i n_j
\sum_{i=1}^m n_i = n
Все числа целые и неотрицательные

kliM

Пишешь функцию Лоренца, ищешь ее седловую точку...

kliM

ой... наврал я...
если целые неизвестные, то надо по-другому...

yukos1988

Есть идея покопать на тему целочисленного программирования.
А вообще самое близкое из того, что на ВМиК читали - линейное целочисленное программирование.

kliM

в данном случае нужно искать целочисленное выпуклое программирование

Forsit

Возьмем максимизирующий набор (он, очевидно, есть)
Предположим, что элементы n_1 и n_2 отличаются более, чем на 1. и русть n_1-n_2>1
Рассмотрим набор (n_1-1 (n_2+1 ...,n_m.
без труда находим,что его сумма отличается от суммы первого на (n_1- n_2 -1 то есть больше.
Отсюда вывод: В максимальном наборе все числа отличаются не более чем на 1.
Надеюсь точную формулу ты напишешь сам -мне влом
Оставить комментарий
Имя или ник:
Комментарий: