Hola!, en el día de hoy aprenderemos a optimizar nuestros problemas diarios gracias a una herramienta de Excel llamada “Solver”. Se fundamenta en un forma de razonar conocida como Problema de Programación Matemática (PPM) que abordaremos a continuación. A si es que ya sabes, si puedes ponerle números a tu problema (chicas lo siento, dramas del corazón aún no), Como Lo Hago te ayuda a resolverlos.

Más información después del salto.

Cómo resolver una binaria en Solver

Nota: El siguiente tutorial presenta cierto nivel de dificultad para usuarios no avanzados en Excel.

Comenzaremos definiendo algunos términos:

• Problema de programación matemática (PPM): es un problema del cual podemos extraer: parámetros, variables de decisión, restricciones y una función matemática conocida como función objetivo.
• Parámetros: son los datos entregados por el problema, datos fijos que nosotros no podemos modificar.
• Variables de decisión: son los datos que buscamos y que queremos optimizar, por ejemplo ¿cuántas manzanas debemos cosechar de “x” variedad para obtener el rendimiento máximo?, ¿cuánta bencina debo colocar a la moto y de qué octanaje a fin de minimizar mi costo? o ¿Qué ruta es la más corta para llegar de A a B?
• Restricciones: son todas las condiciones dadas por el problema que afectan a la variable de decisión, por ejemplo: la demanda del mercado de “x” variedad de manzanas es de 100, la moto sólo funciona con las bencinas de 93 y 95 octanos (descarta la de 97 octanos), ó debes pasar por la plaza, la estación de trenes y la municipalidad necesariamente para llegar de A a B.
• Función objetivo: es la función matemática que será optimizada (maximizada o minimizada) por Solver para encontrar la respuesta a tu variable de decisión.

Implementos necesarios:

1. Un problema que optimizar: en este caso utilizaremos uno de ruta mínima (¿Cuál es el camino más corto?).
2. Excel y en el Solver activado. Puedes hacerlo en el menú Herramientas > Complementos > Solver.

Lamentablemente la única forma de enseñarte a utilizar binarias en Solver es a través de un ejemplo en particular, de todas formas cualquier consulta o problema recuerda hacerlo a continuación de este artículo.

Procedimiento:

Partiremos viendo el ejemplo a resolver, obtenido de los ejercicios tipo del curso de Optimización de la Escuela de Agronomía e Ingeniería Forestal, Departamento de Economía Agraria de la Pontificia Universidad Católica de Chile:

Ejemplo:

Un parque tiene la siguiente distribución de lugares:

Distribución de lugares

Donde los números son las distancias en KM, O corresponde al origen y T al término o salida, las demás letras representan lugares interesantes que visitar como: “la laguna de los cisnes”, “el mirador”, “la zona de picnic”, entre otros. El guardaparques tiene su cabina en O y al término de la jornada de trabajo desea desplazarse a T en el menor tiempo posible, para lo cual debe escoger la ruta más corta.

Solución:

1.- Abrimos Excel y en una hoja nueva, dentro de las celdas, escribimos los parámetros, las variables de decisión, las restricciones y la función objetivo de manera ordenada:

• Los parámetros corresponden a las distancias de cada arco (OA, OB, OC y así sucesivamente).

• La variable de decisión es una binaria, vale decir, tomará valores de 0 ó 1. 0 cuando no escoja este arco para pasar y 1 si decide utilizarlo (a modo de encontrar que combinación de arcos le proporciona la menor distancia posible). Las celdas de esta variable por ahora las dejaremos en blanco.

• Las restricciones corresponden a un algortimo que siempre se utiliza en problemas de ruta mínima, el cual dice que lo que “sale” de un nodo (O, A, B, C, D, E, T) menos lo que “entra” es igual a: 1 si es el nodo de origen (en este caso O), 0 si es un nodo de paso (cualquier letra menos O y T), y -1 si es un nodo de término (en este caso T). Por ahora las restricciones también las mantendremos en blanco.

• La función objetivo para este problema es la suma producto de las distancias entre los nodos y su respectiva binaria, aún no anotamos nada en la celda, la dejamos en blanco.

Después de todo esto, deberiamos tener algo similar a lo siguiente:

Datos. Click para agrandar

2.- Comenzaremos a escribir las restricciones:

Nota: Los siguientes pasos se hacen tomando en consideración la posición respectiva de las celdas de la imagen superior. Para cualquier caso modifiquen las posiciones a las que hayan utilizado Uds.

• En la celda I7 debemos decirle a Excel que O corresponde a un nodo de Origen, o sea, la suma de todos los arcos que empiezan con O menos los que terminan con O debe ser igual a 1. El número 1 se anota en la celda de al lado. Entonces en la celda I7 escribimos=suma(G7:G9)-suma(0). Debes notar que le estamos señalando las celdas que aún permanecen en blanco de la variable de decisión y no la de los parámetros. No te preocupes, Solver lo entenderá cuando se lo indiquemos.

• En la celda I8 debemos decirle a Excel que A es nodo de paso, osea la suma de de los arcos que empiezan con A menos los que terminan con A debe ser 0. El número 0 se anota en la celda de al lado. Entonces en la celda I8 escribimos =suma(G11:G12)-suma(G7).
  

Debes realizar el mismo procedimiento con cada nodo que falta: B, C, D, E. Recordando colocar =suma(celdas de arcos que empiezan con la letra correspondiente)-suma(celdas de arcos que terminan con la letra correspondiente). Cuando llegues a T deberás anotar =suma(0)-suma(G24;G21).

Luego de eso se obtendrá una columna de restricciones repleta de ceros, como esta:

3.- Siguiendo con la función objetivo:

En la celda destinada a la función objetivo debemos indicarle al programa que debe buscar la suma producto de las celdas que empiezan con la misma letra, vale decir, debemos escribir=sumaproducto(celdas de parámetros que empiezan con O; celdas de variable de decisión que empiezan con O)+sumaproducto(celdas de parámetros que empiezan con A; celdas de variables de decisión que empiezan con A)+…+(celdas de parámetros que empiezan con E; celdas de variables de decisión que empiezan con E), así:

Definiendo función objetivo

Debes notar que no todos los nodos de los parámetros fueron colocados en la variable de decisión, a fin de que Solverpueda entender que no deseamos devolvernos en nuestra ruta, de esta forma, por ejemplo el arco DA no fue colocado en la variable de decisión puesto que si el guardaparque ya se encuentra en D, no queremos que se devuelva a A, sabemos que ese arco (DA) no estará aportando a la ruta más corta.

Una vez que tenemos definidas nuestras restricciones y nuestra función objetivo pasamos (¡¡¡al fin!!) a:

4.- Ejecutar Solver (Herramientas > Solver), con lo cual aparecerá la siguiente pantalla:

Solver

Llenaremos:

• Celda objetivo: aquí deberás anotar en qué celda de tu hoja de Excel se encuentra tu función objetivo. Para este ejemplo, la nuestra se encuentra en C37.
• Valor de celda objetivo: como estamos buscando la ruta más corta deberás seleccionar “mínimo”.
• Cambiando las celdas: aquí debes insertar las celdas de nuestra variable de decisión. ¡Ojo!: debes insertar solo las celdas de la variable. Obtendrás una ventana así:

Click para ampliar

• Sujeto a las siguientes restricciones: es hora de indicarle al programa las condiciones que estamos poniendo al problema y son dos: las restricciones de nodos y las que indican que la variable de decisión es binaria. Partiremos con las restricciones de nodos: selecciona “agregar”, verás la siguiente ventana:

En “referencia de celda” debes incluir la columna con las restricciones de nodos. Para este caso de I7 a I13. En el espacio donde salen los signos <= debes buscar con la flechita y seleccionar = (estrictamente igual). En “Restricción” debes seleccionar la columna continua a la de las restricciones, para este caso desde J7 a J13. Luego pincha “Agregar”.

Ahora agregaremos la restricción de binaria, para esto en “referencia de celda” seleccionas las primeras tres celdas de la variable de decisión que se refieren a los arcos que puede formar O, esto es, las celdas desde G7 a G9. En el espacio que aparecen los signos <= debes buscar y seleccionar el que dice “bin” y observarás que automáticamente en el espacio de “restricción” aparece la palabra “binario”. Haz clic en “Agregar”. Agrega todas las binarias necesarias hasta terminar con las últimas celdas correspondientes a los nodos que se pueden formar con E. Obtendrás algo así:

Con esto ya le dijiste al programa todo lo que necesita saber para entregar el camino más corto.

5.- A continuación, presionamos “Resolver” y aparecerá la siguiente ventana:

Presiona “Aceptar”. En las celdas de la variable de decisión aparecerán “unos”(1’s) en aquellos arcos que el guardaparque deberá tomar a fin de recorrer el camino más corto. Veamos:

Luego, el camino más corto está dado por: O-A-B-E-D-T.

La distancia total recorrida puedes observarla en la celda de función objetivo. Y son 13 kilómetros.

Con esto has terminado tu PPM de ruta mínima y has minimizado la función que le permite al guardaparque llegar más rápido a su destino. ¡Felicidades! =). Es hora de que trates de resolver tus propios problemas. Estaremos aquí parta ayudarte. Suerte.

Cualquier duda o problema, pueden dejar un comentario en el área a continuación. Como siempre, este tutorial cuenta con el sello de garantía de Comolohago.cl