Introducción a los problemas de optimización

01 · Elegir la mejor alternativa

Qué significa optimizar

Optimizar consiste en seleccionar, entre todas las decisiones permitidas, aquella que produce el mejor valor de una magnitud de interés.

Según el problema, «mejor» puede significar menor tiempo, menor costo, menor consumo de memoria, mayor rendimiento, mayor beneficio o mayor calidad.

02 · Anatomía del problema

Los cinco componentes básicos

Si uno de estos componentes queda ambiguo, es probable que el modelo responda una pregunta distinta de la planteada.

03 · Sentido de optimización

Maximizar o minimizar

Un mismo problema puede expresarse de ambas formas: maximizar B(x) equivale a minimizar −B(x). Aun así, conservar el sentido natural suele facilitar la interpretación.

04 · Variable de decisión

Representar aquello que puede cambiar

La variable de decisión debe corresponder a una elección controlable. En este curso trabajaremos principalmente con una variable real x.

Una buena definición incluye significado y unidades:

No todo dato del enunciado debe convertirse en variable. La cantidad total de registros, el precio por unidad o la memoria disponible pueden permanecer como parámetros fijos.

05 · Función objetivo

Traducir la calidad de una decisión a un número

La función objetivo asigna un valor medible a cada decisión:

Para comparar decisiones, todas deben evaluarse con la misma función y bajo las mismas hipótesis. El objetivo debe incluir los efectos relevantes, no solamente el término más fácil de calcular.

Por ejemplo, aumentar un lote puede reducir la cantidad de operaciones, pero aumentar el uso de memoria. Un modelo útil debe representar el intercambio que realmente importa.

06 · Datos y parámetros

Separar lo elegido de lo conocido

Variable

Valor que se permite modificar para buscar una mejor solución.

Parámetro

Constante del modelo durante una ejecución, aunque pueda cambiar entre escenarios.

Medición

Dato observado que ayuda a estimar parámetros o validar resultados.

Si T(x) = A/x + Bx, x puede ser el tamaño elegido, mientras A y B representan características conocidas de la carga y del sistema.

07 · Decisiones permitidas

Restricciones y dominio factible

Las restricciones expresan límites físicos, lógicos o comerciales:

• x > 0 porque un tamaño no puede ser nulo;
• x ≤ 64 por memoria disponible;
• x entero si representa una cantidad de elementos;
• una condición de seguridad o calidad mínima;
• un intervalo impuesto por una interfaz o protocolo.

El conjunto de todos los valores que satisfacen simultáneamente las restricciones se llama dominio factible.

08 · Antes de comparar

Solución factible y solución óptima

Una alternativa con un valor objetivo excelente pero fuera de las restricciones no compite por la solución. La factibilidad se comprueba antes de comparar calidad.

09 · Dos respuestas relacionadas

Optimizador y valor óptimo

Conviene distinguir:

Si x* es el tamaño de lote que minimiza una latencia, entonces J(x*) es la latencia mínima predicha.

Puede haber varios optimizadores con el mismo valor óptimo. Informar solo el valor de la función no indica qué decisión debe implementar el programa.

10 · Alcance de la solución

Óptimos locales y absolutos

• Un óptimo local supera a las decisiones suficientemente cercanas.
• Un óptimo absoluto supera a todas las decisiones factibles.

En un problema real buscamos normalmente una solución absoluta dentro del dominio factible. Las derivadas generan y clasifican candidatos locales; luego es necesario comparar todos los candidatos relevantes y las fronteras permitidas.

Una función con varios valles puede ofrecer una buena solución local que no sea la mejor global.

11 · Naturaleza de la decisión

Variables continuas y discretas

Una aproximación frecuente consiste en resolver primero un modelo continuo y después comparar los enteros factibles cercanos. El redondeo automático no garantiza la mejor opción discreta.

12 · Calidad del modelo

Un óptimo matemático puede no ser una buena decisión real

La solución solo es tan útil como las hipótesis del modelo. Antes de aceptarla conviene revisar:

• si las unidades de todos los términos son compatibles;
• si se omitió algún costo o restricción importante;
• si los parámetros corresponden al entorno actual;
• si la función es válida en todo el dominio utilizado;
• si la decisión soporta variaciones o ruido en los datos;
• si el resultado puede implementarse.

Optimizar una métrica incompleta puede empeorar el sistema en dimensiones que el objetivo no representa.

13 · Caso de identificación

Elegir el tamaño de un lote

Supongamos el modelo:

Sin resolver todavía el problema, podemos identificar:

• decisión: x, tamaño del lote;
• objetivo: T(x), tiempo estimado;
• sentido: minimizar;
• restricción: 2 ≤ x ≤ 64;
• parámetros: 120, 0,15 y 8;
• decisión real: probablemente entera, aunque la aproximación analítica use reales.

El término 120/x disminuye con lotes mayores, mientras 0,15x aumenta. El intercambio entre ambos hace razonable buscar un mínimo interior.

14 · Exploración interactiva

Laboratorio: comparar decisiones factibles

Elegí un escenario, mové la decisión y guardá un candidato de referencia. El laboratorio compara objetivos respetando si el problema minimiza o maximiza.

La zona factible aparece resaltada. El punto cambia de color cuando la decisión viola una restricción.

Preguntas para explorar

1. Guardá dos candidatos factibles y comprobá cómo cambia «mejor» entre minimizar y maximizar.
2. Seleccioná un valor fuera del intervalo permitido. ¿Por qué su objetivo deja de competir?
3. En rendimiento, compará puntos simétricos respecto de x = 20.
4. ¿El mejor valor continuo sería necesariamente implementable si x debe ser entero?

15 · Implementación

Representar el problema como un objeto

const problema = {
  nombre: "tamaño de lote",
  sentido: "min",
  limiteInferior: 2,
  limiteSuperior: 64,
  objetivo: x => 120 / x + 0.15 * x + 8
};

function evaluarCandidato(problema, x) {
  const factible = Number.isFinite(x) &&
    x >= problema.limiteInferior &&
    x <= problema.limiteSuperior;

  return {
    x,
    factible,
    valor: factible ? problema.objetivo(x) : null
  };
}

for (const x of [1, 8, 24, 64, 80]) {
  console.log(evaluarCandidato(problema, x));
}

Comparar dos candidatos factibles

function evaluarCandidato(problema, x) {
  const factible = Number.isFinite(x) &&
    x >= problema.limiteInferior &&
    x <= problema.limiteSuperior;
  return { x, factible, valor: factible ? problema.objetivo(x) : null };
}

function elegirMejor(problema, candidatoA, candidatoB) {
  const a = evaluarCandidato(problema, candidatoA);
  const b = evaluarCandidato(problema, candidatoB);

  if (!a.factible) return b.factible ? b : null;
  if (!b.factible) return a;

  const mejoraA = problema.sentido === "min"
    ? a.valor <= b.valor
    : a.valor >= b.valor;

  return mejoraA ? a : b;
}

const problema = {
  sentido: "max",
  limiteInferior: 0,
  limiteSuperior: 40,
  objetivo: x => x * (40 - x)
};

console.log(elegirMejor(problema, 10, 20));
console.log(elegirMejor(problema, 20, 50));

16 · Comprensión

Confusiones frecuentes

17 · Práctica guiada

Ejercicios de identificación

Ejercicio 1: tiempo de respuesta

«Elegir la cantidad de procesos para obtener el menor tiempo, usando entre 1 y 16 procesos». Identificá decisión, objetivo y restricción.

Ejercicio 2: cobertura

«Ajustar el radio de búsqueda para encontrar la mayor cantidad de resultados sin superar 200 ms». ¿Qué se maximiza y qué restringe?

Ejercicio 3: factibilidad

Si el dominio exige 5 ≤ x ≤ 30, clasificá x = 4, x = 18 y x = 31.

Ejercicio 4: decisión y resultado

Una configuración óptima usa 12 hilos y tarda 43 ms. Identificá x* y J(x*).

Ejercicio 5: modelo incompleto

Se maximiza rendimiento sin limitar memoria. El resultado exige más memoria que la disponible. ¿Qué falló?

18 · Síntesis

Ideas para recordar

En el próximo tema aprenderemos a traducir un enunciado a una función objetivo, restricciones y dominio factible de una variable.