49. Optimización y análisis de relaciones discretas

49.1 Introducción: optimizar es elegir dentro de un espacio

Una relación describe qué opciones son compatibles. La optimización agrega una función que asigna un valor a cada opción y establece qué significa “mejor”. Si S es el conjunto de soluciones factibles y c: S → ℝ es el costo, buscamos una solución s* tal que:

c(s*) ≤ c(s) para toda solución s ∈ S        (minimización)
o
v(s*) ≥ v(s) para toda solución s ∈ S        (maximización)

La relación entre variables, restricciones y objetivos es discreta cuando las alternativas son finitas o están formadas por elementos contables: rutas, horarios, asignaciones, subconjuntos o secuencias. Optimizar no siempre significa encontrar un único número; a veces hay varias soluciones equivalentes o varias soluciones no dominadas.

Esta formulación evita una confusión frecuente: un algoritmo puede ser rápido y producir una respuesta válida sin producir la mejor respuesta. Primero se define qué se desea optimizar; después se decide cómo calcularlo.

49.2 Modelar una relación de costos

Supongamos una red de ciudades. La relación E ⊆ V × V indica qué desplazamientos existen y una función de peso w: E → ℝ asigna kilómetros, tiempo o precio a cada conexión. El resultado es un grafo ponderado.

En JavaScript podemos guardar las aristas como objetos. Esta estructura conserva el origen, el destino y el significado del peso:

const conexiones = [
  { desde: 'A', hasta: 'B', costo: 4 },
  { desde: 'A', hasta: 'C', costo: 2 },
  { desde: 'B', hasta: 'D', costo: 5 },
  { desde: 'C', hasta: 'B', costo: 1 },
  { desde: 'C', hasta: 'D', costo: 8 }
];

function salidasDesde(origen, aristas) {
  return aristas.filter(e => e.desde === origen);
}

function costoDeCamino(camino, aristas) {
  return camino.slice(0, -1).reduce((total, nodo, i) => {
    const arista = aristas.find(e => e.desde === nodo && e.hasta === camino[i + 1]);
    return total + arista.costo;
  }, 0);
}

const caminoEjemplo = ['A', 'C', 'B', 'D'];
console.log('Salidas desde A:', salidasDesde('A', conexiones));
console.log('Camino:', caminoEjemplo.join(' → '));
console.log('Costo total:', costoDeCamino(caminoEjemplo, conexiones));

El peso debe tener una interpretación consistente. No es correcto sumar “kilómetros” y “minutos” sin una conversión o una decisión explícita. Cuando existen varios criterios, se puede combinar una función de utilidad, usar restricciones o buscar soluciones Pareto.

49.3 Propiedades que simplifican el análisis

Antes de elegir un algoritmo conviene analizar la relación:

• Dirección: si (u, v) implica (v, u), la relación es simétrica; si no, debemos conservar el sentido.
• Pesos no negativos: permiten usar Dijkstra para caminos mínimos desde un origen.
• Ausencia de ciclos negativos: es necesaria para que un costo mínimo esté bien definido en ciertos modelos.
• Transitividad: si u se relaciona con v y v con w, quizá podamos inferir u con w.
• Densidad: el número de aristas respecto del máximo determina qué representación es conveniente.
• Subestructura óptima: una solución óptima contiene soluciones óptimas de subproblemas; esta propiedad habilita programación dinámica.

También debemos distinguir factibilidad de optimalidad. Una ruta puede llegar al destino y ser válida, aunque exista otra de menor costo. Del mismo modo, un emparejamiento puede no tener conflictos y aun así dejar recursos sin aprovechar.

49.4 Caminos mínimos: de la relación al algoritmo

El problema de camino mínimo busca una secuencia de vértices conectados cuyo costo total sea mínimo. Si todos los pesos son no negativos, Dijkstra mantiene para cada vértice la mejor distancia conocida y la mejora cuando encuentra una conexión más barata.

La actualización central es una relajación:

si distancia[u] + peso(u, v) < distancia[v]
entonces distancia[v] = distancia[u] + peso(u, v)

La función de distancia cumple una relación recursiva: la mejor ruta hasta v puede obtenerse extendiendo una mejor ruta hasta un vecino u. El algoritmo termina cuando la cola de prioridad no contiene vértices pendientes. Con una cola binaria, su complejidad típica es O((V + E) log V).

function dijkstra(grafo, inicio) {
  const distancia = Object.fromEntries(Object.keys(grafo).map(v => [v, Infinity]));
  const anterior = {};
  const pendientes = new Set(Object.keys(grafo));
  distancia[inicio] = 0;

  while (pendientes.size) {
    const u = [...pendientes].reduce((mejor, v) =>
      distancia[v] < distancia[mejor] ? v : mejor
    );
    pendientes.delete(u);
    if (distancia[u] === Infinity) break;

    for (const { hasta, costo } of grafo[u]) {
      const alternativa = distancia[u] + costo;
      if (alternativa < distancia[hasta]) {
        distancia[hasta] = alternativa;
        anterior[hasta] = u;
      }
    }
  }
  return { distancia, anterior };
}

const grafoEjemplo = {
  A: [{ hasta: 'B', costo: 4 }, { hasta: 'C', costo: 2 }],
  B: [{ hasta: 'D', costo: 5 }],
  C: [{ hasta: 'B', costo: 1 }, { hasta: 'D', costo: 8 }],
  D: []
};
const resultado = dijkstra(grafoEjemplo, 'A');
console.log('Distancias mínimas desde A:', resultado.distancia);
console.log('Costo mínimo hasta D:', resultado.distancia.D);
console.log('Predecesor de D:', resultado.anterior.D);

La implementación anterior usa un conjunto lineal para simplificar la explicación. En una aplicación grande se sustituye por una cola de prioridad. La elección de la estructura no cambia la relación matemática que el algoritmo está resolviendo.

49.5 Explorador interactivo de costos y caminos

El siguiente explorador permite comparar tres estrategias sobre la misma red. “Camino directo” usa una sola arista cuando existe; “ruta mínima” aplica relajaciones; “ruta con menos saltos” optimiza cantidad de conexiones y no costo. Observar la diferencia ayuda a separar objetivos.

La red contiene aristas dirigidas. Por ejemplo, una ruta A → C → B → D → F puede costar menos que A → B → D → F aunque use más aristas. La visualización resalta la solución elegida y muestra sus datos para que el resultado no dependa solamente del color.

49.6 Optimización multiobjetivo y relaciones de dominancia

En problemas reales suelen competir varios objetivos: reducir costo y tiempo, aumentar calidad y disminuir riesgo. Una solución s domina a otra t si no es peor en ningún objetivo y es estrictamente mejor en al menos uno.

Las soluciones que no son dominadas forman el frente de Pareto. No existe una única mejor alternativa sin indicar cuánto valoramos cada criterio. El frente permite presentar opciones y dejar la decisión final a una persona o a una regla de negocio.

function domina(a, b) {
  const noPeor = a.costo <= b.costo && a.tiempo <= b.tiempo;
  const mejorEnUno = a.costo < b.costo || a.tiempo < b.tiempo;
  return noPeor && mejorEnUno;
}

function frentePareto(soluciones) {
  return soluciones.filter(s =>
    !soluciones.some(t => t !== s && domina(t, s))
  );
}

const alternativas = [
  { id: 'R1', costo: 4, tiempo: 9 },
  { id: 'R2', costo: 5, tiempo: 7 },
  { id: 'R3', costo: 7, tiempo: 5 },
  { id: 'R4', costo: 9, tiempo: 4 }
];
console.log('Frente de Pareto:', frentePareto(alternativas).map(s => s.id).join(', '));

Una buena interfaz debe indicar qué significa “menor” o “mayor” en cada eje. Si uno de los objetivos es maximizar calidad, se puede transformar a un costo equivalente o adaptar la condición de dominancia.

49.7 Restricciones y soluciones factibles

Una relación de compatibilidad puede expresar restricciones: dos tareas no pueden ocupar el mismo horario, un recurso no puede asignarse dos veces o una ruta no puede atravesar una zona bloqueada. El conjunto factible es el subconjunto que satisface todas las restricciones.

Podemos modelar una solución como un objeto y centralizar la validación:

const restricciones = [
  solucion => solucion.horas.every(h => h >= 8 && h <= 18),
  solucion => new Set(solucion.recursos).size === solucion.recursos.length,
  solucion => solucion.tareas.length <= 6
];

function esFactible(solucion) {
  return restricciones.every(regla => regla(solucion));
}

function mejorSolucion(candidatas, valor) {
  return candidatas.filter(esFactible)
    .reduce((mejor, actual) => valor(actual) < valor(mejor) ? actual : mejor);
}

const candidatas = [
  { id: 'S1', horas: [9, 12], recursos: ['R1', 'R2'], tareas: ['A', 'B'], costo: 14 },
  { id: 'S2', horas: [10, 19], recursos: ['R1', 'R2'], tareas: ['A', 'B'], costo: 8 },
  { id: 'S3', horas: [8, 16], recursos: ['R1', 'R1'], tareas: ['A', 'B'], costo: 5 }
];
const mejor = mejorSolucion(candidatas, solucion => solucion.costo);
console.log('Solución factible de menor costo:', mejor.id, 'con costo', mejor.costo);

Separar la función de factibilidad de la función objetivo permite reutilizar las mismas restricciones al comparar algoritmos. Además, si no existen soluciones factibles, el programa debe comunicarlo explícitamente: no corresponde devolver una alternativa que viola una regla solo porque tiene un costo menor.

49.8 Asignación y emparejamientos

Una asignación relaciona elementos de un conjunto de tareas con elementos de un conjunto de recursos. Si cada tarea debe recibir un único recurso y cada recurso puede usarse una vez, buscamos un emparejamiento. Los costos pueden representar tiempo, dinero o incompatibilidad.

Una estrategia voraz elige en cada paso el par disponible de menor costo. Es sencilla y a veces muy útil, pero no siempre es óptima: una elección barata ahora puede impedir dos asignaciones mucho mejores después. Para asegurar optimalidad se necesitan algoritmos específicos, como el método húngaro, o una búsqueda exhaustiva cuando el tamaño es pequeño.

function asignacionVoraz(tareas, recursos, costo) {
  const usados = new Set();
  const resultado = [];
  const pares = tareas.flatMap(t => recursos.map(r => ({ t, r, c: costo(t, r) })));
  pares.sort((a, b) => a.c - b.c);

  for (const par of pares) {
    if (!resultado.some(x => x.t === par.t) && !usados.has(par.r)) {
      resultado.push(par);
      usados.add(par.r);
    }
  }
  return resultado;
}

const tareas = ['T1', 'T2', 'T3'];
const recursos = ['R1', 'R2', 'R3'];
const costos = { 'T1-R1': 4, 'T1-R2': 8, 'T1-R3': 5, 'T2-R1': 7, 'T2-R2': 2, 'T2-R3': 6, 'T3-R1': 3, 'T3-R2': 9, 'T3-R3': 4 };
const asignacion = asignacionVoraz(tareas, recursos, (t, r) => costos[`${t}-${r}`]);
console.log('Asignación voraz:', asignacion.map(p => `${p.t} → ${p.r}`).join(', '));
console.log('Costo de la asignación:', asignacion.reduce((total, p) => total + p.c, 0));

La relación también puede ser incompleta. Si una tarea no es compatible con ningún recurso, el emparejamiento máximo será menor que la cantidad de tareas; ese dato es importante para diagnosticar el sistema.

49.9 Programación dinámica y subproblemas relacionados

Cuando muchas alternativas comparten subproblemas, recalcular cada posibilidad resulta costoso. La programación dinámica almacena soluciones parciales y construye la óptima mediante una recurrencia. Esta técnica aparece en mochila, edición de cadenas, caminos en una cuadrícula y planificación.

En el problema de la mochila 0/1, cada objeto se puede tomar o dejar. Si V(i, c) es el máximo valor usando los primeros i objetos y capacidad c:

V(i, c) = V(i - 1, c)                                      si pesoᵢ > c
V(i, c) = max(V(i - 1, c), valorᵢ + V(i - 1, c - pesoᵢ))    en otro caso

function mochila(pesos, valores, capacidad) {
  const n = pesos.length;
  const tabla = Array.from({ length: n + 1 }, () => Array(capacidad + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let c = 0; c <= capacidad; c++) {
      tabla[i][c] = tabla[i - 1][c];
      if (pesos[i - 1] <= c) {
        tabla[i][c] = Math.max(tabla[i][c], valores[i - 1] + tabla[i - 1][c - pesos[i - 1]]);
      }
    }
  }
  return { valorOptimo: tabla[n][capacidad], tabla };
}

const resultadoMochila = mochila([2, 3, 4], [4, 5, 7], 5);
console.log('Valor óptimo de la mochila:', resultadoMochila.valorOptimo);
console.log('Última fila de la tabla:', resultadoMochila.tabla.at(-1));

La tabla es otra relación: cada celda vincula un estado (i, c) con el mejor valor conocido. Visualizarla permite seguir qué estados dependen de otros y comprobar la recurrencia.

49.10 Análisis de sensibilidad

Una solución óptima depende de los datos del modelo. El análisis de sensibilidad estudia qué sucede si cambian los costos, la capacidad, una restricción o la valoración de un criterio. Una solución robusta mantiene un buen resultado ante pequeñas variaciones.

• Perturbación local: cambiar un peso o una preferencia y recalcular.
• Análisis de umbral: encontrar el valor a partir del cual cambia la solución elegida.
• Escenarios: comparar configuraciones optimista, esperada y pesimista.
• Robustez: preferir una solución ligeramente menos óptima si es mucho menos sensible al error.

En JavaScript, un análisis sencillo puede ejecutar el mismo optimizador sobre una secuencia de valores y registrar cuándo cambia el resultado:

function barrerParametro(valores, construirModelo, optimizar) {
  return valores.map(parametro => {
    const modelo = construirModelo(parametro);
    const solucion = optimizar(modelo);
    return { parametro, solucion };
  });
}

const escenarios = barrerParametro(
  [1, 2, 3],
  capacidad => ({ capacidad }),
  modelo => ({ capacidad: modelo.capacidad, costo: 10 - modelo.capacidad })
);
console.log('Escenarios analizados:', escenarios);
console.log('Costo del escenario con capacidad 3:', escenarios[2].solucion.costo);

El resultado no debe interpretarse como una predicción absoluta. Es una exploración de las consecuencias del modelo bajo los supuestos elegidos.

49.11 Complejidad, exactitud y heurísticas

Los problemas de optimización discretos pueden crecer rápidamente. Probar todas las combinaciones de n elementos suele producir una complejidad exponencial. Por eso se utilizan relaciones estructurales, programación dinámica, poda, relajaciones, algoritmos aproximados y heurísticas.

El análisis correcto informa la garantía. Decir “la ruta encontrada es la mejor” requiere una prueba o un algoritmo con garantía; decir “encontramos una ruta de costo 42” solo afirma que se encontró una solución factible.

49.12 Actividades de práctica

1. Construye un grafo ponderado de seis ciudades y calcula el camino mínimo desde A hasta cada vértice. Verifica manualmente dos relajaciones.
2. Agrega una arista de peso negativo. ¿Qué hipótesis de Dijkstra deja de cumplirse? Investiga qué algoritmo permite manejar pesos negativos sin ciclos negativos.
3. Genera diez alternativas con costo y tiempo. Calcula el frente de Pareto y explica por qué una solución dominada no debería presentarse como opción preferida.
4. Compara una asignación voraz con una búsqueda exhaustiva en instancias pequeñas. Encuentra un caso en el que la estrategia voraz no sea óptima.
5. Implementa análisis de sensibilidad: aumenta gradualmente el costo de una arista y registra cuándo cambia el camino mínimo.
6. Define una restricción de compatibilidad para horarios. Calcula el conjunto factible antes de aplicar la función objetivo.

Qué debes recordar de este tema

Conclusión

Las relaciones discretas ofrecen un lenguaje preciso para representar opciones, compatibilidades, dependencias y recorridos. Al añadir pesos, restricciones y funciones objetivo, ese lenguaje se convierte en un modelo de optimización.

La parte esencial no es llamar a un algoritmo, sino formular correctamente el problema: qué se puede elegir, qué está prohibido, qué se desea mejorar y qué garantía necesitamos. Una solución óptima solo tiene sentido respecto de esa formulación.

Analizar una relación es descubrir su estructura; optimizarla es usar esa estructura para tomar mejores decisiones.