Maximizar $\sum{a_i^2}$ dado $\sum{a_i}=237$

Question

Hace poco me encontré con el siguiente problema:

Considere 18 números enteros en el segmento $[10; 20]$ . Encuentre el máximo valor posible de $$ \sum_{i=1}^{18} {a_i^2} $$ dado que $$\sum_{i=1}^{18} {a_i}=237$$

No sé muy bien cómo enfocar este problema. El caso es que resolviéndolo como un problema de optimización de restricciones obtuve la solución $a_1=a_2=...=a_n=\frac{237}{18} \approx13.2$

Pero tenemos que resolverlo en números enteros. Y sólo tomando números alrededor de $13.2$ no tiene sentido para mí. ¿Alguna idea?

Answer 1

Una solución óptima no puede tener $10 < a_i \leq a_j < 20$ para algunos $i$ , $j$ porque eso contradice la optimización (se podría incrementar $a_j$ y decremento $a_i$ y obtener un valor objetivo más alto). Por lo tanto, puede haber como máximo un elemento que no sea $10$ o $20$ .

Por tanto, existe una solución óptima para la que $a_1, \ldots, a_m$ tomar el valor $10$ , $a_{m+1},\ldots,a_{17}$ tomar el valor $20$ y $a_{18} \in [10,20] \cap \mathbb{Z}$ . De la restricción de igualdad se deduce que $a_{18} = 237 - 10m - 20(17-m) = 10m-103$ . La única $m$ para lo cual $10m-103 \in [10,20]$ es $m=12$ Así que el problema está resuelto.

Si tuviera varios $m$ , debe evaluar el valor objetivo ( $100m + 400(17-m) + a_{18}^2 = 100m^2 - 2360m + 17409$ ) y elija el que tenga el objetivo más alto.

---

Otro método Este problema también es fácil de resolver con un solucionador de programación entera después de formularlo adecuadamente. Sea $x_{10}$ denotan el número de veces que se elige $10$ etc, entonces el problema es:

\begin{align} \max_{x} \quad & \sum_{i=10}^{20} i^2 x_i \\ \text{s.t.} \quad & \sum_{i=10}^{20} i x_i = 237 \\ & \sum_{i=10}^{20} x_i = 18 \\ & x_i \in \mathbb{Z}_+ \end{align}

He añadido el modelo GAMS a continuación, que puedes resolver en el servidor NEOS. La solución óptima es $$a = (10,10,10,10,10,10,10,10,10,10,10,10,17,20,20,20,20,20)$$

con un valor objetivo de 3489.

Set
   i 'idx'    / r10*r20 /;

Parameter
   a(i) / r10 10, r11 11, r12 12, r13 13, r14 14, r15 15, r16 16, r17 17, r18 18, r19 19, r20 20 /;

Integer   Variable x(i);
Variable z;

Equation objective, budget, eighteen_numbers;
objective.. z =e= sum(i, a(i)*a(i)*x(i));
budget.. sum(i, a(i)*x(i)) =e= 237;
eighteen_numbers.. sum(i, x(i)) =e= 18;

Model knapsack / all /;
solve knapsack max z using mip;

Answer 2

La idea es suponer que todos los $a_i$ son fijos excepto dos de ellos, y ver lo que sucede si se añade $1$ a uno y restar $1$ del otro. Así, por ejemplo $a_1 = x$ , $a_2 = y$ y todos los demás $a_i$ son fijos. A continuación, añadiendo $1$ a $x$ y restando $1$ de $y$ da la misma suma, pero ¿qué ocurre con la suma de cuadrados? $$(x+1)^2 + (y-1)^2 - (x^2 + y^2)$$ es la cantidad en la que aumenta o disminuye la suma de cuadrados. Pero esto es $$2x + 1 - 2y + 1 = 2(x-y+1).$$ Así que si $x \ge y$ Esto significa que la suma de los cuadrados aumentará si añadimos $1$ a $x$ y restar $1$ de $y$ . La aplicación repetida de esta lógica significa que la suma de cuadrados se maximiza realmente cuando $x$ es lo más grande posible y $y$ es lo más pequeño posible. Luego repetimos esta lógica para los demás términos de la suma; se deduce que el máximo se alcanza cuando podemos hacer que el mayor número de $a_i$ lo más grande posible. Dado que el $a_i$ se limitan a $[10; 20]$ queremos el mayor $m$ tal que $20 m + 10(18 - m) \le 237$ o $m = 5$ . Esto significa que $5$ de la $a_i$ son iguales a $20$ , $12$ de ellos son $10$ y el último constituye el resto, que tiene valor $17$ y la suma de los cuadrados es $3489$ .

---

Una forma ligeramente diferente de ver la segunda parte de la solución es observar que, dado que cada uno de los $a_i$ debe ser como mínimo $10$ podemos crear una secuencia auxiliar $b_1, b_2, \ldots, b_{18}$ con $b_i = a_i - 10$ Por lo tanto $b_i \in [0; 10]$ y la restricción sobre ellos es $$\sum_{i=1}^{18} b_i = 57.$$ Entonces, el mismo razonamiento anterior da cinco $b_i$ igual a $10$ y una $b_i$ es igual a $7$ .

Answer 3

Esto parece un trabajo para la desigualdad de Cauchy. Por Cauchy, tenemos que $(a_1^2+a_2^2+a_3^2...+a_{17}^2+a_{18}^2)(1+1+1 ... + 1 +1) \ge (a_1(1) + a_2(1) +a_3(1)...a_{17}(1) + a_{18}(1))^2$ .

Tenga en cuenta que hay $18$ los en $(1+1+1 ... + 1 +1)$ para emparejarse con $18$ $a$ s.

Así, esta desigualdad se simplifica como $18(a_1^2+a_2^2+a_3^2...+a_{17}^2+a_{18}^2) \ge (a_1 + a_2 +a_3...a_{17} + a_{18})^2$ . Sabemos que la suma de la izquierda es $237$ Por lo tanto, tenemos $18(a_1^2+a_2^2+a_3^2...+a_{17}^2+a_{18}^2) \ge (237)^2$ . Simplificando, obtenemos $(a_1^2+a_2^2+a_3^2...+a_{17}^2+a_{18}^2) \ge 3120.5$ . Por la condición de desigualdad de Cauchy, debemos tener todos $a$ sean iguales, por lo que obtenemos $18a_1^2 \ge 3120.5$ o $a_1 \le -13.6666$ o $a_1\ge 13.16666...$ . Sin embargo, eso significa que hacer todos los términos $13/-13$ en realidad te lleva al MÍNIMO. Sin embargo, como la desigualdad de Cauchy no tiene límite superior, eso significa que el máximo de los cuadrados es INFINITO. Esto se debe a que se pueden tomar enteros negativos ridículamente pequeños, y enteros ridículamente grandes, y aún así tener una suma de $237$ . Sin embargo, la suma de sus cuadrados será ENORME.

Por ejemplo, la suma de $-1000,-2000,-3000,-4000,-5000,-6000,-7000,-8000,-9000,-10000,-11000,-12000,-13000,-14000,-15000,-16000,-17000, 153237$

es $237$ pero la suma de los cuadrados de este conjunto es $2.5266578169×10^{10}$ .