• Author / Uploaded
• Cexar Arriola

• Categories
• Matriz (Matemáticas)
• Software
• Lenguaje de programación
• Función (Matemáticas)
• Programación lineal

Citation preview

Investigación Operativa 1 PONTIFICIA UNIVERSIDAD CATÓLICA DEL PERÚ FACULTAD DE CIENCIAS E INGENIERÍA PRIMERA GUÍA DE LINGO PARA EL LABORATORIO DE INVESTIGACIÓN OPERATIVA 1 Temas: El lenguaje de modelación del software LINGO Resolución de modelos de programación lineal usando LINGO

1.

OBJETIVOS La guía tiene como finalidad exponer el lenguaje de modelación del LINGO y que el alumno sea capaz de formular modelos de programación lineal usando este lenguaje.

2.

METODOLOGÍA Los alumnos trabajarán individualmente en una computadora, bajo la tutoría de los jefes de práctica de laboratorio.

3.

GUÍA DE LABORATORIO

3.1

INTRODUCCIÓN AL LINGO

Según el LINGO 11 Users Manual, LINGO es una herramienta que permite formular modelos de programación lineal de manera sencilla y eficiente, para tal fin LINGO tiene, entre otras, las siguientes características: Un lenguaje algebraico para modelación LINGO tiene un potente lenguaje de modelación basado en sets que permite al usuario expresar los modelos matemáticos de manera compacta y eficiente. Manejo de datos conveniente LINGO permite construir modelos que importan la información y exportan los resultados desde y hacia las hojas de cálculo o bases de datos. Esta capacidad del LINGO facilita el análisis de sensibilidad de los modelos de programación lineal y la elaboración de reportes y gráficos apropiados para la toma de decisiones. Con estas ventajas, usted desarrollará habilidades para manejar un software potente que le permitirá realizar trabajos de investigación, tesis y usar la programación lineal en situaciones reales cuando la cantidad de variables y restricciones es a menudo sumamente grande. Los requisitos para leer esta guía son aprender primero el funcionamiento del LINDO; luego instale el LINGO. Este software es de libre disponibilidad y se encuentra en la web de LINDO Systems cuya dirección electrónica es http://www.lindo.com/. Asimismo previamente debe leer el primer capítulo Getting Started with LINGO del LINGO 11 Users Manual en donde se explica el entorno de este software; se sugiere leer dicho capítulo y a la vez digite y resuelva los ejemplos en el LINGO. En el laboratorio de computadoras en el segundo piso del pabellón de Ingeniería Industrial está instalado este software. Luego de cumplir los requisitos, lea y simultáneamente ejecute las indicaciones de esta guía en su editor de LINGO. 3.2

INICIO DEL MODELO EN LINGO

En LINGO, el modelo se inicia con el comando MODEL seguido del caracter “:“. En la figura 1 se muestra el editor del LINGO y el comando indicado.

Figura 1

En la imagen también se lee el comentario “!Ejemplo en LINGO del primer laboratorio de Investigación Operativa 1;”, LINGO admite agregarlos con la condición que empiecen con el caracter “!” y finalicen con “;”. 3.3

DISEÑO DE SETS

FINALIDAD E IDENTIFICACIÓN DE LOS SETS Una inquietud que quizá tenga el estudiante es por qué debe aprender otro software para la resolución de modelos de programación lineal. Si usted ya exploró el LINDO habrá notado que es necesario digitar completamente en su editor el programa lineal diseñado; ésta es una tarea muy laboriosa cuando los modelos son de gran magnitud, situación frecuente en la realidad. Los sets son un grupo de objetos relacionados que permite agrupar parámetros, variables y restricciones las cuales se agrupan en una serie de familias de características similares con lo cual el ingreso de los programas lineales de gran tamaño se hace de manera sencilla y ágil con LINGO. Ejemplo 1 En cierta empresa manufacturera se fabrica 20 diferentes productos y cada uno pasa por una secuencia se siete procesos distintos en donde la materia prima se agrega en los cinco primeros. Los dos últimos procesos son de acabado de los productos. La secuencia de los procesos para cada producto es la misma y se identifica con proceso 1 al primero, proceso 2 al segundo y así sucesivamente. En el anexo 1 se muestra los costos variables unitarios, los precios de venta, el margen de contribución, la demanda máxima de los 20 productos y la mínima por obligaciones contractuales. En el anexo 2 se presenta el tiempo en cada proceso requerido por cada unidad de tipo de producto y en el anexo 3 se encuentran los datos de la cantidad de materia prima por cada kilogramo de producto terminado. Esta empresa desea determinar cuántos productos de cada tipo debe fabricar para maximizar las utilidades pero sujeta a las restricciones de recursos y demanda; para tal fin, las variables de decisión son: Pi: cantidad de kilogramos por fabricar de cada tipo de producto. i= 1,2,3…20

En el anexo 4 se muestra el resto del modelo de programación lineal y lo llamaremos modelo 1. Quizá usted ya habrá notado que digitar el modelo 1 en el editor del LINDO es laborioso, asimismo, por su magnitud es probable que cometa varios errores en esta tarea. Por otro lado, la revisión de sus parámetros con el fin de detectar errores es también engorrosa porque exige observar exhaustivamente todo lo que se ingresó en el editor. Usando notación matemática, el modelo 1 equivalente es el siguiente y lo llamaremos modelo 2: Modelo 2 Maximizar

i=1..20(MCi*Pi)

Restricciones de demanda: Pi ≥ Dmínima i

;

i=1,2…20

2

Pi ≤ Dmáxima i ; Restricciones de tiempo: j=1..20(Tuji*Pj)

≤ Ti

;

i=1,2…20

i=1,2…7

Restriccones de materia prima: j=1..20(MPuji*Pj)

≤ MPi

;

i=1,2…5

Ahora lea nuevamente el texto del ejemplo 1, observe el modelo 2 e identifique la siguiente lista de parámetros: El margen de contribución de cada producto: MCi. La demanda mínima de cada producto: Dmínima i. La demanda máxima de cada producto: Dmáxima i. Disponibilidad del recurso tiempo en cada proceso: Ti. Disponibilidad de recurso materia prima: MPi. El tiempo unitario de cada producto en cada proceso: Tuji. El consumo de materia prima de cada producto: MPuji. Finalmente, identifique la lista de las variables: Cantidad de cada tipo de producto por fabricar. SETS PRIMITIVOS En la lista de parámetros y variables anterior, identificamos tres grupos con características similares: el margen de contribución, la demanda y las variables. Cada grupo se denomina atributo (attributes), y a este conjunto de grupos se denomina set. Revise los anexos 1, 2 y 3 y note que los atributos margen de contribución y demanda tienen 20 datos; el atributo variables tendrá 20 valores que se determinarán al resolver el programa lineal, éstas son las variables de decisión. La dimensión 20 es una característica común de estos atributos del set al que llamaremos PRODUCTOS; LINGO permite que usted elija el nombre del set con un máximo de 32 caracteres pero necesariamente el primero es alfabético. Para indicar la dimensión escriba después de PRODUCTOS la secuencia de caracteres “/1..20/” . Antes de ingresar los sets en el editor, primero escriba el comando SETS seguido del caracter “:” ; hasta aquí el editor del LINGO tendrá la apariencia de la figura 2. Figura 2

Nuevamente se observa comentarios en el editor; en este caso se anotó “!Sets primitivos;” y el otro referido a las variables de decisión. Para declarar los atributos del set PRODUCTOS usaremos las etiquetas MARGEN, DEMANDAMIN, DEMANDAMAX y P (usted puede elegir otros nombres). La etiqueta MARGEN contiene los 20 datos del margen de contribución unitario de cada producto; las etiquetas

3

DEMANDAMIN y DEMANDAMAX contienen cada una los datos de la demanda mínima y máxima de los 20 productos respectivamente y la etiqueta P son las 20 variables de decisión de este modelo. Luego de digitar los nombres de estos atributos, la figura 3 muestra cómo se verá el editor. Figura 3

En la pantalla hemos anotado el comentario “!VARIABLES DE DECISIÓN definidas en la matriz P;” para recordar que cada elemento de la matriz P es una de las 20 variables de decisión. En la lista de parámetros identificamos otro set cuyo atributo es la disponibilidad del recurso tiempo en cada proceso, como son siete procesos, son siete los datos de este atributo (vea el anexo 2). No hay otro atributo con esta dimensión. En la figura 4 se muestra el set PROCESOS (usted puede elegir otro nombre) y para indicar su dimensión PROCESOS/1..7/:. Figura 4

Quizá se esté preguntando por qué se digitó PROCESOS: en vez de PROCESOS/1..7/:, es decir, sin dimensión. Esto es posible siempre y cuando se declare la dimensión en la zona de datos, este detalle se explicará más adelante, sin embargo, si desea digite PROCESOS/1..7/:. Para declarar el único atributo del set PROCESOS usaremos la etiqueta RECURSOT (u otro nombre) que contiene los siete datos del tiempo disponible de cada proceso, observe la figura 5. Figura 5

En la lista de parámetros también tenemos la disponibilidad del recurso materia prima en cada proceso, el texto del ejemplo 1 indica que sólo en los cinco primeros procesos se agregan distintos tipos de materia prima. Este es otro atributo al que llamaremos RECURSOMP (u otro nombre) y

4

definimos el set PROCESOMP/1..5/ (vea el anexo 3 y verifique la dimensión). La figura 6 presenta este set y su atributo. Figura 6

Los tres primeros sets diseñados son llamados sets primitivos y son semejantes a matrices cuya dimensión es una fila y n columnas, por ejemplo, el set PRODUCTOS es un arreglo de números de 20 datos (columnas). La lista de parámetros muestra dos grupos de datos que son el tiempo unitario de cada producto en cada proceso y el consumo de materia prima de cada producto. Estos grupos de datos son de dos entradas: el primero tiene 140 datos porque son tiempos unitarios de los 20 productos en cada uno de los siete procesos; el segundo tiene 100 datos porque son los consumos de materia prima por cada unidad de los 20 productos en cada uno de los cinco procesos que sí requieren estos materiales. SETS DERIVADOS Los sets derivados ayudan a definir los arreglos de datos o variables cuyo orden es nxm donde n es la cantidad de filas y m la cantidad de columnas. Como usted ya habrá notado, tanto los datos de los tiempos unitarios como los de la materia prima por unidad son matrices de n filas y m columnas; así por ejemplo, el tiempo unitario tiene 20 filas y 7 columnas, (o viceversa, usted elija cómo) mientras que la materia prima por unidad tiene 20 filas y 5 columnas (en los anexos 2 y 3 verifique las dimensiones indicadas). Para el grupo de datos tiempos unitarios de cada producto en cada proceso, definamos el atributo TIEMPO (u otro nombre) dentro del set derivado MATRIZ1 (u otro nombre). Este set es derivado de los sets primitivos PRODUCTOS y PROCESOS cuyas dimensiones son 20 y 7 respectivamente, lo que permite indicar a LINGO que la MATRIZ1 (PRODUCTOS , PROCESOS) es de orden 20x7. Este set y su atributo se muestran en la figura 7. Figura 7

Por otro lado, los consumos de materia prima de cada producto en cada uno de los cinco primeros procesos, se asignarán al atributo MP (u otro nombre) dentro del set derivado MATRIZ2 (u otro nombre). Este set es derivado de los sets primitivos PRODUCTOS y PROCESOMP cuyas dimensiones son 20 y 5 respectivamente, lo que permite indicar a LINGO que la MATRIZ2 (PRODUCTOS , PROCESOMP) es de orden 20x5.

5

La zona de los sets termina con el comando ENDSETS, esto y todos los sets diseñados se muestran en la figura 8. Figura 8

ASPECTOS CLAVES EN EL DISEÑO DE SETS Culminada la definición de los sets, observe nuevamente la figura 8 y anotemos algunos aspectos claves que a menudo son fuentes de error: Los comentarios y las líneas que contienen los nombres de los sets y atributos terminan con el caracter “;”. Después de los comandos MODEL y SETS anote “:”, no el caracter “;” . Termine la zona de los sets con el comando ENDSETS sin el caracter “;” ni “:”. Los nombres de los atributos y de los sets primitivos invocados en los sets derivados se separan con comas, por ejemplo, MARGEN , DEMANDAMIN , DEMANDAMAX , P y (PRODUCTOS , PROCESOS). Se recomienda nombres para los sets y atributos que sean fáciles de recordar (se sugiere que tengan relación con los datos que contienen o las variables de decisión definidas) porque serán usados en el resto del programa y usted deberá invocarlos exactamente igual a como los definió en la zona de sets. A menudo es fuente de error omitir alguna de las letras o agregar otras, por ejemplo, anotar en las restricciones PROCESO en vez de PROCESOS; LINGO no reconocerá la etiqueta PROCESO y enviará un mensaje de error. Defina la dimensión de los sets, usando los caracteres “/1..m/”. Note que el primer número necesariamente es uno seguido de “..” (dos puntos, no tres o más) y m debe ser un número entero positivo. En caso omita la dimensión, deberá ser definida en la zona de datos como se explicará en la siguiente sección. También es posible definir implícitamente la dimensión con nombres y otras secuencias de caracteres en cuyo caso la cantidad de nombres anotadas será la dimensión. Si desea conocer más detalles, consulte el segundo capítulo del LINGO 11 Users Manual. 3.4

EL INGRESO DE DATOS

El ingreso de datos empieza con el comando DATA seguido del caracter “:”. Recuerde que el ejemplo 1 tiene varios conjuntos de datos, a saber, margen de contribución unitario de cada producto; demanda mínima y máxima de cada producto; recurso tiempo disponible de cada proceso; recurso materia prima disponible de cada tipo; tiempo unitario de cada producto en cada proceso y cantidad de materia prima por unidad de cada tipo de producto en cada proceso. Estos datos se identificaron como atributos en la zona de sets y se les asignó los nombres MARGEN, DEMANDAMIN, DEMANDAMAX, RECURSOT, RECURSOMP, TIEMPO y MP, respectivamente. Los datos de estos atributos son parámetros del modelo conocidos de antemano y deben ser ingresados al LINGO. El ingreso consiste en anotar el nombre del atributo seguido del caracter “=” y de los datos del atributo. Evite digitar los datos, cópielos directamente del archivo Excel “Datos.xls” que se proporcionó junto con esta guía. Si los pega directamente desde el Excel al

6

editor del LINGO pegará también la cuadrícula, para evitar esto y así mejorar la apariencia del 1 modelo, primero pegue los datos del Excel al Bloc de notas y de éste al LINGO. En la figura 9 se muestra el ingreso de los datos MARGEN, DEMANDAMIN, DEMANDAMAX, RECURSOT y RECURSOMP. Figura 9

Note en la figura 9 que cada arreglo de datos culmina con “;”. Un detalle pendiente de la sección 3.3 fue por qué se omitió la dimensión del set primitivo PROCESOS en la zona de los sets. En la figura 9 observe en la zona sets que se escribió PROCESOS en vez de PROCESOS/1..7/, sin embargo, en la zona de datos implícitamente se ha definido su dimensión al anotar “PROCESOS =” seguido de siete etiquetas, la primera es PROCESO1 y así sucesivamente. ¿Recuerda que la dimensión de este set es siete porque esa es la cantidad de procesos en la línea de producción? 1

Para ubicar el Bloc de notas presione el ícono de Windows ubicado en la zona inferior izquierda y en el menú busque “Todos los programas“ y luego “Accesorios”, ahí encontrará dicha aplicación.

7

La figura 10 presenta el resto de datos, observe los atributos TIEMPO Y MP que son las matrices de orden 20x10 y 20x5 que se diseñaron con el apoyo de los sets derivados. La zona de datos finaliza con el comando ENDDATA. Figura 10

ASPECTOS CLAVES EN EL INGRESO DE DATOS Culminada la definición de los datos, observe nuevamente las figuras 9 y 10 y anotemos algunos aspectos claves que a menudo son fuentes de error: Cada grupo de datos termina con el caracter “;”. Después del comando DATA anote “:”, no el caracter “;”. Termine la zona de los datos con el comando ENDDATA sin el caracter “;” ni “:”. No olvide de usar el nombre exacto de cada set o atributo tal como se definió en la zona de sets, cualquier diferencia en los nombres LINGO no las reconocerá y automáticamente enviará un mensaje de error. Por ejemplo, observe la figura 10, luego pruebe en su editor qué ocurre si en la zona de datos, en vez de usar la etiqueta TIEMPO usa TIEMPOS. Los datos de los atributos de sets derivados nxm deben anotarse en n filas y m columnas; n y m deben ser iguales a las dimensiones del primer y segundo set primitivo invocados en el set derivado, de lo contrario, LINGO generará un modelo que no corresponde al caso que usted

8

quiere resolver. Por ejemplo, TIEMPO es un atributo del set derivado MATRIZ1, éste invoca a los sets primitivos PRODUCTOS y PROCESOS así: MATRIZ1 (PRODUCTOS , PROCESOS). Como la dimensión de PRODUCTOS es 20 y la de PROCESOS es siete, entonces el orden del set derivado MATRIZ1 es 20x7 (20 filas y 7 columnas); luego los datos deben ser ingresados según dicho orden: 20 filas y 7 columnas, verifique esto en la figura 10. Por ningún motivo ingrese los datos en 7 filas y 20 columnas. Observe de nuevo la figura 10, ¿cómo se ha ingresado los datos del atributo MP? 3.5

DEFINICIÓN DE LA FUNCIÓN OBJETIVO, LAS RESTRICCIONES Y EL RANGO DE EXISTENCIA USANDO EL LENGUAJE DE MODELACIÓN

SET LOOPING FUNCTIONS Según el LINGO 11 Users Manual, el poder de la modelación basada en sets está en la habilidad de este software para aplicar una operación a una parte o a todos los miembros de los sets usando una sola sentencia. Las funciones que permiten esto son las denominadas set looping functions En esta sección presentaremos las funciones @SUM y @FOR, sin embargo, hay otras funciones que usted podrá encontrar en el segundo capítulo del Users Manual. LA FUNCIÓN OBJETIVO En el ejemplo 1 la función objetivo es la maximización de las utilidades (el margen de contribución) y en el modelo 1 tenemos la siguiente función objetivo en lenguaje algebraico: MAX 11P1+15.75P2+10.5P3+10.75P4+14.5P5+17.25P6+13.5P7+12P8+16P9+17P10+20P11+22P12+18.5P13+17P14 +15.5P15+19P16+21.5P17+21.5P18+15.5P19+14.5P20

Con el lenguaje de modelación del LINGO evitaremos digitar esta expresión engorrosa, para tal fin, escriba en el editor lo que se muestra en la figura 11. Figura 11

En el modelo 2 se definió la función objetivo así: Maximizar

i=1..20(MCi*Pi)

En la tabla 1 compare cada uno de los componentes de la expresión anterior con la sintaxis de la función objetivo en LINGO. Tabla 1 Función objetivo en notación matemática Maximizar

Función objetivo en LINGO MAX = @SUM( PRODUCTOS ( I ) :

i=1..20(

MCi * Pi)

MARGEN ( I ) * P( I ) );

La expresión “@SUM( PRODUCTO ( I ): MARGEN( I )* P( I ) ) ;” toma cada una de las 20 variables de decisión en el atributo P y las multiplica por sus correspondientes márgenes de contribución anotados en el atributo MARGEN. El caracter “I” es similar a un contador que empieza en uno y con un loop de 20 iteraciones suma el producto de cada margen de contribución por cada variable de decisión.

9

Un aspecto relevante en la sintaxis de la función @SUM es que enseguida debe escribir el nombre de un set; en caso lo omita, LINGO enviará un mensaje de error en la sintaxis; también es posible que lea el atributo, lo confunda con un set y envíe otro mensaje de error. Por ejemplo, vea la figura 11, luego en su editor omita el set PRODUCTO ( I ) y lea el mensaje que arroja LINGO. Finalmente, no se olvide de retornar a las condiciones originales. LAS RESTRICCIONES En el modelo 2 ubicado en la página 2 identifique esta lista de restricciones: Restricciones de demanda. Restricciones de tiempo disponible para cada proceso. Restricciones de materia prima disponible. En el anexo 4 se muestra las restricciones de demanda en lenguaje algebraico. Con el lenguaje de modelación del LINGO evitaremos digitar estas restricciones, para tal fin, escriba en el editor lo que se muestra en la figura 12. Figura 12

En el modelo 2 se definió las restricciones de demanda así: Pi ≥ Dmínima i

;

i=1,2…20

Pi ≤ Dmáxima i ; i=1,2…20 En la tabla 2 compare cada uno de los componentes de la expresión anterior para la demanda mínima con la sintaxis de las restricciones en LINGO. Tabla 2 Restricciones de demanda en notación matemática Pi ≥ Dmínima i

Restricciones de demanda en LINGO P( I ) >= DEMANDAMIN ( I ) ); @FOR( PRODUCTOS ( I ):

i=1,2…20

La expresión “@FOR( PRODUCTOS ( I ): P( I ) >= DEMANDAMIN( I ) ) ;” toma cada una de las 20 variables de decisión en el atributo P e indica que sean mayores o iguales que la demanda mínima correspondiente que se registraron en los datos del atributo DEMANDAMIN. El caracter “I” es similar a un contador que empieza en uno y en con loop de 20 iteraciones genera las 20 restricciones de demanda mínima (o menos en caso algunas de las demandas mínimas sean cero). De manera similar usted puede explicar la sentencia para la demanda máxima escrita en la figura 12. En el anexo 4 se muestran las restricciones del recurso tiempo en lenguaje algebraico, éstas son especialmente engorrosas de digitar. En la figura 13 se muestra cómo el lenguaje de modelación del LINGO con una sola sentencia genera las siete restricciones de tiempo.

10

Figura 13

En el modelo 2 se definió las restricciones del recurso tiempo en cada proceso así: j=1..20(Tuji*Pj)

≤ Ti

;

i=1,2…7

En la tabla 3 compare cada uno de los componentes de la expresión anterior con la sintaxis de las restricciones en LINGO. Tabla 3 Restricciones de tiempo en notación matemática j=1..20(Tuji*Pj)

Restricciones de tiempo en LINGO @SUM( PRODUCTOS ( J ) : TIEMPO ( J , I )*P( J ) ) =10 P9>=20 P10>=25 P11>=15 P12>=10 P16>=10 P1