Reflexiones y aplicaciones

Rutas turísticas: ¿Problema de maximización o minimización?

Un escenario, equivalente matemáticamente al problema anterior, es pensar en el gobierno de un estado de la República Mexicana que busca promover el turismo. Para ello habrá de invertir en mejorar y/o ampliar las carreteras que conectan ciertos poblados. Como la inversión en carreteras es costosa, se busca que haya siempre una ruta, pero solo una, que conecte cada par de poblados. Rutas adicionales encarecerían el proyecto sin necesidad.

Tarea

Encuentra la respuesta a las siguientes preguntas.

  1. El problema descrito anteriormente, ¿es un problema de minimización o maximización?

  2. ¿Puedes pensar en un problema similar, relacionado con la promoción turística en México (u otro país), pero que represente el escenario opuesto, es decir, minimización en lugar de maximización, o viceversa?

  3. ¿Qué ajuste habría que hacer en el procedimiento del problema descrito arriba para encontrar la solución al problema inverso? Describe claramente este ajuste.

  4. Describe la forma en la que aplicarías la inducción matemática para verificar que el procedimiento que hemos desarrollado funciona para optimizar la conexión de cualquier número natural \(N\) de puntos.

Respuestas

  1. Es un problema de minimización: al agregar cada nuevo enlace a la red, habrá que buscar siempre el que extienda la red existente al menor costo posible.

  2. Un posible escenario de maximización del problema sería que para la elección de las carreteras, en vez de considerar el costo de construcción de las mismas, se tomara en cuenta la cantidad y calidad de atractivos turísticos entre los poblados a conectar. A cada una de las vías se podría dar una calificación de 0 a 10 de la forma tradicional.

  3. En este último caso, el cuadro de calificaciones reemplazará al cuadro de costos que habíamos venido considerando, y nos interesará que la suma de calificaciones sea lo más grande posible porque ello querrá decir que la red de carreteras mejoradas y/o ampliadas permite visitar los atractivos turísticos en mayor cantidad y/o calidad. El ajuste consiste en tomar el costo máximo como el óptimo en lugar del costo mínimo. Lo anterior al momento de escoger cada enlace.

  4. Suponemos que tenemos una configuración de \(N\) puntos junto con su correspondiente tabla de costos de enlaces y tomamos un primer punto \(P\) al azar.

    El caso \(n=2\) es una configuración óptima para 2 puntos a partir de \(P\), ya que se construye con uno de los enlaces óptimos que conectan a \(P\) con el resto de los puntos.

    Si damos por hecho que hemos construido a partir de \(P\) una configuración óptima \(S_n\) de \(n\) puntos y con \(n\le N-1\), entonces la configuración con \(S_{n+1}\) puntos es óptima ya que se construye con uno de los enlaces óptimos que conectan a \(S_n\) con el resto de los puntos que no están ya en \(S_n\).

    Cuando \(n=N\) el proceso inductivo se detiene porque hemos terminado el proceso.