Ejercicios de laboratorio de Programación Lineal
Full text
EST 100 ...__-~~~~~~~~~~~~~~~~~~~~ ~~ ~~~~~~~~~~~~~~~~ .... / INVESTIGACIO OPERATIVA DETERMINISTA ~ - <>--- Javier Heredia ~' " '"' /, ó~ i)Z:: l'.1D[J:.~'1" -e _:~,K~~l,, v 1-i h t t' -,.,., i t: -- UN IVERS ITAT POLITECNICA DE CATALUNYA Bibliot eca 11 11 11 111 11 1 11111111111111111111111111111 111 1111 111 111111 111 1400286159
EJERCICIOS DE LABORATORIO DE PROGRAMACION LINEAL (v.07.96) F. Javier Heredia Cervera Departament d'Estadísti ca i Investigació Operativa Secció d'Informatica UPC C ur s 96-97
INDICE PRESENTA C IÓN .. .. . .. .. . ..... ... ... ... .... .. .. . .. ..... . .... .. . .... . ..... .. .. .. . ..... . .. 1 EJERCICIO 1 : INTRODUCCION, RESOLUCION Y ALMACENAMIENTO . ......... .... 2 EJERCICIO 2 : CAMBIOS DE FORMULACION .... . .. . .. . . .. . .. .... ........... . ..... . .. . 4 EJERCICIO 3 : TABLEA U DEL SIMPLEX ..... . ... . ................ . ...... . .. .. . . . . .. . ... 6 EJERCICIO 4: SELECCION DE LA VARIABLE DE SALIDA . . .... .. . .. . . ... . . .. . . . . .... 7 EJERCICIO 5 : SELECCION DE LA VARIABLE DE ENTRADA .. ... ... . ... . . . .. . . .... . . 8 EJERCICIO 6 : ANALISIS DE SENSIBILIDAD ...... . .. . . .. . ... . . .. . ...... . . ...... .. . . .. . 9 EJERCICIO 7 : ADICION DE VARIABLES Y RESTRICCIONES .. .. .. . . ..... . . . . .. ... .. 11 EJERCICIO 8 : PROGRAMACIÓN LINEAL ENTERA .. .. ...... ... . ......... . .. . . .. . . . .. 13
Dept. EIO/UPC/5-2-1997 Ejercicios de Laboratorio de PL (v.07.96)/ IOD/ DE-FME 1 PRESENTACIÓN. Los "Ejercicios de Laboratorio de Programación Lineal" consisten en una serie de prácticas cortas (de ahí el nombre de Ejercicios) que abordan aspectos concretos de la resolución de problemas de programación lineal (P) mediante el algoritmo del símplex. El objetivo de estos Ejercicios es doble: por un lado se pretende favorecer la consolidación de los conceptos estudiados en clase de teoría mediante su "manipulación" con LINDO; por otro lado se intenta familiarizar al alumno con el uso del paquete de optimización lineal LINDO, de forma que pueda resolver automáticamente problemas (P). Cada Ejercicio contiene una serie de apartados en los que se indica al alumno la realización de una o varias operaciones simples sobre el modelo (P) que tiene asignado, junto con algunas preguntas sobre los resultados obtenidos. El conjunto de Ejercicios es : Ejercicio l. Ejercicio 2. Ejercicio 3. Ejercicio 4. Ejercicio 5. Ejercicio 6. Ejercicio 7. Ejercicio 8. introducción, resolución y almacenamiento. cambios de formulación. tableau del simplex. selección de la variable de salida. selección de la variable de entrada . análisis de sensibilidad. adición de variables y restricciones. programación lineal entera . Los guiones de prácticas pretenden ser autoexplicativos, por lo que, una vez invocado LINDO, debería ser posible realizar cada ejercicio siguiendo paso a paso las instrucciones indicadas en los diferentes apartados . LINDO posée tres comandos de ayuda : HELP , CAT y COM . Estos comandos pueden resultar muy útiles durante la realización de los ejercicios. Se recomienda inspeccionarlos, en el orden indicado, antes de empezar el primer ejercicio.
Dept. EIO/UPC/5-2-1997 Ejercicios de Laboratorio de PL (v.07.96)/ IOD/ DE-FME 2 EJERCICIO l. INTRODUCCION, RESOLUCION Y ALMACENAMIENTO. OBJETIVOS : En el primer ejercicio nos limitaremos a introducir un problema lineal, resolverlo y almacenar y recuperar tanto su formulación como su solución. INSTRUCCIONES: MIN, ST, END, LOOK, GO, SAVE, RETRIEVE, DIVERT, RVRT, QUIT. GUIÓN: Lo primero que debemos hacer es definir el problema, comprobando los posibles errores de formulación : 1.1.- Definid el problema que os ha sido asignado en LINDO usando las instrucciones MIN, SUBJECT TO, y END. Por ejemplo, si vuestro problema fuese : (P) max s.a. : deberíais teclear : Z= -2 X1 + 4 X1 + 3 X¡ + X¡ ' : MAX -2X1 +3X2 ? SUBJECT TO ?R1) 4X1 + 3X2 < 10 ?R2) 3X1 + 5X2 < 12 ? END 3 Xz 3 Xz :<:::: 10 5 Xz :<:::: 12 Xz 2: o El nombre de las variables (Xi, X2) es arbitrario, pudiéndose elegir nombres relacionados con su significado físico (por ejemplo, CARNE y PESCADO en el problema de la dieta). R1) y R2) sirven para dar nombre a las restricciones (R1 para la primera y R2 para la segunda). Al acabar de escribir el nombre de una restricción se debe teclear ")" o " : ". Los nombres de las variables y restricciones deben consistir en un conjunto de, como máximo, ocho carácteres cualesquiera, excepto " <" , ">" , "+ ", "= ", "." y el espacio en blanco. Tampoco se permiten nombres cuyo primer carácter corresponda a un número. LINDO define por defecto todas las variables como no negativas, por lo que no es preciso introducir restricciones adicionales del tipo x; 2: O 1.2.- Comprobad que no habéis cometido errores en la definición del problema : haced que LINDO os muestre por pantalla el problema introducido usando la instrucción LOOK. Tras introducir LOOK LINDO responde preguntando el número de fila que queremos ver. Si respondemos ALL nos mostrará el modelo completo. Hacedlo. Observad que LINDO numera las filas comenzando por el número 2) . Esto es así porque considera que la fil a número 1) es la función objetivo. Si tecleais LOOK numres1, numres2 os mostrará to das las restricciones entre la número numres1 y la número numres2. Comprobadlo. Una vez definido, procedemos a resolverlo : 1.3.- Si el problema está bien definido, resolvedlo con la instrucción GO. LINDO presenta en pantalla el número de iteraciones, el valor de la función objetivo, el valor de las va ria bles
Dept. EIO/UPC/5- 2-1997 Ejercicios de Laboratorio de PL (v.07.96)/ IOD/ DE-FME 3 y sus costes reducidos, el valor de las holguras y excesos y el valor de las variables duales. A continuación nos permite realizar análisis de sensibilidad (DO RANGE(SENSITIVITY) ANALYSIS?) De momento responded NO. Usualmente una vez definido y resuelto un modelo lineal, se seguirá trabajando con él en sesiones posteriores. Veamos cómo guardar y recuperar el modelo definido : 1.4.- Para guardar la definición del problema debemos usar la instrucción SAVE prob siendo prob el nombre del fichero donde se guardará el modelo (precedido del "path" si se desea guardar en un directorio diferente del actual) . Elegid un nombre prob y guardad el modelo (P). 1.5.- Recuperaremos el modelo cargando el fichero prob con la instrucción RETRIEVE (RETR) . Si tecleamos esta instrucción aparecerá en pantalla el directorio actual, sobre el que podremos seleccionar el fichero a cargar. Si el fichero prob no se encuentra en el directorio actual , deberemos cargarlo haciendo RETR {path]\prob. Cargad el fichero prob y comprobad con LOOK que la recuperación ha sido satisfactoria . Al trabajar con un problema lineal no sólo nos puede interesar guardar el modelo matemático, sinó tambien los resultados obtenidos en su resolución (por ejemplo, para preparar informes de prácticas, presentaciones de resultados, etc.). Con LINDO es posible crear ficheros que contengan cualquier resultado mostrado por pantalla usando las instrucciones DIVERT (DIV) y RVRT : 1.6.- La instrucción DIV sali envia la salida del resto de instrucciones de LINDO hacia el fichero sali. Elegid un nombre sali y teclead DIV sali. A part ir de ahora la respuesta de LINDO a cualquier instrucción se enviará, no a la pantalla, sinó al fichero sali. Probadlo tecleando LOOK ALL. Veréis que no se obtiene ninguna respuesta en pantalla mientras que en el fichero sali se habrá escrito la definición del problema actual (esto lo comprobaréis más tarde) . Resolved el problema con GO. De nuevo, no se obtiene por pantalla más que un mínima información, mientras que el informe completo se habrá escrito en el fichero sali. l. 7 .- Una vez hemos escrito sobre el fichero sali toda la información deseada, podemos volver a dirigir la información hacia la pantalla con la instrucción RVRT. Comprobadlo tecleando RVRT y LOOK ALL. Finalizaremos el ejercicio saliendo de LINDO y comprobando el contenido del fichero sali . 1.8.- Salid de LINDO tecleando QUIT. 1.9 .- El fichero sali creado con DIV es un fichero ASCII que puede ser impreso o incorporado a cualquier texto mediante un editor. Comprobad que sali contiene efectivamente el resultado de LOOK ALL y de GO viendo su contenido con un editor de textos (o simplemente tecleando la instrucción del DOS type). Las instrucciones DIV y RVRT deberán ser usadas en la realización de los informes de Ejercicios de Laboratorio para incluir en estos la salida obtenida por pantalla. En cada ejercicio se indicará e xplícitamente las salida que deberán ser incluidas. INFORME: No se debe entregar ningún informe de este primer ejercicio. Dept. EIO/ CPC ~---- GUIÓ 2.1.- Ca..-g-c.i "'- = 1. -L -OS e::=~~ 2. - Las co=::- 3. - Lo.s i:.oe= ¿ - 4. -El -·g;:o :::~ - 5. - El no=::;~ :.~ Ve am os cóm o :. - ~ - . 2. 2.- 2.3.- Modm ca · indepe:!l ci=;;. -_ como=--=-~ 2.5 .- nomres nornres.
:=.-F. \fE 3 = A.O -.c.:i2bles duales. , '.;" .... ::: cs ::: tiS ITIV ITY) ro;: él en s es iones ~;-:::. :::::-ob siendo prob ••.-;e:! se desea guarda r .:_;;..::. ~ mod elo ( P). :.:..~:::::.vz ( RETR). Si -- .::::: & que podremos á ,:=~to rio actual, F·=:: comp robad con que co ntengan C?i ) 7 ?.VR T : i.!:c::G. _a :- espuesta de , :::::.=:-:: sal i . Probadlo 1 ~:G.2a mie nt ras que ~.o !o comprobaréis i ~-o: ~=talla. más que i ~C::o en el fichero ?<>dem os vo lver ~.:: =;:o.:ia.dlo te cleando =" :.:::.;: ;-o sal i. ;::-~ o incor porado =;: ~e<:ti \-ame nte el ? ;.er;~ o simple mente ~:::;:es de Ejercicios · : :.;::cicio se indicará Dept. EIO/UPC/5-2-1997 Ejercicios de Laboratorio de PL (v.07.96)/ IOD/ DE-FME 4 EJERCICIO 2. : CAMBIOS DE FORMULACION. OBJETIVOS modificación del modelo introducido alterando los elementos de e, A y b. Se experimentará con los conceptos de degeneración posibilidad y acotación. INSTRUCCIONS : ALTER, EDIT . GUIÓN: 2.1.- Cargad el fichero prob que contiene la definición del problema (P) y resolvedlo. Usando la instrucción ALTER podremos modificar : 1.- Los elementos de la matriz de restricciones. 2.- Las componentes del vector de términos independientes. 3.- Los coeficientes de la función objetivo. 4.- El signo de las restricciones y de la función objetivo. 5.- El nombre de las restricciones. Veamos cómo hacerlo : 2.2 .- Modificación de A : Teclead ALTER. LINDO responde pidiendo primero el nombre de la fila a modificar (ROW: ), después el nombre de la variable cuyo coeficiente deseamos modificar (VAR:) y por último el valor del nuevo coeficiente (NEW COEFFICIENT: ). También es posible introducir el nombre de la restricción y de la variable directamente tras la instrucción ALTER (ALTER nomres nomvar). 2.3.- Modificación de b : Si queremos modificar la componente del vector de términos independientes asociada a la restricción nomres debemos invocar ALTER introduciendo RHS como nomres (ALTER nomres RHS) . Pensad una modificación de (P) que produzca un problema lineal con solución óptima degenerada. Introducid esta modificación en la definición de (P) y comprobad, usando LINDO, que el nuevo modelo tiene una solución óptima degenerada. 2.4.- Modificación de e : LINDO considera a la función objetivo como la primera restricción. 2 .5. - Por ello, si al invocar a ALTER se introduce como nombre de restricción 1, podremos modificar las componentes del vector de costes c. Pensad una modificación de (P) que produzca un problema lineal con óptimos alternativos. Introducid esta modificación en la definición de (P) y comprobad, usando LINDO, que el nuevo modelo tiene óptimos alternativos. Modificación del signo de las restricciones y de la f.o. : Si tras de teclear ALTER nomres introducimos DIR, podremos cambiar el signo de la desigualdad de la restricción nomres. A la pregunta de LINDO NEW DIRECTION: se debe responder introduciendo >, < o =, según la nueva definición elegida para nomres. Introduciendo ALTER 1 DIR podemos transformar un problema <le maximización en otro de minimización y viceversa, respondiendo MAX o MIN a la pregunta NEW DIRECTION: .
Dept. EJO/UPC/5-2-1997 Ejercicios de Laboratorio de PL (v .07.96)/ IOD/ DE-FME 5 Pensad una modificación de (P) que produzca un problema lineal no posible. Introducid esta modificación en la definición de (P) y comprobad, usando LINDO, que el nuevo modelo es no posible. Describid la salida de GO obtenida al intentar resolver el modelo no posible. 2.6.- Cambio de nombre de las restricciones : Tecleando ALTER nomres NAME podemos cambiar los nombres asignados inicialmente a las restricciones, introduciendo el nuevo nombre tras la pregunta NEW NAME=. Renombrad todas las restricciones según el convenio RES1,RES2, etc, y comprobad el cambio de nombre. Existe una forma, mucho más cómoda que las vistas hasta ahora, de modificar cualquier característica del modelo actual : invocando el editor de pantalla completa de LINDO : 2.7.- Cargad el modelo guardado en el apartado anterior. Una vez cargado en memoria teclead EDIT. Entraréis de esta forma en el editor de pantalla completa de LINDO. En él podréis observar el modelo residente en memoria y realizar las mismas modificaciones que con las instrucciones vistas en este ejercicio, pero solo para modelos de menos de 30998 carácteres. Usándo las teclas del cursor y de edición podréis moveros y editar el modelo (podréis ver la definición de otras teclas interesantes si, una vez fuera del editor, tecleáis help edi t ). Usando este editor deshaced los cambios introducidos con ALTER en el modelo (P) en el último ejercicio. Una vez hayáis recuperado el problema incial (P), salid del editor presionando la tecla Ese y comprobad que, efectivamente, habéis recuperado el modelo original. INFORME: El informe de es te ejercicio deberá incluir 1. -La salida de LINDO mostrando la formulación de los modelos c on solución óptima degenerada (apartado 2.3 ), con óptimos alternativos ( 2.4 ) y no posible ( 2.5 ), junto con una breve just ificación de las modificaciones introducidas cada caso. 2.- La salida de LINDO mostrando la solución óptima de Jos modelos de los apartados 2.3 , 2.4 y 2.5 , y la comprobación, a partir de esta información, de que las modificaciones introducidas en ca da ap a rtado son correctas. Dep . EJO Podem o;; ~--;::= ( TA B ): 3.1.- 3.2.- Poc;::::::e A'ª ..:. - variab.:~ _ Resolveremos - - 3.3.- Tecleai. -: . iOb= •.:..! en c!G....~ INFOR: \fE : El informe Ce :a. :?:a 1 .- La sai ·- ::,,, y 3.'.? i. 2.- La~~-~· 3. -El P- -~ -
.C:-F_'.fE 5 Int roducid : ~ :: -: evo modelo :;;o posible . . .JS podemos :.a::::: co el nuevo ~..., el convenio -:.::::;:ce.: cu alquier -~= - .:=o :-,a teclead J . .:=.::. él po dréis _ iréis ver ~ :::.2 :.p edit). ! = o::.:lo (P) en el editor -=..-<.<::.:> e.l modelo ::i óptima _ :. ·. ionio con .c.;::¿¡-¡.ados 2.3 ¿ · =:Y3ca.c iones ~ Dept. EIO/UPC/5-2-1997 Ejercicios de Laboratorio de PL (v.07. 96)/ I OD/ DE-FME 6 1 EJERCICIO 3. : TABLEAD DEL SIMPLEX. I · OBJETIVOS : obtener el tablean asociado a la base actual y cierta información sobre la solución asociada. Estudiar las diferencias entre la notación usada por LINDO y la utilizada en clase de teoría. INSTRUCCIONES GUIÓN : TABLEAU, SOLUTION. Podemos inspeccionar el tablean del simplex asociado a la base actual con la intrucción TABLEAU (TABL): 3.1.- Cargad el modelo (P). Si (P) incluye restricciones de 2'. eliminadlas. Teclead TABL. Aparecerá por pantalla el tableau del simplex del modelo (P) asociado a la base ac tual. Los costes reducidos y el valor de la función objetivo se indican en la pr i mera fila del tableau (indicada como ART ). A la vista del tableau obtenido, ¿ cual es la base inicial adoptada por LINDO?. 3.2.- Podemos obtener información sobre todas las variables de la solución actual con la instrucción SOL. Teclead SOL y observad el resultado. A la vista de la información presentada, ¿ creéis que SOL permite identificar siempre las variables básicas ? Resolveremos ahora el modelo y estud iar emos la notación usada por LINDO : 3.3. -Tecle ad GO. Como ya vimos en el primer ejercicio, LINDO resolverá el modelo actual. Sin realizar ninguna iteración del algoritmo el simplex, calculad los elementos del table au del simplex asociado a la base óptima proporcionada por LINDO y comparadlos con los valores obtenidos al hac er TABL y SOL. ¿Observais al guna diferencia e ntre la forma de presentar el t ab lean de LINDO y la usada en clase? INFORME El informe de la práct ica deberá incluir: 1.- La sa lida de las instrucciones SOL y TABL correspondientes a la base inicial (apartados 3.1 y 3.2 ) y a la base ó ptima (apartado 3.3 ). 2. -La respuesta a las preguntas fromuladas en los tre s apartados . 3.- El proceso de cálculo del tableau del símplex asociado a la base óptima (apa rt ado 3.3 ).
:;:;.:=:-:!!E: 12 ~::.\~ :::i seguido -::; =.:;. :,:aneo ( DEL :.:;.;::. :. ·.l eva. DEL :.z. o.-:<:. ~est ricció n ,;:¿ :-,,:;-?on de ALL, \ Dept. EIO/UPC/5-2 -1997 Ejercicios de Laboratorio de PL (v.07.96)/ IOD/ DE -FME 13 EJERCICIO 8. : PROGRAMACIÓN LINEAL ENTERA . OBJETIVOS : Aplicación del algoritmo de Branch& Bound con ayuda de LINDO. Resolución de problemas de Programación Lineal Entera con LINDO. INSTRUCCIONES : GINT. GUIÓN : El propósito de este ejercicio es resolver el problema (P) asignado a cada grupo pero como problema ente ro, es decir, considerando las variables X1, X2 y X3 enteras. Ll ama remos (PE) a e ste problema. Debemos tene r, primero, un problema (P) con solución fracciona.!: 8.1.- Cargad el fichero prob que contiene la definición del problema (P) y resolvedlo. Observad si la solución obtenida x* es entera. Si lo es, modificad la formulación de vuest ro modelo hasta conseguir una solució x* no e ntera . Una vez obten ido un problema (P) con solución no en ter a, deberéis re solver el proble ma (PE) aplicando, con ayuda de LINDO, el algorimo de B&B estudiado en clase de teoría: 8.2.- Resolved el problema (PE) aplicando el algoritmo B&B. Usad LINDO para resolver las relajaciones lineales de los subproblemas asociados a cada nodo del árbol de exploración. LINDO permite resolver problemas (PE) directamente: tan solo es preciso definir las variables como e nt eras media nte la instrucción GINT. 8.3. - Cargad de nuevo el modelo (P) . Si en el apartado 8.1 habíais modificado (P), hacedlo ahora tambié n. Definid las variables como ent eras in tro duciendo GINT 3 y resolved el mod elo. Comprobad que la solución que proporciona LINDO coincide con la enco ntr ada en el apartado 8.2 . INFORME: El informe de este ejercicio debe rá incluir: 1. -La salida de LINDO mos tr ando el proble ma original (P) , con ó ptim o no entero ( 8.1 ). 2.- El árbo l de exploración de la resolución de (PE) mediante el alg or i tmo de B&B ( 8.2 ). 3.- La sa lida de LINDO mostrando la so lu ción ópt ima de la rel ajac ión lin ea l asoci ada a los tres primeros nodo s vi sitados ( 8.2 ). 4. -La sa lida de LINDO mostrando la solución del problema (PE) ( 8.3 ).