Excel

Ξ 14 comentarios

Cómo resolver una binaria en Solver

por Xabadu
Cómo resolver una binaria en Solver

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

Comparte este tutorial

El culpable de todo esto

Las tardes gloriosas de domingo y las grandes ovaciones a estadio lleno, no son algo extraño para Xabadu. Luego de ser descubierto a los 4 años en un partido de barrio por los ojeadores del gran Aviación F.C., sacudió el mercado nacional al ser traspasado en $500 pesos chilenos (1 USD) y 3 coca colas al renombrado Estrella Blanca de Lolol. Luego de una impresionante carrera por equipos como Lozapenco, Santa Cruz, Deportivo Lago Chungará y una incursión en la 3a división del futbol de Kazajstan, su record imbatible hasta la fecha de 1257 goles en 20 partidos lo llevo a ser elegido como uno de los arqueros más recordados en la historia pelotera nacional. Una lesión en el colmillo superior derecho lo llevó al retiro el año 2003, pero está de vuelta y sin duda que su jerarquía y experiencia internacional será un gran aporte.

En los barrios marginales se le conoce como: Xabadu

Comentarios en Facebook

14 Comentarios

  • hey!..el proximo semestre tendré que utilizar este manual!…que gran ayuda!..a ver si en un rato de ¿ocio? adelanto algo de trabajo!..jeje

    muy buen aporte!

  • sorry tengo una pregunta si me dan una tabla de notas y me dicen crear una formula q promedie las 2 notas mas altas de 3 es decir crer una formula q pueda identificar las mas altas

  • @jossel: Te recomiendo revisar este tutorial donde se cubren esos aspectos de Excel:

    http://www.comolohago.cl/2008/06/como-dominar-excel-parte-1/

    Saludos

  • hola como estas espero que bien ahhhhhhhhhhhh
    me enseñaron demasiado gracias

  • esta muy buena laq informasion y muy completo .bay

  • Muchas gracias por la información¡ me ayudó mucho para hacer una tarea. Muy bien explicado.
    Gracias

  • viejo revise el tutorial, y necesitaba resolver este problema, pero con arcos dirigidos. lo modele con gams y el resultado es perfecto un Z= 55, pero al resolverlo con solver me da 150. no se qeu hize mal.

  • Excelente explicación… Muchas felicidades y muchas gracias!!!

  • mmmm iba bien hasta que lo resolví xD y no me tomó en cuenta los nodos de termino !!! ayuda por favor!

  • facil la wea…. peka!

1 2

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Gente linda que nos quiere

Donde mas estamos