Estos apuntes son libres y los puedes editar.

Algunas secciones están en inglés puedes colaborar traduciendo algunos párrafos.

LINGO

Introducción General

LINGO es software comercial de la empresa “LINDO SYSTEMS INC.”.

Desde la web del vendedor http://www.lindo.com y después de registrarse, se puede obtener una versión de demostración completamente funcional aunque restringida en el tamaño de los problemas que puede tratar.

LINGO es software especializado en la resolución de problemas de optimización. Dispone de ejemplos en los que se ilustra la forma de modelar un gran número de sistemas y problemas usuales en el ámbito de la Investigación Operativa.

Comenzando con LINGO

Ejemplo inicial

Tras iniciar el programa introduce el código siguiente en la ventana:

 max=2*x+y;
 5*x+2*y<10;
 3*x+5*y<15;

y pulsa sobre el icono con forma de diana.

Obtendrás la solución del problema. Observa el valor objetivo y los correspondientes valores de las variables.

Ahora 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.

Las Variables

El comportamiento habitual de LINGO es suponer que todas son no negativas.

Para modificar este comportamiento se dispone de las instrucciones:

  • @free(x) que declara la variable x como libre.
  • @gin(x) que declara la variable x como entera.
  • @bin(x) que declara la variable x como binaria, es decir, x ∈ {0,1}.
  • @bnd(i,x,s) restringe la variable a valores comprendidos entre i y s.

En el ejemplo anterior para la función objetivo de minimizar añade las instrucciones: @free(x); y @free(y);. Y vuelve a resolver. ¿Qué tipo de solución se obtiene?

Tipos de solución

Al terminar el procedimiento podemos obtener:

  • La solución óptima, “Global optimal solution found”
  • Que el problema es no acotado, “Unbounded solution”
  • Que no se ha encontrado un punto factible, “No feasible solution found”. En programación matemática lineal esto implica que el problema es infactible.

Sintaxis Avanzada

Formato de ficheros

La descripción de los problemas de optimización en LINGO se divide en bloques, algunos de los cuales puede estar ausente:

  • Bloque SETS
  • Bloque Principal
  • Bloque DATA
  • Bloque INIT

Bloque SETS

Un bloque SETS es de la forma:

 SETS:
  centro/1..5/:x;
 ENDSETS

En la línea central se define un conjunto llamado “centro” con los elementos 1..5, es decir, 1 a 5. Los elementos del conjunto pueden darse de forma explícita, por ejemplo:

 centro/alcala, madrid, barcelona/

define un conjunto con tres elementos “alcala”, “madrid”, “barcelona”.

Después de los dos puntos se definen las variables que tienen sus índices en dicho conjunto, en:

 centro/alcala, madrid, barcelona/:v

se define una variable, en realidad, un vector de variables cuyos elementos son: v(alcala), v(madrid), v(barcelona) que podrían representar los montos de venta en cada centro.

En el bloque

 SETS:
  maquina/1..3/;
  tarea/1..5/;
  asignacion(maquina,tarea):x;
 ENDSETS

se define un conjunto asignacion cuyos índices son una máquina y una tarea.

Bloque Principal

En este bloque se define el problema a resolver.

Bloque DATA

El bloque DATA tiene una estructura similar al bloque SETS:

 DATA
  w = 2, 3, 5;
 ENDDATA

En él se asocian valores a cada uno de los datos que intervienen en la formulación y que previamente han sido definidos.

Si w fuese una variable con dos índices los valores a asignar se especifican de forma consecutiva fila tras fila.

El bloque data permite que los valores de los parámetros sean especificados de forma interactiva, sustituyendo los valores por el símbolo ?. Un ejemplo de uso es max_flu.lng donde los valores fuente y sumidero se introducen de forma interactiva.

Bloque INI

Se especifican los valores iniciales para las variables.

Importación de datos

Ficheros de texto

En el fichero del modelo se puede insertar porciones texto de un fichero externo. El uso habitual de esto es la separar la formulación y los datos en dos ficheros distintos.

Un ejemplo de uso es max_flu_mul.lng que importa los datos de max_flu_mul.dat.

Hoja de cálculo

Para importar datos de una hoja de cálculo de “Microsoft Excell” en el párrafo data se utiliza la instrucción

 nombre_variable = @ole("nombre_fichero",nombre_rango)

donde:

  • nombre_variable es la variable que recibe los datos.
  • nombre_fichero es el nombre del fichero del que se importan los datos.
  • nombre_rango es el nombre del rango de los datos que debe importarse, dicho nombre ha de ser previamente definido en el fichero. Para definir nombre_rango en la hoja de cálculo se seleccionan sucesivamente las opciones Insertar→Nombre→Definir y se introduce el nombre y se seleccionan las casillas correspondientes.

Un ejemplo de este uso es minisum.ole.lng que importa los datos del fichero demanda.xls.

Exportación de resultados

Modelos

Modelos de localización

Problema de localización minisum

Encontrar el punto que minimiza la suma de distancias a los puntos (6,10) (5,2) (2,8) (0,2) (4,2)

Solución: minisum_noponderado.lng

Problema de localización minisum ponderado

Encontrar el punto que minimiza la suma de distancias ponderadas a los puntos (6,10) (5,2) (2,8) (0,2) (4,2) con pesos 0.2, 0.6, 0.5, 0.3, 0.7

Solución: minisum_ponderado.lng

Problema de localización minisum ponderado con datos externos del fichero demandas.xls

Solución: minisum.ole.lng

Problema de localización minimax

Encontrar el punto que minimiza la mayor de las distancias al punto a localizar.

Solución: minimax.lng

Problema de localización minimax con datos externos del fichero demandas.xls

Solución: minimax.ole.lng

Caminos Mínimos en grafos

Dada la matriz de distancias:

4 6
3 2 12
5 3 4 9
10 4 5 1
8 4 2
1 3
  • Formular y resolver el problema de encontrar el camino más corto que une los vértices 1 y 6.

Solución: camino_minimo.lng

  • Modificar la formulación para que se pregunte interactivamente el nodo de origen y el de destino.

Solución: camino_minimo_1.lng

  • Modificar la formulación planteando el problema como un problema de asignación.

Solución: camino_minimo_2.lng

  • Modificar la formulación para calcular las longitudes de todos los caminos mínimos entre todos los pares de nodos.

Solución: camino_minimo_3.lng

Problemas de flujo máximo

El problema de máximo flujo en un grafo consiste en dadas unas restricciones de capacidad en cada uno de los arcos del grafo y dados un nodo origen, llamado fuente y uno destino, llamado sumidero. Encontrar el flujo que debe circular por cada arco para maximizar el flujo entrante en el sumidero.

  • Formular el problema de flujo máximo para un grafo de forma que la fuente y el sumidero se especifiquen de forma interactiva.

Solución: max_flu.lng

  • Formular el problema de flujo máximo admitiendo que cada nodo tiene asignada una capacidad de generación y resolverlo usando los datos del fichero max_flu_mul.dat.

Solución: max_flu_mul.lng

Análisis de Sensibilidad

Activar el cálculo de rangos

Para poder hacer análisis de sensibilidad es necesario activar el cálculo de rangos, se activa:

  • Seleccionar options dentro del menú LINGO
  • Selecionar la pestaña General Solver
  • En el desplegable Dual Computations se selecciona Prices & Range
  • Pulsar el botón OK

Análisis de Sensibilidad

Para realizar un análisis de sensibilidad en LINGO se empieza resolviendo el problema y a continuación se selecciona la opción Range del menú LINGO. La opción Range sólo está activa cuando la ventana del modelo está en primer plano y el problema se ha resuelto previamente.

Ejemplo:

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

Después de resolver y seleccionar la opción Range se obtiene:

 Ranges in which the basis is unchanged:
 Objective Coefficient Ranges
  
      Current 	    Allowable 	Allowable
 Variable   Coefficient   Increase 	Decrease
 X1        -1.000000      0.7500000 	0.0
 X2        -2.000000      1.500000    INFINITY
 X3        -1.000000      0.0         1.800000
 Righthand Side Ranges
 Row       Current        Allowable   Allowable
           RHS            Increase 	Decrease
 2         6.000000       14.00000 	1.000000
 3         10.00000       2.000000 	7.000000

Lo que se interpreta como:

 0<=Dc1<=.75
-1<=c1<=-.25
 Dc2<=1.5
 c2<=-0.5
 -1.8<=Dc3<=0
 -2.8<=c3<=-1
 -1<=Db1<=14
 5<=b1<=20
 -7<=Db2<=2
 3<=b2<=12

Bibliografía


QR Code
QR Code lingo (generated for current page)