LPSolve IDE

LPSolve IDE es un entorno integrado de desarrollo (Integrated Development Interface) muy amigable para Windows. Todas las funcionalidades de lpsolve pueden ser usadas desde el entorno gráfico de una manera muy amigable para el usuario.

Muchas gracias a Henri Gourvest por el desarrollo de este entorno para lpsolve y por ponerlo a disposición de la comunidad.

La página principal de LPSolve IDE es http://lpsolve.sourceforge.net/5.5/IDE.htm. (lp_solve_5.5.2.11_ide)

Algunas prestaciones del entorno son:

• Todo se controla de forma gráfica y con el ratón.
• Trabaja con problemas en todos los formatos soportados por lp_solve.
• Transforma el modelo desde cualquier formato soportado a cualquier otro formato soportado.
• Editor muy amigable para el usuario para la introducción y la modificación de los modelos con resaltado de sintaxis.
• Comprobación de la sintaxis del modelo.
• Resolución del modelo.
• Visualización de los resultados en rejillas.
• Controla todas las opciones de lp_solve.
• Visualización de resultados en rejillas.
• Exporta el modelo a HTML, RTF, LaTeX
• Exporta matrices a CSV, HTML, RTF
• Export resultados a CSV, HTML, RTF
• Muestra estadísticas sobre el modelo.
• …

Para más información se puede consultar el la guía de referencia de la versión 5.5 (en inglés) o su traducción en curso guía de referencia de la versión 5.5 (en español).

Para la instalación de lp_solve_ide bajo Microsoft Windows se descarga el programa de instalación desde lp_solve_5.5.2.11_ide y se ejecuta.

Se pide que se acepte la licencia de usuario final del programa, una licencia libre, más concretamente es la licencia GNU LESSER GENERAL PUBLIC LICENSE 2.1. Además se pregunta sobre algunas opciones que se pueden dejar a los valores por defecto.

Si la instalación se ha realizado correctamente y no se ha desmarcado la última opción se iniciará automáticamente la aplicación lp_solve_ide. Obteniéndose una ventana similar a la que se muestra.

La aplicación lp_solve_ide es una aplicación nativa de Microsoft Windows pero la experiencia muestra que funciona correctamente en entornos linux o MacOS usando el emulador wine.

En este caso los pasos a seguir son:

1. Descargar e instalar el emulador wine
2. Descargar el instalador de lp_solve_ide como se mostró anteriormente
3. Ejecutar el instalador usando wine

lp_solve_ide resuelve problemas en varios formatos:

• LP format: Formato LP, es el formato por defecto.
• MPS format: Formato MPS
• XLI_MathProg: Formato GNU MATHProg
• xli_CPLEX: Formato CPLEX
• xli_LINDO: Formato LINDO
• xli_LPFML: Formato LPFML

Usando la opción “View” del menú principal se puede convertir un modelo de un formato a otro.

Tras iniciar el programa introduce el código siguiente en la pestaña Source:

 max:2 x+y;
 5 x + 2 y<9;
 3 x + 5 y<13;

y pulsa sobre el icono con forma de triángulo verde, pulsa la tecla F9 o selecciona en el menú las opciones Action→Solve.

Para visualizar la solución pulsa sobre la pestaña Results. Observa el valor objetivo y los correspondientes valores de las variables:

 Variables   result
                4
     x          1
     y          2
 

Pulsa sobre la pestaña Source, reemplaza “max” por “min” y vuelve a resolver. Observa que la solución obtenida corresponde al caso en que se consideren únicamente valores no negativos de las variables.

Observación: A veces las columnas en la pestaña de resultados no enseñan los números completos. Si algún número acaba en … entonces es necesario aumentar el ancho de la columna, pues de lo contrario el número puede interpretarse erróneamente, por ejemplo: 2,3… puede interpretarse como 2,3 cuando en realidad el número podría ser 2,37831e-30 que debe interpretarse como 0. Para ampliar las columnas desplace la barra vertical que separa las columnas en la cabecera de la tabla.

En los modelos lp_solve se asume que todas las variables son no negativas.

Para modificar este comportamiento se dispone de las instrucciones:

• free x que declara la variable x como libre.
• int x que declara la variable x como entera.
• bin x que declara la variable x como binaria, es decir, x ∈ {0,1}.

En el ejemplo anterior para la función objetivo de minimizar añade las instrucciones: free x; y free y; y vuelve a resolver. Ten en cuenta que las instrucciones free siempre deben ir al final del problema y empezando en la primera columna. ¿Qué tipo de solución se obtiene?

También es posible especificar el rango de variación de una variable. Por ejemplo, para una variable no positiva: -Inf <= x <= 0;.

Para especificar que una variable debe tomar valores enteros se utiliza la instrucción int. La instrucción int x declara la variable x como entera.

De forma similar la instrucción bin x que declara la variable x como binaria, es decir, x toma el valor 0 o 1.

Las restricciones sobre el rango de las variables deben incluirse al final de la formulación del problema.

Tras indicarle a LPSolveIDE que resuelva el problema, en la pestaña Log, se puede obtener uno de los siguientes mensajes:

• Parse error: Indica que existe un error de sintaxis en el problema introducido
• Optimal solution: Se ha encontrado una solución óptima
• The model is UNBOUNDED: El problema es no acotado
• The model is INFEASIBLE: El problema es infactible

Usando la opción “View” del menú principal se selecciona el formato “xli_MathProg”. A continuación se introduce:

 /* Variable definitions */
 var x >= 0;
 var y >= 0;
 
 /* Objective function */
 maximize obj: +2*x +y;
 
 /* Constraints */
 R1: +5*x +2*y <= 9;
 R2: +3*x +5*y <= 13;

y se procede como en el caso anterior.

En el formato MathProg las variables son libres. Se pueden especificar los límites inferior y superior en la definición de las variables.

En este formato los límites de las variables se especifican en la declaración, pudiendo omitirse alguno de ellos. Una variable no positiva se declara:

 var x <= 0;

El análisis de sensibilidad pretende determinar el rango de variación de los coeficientes del modelo sin que se produzca un cambio en la base que genera la solución óptima.

Para obtener dichos rangos se procede a resolver el problema y luego se pincha sobre la pestaña Results y luego sobre la pestaña Sensitivity. Los rangos de variación es desde el valor dado en la columna from hasta el valor dado en la columna till.

Ejemplo:

 max:-x1-2*x2-x3;
 2*x1+x2+2*x3>6;
 x1+3*x2+4*x3>10;

En la pestaña de variables, en la fila de x1 se obtiene from -1 till -0.25. En consecuencia el rango de variación de c₁ es desde -1 hasta -0.25. Que dado que c₁ = -1 en términos de incrementos significa que Δc₁ puede variar entre 0 y 0.75.

Para x₂ se obtiene -∞ < c₂ ≤ -0.5, o lo que es lo mismo, -∞ < Δc₂ ≤ 1.5. Análogamente, para x₃ se obtiene -2.8 ≤ c₃ ≤ -1, o equivalentemente -1.8 ≤ Δc₃ ≤ 0.

Para el lado derecho, mirando en la fila R1 (primera restricción) se obtiene 5 ≤ b₁ ≤ 20 o equivalentemente -1 ≤ Δb₁ ≤ 14. De la fila R2 se obtiene 3 ≤ b₂ ≤ 12 o equivalentemente -7 ≤ Δb₂ ≤ 2.

El uso de un lenguaje de modelización para la descripción de los problemas de programación matemática permite:

• Separar la descripción del modelo de los datos de la instancia particular a resolver.
• Describir en forma compacta modelos muy elaborados.

El lenguaje de modelización que utiliza lp_solve es GNU MathProg. Un modelo escrito el lenguaje GNU MathProg consiste en un conjunto de instrucciones y bloques de datos construidos por el usuario.

En MathProg la descripción de un modelo consiste en dos secciones: modelo y datos. Esto permite la resolución del mismo modelo usando diferentes datos.

La sección de modelo incluye las declaraciones de los objetos del modelo y es común a todos los problemas basados en el modelo correspondiente.

La sección de datos es opcional y contiene los datos particulares de un problema.

Se trata de encontrar la forma de enviar mercancía desde un conjunto de puntos de origen a los puntos de demanda con menor coste. El problema tiene restricciones de disponibilidad y de satisfacción de la demanda.

Ejemplo: transp.mod

Una explicación más detallada del problema de transporte y de la forma de introducir un modelo para su resolución con lp_solve se encuentra en el fichero transp_ext.mod siguiente.

Ejemplo: transp_ext.mod

En el problema de asignación se busca la forma de asignar máquinas a tareas con el menor coste posible. De forma que cada máquina realiza una tarea y cada tarea debe hacerse en una máquina.

Ejemplo: assign.mod

El clásico juego sudoku puede formurlarse y resolverse como un problema de programación lineal.

Ejemplo: sudoku.mod

Las páginas Resolviendo sudokus con shiny mediante programación lineal y Sudoku solver utilizan lp_solve para resolver sudokus.

El problema de colocar 8 (en general n) damas en un tablero de ajedrez (de n x n).

Ejemplo: queens.mod

El problema de completar un cuadrado con n^2 de forma que no se repitan y que todas las filas, las columnas y las diagonales principales sumen lo mismo también puede formularse como un problema de programación lineal.

Ejemplo magic_square.mod

Nota Estos ejemplos pueden resolverse con lp_solve, pero la salida se visualiza mejor si se resuelven con glpsol mediante la instrucción glpsol -m fichero.mod

• Guía de referencia de lp_solve (en inglés)
• Guía de referencia de lp_solve (en español)