Exploración inicial del problema

Optimización de una red arbitraria

Como te prometimos, ahora trabajaremos con un cuadro de costos generado al azar, simulando una problemática real cualquiera.

De manera muy similar a la escena anterior, a continuación incluimos un cuadro de costos y la representación gráfica correspondiente. Podrás marcar y desmarcar los enlaces al presionar sobre los puntos anaranjados o sobre los costos del cuadro.

Podrás variar entre 3 y 9 el valor de \(N\), que representa el número de puntos a conectar.

¿Solución inválida?

Es importante aclarar a qué se refiere esta situación.

Si obtuviste este resultado al trabajar con la escena anterior, o incluso en alguna de las previas, ya sabes de qué se trata. Si no fue así, puedes obtenerlo, por ejemplo, si ajustas a 5 el número de puntos y marcas los siguientes enlaces: AB, BC, CA y DE.

¿Qué pasa?, ¿por qué, a pesar de que todos los puntos están conectados con algún otro y el número de enlaces es suficiente para unir todos los puntos, esta configuración no nos es útil para solucionar el problema?

Preguntas

Después de haber practicado varias veces la búsqueda de la solución óptima, seguramente ya tienes algunas ideas del procedimiento.
  1. ¿Cuáles son estas ideas o recomendaciones generales?

  2. ¿Qué pasos te permiten acercarte a la solución óptima?

  3. ¿Crees que el procedimiento para solucionar este tipo de problemas puede modificarse si en lugar de buscar la suma mínima de costos, nos interesara lo contrario y buscásemos la suma máxima de costos?

  4. ¿Se te ocurre alguna situación donde el costo máximo, a lo mejor visto como capacidad, voltaje o ganancia, por ejemplo, tenga sentido?

En relación con la última pregunta, en la parte de las matemáticas que se dedica a estudiar este tipo de problemas, la terminología que generalmente se usa en lugar de costo es peso. También a los puntos se les conoce como vértices o nodos y a los enlaces como aristas.

En la siguiente sección estudiaremos algunos conceptos y daremos solución al problema desarrollando un procedimiento general que será aplicable tanto para minimizar como para maximizar la suma de pesos.