Modelado y optimización de los horarios de un centro universitario con Programación Matemática

Grado en Matemáticas TRABAJO FIN DE GRADO Modelado y optimización de los horarios de un centro universitario con Programación Matemática Francisco Valls Mestanza Sevilla, Junio de 2020 Índice general Resumen....................................... iii Abstract....................................... iv ÍndicedeFiguras.................................. v ÍndicedeCuadros.................................. viii 1. Introducción 1 1.1. Motivación................................... 1 1.2. Antecedentes bibliográficos . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Objetivos ................................... 2 2. Programación Lineal 3 2.1. Introducción histórica y aplicaciones . . . . . . . . . . . . . . . . . . . . 3 2.2. Modelado y ejemplos de programación lineal . . . . . . . . . . . . . . . . 4 2.3. Conceptos y resultados de análisis convexo . . . . . . . . . . . . . . . . . 6 2.4. Optimalidad en programación lineal . . . . . . . . . . . . . . . . . . . . . 8 2.4.1. El algoritmo del Simplex . . . . . . . . . . . . . . . . . . . . . . . 11 2.5. Programación Lineal Entera . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5.1. Planosdecorte ............................ 14 2.5.1.1. Esquemas de ramificación y acotación . . . . . . . . . . 15 2.6. AMPLyCPLEX............................... 16 3. Planteamiento del problema de horarios 17 3.1. Descripción del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1. Asignaturas y horarios . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.2. Estudiantes .............................. 20 3.1.3. Profesores............................... 21 3.1.4. Aulas.................................. 21 3.1.5. Restricciones ............................. 22 3.2. Formulación.................................. 23 3.2.1. Modelo................................. 23 3.2.2. Datos ................................. 31 4. Resultados y análisis 35 4.1. Horariosobtenidos .............................. 35 4.2. Aspectos computacionales del modelo . . . . . . . . . . . . . . . . . . . . 40 4.3. Análisis de sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.4. Comparativa con el horario real del curso 2019/2020 . . . . . . . . . . . . 43 4.5. Conclusiones y líneas futuras de trabajo . . . . . . . . . . . . . . . . . . 45 4.6. CódigoAMPL................................. 45 i 4.6.1. Código del fichero de extensión ‘.mod’ . . . . . . . . . . . . . . . . 46 4.6.2. Código del fichero de extensión ‘.dat’ . . . . . . . . . . . . . . . . 52 4.6.3. Código del fichero de extensión ‘.run’ . . . . . . . . . . . . . . . . 58 A. Apéndice: Modelo y horario del segundo cuatrimestre 59 A.1. Asignaturas del segundo cuatrimestre . . . . . . . . . . . . . . . . . . . . 59 A.2. Formulación del modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 A.3.Datos ..................................... 69 A.4. Horarios del segundo cuatrimestre . . . . . . . . . . . . . . . . . . . . . . 72 A.5.CódigoAMPL................................. 76 A.5.1. Código del fichero de extensión ‘.mod’ . . . . . . . . . . . . . . . . 76 A.5.2. Código del fichero de extensión ‘.dat’ . . . . . . . . . . . . . . . . 83 A.5.3. Código del fichero de extensión ‘.run’ . . . . . . . . . . . . . . . . 88 Bibliografía 90 ii Resumen En este trabajo se presenta un modelo de programación lineal entera para la obtención del horario del primer cuatrimestre del Grado en Matemáticas de la Facultad de Matemáticas de Sevilla, para el curso 2019/2020. Se ha dividido en cuatro capítulos. En el primero de ellos, se introduce el problema de horarios y asignación de aulas, exponiendo asimismo los antecedentes bibliográficos que abordan la resolución de este tipo de problemas mediante el uso de la programación lineal, y se enumeran los objetivos que se han planteado en este trabajo. En el segundo capítulo, se exponen las nociones y resultados básicos de programación lineal y programación lineal entera necesarios para la comprensión y desarrollo del modelo formulado. Además, se explican las principales características del programa informático AMPL. En el tercer capítulo, se describen, de manera general, las características y requerimientos que debe de verificar un problema de horarios desde el punto de vista de la programación lineal. También se exponen las características propias de la Facultad de Matemáticas de Sevilla que influyen en la formulación del modelo buscado. Asimismo, se aporta la formulación del modelo y la explicación de las respectivas restricciones que aparecen en ella, junto con el código de dicha formulación escrito en lenguaje AMPL y algunas tablas con los datos del problema necesarios para su resolución. En el cuarto y último capítulo, se presentan los horarios obtenidos, se realiza un análisis de sensibilidad del modelo creado y se explican las conclusiones sobre el trabajo realizado, comparando los resultados con el horario real del curso 2019/2020 para comprobar la eficacia del modelo desarrollado. Finalmente, se incluye un apéndice en el cual se expone la formulación del modelo para obtener el horario correspondiente al segundo cuatrimestre, dando los datos necesarios para la resolución del modelo para este período académico, así como los horarios obtenidos. iii Abstract This document presents an interger programming problem to design the timetable for the first four-month period of Degree in Maths at University of Seville. This document has been divided in four chapters. In Chapter 1, the problem is introduced and some reports which use linear programming to create models for the problem of scheduling courses at universities are quoted. In addition, the objectives of this work are enumerated too. In Chapter 2, a list of mathematical definitions and theorems are given to understand the formulation of the model; furthermore, principals characteristics of the program AMPL are explained. In Chapter 3, the requeiremets of Faculty of Maths at Seville that are necessary to the timetable to be valid are discribed. Also, the formulation of the model is given as well as the explanation of the constraints, the datums of the problem and the AMPL code for the problem. In Chapter 4, the timetables obtained are presented and the conclusions of this work are exposed. Sensivity analysis is performed in order to investigate how the solution is affected when some conditions are changed. Finally, the formulation of the model for the second four-month period is described in Appendix A as well as the results obtained by this model. iv Índice de figuras 2.1. Ejemplo ramificación y acotación . . . . . . . . . . . . . . . . . . . . . . 16 4.1. Horario real del grupo A de primero para el primer cuatrimestre del curso 2019/2020................................... 43 4.2. Horario real de cuarto para el primer cuatrimestre del curso 2019/2020 . 44 v Índice de cuadros 3.1. Estudiantes matriculados en asignaturas de primero en el primer cuatrimestre 31 3.2. Estudiantes matriculados en asignaturas de segundo en el primer cuatrimestre 31 3.3. Estudiantes matriculados en asignaturas de tercero en el primer cuatrimestre 31 3.4. Estudiantes matriculados en asignaturas de cuarto en el primer cuatrimestre 32 3.5. Número de clases de asignaturas de primero en el primer cuatrimestre . . 32 3.6. Número de clases de asignaturas de segundo en el primer cuatrimestre . . 32 3.7. Número de clases de asignaturas de tercero en el primer cuatrimestre . . 33 3.8. Número de clases de asignaturas de cuarto en el primer cuatrimestre . . . 33 3.9. Capacidaddelasaulas............................ 34 4.1. Horario del grupo 1 de primer curso para el primer cuatrimestre . . . . . 35 4.2. Horario del grupo 2 de primer curso para el primer cuatrimestre . . . . . 36 4.3. Horario del grupo 3 de primer curso para el primer cuatrimestre . . . . . 36 4.4. Horario del grupo 4 de primer curso para el primer cuatrimestre . . . . . 36 4.5. Horario del grupo 5 de primer curso para el primer cuatrimestre . . . . . 37 4.6. Horario del grupo 1 de segundo curso para el primer cuatrimestre . . . . 37 4.7. Horario del grupo 2 de segundo curso para el primer cuatrimestre . . . . 37 4.8. Horario del grupo 3 de segundo curso para el primer cuatrimestre . . . . 38 4.9. Horario del grupo 1 de tercer curso para el primer cuatrimestre . . . . . . 38 4.10. Horario del grupo 2 de tercer curso para el primer cuatrimestre . . . . . . 38 4.11. Horario del grupo 3 de tercer curso para el primer cuatrimestre . . . . . . 39 4.12. Horario de cuarto curso para el primer cuatrimestre . . . . . . . . . . . . 39 4.13. Horario del grupo 2 de segundo curso tras análisis de post optimalidad . 41 4.14. Horario del grupo 1 de tercer curso tras análisis de post optimalidad . . . 42 4.15. Horario del grupo 2 de tercer curso tras análisis de post optimalidad . . . 42 A.1. Estudiantes matriculados en asignaturas de primero en el segundo cuatrimestre 69 A.2. Estudiantes matriculados en asignaturas de segundo en el segundo cuatrimestre..................................... 69 A.3. Estudiantes matriculados en asignaturas obligatorias de tercero en el segundocuatrimestre.............................. 69 A.4. Estudiantes matriculados en asignaturas optativas de tercero en el segundo cuatrimestre.................................. 69 A.5. Estudiantes matriculados en asignaturas de cuarto en el segundo cuatrimestre 70 A.6. Número de clases de asignaturas de primero en el segundo cuatrimestre . 70 A.7. Número de clases de asignaturas de segundo en el segundo cuatrimestre . 70 A.8. Número de clases de asignaturas obligatorias de tercero en el segundo cuatrimestre.................................. 71 vii 2.3. CONCEPTOS Y RESULTADOS DE ANÁLISIS CONVEXO El modelado (formulación) y análisis de un problema de programación lineal como el anterior, se genera a través de varias etapas (Bazaraa, 2012). La primera de ellas se conoce como fase de planteamiento del problema, en la cual se estudia y analiza el problema que se pretende modelizar, identificando las limitaciones y función objetivo. La segunda etapa, consiste en abstraer el problema real a un modelo matemático mediante la formulación de un problema de programación lineal. Posteriormente, la siguiente etapa, aborda la búsqueda de la solución mediante el uso de diferentes algoritmos y técnicas matemáticas (Luenberger, 1989), observando si se alcanzan una o varias soluciones óptimas o en cambio sólo se puede determinar una solución aproximada. Además, en esta etapa puede incluirse el análisis de sensibilidad , donde se cambian algunos parámetros o restricciones del modelo para estudiar escenarios del tipo “qué sucede si”. Por último, se concluye con la implementación, poniendo en marcha el modelo a través de diferentes programas informáticos para auxiliar en la toma de decisiones. A continuación se presenta la formulación de un problema clásico en programación lineal, El problema de transporte . Otros ejemplos, como el problema de almacenamiento aparecen detallados en (Luenberger, 1989). El problema de transporte Se consideran m orígenes con ciertas cantidades de un mercancía que debe ser enviada a n destinos con el fin de satisfacer las necesidades de la demanda. En particular, el origen i dispone de una cantidad ai , y el destino j necesita una cantidad bj . Se supone que el sistema está equilibrado ; es decir, la oferta total coincide con la demanda total, lo que se expresa como Pm i=1 ai = Pm j=1 bj . Además, se supone también que los números ai y bj , i = 1 , . . . , m , j = 1 , . . . , n , son no negativos. Hay un costo unitario cij para el envío de la mercancía del origen i al destino j . El problema consiste en encontrar el modelo de envío entre orígenes y destinos, satisfaciendo todas las necesidades al mismo tiempo que se minimiza el costo total del envío. Desde el punto de vista matemático, el problema se puede expresar como la búsqueda de un conjunto de xij , i = 1 , . . . , m , j = 1 , . . . , n , que corresponden a las variables de decisión y representan las cantidades de mercancía enviadas del origen ial destino j. La formulación del modelo es la siguiente: Minimizar Pm i=1 Pn j=1 cijxij sujeto a Pn j=1 xij =aii= 1,2, . . . , m Pm i=1 xij =bjj= 1,2, . . . , n xij ≥0para todo i y j. 2.3. Conceptos y resultados de análisis convexo Los conceptos relacionados con los conjuntos convexos son muy relevantes en la teoría de optimización. En esta sección se dan definiciones y resultados que predominan en programación lineal. 6CAPÍTULO 2. PROGRAMACIÓN LINEAL 2.3. CONCEPTOS Y RESULTADOS DE ANÁLISIS CONVEXO Definición 1 Sean los vectores a1, . . . , ak⊆Rn . Se dice que b es combinación convexa ( estrictamente convexa ) de a1, . . . , ak si existen escalares λ1, . . . , λk⊆R con λj≥ 0 (λj>0) yPk j=1 λj= 1 tal que b=Pk j=1 λjaj. Definición 2 Sea S⊆Rn . Se dice que S es un conjunto convexo si ∀x e y∈S y ∀λ∈ [0,1] se tiene que λx + (1 −λ)y∈S. Definición 3 Sea S⊆Rn . Se denomina envolvente convexa de S , H ( S ), al conjunto de todas las combinaciones convexas de puntos de S. Es decir, al conjunto: H(S) = {x:x=Pk i=1 λixi, xi∈S, λi≥0,Pk i=1 λi= 1},k∈Z. Teorema 1 — Teorema de Caratheodory. Sea S⊆Rn . Si x∈H ( S ), entonces puede ser expresado como combinación convexa de a lo sumo n+ 1 puntos de S. Definición 4 Un hiperplano en Rn es un conjunto de la forma H = {x : ptx = a} , con p∈Rn, p 6 = 0 , a ∈R , o de forma equivalente si x0∈H, H = {x : pt ( x−x0 )=0 } . A p se le llama vector normal al hiperplano. Un hiperplano define dos semiespacios cerrados {x:ptx≥α},{x:ptx≤α}y dos semiespacios abiertos {x:ptx>α},{x:ptx<α}. Teorema 2 — Teorema de la proyección. Sea S⊆Rn no vacío, cerrado y convexo, e y /∈S . Entonces existe un único x0∈S que minimiza la distancia de y a S . Además, x0 es el punto que minimiza la distancia si y solo si (y−x0)t(x−x0)≤0∀x∈S. A continuación, se enuncia un importante resultado dentro de los conocidos como teoremas de alternativa, cuya demostración se detalla en (Luenberger, 1989): Teorema 3 — Lema de Farkas. Sea A∈Rm×n y c∈Rn . Uno y solo uno de los siguientes sistemas tienen solución: (1) Ax =c,x≥0, para algún x∈Rn. (2) ytA≤0,ytc≥0, para algún y∈Rm. Se exponen ahora las definiciones de punto extremo, dirección extrema, cono y poliedro, junto con algunos resultados de caracterización de dichos conceptos. Las demostraciones de dichos resultados se desarrollan en (Bazaraa y Shetty, 1949). Definición 5 Un punto extremo x∈S , con S convexo, es aquel que si puede escribirse de la forma x = λx1 + (1 −λ ) x2 con x1 y x2∈S y λ∈ (0 , 1), entonces necesariamente x=x1=x2. Definición 6 Sea S⊆Rn no vacío y convexo. Un vector d de S , con d6 = 0, se denomina dirección de S si ∀x∈S se tiene que x + λd ∈S∀λ≥ 0. Una dirección se dice dirección extrema si no puede expresarse como combinación lineal positiva de dos direcciones distintas de S, es decir, si d=λ1d1+λ2d2entonces d=d1=d2. Definición 7 Un poliedro es el conjunto de puntos definido por la intersección de un número finito de semiespacios cerrados, es decir, un conjunto de la forma S = {x∈Rn, pt ix≤ αi, i = 1, . . . , n}. Si además el conjunto es acotado, entonces se denomina polítopo. Definición 8 Sea A∈Rm×n , con m≤n y rango ( A ) = m , y b∈Rm . El conjunto S={x∈Rn:Ax =b, x ≥0}se denomina poliedro en forma estándar. CAPÍTULO 2. PROGRAMACIÓN LINEAL 7 2.4. OPTIMALIDAD EN PROGRAMACIÓN LINEAL Ejemplo 1 Sea S el poliedro S = {x∈Rn : Ax = b, x ≥ 0 } con A∈Rm×n , b∈Rm . Consideremos el sistema de ecuaciones Ax = b . Por el teorema de Rouché-Frobenius , sigue que: (1) Si rg(A|b)> rg(A) =⇒sistema incompatible, y por tanto, S=∅. (2) Si rg ( A|b ) = rg ( A ) = n = ⇒ existe una única solución del sistema, S está, como mucho, formado por un único punto. (3) Si rg(A|b) = rg(A)< m ≤n=⇒existen restricciones redundantes, se eliminan. (4) Si rg ( A|b ) = rg ( A ) = m < n = ⇒ se reordenan las columnas de A tal que A = [B|N] (no tiene por qué ser única), donde B∈Mm×m no singular y N∈Mm×(n−m) . Se reordenan las componentes de xtal que x= [ xB|xN]tcon xB∈RnyxN∈Rn−m. Así, Ax =b⇔hB|Ni"xB xN#=b ⇔BxB+NxN=b. Teorema 4 — Caracterización de puntos extremos. Sea P un poliedro en forma estándar. Entonces x es un punto extremo de P si y solo si existe una submatriz de A , B⊂A , con B∈Rm×myrg(B) = m, tal que B−1b≥0yx="xB xN#="B−1b 0#. Teorema 5 — Existencia de puntos extremos.Sea Sel conjunto definido por S = {x∈Rn : Ax = b, x ≥ 0 } , con A∈Rm×n , rg ( A ) = m y b∈Rm . Entonces S tiene al menos un punto extremo. Teorema 6 — Caracterización de direcciones extremas.Sea Sel conjunto dado por S = {x∈Rn : Ax = b, x ≥ 0 } , con A∈Rm×n , rg ( A ) = m y b∈Rm . Una dirección d es una dirección extrema de S si y solo si A puede ser descompuesta de la forma A = [B|N] tal que B−1aj≤0para alguna columna ajde Ny d es un múltiplo positivo de d0="B−1aj ej#, donde ej∈Rn−m. Teorema 7 — Representación de conjuntos poliédricos.S = {x∈Rn : Ax = b, x ≥ 0 } con A∈Rm×n , b∈Rm . Sean x1, . . . , xk los puntos extremos de S y d1, . . . , dl las direcciones extremas de S . Entonces, x∈S⇔x puede expresarse como x = Pk i=1 λixi + Pl j=1 µjdj , con Pk i=1 λi= 1,λi≥0∀i= 1, . . . , k yµj≥0∀j= 1, . . . , l. 2.4. Optimalidad en programación lineal En esta sección se describe un método para la resolución de problemas de programación lineal, conocido como algoritmo del simplex . El estudio de este método empieza demostrando que si existe una solución óptima, entonces también existe un punto extremo óptimo. Luego, los puntos extremos serán caracterizados en términos de soluciones básicas factibles . Posteriormente, este método permite mejorar dichas soluciones hasta alcanzar la optimalidad, o bien, hasta concluir la infactibilidad del problema o la no acotación del valor óptimo. Definición 9 Sean A∈Mm×n y b∈Rm la matriz de restricciones y el vector de recursos de un problema de programación lineal en forma estándar. Se dice que el punto x∈Rn es 8CAPÍTULO 2. PROGRAMACIÓN LINEAL 2.4. OPTIMALIDAD EN PROGRAMACIÓN LINEAL un punto factible del problema si Ax = b con x≥ 0; y se dice que el problema es infactible si no existe ningún xque verifique todas las restricciones del problema. Definición 10 Se denomina conjunto o región factible de un problema de programación lineal al cojunto formado por los puntos factibles del problema. El conjunto factible es un poliedro, que será no vacío si rg(A|b) = rg(A). Ejemplo 2 En el caso (4) del Ejemplo 1 de la sección anterior, se había llegado a: Ax =b⇔hB|Ni"xB xN#=b ⇔BxB+NxN=b. Así, xB=B−1b+B−1NxN. Asignando valores a xNen la expresión obtenida, se obtienen los puntos factibles. Definición 11 Se considera la expresión xB = B−1b + B−1NxN . Haciendo xN = 0 y xB = B−1b , x se denomina solución básica y si además xB≥ 0, entonces se dice que x es solución básica factible . A xB se les llama variables básicas y a xNvariables no básicas . Si alguna variable básica es cero, entonces x se denomina solución básica factible degenerada . Definición 12 Se llama solución óptima de un problema de programación lineal al punto de la región factible que optimiza la función objetivo. Si existen varios puntos del conjunto factible con esta característica, la solución del problema se denomina solución óptima múltiple . Si por el contrario, la región factible es no acotada, puede ocurrir que no se alcance el óptimo, obteniéndose así aproximaciones de la solución, la cual, en ese caso, se denomina solución no acotada. Teorema 8 — Teorema fundamental de la programación lineal. Se considera un problema lineal en forma estándar donde A∈Mm×n , de rango m , es la matriz de restricciones. Se tiene que: (1) Si hay una solución factible, entonces hay una solución básica factible. (2) Si hay una solución factible óptima, entonces hay una solución básica factible óptima. Demostración. (1) Sean a1, . . . , ak las columnas de A . Supóngase que x = ( x1, . . . , xn )es solución factible. Entonces, en función de las columnas de A, esta solución satisface: x1a1+. . . +xnan=b. Supóngase que exactamente p de las variables xi son mayores que cero, y, por conveniencia, que son las primeras pvariables. Entonces: x1a1+. . . +xpap=b(∗) Ahora hay dos casos, según si el conjunto a1, . . . , ap es linealmente independiente o dependiente. CASO 1: Supóngase que a1, . . . ap son linealmente independientes. Entonces, es evidente que p≤m . Si p = m , la solución es básica y la demostración está completa. Si p<m , como A tiene rango m , se pueden hallar m−p vectores de los restantes n−p vectores, por lo que el conjunto resultante de m vectores es linealmente independiente. La asignación del valor cero a las m−p variables correspondientes da una solución básica factible degenerada. CAPÍTULO 2. PROGRAMACIÓN LINEAL 9 2.4. OPTIMALIDAD EN PROGRAMACIÓN LINEAL CASO 2: Supóngase que a1, . . . , ap son linealmente dependientes. Entonces, hay una combinación lineal no trivial de estos vectores que es cero. Así, hay un conjunto de constantes y1, . . . , yp , una de las cuales, por lo menos, se puede suponer que es positiva, de forma que y1a1+. . . +ypap= 0 Multiplicando esta ecuación por un escalar y restándosela a (∗), se obtiene (x1−y1)a1+. . . + (xp−yp)ap=b Esta ecuación es válida para todo  , y para cada  las componentes xi−yi corresponden a una solución de las ecuaciones lineales. Haciendo y = ( y1, . . . , yp, 0 ,..., 0) se observa que para cualquier  x−y(∗∗) es una solución para las igualdades. Para  = 0, esto se reduce a la solución factible original. A medida que  aumenta desde cero, las componentes aumentan, disminuyen o permanecen constantes, en función de si la yi correspondiente es positiva, negativa o nula. Como se supuso que, al menos, una yi es positiva, como mínimo una componente decrecerá a medida que  crece. Increméntese  hasta el primer punto donde una o más componentes son cero. Específicamente, hágase =min{xi yi , yi>0}. Para este valor de  , la solución dada por ( ∗∗ )es factible y tiene a lo más p− 1variables positivas. Al repetir este proceso, en caso necesario, se podrían eliminar variables positivas hasta tener una solución factible con las columnas correspondientes que son linealmente independientes. En este punto es aplicable el CASO 1, concluyendo así la demostración de (1). (2) Sea x = ( x1, . . . , xn )una solución factible óptima como en la demostración del caso anterior, y supóngase que hay exactamente p variables positivas x1, . . . , xp . De nuevo hay dos casos; el caso 1, correspondiente a la independencia lineal es exactamente igual que antes. Véase el caso 2. Este caso también se desarrolla igual que el anterior, pero debe demostrarse que para cualquier  la solución de ( ∗∗ )es óptima. Para probarlo, obsérvese que el valor de la solución x−yes ctx−cty(∗∗∗) Para  suficientemente pequeño, x−y es una solución factible para valores positivos o negativos de  . Así, se concluye que cty = 0. Pues, si cty6 = 0, puede determinarse un  muy pequeño y signo apropiado que mantenga a ( ∗∗∗ )más pequeño que cty , conservando la factibilidad. Esto violaría la hipótesis de optimalidad de x , por lo que se debe cumplir cty= 0. Una vez establecido que la nueva solución factible con menos componentes positivos es también óptima, el resto de la demostración se completa exactamente como en el primer caso.  10 CAPÍTULO 2. PROGRAMACIÓN LINEAL 2.4. OPTIMALIDAD EN PROGRAMACIÓN LINEAL Teorema 9 — Equivalencia de puntos extremos y soluciones básicas. Sea A∈Mm×n de rango m y b∈Rm . Sea K el poliedro convexo formado por todos los vectores x∈Rn que verifican Ax =b (P) x≥0 Entonces, un vector x es un punto extremo de K si y solo si x es una solución factible básica de (P). La demostración de este resultado se recoge en (Luenberger, 1989). Corolario 1 Si el conjunto convexo K correspondiente a ( P )es no vacío, entonces tiene al menos un punto extremo. 2.4.1. El algoritmo del Simplex La idea del método simplex es pasar de una solución básica factible (es decir, un punto extremo) del conjunto de restricciones de un problema en forma estándar a otra, de modo que el valor de la función objetivo disminuya continuamente hasta alcanzar el mínimo en el caso de un problema de minimizar, y aumente hasta alcanzar el máximo en el caso de un problema de maximizar. Por el teorema fundamental de la programación lineal , se conoce que para buscar una solución factible óptima basta considerar sólo las soluciones básicas factibles. Definición 13 Se considera la matriz de restricciones expresada de la forma A = [B|N] y supóngase que x∈Rn es una solución básica factible(punto extremo), es decir, se expresa de la forma x = [B−1b, 0]t . Entonces las columnas de la matriz B forman lo que se denomina base de la solución básica factible. En lo que sigue se considerará que se está tratando con un problema de minimización. Supóngase que se tiene una solución básica factible x = ( xB, 0) t = ( y10, . . . , ym0, 0 ,..., 0) t y considérese la expresión z = (ctx ) = z0 +( cm+1 −zm+1 ) xm+1 + . . . +( cnzn ) xn ( ∗ ) , donde z0 es el valor inicial de la función objetivo y zj = y1jc1 + . . . + ymjcm , para m+ 1 ≤j≤n. Se tienen los siguientes resultados: Teorema 10 — Mejora de la solución básica factible. Dada una solución básica factible no degenerada con valor objetivo correspondiente z0 , supóngase que para alguna j se cumple que cj−zj< 0. Entonces hay una solución factible con valor objetivo z < z0 . Si alguna columna aj de A se puede sustituir por un vector de la base original y generar una nueva solución básica factible, ésta nueva solución tendrá z < z0 . Si aj no se puede sustituir para generar una solución básica factible, entonces el conjunto K no está acotado y la función objetivo puede hacerse arbitrariamente pequeña (tendiendo a menos infinito). Demostración. Sea ( x1, . . . , xm, 0 ,..., 0) t una solución básica factible con valor objetivo z0 , y supóngase que cm+1 −zm+1 < 0. Entonces siempre pueden construirse nuevas soluciones factibles de la forma ( x0 1, . . . , x0 m+1, 0 ,..., 0) t con x0 m+1 > 0. Al sustituir esta solución en (∗), resulta z−z0= (cm+1 −zm+1)x0 m+1 <0, CAPÍTULO 2. PROGRAMACIÓN LINEAL 11 2.4. OPTIMALIDAD EN PROGRAMACIÓN LINEAL de donde z < z0 para cualquiera de esas soluciones. Es evidente que se desea hacer x0 m+1 lo más grande posible. Al aumentar x0 m+1 , las otras componentes aumentan, permanecen constantes o disminuyen. Así, x0 m+1 puede aumentar hasta que una x0 i = 0, i≤m , en cuyo caso se obtiene una nueva solución básica factible o si ninguna de las x0 i disminuye, x0 m+1 puede aumentar sin ninguna cota que indique un conjunto solución no acotado y un valor objetivo sin cota inferior.  Teorema 11 — Teorema de la condición de optimalidad. Si existe una solución básica factible cj−zj≥0para cualquier j, entonces esa solución es óptima. Demostración. Resulta directamente de ( ∗ ), pues cualquier otra solución factible debe tener xi≥ 0para cualquier i , de ahí que el valor z de la función objetivo satisfaga z−z0≥0. El método del simplex debe partir de un punto extremo inicial. Ello supone encontrar una descomposición A = [B|N] , lo cual no es siempre inmediato. Para ello, las restricciones del problema pueden ser modificadas introduciendo las denominadas variables artificiales , que permiten obtener un punto extremo del conjunto factible de manera inmediata. Ax =b → x≥0 Ax +y=b x≥0 Así, x=0,y=0 es un punto extremo del nuevo conjunto factible. Ahora bien, Ax=b si y solo si y = 0, luego hay que hacer cero las variables artificiales para volver al conjunto factible del problema original. Ejemplos de lo anterio aparecen recogidos en (Bazaraa, 2012). Procedimiento computacional: El algoritmo del simplex, para un problema de optimización, consta de los siguientes pasos: Paso 0 Partir de un punto extremo x = hB|Ni = hb0,0i , con variables artificiales si es necesario. Paso 1 Comprobar si el punto extremo es óptimo, lo que variará dependiendo de si se tiene un problema de minimizar o uno de maximizar. En cada uno de los casos, respectivamente, deberá verificarse que min ct BB−1N−cN≤ 0, max ct BB−1N−cN≥ 0. Los escalares cB y cN son los correspondientes a los costos de las variables básicas y no básicas, respectivamente. A la expresión ct BB−1N−cN = (zj−cj)j∈N se le denomina vector de costos reducidos. Si el punto es óptimo, continuar en el PASO 2. Si no lo es, ir al PASO 3. Paso 2 Si ( zj−cj ) j∈N< 0en el caso de un problema de minimizar y ( zj−cj ) j∈N> 0 en el caso de maximizar y no hay variables artificiales en la base, entonces x es la solución óptima y ct Bb0 es el valor óptimo de la función objetivo. Si en cambio hay variables artificiales en la base con valor positivo, el problema es infactible. Si existe j∈N tal que zj−cj = 0, solución óptima múltiple, ir al PASO 3, calcular el 12 CAPÍTULO 2. PROGRAMACIÓN LINEAL 2.5. PROGRAMACIÓN LINEAL ENTERA otro punto extremo óptimo y la solución se da a lo largo del segmento que une ambos puntos extremos. Paso 3 Si no es óptimo se tiene, para el caso de maximizar, que ∃j∈N con zj−cj> 0 y para el de minimizar, ∃j∈N con zj−cj< 0. En el primero de los casos (minimización) se elige j con el mayor zj−cj , y para el segundo (maximización), j con el menor zj−cj . Sea yj= (y1j, . . . , yij, . . . , ymj) = B−1aj. Sigue que: (a) Si yj<0, solución óptima no acotada a lo largo de la dirección dj="−B−1aj ej#. (b) Si yj 0, sea λ = min1≤i≤n{b0 i yij } = b0 r yrj . Entonces se considera el punto extremo con componentes: xi=b0 i−b0 r yrj yij i= 1, . . . , m, i 6=r xr= 0 (deja la base) xj=λ=b0 r yrj (entra en la base) xk= 0, k ∈N, k 6=j Ir al PASO 1. Se concluye esta sección con el siguiente resultado de convergencia del algoritmo anterior: Teorema 12 — Convergencia finita. Cuando no hay degeneración (y suponiendo factibilidad), el método simplex se detiene en un número finito de iteraciones, ya sea con una solución básica factible óptima o bien, con la tesis de que el valor óptimo es no acotado. Cuando hay degeneración, es posible que haya ciclado en un circuito infinito, lo que significa que siempre se permanece en el mismo punto extremo aunque con distinta base. 2.5. Programación Lineal Entera En los problemas de programación lineal únicamente se exige a las variables la condición de no negatividad, pero esta suposición a veces, en la realidad, no es suficiente. Por ejemplo, si se habla de número de empleados asociados a un determinado puesto de trabajo, la variable debe de cumplir una condición adicional que es la de integridad, es decir, las variables de decisión han de tomar valores enteros. Definición 14 Un problema de programación lineal en el que todas las variables han de ser enteras se denomina problema de programación lineal entero puro. Ejemplo 3 Como ejemplo de problema entero puro, se puede dar el siguiente, conocido como problema de asignación: CAPÍTULO 2. PROGRAMACIÓN LINEAL 13 2.5. PROGRAMACIÓN LINEAL ENTERA Minimizar Pn i=1 Pn j=1 cijxij sujeto a Pn j=1 xij = 1 i= 1,2, . . . , n Pn i=1 xij = 1 j= 1,2, . . . , n xij ∈ {0,1}para todo i y j. Definición 15 Un problema de programación lineal en el que solamente algunas de las variables de decisión han de ser enteras se denomina problema de programación lineal entero mixto . Definición 16 El problema que se obtiene al omitir las restricciones de integridad de un problema de programación lineal se denomina problema entero relajado. Definición 17 Un poliedro P = {x∈Rn : Ax=b} se dice entero si todos sus puntos extremos son enteros. Definición 18 Una matriz entera A∈Mm×n se dice totalmente unimodular (TU) si el determinante de cualquier submatriz cuadrada de Aes igual a 0,1o−1. Teorema 13 Si Aes TU entonces aij = 0,1,−1∀i, j. Observación 1 La matriz de restricciones del problema de asignación es totalmente unimodular. Teorema 14 Si A∈Mm×n es TU , entonces P = {x∈Rn + : Ax≤b} es entero ∀b∈Zm . 2.5.1. Planos de corte Al no existir algoritmos eficientes para resolver problemas de programación lineal entera, se plantean métodos que buscan el óptimo resoviendo una serie de problemas lineales, conocidos como métodos de planos de corte. Considérese el siguiente problema entero puro: Minimizar ctx sujeto a Ax≥b x∈Zn + Un algoritmo general de plano cortante consta de los siguientes pasos (Luenberger, 1989): 1. Se resuelve el problema relajado. Sea x∗la solución óptima. 2. Si x∗∈Zn +,x∗es el óptimo del problema original y se ha finalizado. 3. En caso contrario, se añade al problema relajado una nueva restricción tal que sea satisfecha por toda solución entera del problema original, pero no por x∗ . Volver al paso 1. La forma en que se elijan las nuevas restricciones, determina la eficiencia del algoritmo. Para finalizar esta sección, se expone uno de estos métodos, conocido como método de ramificación y acotación. 14 CAPÍTULO 2. PROGRAMACIÓN LINEAL 2.5. PROGRAMACIÓN LINEAL ENTERA 2.5.1.1. Esquemas de ramificación y acotación Dado un problema de programación entera puro, se tiene el siguiente procedimiento para la búsqueda de soluciones enteras. Se llama: Ramificación : a la partición del espacio continuo del problema relajado ( P )en dos subproblemas también continuos. En esta partición se eliminan partes no factibles del problema relajado. Si el óptimo del problema relajado en la variable xi toma el valor x∗ i , entonces del problema ( P )se obtienen dos subproblemas ( P1, P2 ), introducciendo nuevas restricciones: el problema P1 , obtenido de ( P )al añadir la restricción xi≤ [ x∗ i ], y el problema P2, que se obtiene (P)junto a la restricción xi≥[x∗ i]+1. Se continúa ramificando hasta encontrar la solución entera óptima del problema original. Acotación : consiste en conseguir una enumeración implícita de las soluciones factibles sin necesidad de sondearlas todas explícitamente. Así, pues, no será necesario sondear ni ramificar un nodo cuando se den alguna de las siguientes casuísticas: •El subproblema es infactible. • El valor del óptimo del subproblema no es mejor que una solución encontrada previamente y que es factible para el problema original (está acotado). Ejemplo 4 Se considera el siguiente problema de programación lineal entero puro: Minimizar x1+ 2x2+ 3x3 sujeto a 2x1+ 2x2+ 2x3≥3 x1, x2, x3∈ {0,1} El procedimiento para resolver este problema con ramificación y acotación está ilustrado en la Figura 2.1. Se comienza por resolver el problema relajado correspondiente al problema original. El valor óptimo z0 de la función objetivo del problema P0 corresponde al valor mínimo de la función objetivo del problema original, es decir, no existe una solución factible con un valor mejor. Esto último se deduce del hecho de que el conjunto que contiene las soluciones del problema relajado también contiene todas las soluciones del problema original. Se toma P0 como el nodo inicio en el árbol. La solución de P0 no es entera, y por tanto, se divide la región factible en dos partes, fijando x2 = 0 y x2 = 1. Se comienza con x2 = 1, y a este problema se le llama P1, continuando de la misma manera, ramificando a partir de P1 , hasta que, como se observa en la figura, se encuentra una solución factible y entera correspondiente al problema P2. Cuando se resuelve el problema relajado P3se concluye que el valor objetivo es superior al ya obtenido en P2 , luego no se sigue ramificando este nodo. Por lo tanto, se han examinado todas las posibilidades con x2 = 1, por lo que se pasa a la siguiente rama, donde x2 = 0. Si se encontrase una solución factible entera con valor objetivo más bajo que el actual, esta solución sería la óptima. En el problema P4 se obtiene de nuevo una solución no entera con valor objetivo igual al del problema P1 . Ramificando, el problema P6 es infactible y el problema P5 proporciona una solución entera pero con valor objetivo superior al obtenido anteriormente en P2 ; por lo que se concluye finalmente que la calculada en P2es la solución óptima. CAPÍTULO 2. PROGRAMACIÓN LINEAL 15 3.1. DESCRIPCIÓN DEL PROBLEMA debido a que a veces la capacidad de las aulas informáticas es muy inferior al de las aulas en las que se imparte la teoría, lo que imposibilita que todos los alumnos de un mismo grupo dispongan de un ordenador propio. Este modelo, se ha simplificado obviando ese hecho, de manera que se ha supuesto que la capacidad de los laboratorios de informática es suficiente para albergar a todo el grupo. 3.1.5. Restricciones Al diseñar un horario para una entidad universitaria, se deben tener en cuenta muchos requerimientos diferentes. Si se pretende obtener a través del uso de la programación lineal, como es el caso del presente trabajo, al formular el problema existen dos tipos diferentes de restricciones (Havas, Olsson, Persson y Schierscher, 2013). Por un lado, están las denominadas Restricciones fuertes , cuyo objetivo es el de garantizar que el horario que se consiga sea válido, de manera que no se obtenga uno que sea infactible para llevar a la práctica. Por ejemplo, no tendría sentido el obtener un horario el cual refleje la impartición de clases de dos asignaturas obligatorias de un mismo grupo a la misma hora un mismo día, ya que sería algo infactible para los estudiantes pues no podrían asistir a ambas. Son, por tanto, restricciones que deben estar presentes en el diseño del horario de cualquier facultad. Por otro lado, se encuentran las llamadas Restricciones suaves , que son las que se encargan de que se satisfagan ciertas condiciones que se prefieren sobre otras; por ejemplo, evitar que se impartan clases los viernes por la tarde. Como quedó reflejado en el Capítulo 2, un problema de programación lineal consiste en maximizar o minimizar una expresión algebraica lineal, denominada función objetivo, satisfaciendo al mismo tiempo ciertas restricciones. Nótese, que en este problema particular dedicado a la obtención de un horario, como ocurre en muchos otros, no es necesaria la presencia de una función objetivo. En este caso, sólo se pretende establecer las restricciones correctas, de manera que se obtenga un horario factible, pero el fin buscado no es el de maximizar o minimizar ningún objetivo concreto. No obstante, dicha función objetivo puede ser creada con el fin de alcanzar ciertas preferencias colectivas, como se ha explicado en la sección 1.1.3y como se verá más detalladamente en el siguiente capítulo. A continuación, se exponen las restricciones generales del modelo, las cuales serán explicadas individualmente tras la formulación: Restricciones fuertes Solo debe haber una clase de teoría o práctica de informática en un mismo aula a la misma hora. Cada asignatura debe tener su correspondiente número de horas semanales, previamente establecido. El aula asignada ha de tener capacidad suficiente para albergar a todo el grupo. No deben coincidir asignaturas de un mismo grupo a la misma hora del mismo día, excepto en el caso de cuarto curso. Las clases de teoría serán impartidas en las aulas destinadas a ello, como en el caso de las prácticas informáticas. 22 CAPÍTULO 3. PLANTEAMIENTO DEL PROBLEMA DE HORARIOS 3.2. FORMULACIÓN Restricciones suaves No habrá más de una clase de teoría o práctica de laboratorio de una asignatura en un mismo día. Las asignaturas serán distribuidas a lo largo de la semana, excepto en el caso de prácticas informáticas, que si podrán impartirse en días consecutivos. Cada clase de teoría correspondiente a una misma asignatura se dará siempre en el mismo aula, de la misma manera que cada práctica de informática será impartida siempre en el mismo laboratorio. No hay clase los viernes por la tarde. No se imparten clases de cuarto curso en el horario de 14 : 30 a15 : 30. En la hora de 13 : 30 a14 : 30, sólo se impartirán asignaturas de cuarto curso. No se impartirán más de seis asignaturas de cuarto curso al día. No podrán coincidir más de dos asignaturas de cuarto en una misma franja horaria, y sólo lo harán aquellas que se dividen en dos grupos. Las asignaturas de grupos del mismo curso, se impartirán en las aulas seleccionadas para cada curso. 3.2. Formulación Para formular el modelo, se emplearán variables de decisión de tipo binario. Se trabajará con variables con determinados subíndices donde cada uno de ellos tomará elementos de un determinado conjunto previamente definido. Estos conjuntos serán: días de la semana, franjas horarias, asignaturas y aulas. De esta manera, la variable tomará el valor uno cuando una asignatura se imparta en un cierto día a una hora determinada y en un aula concreta; y devolverá el valor cero cuando esto no ocurra. 3.2.1. Modelo Se definen los conjuntos, variables de decisión y parámetros necesarios para poder formular el problema relativo a la obtención del horario del primer cuatrimestre del Grado en Matemáticas. El modelo correspondiente al horario del segundo cuatrimestre aparece recogido en el Apéndice A. Conjuntos D = { 1 , 2 , 3 , 4 , 5 } . Conjunto correspondiente a los días de la semana; donde 1 corresponde al lunes, 2al martes, 3al miércoles, 4al jueves y 5al viernes. H 1= { 1 , 2 , 3 } . Los elementos de este conjunto se identifican con las franjas horarias asociadas al horario de mañana; así, 1corresponde al período de tiempo comprendido entre 9:00 y 11:00, 2al relativo a las horas entre 11:30 y 13:30 y 3a la hora comprendida entre 13:30 y 14:30. H 2= { 4 , 5 , 6 } . Igual que el anterior, pero referente al horario de tarde. En este caso, 4corresponde a 14:30-15:30, 5a 15:30-17:30 y 6a 18:00-20:00. CAPÍTULO 3. PLANTEAMIENTO DEL PROBLEMA DE HORARIOS 23 3.2. FORMULACIÓN H = H 1 ∪H 2. Unión de los dos anteriores; conjunto formado por todas las franjas horarias. C1G1={ALG11, CI1, IN1, AB1, FI1}. Asignaturas del grupo 1de primer curso. C1G2={ALG12, CI2, IN2, AB2, FI2}. Asignaturas del grupo 2de primer curso. C1G3={ALG13, CI3, IN3, AB3, FI3}. Asignaturas del grupo 3de primer curso. C1G4={ALG14, CI4, IN4, AB4, FI4}. Asignaturas del grupo 4de primer curso. C1G5={ALG15, CI5, IN5, AB5, FI5}. Asignaturas del grupo 5de primer curso. C 2 G 1= {EPE 1 , DFV V 1 , ALG 21 , SFIL 1 , TOP 1 } . Asignaturas del grupo 1de segundo curso. C 2 G 2= {EPE 2 , DFV V 2 , ALG 22 , SFIL 2 , TOP 2 } . Asignaturas del grupo 2de segundo curso. C 2 G 3= {EPE 3 , DFV V 3 , ALG 23 , SFIL 3 , TOP 3 } . Asignaturas del grupo 3de segundo curso. C 3 G 1= {EA 1 , GL 1 , AED 1 , IE 1 , FV C 1 } . Asignaturas del grupo 1de tercer curso. C 3 G 2= {EA 2 , GL 2 , AED 2 , IE 2 , FV C 2 } . Asignaturas del grupo 2de tercer curso. C 3 G 3= {EA 3 , GL 3 , AED 3 , IE 3 , FV C 3 } . Asignaturas del grupo 3de tercer curso. C1=C1G1∪C1G2∪C1G3∪C1G4∪C1G5. Asignaturas de primer curso. C2=C2G1∪C2G2∪C2G3. Asignaturas de segundo curso. C3=C3G1∪C3G2∪C3G3. Asignaturas de tercer curso. C4={ACGA, ADF, AFEDP, ANED, CC, EDP1, EDP2, GAP1, GAP2, MIOP, TAN, V D}. Asignaturas de cuarto curso. C 43= {TAN, CC, EDP 1 } . Asignaturas de cuarto curso que serán impartidas en la franja horaria 3. F = {EDP 1 , EDP 2 , GAP 1 , GAP 2 , TAN} . Conjunto cuyas componentes corresponden a las únicas asignaturas de cuarto cuyo horario se permite que solape con otras materias de este mismo curso. GM = C 1 G 1 ∪C 1 G 2 ∪C 1 G 3 ∪C 1 G 4 ∪C 2 G 1 ∪C 2 G 2 ∪C 2 G 3 ∪C 3 G 1 ∪C 3 G 2. Conjunto formado por las asignaturas de primero, segundo y tercer curso que se impartirán en horario de mañana. GT = C 1 G 5 ∪C 3 G 3. Asignaturas de primero y tercero que tendrán horario de tarde. CF = {AB 5 , FI 5 , GL 3 , FV C 3 , TAN, CC, EDP 1 } . Asignaturas sin prácticas de informática que tendrán clases en días consecutivos. C = GM ∪GT ∪C 4. Conjunto formado por todas las asignaturas del primer cuatrimestre. AT = {EC 01 , EC 02 , EC 03 , EC 04 , EC 05 , EC 06 , EC 11 , EC 12 , EC 21 , EC 22 , H 1 . 11 , H1.13}. Aulas destinadas a la impartición de clases teóricas. AL = {LAB 1 , LAB 2 , LAB 3 , LAB 4 , LAB 5 , LAB 6 , CRAI 1 } . Laboratorios para la impartición de prácticas informáticas. 24 CAPÍTULO 3. PLANTEAMIENTO DEL PROBLEMA DE HORARIOS 3.2. FORMULACIÓN A=AT ∪AL. Conjunto formado por todas las aulas disponibles. A 1= {EC 01 , EC 02 , EC 03 , EC 04 , EC 06 } . Aulas destinadas a clases de teoría de primer curso. A 2= {EC 06 , EC 11 , EC 22 } . Aulas para la impartición de clases de teoría de segundo curso. A 3= {EC 05 , H 1 . 11 , H 1 . 13 } . Conjunto formado por las aulas de clases teóricas de tercer curso. A4={EC12, EC21}. Aulas destinadas a clases teóricas de cuarto curso. Parámetros NEc: Número de estudiantes matriculados en la asignatura c∈C. Ra: Capacidad del aula a∈A. NTc: Número semanal de clases de teoría de la asignatura c∈C. NLc: Número semanal de prácticas informáticas de la asignatura c∈C. Variables de decisión xd,h,c,a : Variable binaria, donde d∈D , h∈H , c∈C y a∈A . Tomará el valor 1si la asignatura c tiene clase de teoría el día d en el horario h y en el aula a ; siendo 0 en otro caso. zd,h,c,a : Variable binaria, con d∈D , h∈H , c∈C y a∈A . Valdrá 1si la asignatura c tiene práctica informática el día d el el horario h y en el laboratorio a ; y 0en otro caso. y 1 c,a : Variable binaria con c∈C y a∈AT . Tomará el valor 1si la asignatura c tiene clase teórica en el aula a; y valdrá 0en otro caso. y 2 c,a : Variable binaria donde c∈C y a∈AL . Su valor será 1si la asignatura c tiene práctica informática en el laboratorio a; y será 0en otro caso. A continuación, se formulan las restricciones, haciendo uso de los conjuntos, parámetros y variables de decisión definidas anteriormente: Restricciones xd,h,c,a ·NEc≤Ra, d ∈D, h ∈H, c ∈C, a ∈AT (1) zd,h,c,a ·NEc≤Ra, d ∈D, h ∈H, c ∈C, a ∈AL (2) Pd∈DPh∈HPa∈AT xd,h,c,a =NTc, c ∈C(3) Pd∈DPh∈HPa∈AL zd,h,c,a =NLc, c ∈C(4) Pc∈C(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H, a ∈A(5) CAPÍTULO 3. PLANTEAMIENTO DEL PROBLEMA DE HORARIOS 25 3.2. FORMULACIÓN Pc∈C1G1Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(6) Pc∈C1G2Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(7) Pc∈C1G3Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(8) Pc∈C1G4Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(9) Pc∈C1G5Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(10) Pc∈C2G1Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(11) Pc∈C2G2Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(12) Pc∈C2G3Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(13) Pc∈C3G1Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(14) Pc∈C3G2Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(15) Pc∈C3G3Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(16) Pd∈DPh∈H2Pa∈A(xd,h,c,a +zd,h,c,a) = 0, c ∈GM (17) Pd∈DPh∈H1Pa∈A(xd,h,c,a +zd,h,c,a) = 0, c ∈GT (18) Ph∈HPa∈A(x5,h,c,a +z5,h,c,a) = 0, c ∈GT (19) Ph∈HPa∈A(xd,h,c,a +zd,h,c,a)≤1, c ∈C(20) x1,4,AB5,EC02 = 1 (21) x2,4,AB5,EC02 = 1 (22) x3,4,F I5,EC02 = 1 (23) x4,4,F I5,EC02 = 1 (24) x1,4,GL3,H1.11 = 1 (25) x2,4,GL3,H1.11 = 1 (26) x3,4,F V C3,H1.11 = 1 (27) x4,4,F V C3,H1.11 = 1 (28) Pd∈DPa∈A(xd,3,c,a +zd,3,c,a)=0, c ∈C\C4 (29) 26 CAPÍTULO 3. PLANTEAMIENTO DEL PROBLEMA DE HORARIOS 3.2. FORMULACIÓN Pd∈DPa∈A(xd,4,c,a +zd,4,c,a) = 0, c ∈C4 (30) Pc∈CPa∈A(x3,3,c,a +z3,3,c,a) = 0,(31) x1,3,T AN,EC21 = 1 (32) x2,3,T AN,EC21 = 1 (33) x4,3,CC,EC21 = 1 (34) x5,3,CC,,EC21 = 1 (35) x1,3,EDP 1,EC12 = 1 (36) x2,3,EDP 1,EC12 = 1 (37) Pd∈DPh∈H(xd,h,c,a)−y1c,a ·NTc= 0, c ∈C, a ∈AT (38) Pd∈DPh∈H(zd,h,c,a)−y2c,a ·NLc= 0, c ∈C, a ∈AL (39) Pc∈CPh∈H2Pa∈A(x5,h,c,a +z5,h,c,a) = 0 (40) Pc∈C4Ph∈HPa∈A(xd,h,c,a +zd,h,c,a)≤6, d ∈D(41) Pd∈DPa∈A(xd,3,c,a +zd,3,c,a) = 0, c ∈C4\C43 (42) Pc∈C4Pa∈A(xd,h,c,a +zd,h,c,a)≤2, d ∈D, h ∈H\ {3}(43) Pc∈C43 Pa∈A(xd,3,c,a +zd,3,c,a)≤1, d ∈D\ {1,2}(44) Ph∈HPa∈A(xd,h,c,a +xd+1,h,c,a)≤1, d ∈D\ {5}, c ∈C\CF (45) Pd∈DPh∈HPa∈A\A1xd,h,c,a = 0, c ∈C1 (46) Pd∈DPh∈HPa∈A\A2xd,h,c,a = 0, c ∈C2 (47) Pd∈DPh∈HPa∈A\A3xd,h,c,a = 0, c ∈C3 (48) Pd∈DPh∈HPa∈A\A4xd,h,c,a = 0, c ∈C4 (49) Pc∈C4Pa∈A4xd,h,c,a ≥1, d ∈D, h ∈H1\ {3}(50) Pc∈C4Pa∈A4xd,h,c,a +Pc∈C4Pa∈AL zd,h,ca ≥1, d ∈D\ {5}, h ∈H2\ {4}(51) Pc∈C4\FPa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H\ {3,4}(52) Pd∈DPh∈H(xd,h,c,EC02 +xd,h,c,EC04 +xd,h,c,EC01)=0, c ∈C1G1 (53) CAPÍTULO 3. PLANTEAMIENTO DEL PROBLEMA DE HORARIOS 27 3.2. FORMULACIÓN Pd∈DPh∈Hxd,h,c,EC06 = 0, c ∈C2G1∪C2G3 (54) Pd∈DPh∈Hxd,h,c,EC11 = 0, c ∈C2G1 (55) Pd∈DPh∈H(xd,h,c,EC03 +xd,h,c,EC04)=0, c ∈C1G2 (56) Pd∈DPh∈H(xd,h,c,EC02 +xd,h,c,EC03 +xd,h,c,EC04)=0, c ∈C1G3 (57) Pd∈DPh∈H(xd,h,c,EC01 +xd,h,c,EC02)=0, c ∈C1G4 (58) Pd∈DPh∈Hxd,h,c,EC03 = 0, c ∈C1G5 (59) Pd∈DPh∈H(xd,h,c,H1.13 +xd,h,c,EC05)=0, c ∈C3G2 (60) Explicación de las restricciones (1) La capacidad de las aulas de teoría debe ser, al menos, suficiente para acoger a todo un grupo. (2) Los laboratorios de informática deben tener capacidad suficiente para albergar a todo el grupo. (3) Cada asignatura debe tener, a la semana, el número de clases de teoría requerido. (4) Cada asignatura debe tener, a la semana, el número de prácticas de informática requerido. (5) En cada aula de teoría y laboratorio de informática, a lo sumo, se impartirá cada día una clase en cada una de las franjas horarias. (6) Las asignaturas del grupo 1de primer curso no coinciden entre sí. (7) Las asignaturas del grupo 2de primer curso no coinciden entre ellas. (8) Las asignaturas del grupo 3de primer curso no coinciden entre sí. (9) Las asignaturas del grupo 4de primer curso no coinciden entre sí. (10) Las asignaturas del grupo 5de primer curso no solapan entre ellas. (11) Las asignaturas del grupo 1de segundo curso no coinciden entre sí. (12) Las asignaturas del grupo 2de segundo curso no coinciden entre sí. (13) Las asignaturas del grupo 3de segundo curso no coinciden entre ellas. (14) Las asignaturas del grupo 1de tercer curso no solapan entre sí. (15) Las asignaturas del grupo 2de tercer curso no coinciden entre ellas. (16) Las asignaturas del grupo 3de tercer curso no coinciden entre sí. (17) Los grupos incluidos en el conjunto GM sólo tienen clase por la mañana. (18) Los grupos incluidos en el conjunto GT sólo tienen clase por la tarde. (19) Los grupos del conjunto GT no tienen clases los viernes. 28 CAPÍTULO 3. PLANTEAMIENTO DEL PROBLEMA DE HORARIOS 3.2. FORMULACIÓN (20) A lo más, habrá una clase al día por asignatura, ya sea teoría o prácticas informáticas. (21) La asignatura Álgebra básica del grupo 5de primer curso, se impartirá los lunes en la cuarta franja horaria y en el aula EC02. (22) La asignatura Álgebra básica del grupo 5de primer curso, se impartirá los martes en la cuarta franja horaria y en el aula EC02. (23) La asignatura Física I del grupo 5de primer curso, se impartirá los miércoles en la cuarta franja horaria y en el aula EC02. (24) La asignatura Física I del grupo 5de primer curso, se impartirá los jueves en la cuarta franja horaria y en el aula EC02. (25) La asignatura Geometría local de curvas y superficies del grupo 3de tercer curso, se impartirá los lunes en la cuarta franja horaria y en el aula H1.11. (26) La asignatura Geometría local de curvas y superficies del grupo 3de tercer curso, se impartirá los martes en la cuarta franja horaria y en el aula H1.11. (27) La asignatura Funciones de una variable compleja del grupo 3de tercer curso, se impartirá los lunes en la cuarta franja horaria y en el aula H1.11. (28) La asignatura Funciones de una variable compleja del grupo 3de tercer curso, se impartirá los jueves en la cuarta franja horaria y en el aula H1.11. (29) En la franja horaria 3, sólo se imparten asignaturas de cuarto curso. (30) No se imparten asignaturas de cuarto curso en la franja horaria 4. (31) No se imparten clases los miércoles en la franja horaria 3. (32) La asignatura Teoría analítica de números , de cuarto curso, se impartirá los lunes en la franja horaria 3y en el aula EC21. (33) La asignatura Teoría analítica de números , de cuarto curso, se impartirá los martes en la franja horaria 3y en el aula EC21. (34) La asignatura Ciencias de la computación , de cuarto curso, se impartirá los jueves en la franja horaria 3y en el aula EC21. (35) La asignatura Ciencias de la computación , de cuarto curso, se impartirá los viernes en la franja horaria 3y en el aula EC21. (36) El grupo 1de la asignatura Ecuaciones en derivadas parciales , de cuarto curso, tendrá una clase los lunes en la franja horaria 3y en el aula EC12. (37) El grupo 1de la asignatura Ecuaciones en derivadas parciales , de cuarto curso, tendrá una clase los martes en la franja horaria 3y en el aula EC12. (38) Las clases teóricas de cada asignatura de un mismo grupo, se impartirán siempre en el mismo aula. (39) Las prácticas de informática de cada asignatura de un mismo grupo, serán siempre en el mismo laboratirio. (40) No se impartirán clases los viernes por la tarde. (41) Cada día, no habrá más de seis clases de cuarto curso. CAPÍTULO 3. PLANTEAMIENTO DEL PROBLEMA DE HORARIOS 29 3.2. FORMULACIÓN (42) En la franja horaria 3, sólo se impartirán las asignaturas de cuarto fijadas en las restricciones (32)-(37). (43) En cada franja horaria no habrá más de dos clases de cuarto curso simultáneamente. (44) En la franja horaria 3, sólo coincidirán las asignaturas de cuarto fijadas en las restricciones (32)-(37), pero ninguna otras de este curso. (45) Las clases de teoría correspondientes a una misma asignatura serán repartidas a lo largo de la semana. Sólo las asignaturas fijadas en estas restricciones tendrán clases teóricas en días consecutivos. (46) Las clases de primero se impartirán en las aulas seleccionadas para este curso. (47) Las asignaturas de segundo se impartirán en las aulas seleccionadas para este curso. (48) Las clases de tercero se darán en las aulas seleccionadas para este curso. (49) Las asignaturas de cuarto se impartirán unicamente en las aulas seleccionadas para este curso. (50) Las clases de teoría relativas a asignaturas de cuarto impartidas en horario de mañana estarán distribuidas. En éstas franjas horarias, salvo en la tres, se impartirá al menos una clase teórica correspondiente a este curso cada día. (51) Ánalogo a la anterior para el horario de tarde. De lunes a jueves, en las franjas horarias 5y6, habrá al menos una clase de teoría o práctica informática de cuarto. (52) Las clases de asignaturas de cuarto que no pertenecen al conjunto F, no conincidirán unas con otras. (53) No habrá clases de teoría del grupo 1de primer curso en las aulas EC 01, EC 02 ni EC04. (54) Los grupos 1y3del segundo curso no tendrán clases teóricas en el aula EC06. (55) El grupo 2de segundo no recibirá clases teóricas en el EC11. (56) No habrá clases de teoría del grupo 2de primer curso en las aulas EC03 YEC04. (57) El grupo 3de primer curso no tendrá clases de teoría en las aulas EC 02 , EC 03 y EC04. (58) No habrá clases teóricas del grupo 4de primero en las aulas EC01 yEC02. (59) El grupo 5de primero no recibirá clases de teoría en el aula EC03. (60) El grupo 2de tercer curso no recibirá clases teóricas en el aula H 1 . 13 ni en el aula EC05. 30 CAPÍTULO 3. PLANTEAMIENTO DEL PROBLEMA DE HORARIOS 3.2. FORMULACIÓN 3.2.2. Datos En este apartado, se presentan, en varias tablas, los datos correspondientes a los parámetros definidos en la sección anterior, referidos al primer cuatrimestre, como son: número de alumnos matriculados en cada asignatura, número de clases de teoría y prácticas informáticas a la semana por asignatura y capacidad de las aulas. De manera análoga, se puede obtener el horario relativo al segundo cuatrimestre. Para ello, en lo referente a los parámetros basta con cambiar el valor de los correspondientes al número de matrículas y número de clases a la semana, pues la capacidad de las aulas seguirá siendo la misma. Estos datos se encuentran recogidos en el Apéndice A. A continuación se presentan cuatro tablas, cada una de las cuales recoge el número de matrículas en las asignaturas de primero, segundo, tercero y cuarto, respectivamente: Código de asignaturas de primer curso ALG1 CI IN AB FI Matrículas en grupo 1 50 50 50 50 50 Matrículas en grupo 2 50 50 50 50 50 Matrículas en grupo 3 50 50 50 50 50 Matrículas en grupo 4 65 50 50 60 65 Matrículas en grupo 5 55 55 55 65 67 Cuadro 3.1: Estudiantes matriculados en asignaturas de primero en el primer cuatrimestre Código de asignaturas de segundo curso EPE DFVV ALG2 SFIL TOP Matrículas en grupo 1 45 45 50 47 45 Matrículas en grupo 2 30 30 30 30 30 Matrículas en grupo 3 45 50 50 42 45 Cuadro 3.2: Estudiantes matriculados en asignaturas de segundo en el primer cuatrimestre Código de asignaturas de tercer curso EA GL AED IE FVC Matrículas en grupo 1 50 42 45 50 42 Matrículas en grupo 2 40 38 40 39 32 Matrículas en grupo 3 35 38 40 38 40 Cuadro 3.3: Estudiantes matriculados en asignaturas de tercero en el primer cuatrimestre CAPÍTULO 3. PLANTEAMIENTO DEL PROBLEMA DE HORARIOS 31 4.1. HORARIOS OBTENIDOS Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 EPE3 TOP3 ALG23 TOP3 DFVV3 10 : 00 −10 : 30 EC11 EC11 EC11 EC11 EC11 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 SFIL3 DFVV3 EPE3 ALG23 12 : 30 −13 : 00 EC11 EC11 EC11 EC11 13 : 00 −13 : 30 SFIL3 13 : 30 −14 : 00 EC11 14 : 00 −14 : 30 Cuadro 4.8: Horario del grupo 3 de segundo curso para el primer cuatrimestre Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 FVC1 EA1 FVC1 AED1 GL1 10 : 00 −10 : 30 H1.13 H1.13 H1.13 H1.13 H1.13 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 AED1 IE1 IE1 EA1 12 : 30 −13 : 00 H1.13 H1.13 H1.13 H1.13 13 : 00 −13 : 30 GL1 13 : 30 −14 : 00 H1.13 14 : 00 −14 : 30 Cuadro 4.9: Horario del grupo 1 de tercer curso para el primer cuatrimestre Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 GL2 AED2 EA2 AED2 IE2 10 : 00 −10 : 30 H1.11 H1.11 H1.11 H1.11 H1.11 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 FVC2 IE2 FVC2 EA2 12 : 30 −13 : 00 H1.11 H1.11 H1.11 H1.11 13 : 00 −13 : 30 GL2 13 : 30 −14 : 00 H1.11 14 : 00 −14 : 30 Cuadro 4.10: Horario del grupo 2 de tercer curso para el primer cuatrimestre 38 CAPÍTULO 4. RESULTADOS Y ANÁLISIS 4.1. HORARIOS OBTENIDOS Lunes Martes Miércoles Jueves Viernes 14 : 30 −15 : 00 GL3 GL3 FVC3 FVC3 15 : 00 −15 : 30 H1.11 H1.11 H1.11 H1.11 15 : 30 −16 : 00 16 : 00 −16 : 30 IE3 AED3 EA3 IE3 16 : 30 −17 : 00 H1.11 H1.11 H1.11 H1.11 17 : 00 −17 : 30 17 : 30 −18 : 00 18 : 00 −18 : 30 18 : 30 −19 : 00 EA3 FVC3 GL3 AED3 19 : 00 −19 : 30 H1.11 H1.11 H1.11 H1.11 19 : 30 −20 : 00 Cuadro 4.11: Horario del grupo 3 de tercer curso para el primer cuatrimestre Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 GAP2 9 : 30 −10 : 00 ACGA EDP2 LAB1 AFEDP GAP1 10 : 00 −10 : 30 EC12 EC12 TAN EC12 EC12 10 : 30 −11 : 00 EC21 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 VD GAP2 VD MIOP 12 : 30 −13 : 00 EC12 EC12 ACGA EC12 EC12 13 : 00 −13 : 30 EC12 13 : 30 −14 : 00 EDP1 TAN EDP1 TAN GAP1 CC CC 14 : 00 −14 : 30 EC12 EC21 EC12 EC21 CRAI1 EC21 EC21 14 : 30 −15 : 00 15 : 00 −15 : 30 15 : 30 −16 : 00 16 : 00 −16 : 30 ADF MIOP EDP1 ADF 16 : 30 −17 : 00 EC12 CRAI1 EC12 EC12 17 : 00 −17 : 30 17 : 30 −18 : 00 18 : 00 −18 : 30 ANED 18 : 30 −19 : 00 AFEDP ANED CC CRAI1 19 : 00 −19 : 30 EC12 EC12 EC21 EDP2 19 : 30 −20 : 00 EC12 Cuadro 4.12: Horario de cuarto curso para el primer cuatrimestre Una vez obtenidos los horarios, se observa que son horarios factibles, en el sentido de que se satisfacen las restricciones fuertes impuestas en la formulación del modelo. De esta manera, se tiene que asignaturas de un mismo grupo no coinciden entre sí a la misma hora un mismo día, y a cada una de ellas se le ha asociado un aula con suficiente capacidad para albergar a todo el grupo. Del mismo modo, se cumplen además todas las restricciones suaves impuestas en el CAPÍTULO 4. RESULTADOS Y ANÁLISIS 39 4.2. ASPECTOS COMPUTACIONALES DEL MODELO modelado, las cuales obedecen a las preferencias tanto de alumnos como de personal docente, por ejemplo, la no impartición de clases los viernes por la tarde, así como la no existencia de clases de cuarto curso en la hora comprendida entre las 14:30 y las 15:30. Se concluye por tanto la eficacia del modelo para la obtención de los horarios requeridos. 4.2. Aspectos computacionales del modelo El modelo creado ha sido validado por medio de ‘AMPL for courses’, que es la versión de estudiante correspondiente a este programa. El equipo utilizado para ello ha sido Hp Pavilion Power 15-cb003nq, de procesador i7-7700HQ de 4 núcleos y 8 GB de memoria RAM. Tras la ejecución del modelo en AMPL, se obtiene que el número de variables es 11037 y el de restricciones totales 1317, de las cuales 279 son de igualdad y 1038 de desigualdad. El tiempo de ejecución es de 1.08 segundos. 4.3. Análisis de sensibilidad En el Capítulo 2, ya se esbozó una idea del concepto de análisis de sensibilidad en programación lineal, también conocido como análisis de post optimalidad (Bazaraa, 2012), explicando que se trata del estudio de escenarios del tipo “qué ocurriría si”. El objetivo de este tipo de análisis consiste en la observación de los nuevos resultados que se obtendrían del modelo formulado si ahora se introduce una variación, pequeña o considerable, en las restricciones, variables o en los parámetros dados. El interés de esto radica en que la solución óptima de un problema de programación lineal, en cierto modo, depende completamente de los datos del problema a modelar. Cabe notar que, en el caso de un problema de horarios como el que se trata en esta memoria, si bien se pueden estudiar, por ejemplo, los nuevos resultados variando o eliminando ciertas restricciones de la formulación, ésto se hará siempre sobre las restricciones suaves, pues el caso de ejecutar los cambios sobre las restricciones fuertes puede conducir a la obtención de un horario infactible, o bien no se alcanzaría solución óptima. A continuación, se pretende, mediante un análisis de este tipo, comparar la influencia que tendrá en el resultado la eliminación de una determinada restricción. Por ejemplo, se pretende observar si el modelo producirá un resultado muy diferente al ya obtenido en el caso de que se quite de la formulación la restricción (45), que garantiza que la impartición de clases de teoría estén distribuidas a lo largo de la semana, evitando así que una misma asignatura se dé dos días consecutivos. Tras la eliminación de dicha restricción, se toma como ejemplo el grupo 2 de segundo curso, y se observa el resultado, siendo éste el que sigue: 40 CAPÍTULO 4. RESULTADOS Y ANÁLISIS 4.3. ANÁLISIS DE SENSIBILIDAD Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 ALG22 DFVV2 SFIL2 EPE2 TOP2 10 : 00 −10 : 30 EC06 EC06 EC06 EC06 EC06 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 DFVV2 ALG22 TOP2 SFIL2 12 : 30 −13 : 00 EC06 EC06 EC06 EC06 13 : 00 −13 : 30 EPE2 13 : 30 −14 : 00 EC06 14 : 00 −14 : 30 Cuadro 4.13: Horario del grupo 2 de segundo curso tras análisis de post optimalidad Se observa que la distribución de asignaturas es muy diferente a la del horario obtenido en el Cuadro 4.7. En este nuevo horario, exceptuando la asignatura Series de funciones e integral de Lebesgue (SFIL), el resto de ellas se imparten todas en días consecutivos. De hecho, aunque en horario inverso, tanto los lunes como los martes se darían las mismas asignaturas. Por tanto, en el horario obtenido del modelo original, expuesto en el cuadro 4.7, se logra una distribución más heterogénea de asignaturas durante la semana. Así, aunque la no inclusión de dicha restricción en la formulación sigue proporcionando soluciones óptimas al problema que se trata, como la del cuadro anterior, se concluye que es preferible introducirla para conseguir un horario con una mejor organización de las clases. Análogamente al estudio anterior, se puede realizar un análisis semejante sobre la función objetivo. Como ya se comentó en el capítulo anterior, en el problema que se ha formulado, la finalidad de obtener un horario factible no implica la necesidad de maximizar o minimizar un cierto objetivo, pues basta con la verificación de ciertas restricciones como las expuestas en este trabajo. No obstante, en esta sección se introduce una función objetivo a la formulación descrita en el capítulo anterior, la cual se pretende minimizar, para mostrar así como varía el horario que resulta de incluir en esta función las preferencias, supuestas, de profesores y/o estudiantes en cuanto a la impartición de las clases. La manera en que estas preferencias pueden ser incluidas en la función objetivo, consiste en asignar coeficientes elevados, que se denominan pesos, a las variables de decisión cuyos subíndices recogen lo contrario a las preferencias que se pretenden obtener. Por ejemplo, si se supone que en la formulación no se ha incluido la restricción (40), que garantiza la no impartición de clases los viernes por la tarde, ésto podría haberse manifestado asociando un coeficiente elevado a la variable x5,h,c,a , donde los subíndices h,c y a recorren los conjuntos correspondientes a horas, asignaturas y aulas, respectivamente. De esta manera, las variables que no se incluyan en la función objetivo se considera que tienen peso cero, de forma que la elección de estas variables produce una solución óptima más efectiva que la minimización de una variable con un coeficiente elevado, obteniendo entonces, siempre que sea posible, la preferencia deseada. Obsérvese que en los horarios obtenidos para los grupos 1 y 2 de tercer curso, véase los cuadros 4.9 y 4.10, la asignatura Geometría Local de curvas y superficies (GL) se CAPÍTULO 4. RESULTADOS Y ANÁLISIS 41 4.3. ANÁLISIS DE SENSIBILIDAD imparte los miércoles en ambos grupos. Se supone ahora, como ejemplo, que los profesores encargados de la docencia de dicha asignatura en los citados grupos prefieren que ésta se desarrolle cualquiera del resto de días, pero no los miércoles. Entonces, puede considerarse la siguiente función objetivo: Minimizar f=Ph∈HPa∈A15 ·(x3,h,GL1,a +x3,h,GL2,a) Obsérvese que la asignación de peso 15 a dichas variables de decisión, contribuye a que no sean incluídas en la solución óptima. El nuevo horario obtenido para los grupos de tercero es el siguiente: Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 IE1 GL1 EA1 FVC1 GL1 10 : 00 −10 : 30 EC05 H1.13 H1.13 EC05 H1.13 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 FVC1 AED1 AED1 EA11 12 : 30 −13 : 00 EC05 EC05 EC05 H1.13 13 : 00 −13 : 30 IE1 13 : 30 −14 : 00 EC05 14 : 00 −14 : 30 Cuadro 4.14: Horario del grupo 1 de tercer curso tras análisis de post optimalidad Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 FVC2 AED2 IE2 AED2 IE2 10 : 00 −10 : 30 H1.11 H1.11 H1.11 H1.11 H1.11 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 GL2 EA2 EA2 GL2 12 : 30 −13 : 00 H1.11 H1.11 H1.11 H1.11 13 : 00 −13 : 30 FVC2 13 : 30 −14 : 00 H1.11 14 : 00 −14 : 30 Cuadro 4.15: Horario del grupo 2 de tercer curso tras análisis de post optimalidad Como se observa en los cuadros anteriores, 4.14 y 4.15, tras introducir la anterior función objetivo en la formulación del modelo, la asignatura GL no se imparte los miércoles en ninguno de los dos grupos, alcanzando así el nuevo requerimiento deseado. No obstante, el modelo sigue verificando todas las restricciones impuestas en su formulación; observando de esta manera la utilidad de dicha función objetivo para la inclusión de ciertas preferencias en el resultado que se obtiene. 42 CAPÍTULO 4. RESULTADOS Y ANÁLISIS 4.4. COMPARATIVA CON EL HORARIO REAL DEL CURSO 2019/2020 4.4. Comparativa con el horario real del curso 2019/2020 El objetivo de este trabajo, ha sido la creación de un modelo de programación lineal entera capaz de obtener un horario semejante, para el primer cuatrimestre, al del Grado en Matemáticas del curso 2019/2020 de la Facultad de Matemáticas de la Universidad de Sevilla. Se realiza, a continuación, la comparativa entre los horarios vigentes de algunos grupos, tomados de la página web de la Facultad de Matemáticas https://matematicas.us.es, y los obtenidos mediante este trabajo, asegurando la eficacia del modelo formulado. En el primer cuatrimestre del curso 2019/2020, el horario del grupo 1 de primer curso es el que sigue: Figura 4.1: Horario real del grupo A de primero para el primer cuatrimestre del curso 2019/2020 El horario equivalente al anterior, obtenido mediante el modelo, corresponde al expuesto en el cuadro 4.1. Cabe destacar el hecho de que mientras en este trabajo los grupos se han enumerado, en el horario vigente de la Facultad de Matemáticas se han designado por letras. Así, por ejemplo, grupo 1 de primer curso, en la figura anterior se ha llamado grupo A de primer curso. Además, respecto al código de las asignaturas, en el modelo creado se le ha añadido un último dígito a cada una de ellas referente al grupo en el que se imparten. Se observa que ambos horarios comparten una estructura común. En cada uno de ellos las franjas horarias son las mismas, todas las asignaturas se imparten en un mismo aula, excepto las prácticas de informática que se llevan a cabo en el correspondiente laboratorio destinado a ellas. Además, en los dos horarios las asignaturas están extendidas a lo largo de la semana, en el sentido de que no se imparte una misma asignatura dos días consecutivos. Por tanto, la única diferencia entre ambos radica en los días en los que se dará cada asignatura así como en el aula en el que serán impartidas; mientras en el curso 2019/2020 CAPÍTULO 4. RESULTADOS Y ANÁLISIS 43 4.4. COMPARATIVA CON EL HORARIO REAL DEL CURSO 2019/2020 el grupo 1 de primer curso recibiría sus clases en el aula EC01, según el modelo creado, éstas serían impartidas en el aula EC03. Para observar las similitudes y diferencias entre ambos horarios, se compara también el correspondiente a cuarto curso. El horario asociado a cuarto en el curso 2019/2020 es el siguiente: Figura 4.2: Horario real de cuarto para el primer cuatrimestre del curso 2019/2020 El horario para cuarto obtenido a través del modelo es el representado en el Cuadro 4.12. Al igual que ocurre en el caso de primero, en el horario de la Facultad de Matemáticas, se ha optado de nuevo por diferenciar los grupos de asignaturas de cuarto mediante letras. Así, en asignaturas divididas en dos grupos, como Ecuaciones en derivadas parciales (EDP), éstos se han llamado EDP(A) y EDP(B), mientras que en el modelo diseñado en este trabajo se han designado por EDP1 y EDP2. Lo mismo ocurre para el caso de la asignatura Geometría Aplicada (GAP). En ambos, las franjas horarias son las mismas, además de compartir la característica de la no impartición de clases los viernes por la tarde. En cuando a las diferencias, se observa que en el horario vigente, aparte de las asignaturas impartidas en la hora comprendida entre las 13:30 y las 14:30, las asignaturas ACGA y GAP(B) tienen ambas clase de teoría en la misma franja horaria, los lunes entre las 11:30 y las 13:30. Por el contrario, en el 44 CAPÍTULO 4. RESULTADOS Y ANÁLISIS 4.5. CONCLUSIONES Y LÍNEAS FUTURAS DE TRABAJO modelo se ha impuesto la condición de que, exceptuando las clases de las asignaturas EDP1 y TAN, impartidas de 13:30 a 14:30, sólo coincidan entre sí a la misma hora de un mismo día, en el caso de ser necesario, una clase de teoría con una de prácticas informáticas, pero no dos clases teóricas a la vez. Asimismo, en el horario actual sólo se considera para la impartición de clases teóricas el aula EC21, excepto para las clases de EDP(B) de las 13:30, que son en el aula H1.13. Por su parte, en el modelo también se ha considerado disponible para cualquier clase de teoría de este curso el aula EC12. Para los demás grupos no comentados en esta comparativa, como son el resto de grupos de primero, de segundo y tercero, las diferencias y similitudes entre ambos horarios son las mismas que las expuestas en el caso del grupo 1 de primer curso, siempre y cuando se obvie la coordinación dentro de un mismo grupo del Grado en Matemáticas con alguno de los dobles grados impartidos en la Facultad de Matemáticas de Sevilla, pudiéndose ver el horario, en estos casos, considerablemente alterado respecto al obtenido en este trabajo, debido al ajuste que debe de hacerse para coordinar las asignaturas de matemáticas con las de la Facultad de Física que se imparten en estos cursos. Por consiguiente, se puede afirmar la notable semejanza entre la estructura del horario utilizado por la facultad en el curso 2019/2020 y la del creado mediante este modelo de programación entera. 4.5. Conclusiones y líneas futuras de trabajo El modelo de programación lineal entera creado satisface todas las restricciones fuertes formuladas en el Capítulo 3, por lo que es un horario factible de llevar a la práctica. Asimismo, es eficaz en el sentido de que también se verifican todos los requerimientos (restricciones suaves) impuestas por la facultad, por lo que se ha conseguido un horario similar al utilizado por la Facultad de Matemáticas de Sevilla. Los datos que han sido utilizados para validar el modelo son arbitrarios, a excepción de la capacidad de las aulas que han sido tomadas de la web de la facultad. No obstante, en otros cursos, el modelo podría ser utulizado por el centro para elaborar el horario del Grado en Matemáticas, aunque para ésto sería necesario conocer previamente el número de alumnos matriculados en cada una de las asignaturas. En este sentido, una posible ampliación del modelo consiste en introducir nuevas variables de decisión y parámetros de manera que se obtenga un horario sin necesidad de conocer previamente el número de matrículas por asignatura; por ejemplo, fijando la cantidad máxima de alumnos que podrá haber en cada grupo, de manera que entre cada uno de ellos no haya una diferencia de ± 15 alumnos, siendo éste un criterio utilizado por la facultad. Además, se podrían también incorporar nuevos conjuntos y variables binarias para obtener los horarios de las dobles titulaciones de manera simultánea al del Grado en Matemáticas. 4.6. Código AMPL Para terminar el presente capítulo, se presenta la formulación del modelo en código del lenguaje AMPL, cuyas características principales se expusieron en el Capítulo 2, desarrolladas más ampliamente en (P.L. Luque-Calvo, 2002). Se presentan en primer lugar los códigos correspondientes a los ficheros de extensión ‘.mod’ y ‘.dat’. En el primero de CAPÍTULO 4. RESULTADOS Y ANÁLISIS 45 4.6. CÓDIGO AMPL ellos se recogen los conjuntos, parámetros, variables de decisión y restricciones escritas en lenguaje AMPL; además de la función objetivo introducida en el análisis de sensibilidad. En el segundo, aparecen los datos indicados en las tablas del capítulo anterior. También se adjunta el fichero de comandos AMPL con extensión ‘.run’ para obtener la solución del problema planteado. Como optimizador para resolver el problema de programación lineal entera se ha usado CPLEX. Cabe destacar, que al escribir el código se han omitido las tildes para evitar problemas con la escritura en lenguaje AMPL. 4.6.1. Código del fichero de extensión ‘.mod’ # CONJUNTOS: set D; # Conjunto de dias de la semana set H1; # Conjunto de franjas horarias de mañana set H2; # Conjunto de franjas horarias de tarde set H := H1 union H2; # Conjunto de todas las franjas horarias set C1G1; # Asignaturas del grupo 1 del primer curso set C1G2; # Asignaturas del grupo 2 del primer curso set C1G3; # Asignaturas del grupo 3 del primer curso set C1G4; # Asignaturas del grupo 4 del primer curso set C1G5; # Asignaturas del grupo 5 del primer curso set C2G1; # Asignaturas del grupo 1 del segundo curso set C2G2; # Asignaturas del grupo 2 del segundo curso set C2G3; # Asignaturas del grupo 3 del tercer curso set C3G1; # Asignaturas del grupo 1 del tercer curso set C3G2; # Asignaturas del grupo 2 del tercer curso set C3G3; # Asignaturas del grupo 3 del tercer curso set C1 := C1G1 union C1G2 union C1G3 union C1G4 union C1G5; set C2 := C2G1 union C2G2 union C2G3; set C3 := C3G1 union C3G2 union C3G3; set C4; # Asignaturas de cuarto curso set C43; # Asignaturas de cuarto en la franja horaria 3 set F; # Asignaturas de cuarto que pueden solapar con otras de este mismo curso set GM := C1G1 union C1G2 union C1G3 union C1G4 union C2G1 union C2G2 union C2G3 union C3G1 union C3G2; # Grupos cuyas clases se impartiran en horario de mañana set GT := C1G5 union C3G3; # Grupos cuyas asignaturas se impartiran en horario de tarde set CF; # Asignaturas con clases consecutivas set C := GM union GT union C4; # Todos los grupos de todos los cursos set AT; # Aulas para las clases teorico-practicas set AL; # Laboratorios set A := AT union AL; # Todas las aulas disponibles set A1; # Aulas para clases de teoria de primero. set A2; # Aulas destinadas a clases teoricas de segundo. 46 CAPÍTULO 4. RESULTADOS Y ANÁLISIS 4.6. CÓDIGO AMPL set A3; # Aulas para la imparticion de clases teoricas de tercero. set A4; # Aulas para clases de teoria de cuarto. # PARAMETROS: param NE{C}; # Numero de estudiantes matriculados en la asignatura c de C param R{A}; # Capacidad del aula param NT{C}; # Numero de clases teorico-practicas semanales de la asignatura # c de C param NL{C}; # Numero de clases de laboratorio semanales de la asignatura c de C # VARIABLES DE DECISION: var x{D,H,C,A} binary; # 1 si la asignatura c se imparte en la hora h # el dia c en el aula a; 0 en cc. var z{D,H,C,A} binary; # 1 si la asignatura c tiene laboratorio en la hora h # el dia c en el aula a; 0 en cc var y1{C,AT} binary; # 1 si la asignatura c se imparte en el aula a; 0 en cc var y2{C,AL} binary; # 1 si la asignatura c se imparte en el laboratorio a; 0 en cc. # RESTRICCIONES: subject to restriccion1{d in D,h in H,c in C,a in AT}: x[d,h,c,a]*NE[c]<=R[a]; # El aula debe tener capacidad para todo el grupo restriccion2{d in D,h in H,c in C,a in AL}: z[d,h,c,a]*NE[c]<=R[a]; # El laboratorio debe tener capacidad para todo el grupo restriccion3{c in C}: sum{d in D,h in H,a in AT}x[d,h,c,a]=NT[c]; # Cada asignatura debe tener a # la semana el numero de clases teorico-practicas requerido. restriccion4{c in C}: sum{d in D,h in H,a in AL}(z[d,h,c,a])=NL[c]; # Cada asignatura debe tener a la semana el numero de clases #de laboratorio requerido. restriccion5{d in D,h in H,a in A}: sum{c in C}(x[d,h,c,a]+z[d,h,c,a])<=1; # En cada aula/laboratorio, solo se dara # una clase en un dia y franja horarias dadas. # Las siguientes restricciones imponen que no coincidan asignaturas de un mismo # grupo a la misma hora, exeptuando cuarto curso: CAPÍTULO 4. RESULTADOS Y ANÁLISIS 47 4.6. CÓDIGO AMPL AED1 45 IE1 50 FVC1 42 EA2 40 GL2 38 AED2 40 IE2 39 FVC2 32 EA3 35 GL3 38 AED3 40 IE3 38 FVC3 40 ACGA 20 ADF 20 AFEDP 55 ANED 55 CC 15 EDP1 30 EDP2 28 GAP1 35 GAP2 30 MIOP 50 TAN 40 VD 20 ; param NT := ALG11 2 CI1 2 IN1 0 AB1 2 FI1 2 ALG12 2 CI2 2 IN2 0 AB2 2 FI2 2 ALG13 2 CI3 2 IN3 0 AB3 2 FI3 2 ALG14 2 CI4 2 IN4 0 AB4 2 FI4 2 ALG15 2 54 CAPÍTULO 4. RESULTADOS Y ANÁLISIS 4.6. CÓDIGO AMPL CI5 2 IN5 0 AB5 3 FI5 3 EPE1 2 DFVV1 2 ALG21 2 SFIL1 2 TOP1 2 EPE2 2 DFVV2 2 ALG22 2 SFIL2 2 TOP2 2 EPE3 2 DFVV3 2 ALG23 2 SFIL3 2 TOP3 2 EA1 2 GL1 2 AED1 2 IE1 2 FVC1 2 EA2 2 GL2 2 AED2 2 IE2 2 FVC2 2 EA3 2 GL3 3 AED3 2 IE3 2 FVC3 3 ACGA 2 ADF 2 AFEDP 2 ANED 1 CC 3 EDP1 3 EDP2 2 GAP1 1 GAP2 1 MIOP 1 TAN 3 VD 2 ; CAPÍTULO 4. RESULTADOS Y ANÁLISIS 55 4.6. CÓDIGO AMPL param NL := ALG11 0 CI1 0 IN1 2 AB1 0 FI1 0 ALG12 0 CI2 0 IN2 2 AB2 0 FI2 0 ALG13 0 CI3 0 IN3 2 AB3 0 FI3 0 ALG14 0 CI4 0 IN4 2 AB4 0 FI4 0 ALG15 0 CI5 0 IN5 2 AB5 0 FI5 0 EPE1 0 DFVV1 0 ALG21 0 SFIL1 0 TOP1 0 EPE2 0 DFVV2 0 ALG22 0 SFIL2 0 TOP2 0 EPE3 0 DFVV3 0 ALG23 0 SFIL3 0 TOP3 0 EA1 0 GL1 0 AED1 0 IE1 0 FVC1 0 EA2 0 GL2 0 56 CAPÍTULO 4. RESULTADOS Y ANÁLISIS 4.6. CÓDIGO AMPL AED2 0 IE2 0 FVC2 0 EA3 0 GL3 0 AED3 0 IE3 0 FVC3 0 ACGA 0 ADF 0 AFEDP 0 ANED 1 CC 0 EDP1 0 EDP2 0 GAP1 1 GAP2 1 MIOP 1 TAN 0 VD 0 ; param R := EC01 154 H1.11 77 H1.13 70 EC04 154 EC03 154 EC11 156 EC06 144 EC22 152 EC02 154 EC21 156 EC05 154 EC12 152 LAB1 55 LAB2 55 LAB3 55 LAB4 55 LAB5 55 LAB6 55 CRAI1 55; CAPÍTULO 4. RESULTADOS Y ANÁLISIS 57 4.6. CÓDIGO AMPL 4.6.3. Código del fichero de extensión ‘.run’ reset; model formulacion.mod # Llama al fichero de extension '.mod' data formulacion.dat # Llama al fichero de extension '.dat' option solver cplex; solve; # Elige como optimizador CPLEX y resuelve display x,z; # Imprime por pantalla los valores de las variables de decision 58 CAPÍTULO 4. RESULTADOS Y ANÁLISIS Apéndice A Apéndice: Modelo y horario del segundo cuatrimestre A.1. Asignaturas del segundo cuatrimestre Asignaturas de primer curso: •Asignaturas de formación básica: ◦Álgebra lineal y geometría I(ALG1) ◦Cálculo infinitesimal (CI) ◦Informática (IN) •Asignaturas obligatorias: ◦Cálculo numérico I(CI) ◦Matemática discreta (MD) Asignaturas de segundo curso: •Asignaturas de formación básica: ◦Física II (FII) •Asignaturas obligatorias: ◦Teoría de la probabilidad (TP) ◦Cálculo numérico II (CN2) ◦Integración de funciones de varias variables (IFV V ) ◦Ecuaciones diferenciales ordinarias (EDO) Asignaturas de tercer curso: •Asignaturas obligatorias: ◦Geometría y topología de superficies (GTS) ◦Programación matemática (PM) 59 A.2. FORMULACIÓN DEL MODELO ◦Modelización matemática (MOM) •Asignaturas optativas: ◦Análisis funcional (AF) ◦Lógica matemática y fundamentos (LMF) ◦Modelos lineales y diseño de experimentos (MLDE) ◦Teoría de códigos y criptografía (TCY C) Asignaturas de cuarto curso: •Asignaturas optativas: ◦Álgebra, combinatoria y computación (ACC) ◦Análisis de datos multivariantes (ADM) ◦Cálculo en variedades (CV ) ◦Complementos de modelización y optimización numérica (CMON) ◦Homología simplicial (HS) ◦Variable compleja (V C) A.2. Formulación del modelo Conjuntos D = { 1 , 2 , 3 , 4 , 5 } . Conjunto correspondiente a los días de la semana; donde 1 corresponde al lunes, 2al martes, 3al miércoles, 4al jueves y 5al viernes. H 1= { 1 , 2 , 3 } . Los elementos de este conjunto se identifican con las franjas horarias asociadas al horario de mañana; así, 1corresponde al período de tiempo comprendido entre 9:00 y 11:00, 2al relativo a las horas entre 11:30 y 13:30 y 3a la hora comprendida entre 13:30 y 14:30. H 2= { 4 , 5 , 6 } . Igual que el anterior, pero referente al horario de tarde. En este caso, 4corresponde a 14:30-15:30, 5a 15:30-17:30 y 6a 18:00-20:00. H = H 1 ∪H 2. Union de los dos anteriores; conjunto formado por todas las franjas horarias. C 1 G 1= {ALG 11 , CI 1 , IN 1 , CN 11 , MD 1 } . Asignaturas del grupo 1de primer curso. C 1 G 2= {ALG 12 , CI 2 , IN 2 , CN 12 , MD 2 } . Asignaturas del grupo 2de primer curso. C 1 G 3= {ALG 13 , CI 3 , IN 3 , CN 13 , MD 3 } . Asignaturas del grupo 3de primer curso. C 1 G 4= {ALG 14 , CI 4 , IN 4 , CN 14 , MD 4 } . Asignaturas del grupo 4de primer curso. C 1 G 5= {ALG 15 , CI 5 , IN 5 , CN 15 , MD 5 } . Asignaturas del grupo 5de primer curso. C 2 G 1= {FII 1 , TP 1 , CN 21 , IFV V 1 , EDO 1 } . Asignaturas del grupo 1de segundo curso. 60 APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE A.2. FORMULACIÓN DEL MODELO C 2 G 2= {FII 2 , TP 2 , CN 22 , IFV V 2 , EDO 2 } . Asignaturas del grupo 2de segundo curso. C 2 G 3= {FII 3 , TP 3 , CN 23 , IFV V 3 , EDO 3 } . Asignaturas del grupo 3de segundo curso. C 3 G 1= {GTS 1 , MOM 1 , PM 1 } . Asignaturas obligatorias del grupo 1de tercer curso. C 3 G 2= {GTS 2 , MOM 2 , PM 2 } . Asignaturas obligatorias del grupo 2de tercer curso. C 3 G 3= {GTS 3 , MOM 3 , PM 3 } . Asignaturas obligatorias del grupo 3de tercer curso. C1=C1G1∪C1G2∪C1G3∪C1G4∪C1G5. Asignaturas de primer curso. C2=C2G1∪C2G2∪C2G3. Asignaturas de segundo curso. C3=C3G1∪C3G2∪C3G3. Asignaturas de tercer curso. C4={ACC, ADM, CV, CMON, HS, V C}. Asignaturas de cuarto curso. C 43= {ADM, CMON} . Asignaturas de cuarto curso que serán impartidas en la franja horaria 3. OP 3= {AF 1 , AF 2 , LMF, MLDE, TCY C} . Asignaturas optativas de tercer curso, comunes para todos los grupos. F = {AF 1 , AF 2 } . Conjunto cuyas componentes corresponden a las únicas asignaturas optativas de tercero cuyo horario se permite que solape con otras materias de este mismo curso. GM = C 1 G 1 ∪C 1 G 2 ∪C 1 G 3 ∪C 1 G 4 ∪C 2 G 1 ∪C 2 G 2 ∪C 2 G 3 ∪C 3 G 1 ∪C 3 G 2. Conjunto formado por las asignaturas de primero, segundo y tercer curso que se impartirán en horario de mañana. GT = C 1 G 5 ∪C 3 G 3. Asignaturas de primero y tercero que tendrán horario de tarde. CF = {MOM 3 , PM 3 , IN 5 , ALG 15 } . Asignaturas que tendrán clases en días consecutivos. G={GTS1, CMON, ADM}. Asignaturas impartidas en la franja horaria 3. C = GM ∪GT ∪C 4 ∪OP 3. Conjunto formado por todas las asignaturas del segundo cuatrimestre. AT = {EC 01 , EC 02 , EC 03 , EC 04 , EC 05 , EC 06 , EC 11 , EC 12 , EC 21 , EC 22 , H 1 . 11 , H 1 . 13 } . Aulas destinadas a la impartición de clases teóricas. AL = {LAB 1 , LAB 2 , LAB 3 , LAB 4 , LAB 5 , LAB 6 , CRAI 1 } . Laboratorios para la impartición de prácticas informáticas. A=AT ∪AL. Conjunto formado por todas las aulas disponibles. A 1= {EC 01 , EC 02 , EC 03 , EC 04 , EC 06 } . Aulas destinadas a clases de teoría de primer curso. A 2= {EC 06 , EC 11 , EC 22 } . Aulas para la impartición de clases de teoría de segundo curso. APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE 61 A.2. FORMULACIÓN DEL MODELO A 3= {EC 05 , H 1 . 11 , H 1 . 13 } . Conjunto formado por las aulas de clases teóricas de tercer curso. A4={EC12, EC21}. Aulas destinadas a clases teóricas de cuarto curso. Parámetros NEc: Número de estudiantes matriculados en la asignatura c∈C. Ra: Capacidad del aula a∈A. NTc: Número semanal de clases de teória de la asignatura c∈C. NLc: Número semanal de prácticas informáticas de la asignatura c∈C. Variables de decisión xd,h,c,a : Variable binaria, donde d∈D , h∈H , c∈C y a∈A . Tomará el valor 1si la asignatura c tiene clase de teoría el día d en el horario h y en el aula a ; siendo 0 en otro caso. zd,h,c,a : Variable binaria, con d∈D , h∈H , c∈C y a∈A . Valdrá 1si la asignatura c tiene práctica informática el día d el el horario h y en el laboratorio a ; y 0en otro caso. y 1 c,a : Variable binaria con c∈C y a∈AT . Tomará el valor 1si la asignatura c tiene clase teórica en el aula a; y valdrá 0en otro caso. y 2 c,a : Variable binaria donde c∈C y a∈AL . Su valor será 1si la asignatura c tiene práctica informática en el laboratorio a; y será 0en otro caso. Restricciones xd,h,c,a ·NEc≤Ra, d ∈D, h ∈H, c ∈C, a ∈AT (1) zd,h,c,a ·NEc≤Ra, d ∈D, h ∈H, c ∈C, a ∈AL (2) Pd∈DPh∈HPa∈AT xd,h,c,a =NTc, c ∈C(3) Pd∈DPh∈HPa∈AL zd,h,c,a =NLc, c ∈C(4) Pc∈C(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H, a ∈A(5) Pc∈C1G1Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(6) Pc∈C1G2Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(7) Pc∈C1G3Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(8) Pc∈C1G4Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(9) Pc∈C1G5Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(10) 62 APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE A.2. FORMULACIÓN DEL MODELO Pc∈C2G1Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(11) Pc∈C2G2Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(12) Pc∈C2G3Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(13) Pc∈C3G1Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(14) Pc∈C3G2Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(15) Pc∈C3G3Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(16) Pc∈OP 3Pa∈A(xd,h,c,a +zd,h,c,a)≤1, d ∈D, h ∈H(17) Pd∈DPh∈H2Pa∈A(xd,h,c,a +zd,h,c,a) = 0, c ∈GM (18) Pd∈DPh∈H1Pa∈A(xd,h,c,a +zd,h,c,a) = 0, c ∈GT (19) Ph∈HPa∈A(x5,h,c,a +z5,h,c,a) = 0, c ∈GT (20) Ph∈HPa∈A(xd,h,c,a +zd,h,c,a)≤1, c ∈C(21) x1,4,IN5,LAB2= 1 (22) x2,4,IN5,LAB2= 1 (23) x3,4,ALG15,EC02 = 1 (24) x4,4,ALG15,EC02 = 1 (25) x1,4,MOM3,H1.11 = 1 (26) x2,4,MOM3,H1.11 = 1 (27) x3,4,P M3,H1.11 = 1 (28) x4,4,P M3,H1.11 = 1 (29) Pd∈DPa∈A(xd,3,c,a +zd,3,c,a)=0, c ∈C\C4∪ {GTS1}(30) Pd∈DPa∈A(xd,4,c,a +zd,4,c,a)=0, c ∈C4 (31) Pc∈CPa∈A(x3,3,c,a +z3,3,c,a) = 0,(32) x1,3,ADM,EC21 = 1 (33) x2,3,CMON,EC21 = 1 (34) APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE 63 A.3. DATOS Código de asignaturas de cuarto curso Número de estudiantes matriculados ACC 40 ADM 35 CV 38 CMON 45 HS 20 VC 40 Cuadro A.5: Estudiantes matriculados en asignaturas de cuarto en el segundo cuatrimestre Código de asignaturas de primer curso ALG1 CI IN CN1 MD1 Clases de teoría grupo 1 2 2 0 2 2 Prácticas de informática grupo 1 0 0 2 0 0 Clases de teoría grupo 2 2 0 2 2 Prácticas de informática grupo 2 0 0 2 0 0 Clases de teoría grupo 3 2 2 0 2 2 Prácticas de informática grupo 3 0 0 2 0 0 Clases de teoría grupo 4 2 2 0 2 2 Prácticas de informática grupo 4 0 0 2 0 2 Clases de teoría grupo 5 2 2 0 3 3 Prácticas de informática grupo 5 0 0 2 0 0 Cuadro A.6: Número de clases de asignaturas de primero en el segundo cuatrimestre Código de asignaturas de segundo curso FII TP CN2 IFVV EDO Clases de teoría grupo 1 2 2 2 2 2 Prácticas de informática grupo 1 0 0 0 0 0 Clases de teoría grupo 2 2 2 2 2 Prácticas de informática grupo 2 0 0 0 0 0 Clases de teoría grupo 3 2 2 2 2 2 Prácticas de informática grupo 3 0 0 0 0 0 Cuadro A.7: Número de clases de asignaturas de segundo en el segundo cuatrimestre 70 APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE A.3. DATOS Código de asignaturas obligatorias de tercero GTS PM MOM Clases de teoría grupo 1 3 2 1 Prácticas de informática grupo 1 0 0 1 Clases de teoría grupo 2 2 2 1 Prácticas de informática grupo 2 0 0 1 Clases de teoría grupo 3 2 3 2 Prácticas de informática grupo 3 0 0 1 Cuadro A.8: Número de clases de asignaturas obligatorias de tercero en el segundo cuatrimestre Código de asignaturas optativas de tercero Clases de teoría Prácticas de informática AF1 2 0 AF2 2 0 LMF 2 0 MLDE 1 1 TCYC 1 1 Cuadro A.9: Número de clases de asignaturas optativas de tercero en el segundo cuatrimestre Código de asignaturas de cuarto curso Clases de teoría Prácticas de informática ACC 2 0 ADM 2 0 CV 2 0 CMON 2 0 HS 2 0 VC 2 0 Cuadro A.10: Número de clases de asignaturas de cuarto en el segundo cuatrimestre APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE 71 A.4. HORARIOS DEL SEGUNDO CUATRIMESTRE A.4. Horarios del segundo cuatrimestre Los horarios aparecen reflejados en las siguientes tablas siguiendo la misma estructura que los recogidos para el primer cuatrimestre en el Capítulo 3, si bien ahora también se reflejan los códigos correspondientes a las asignaturas optativas de tercero, escritos en amarillo en los horarios relativos a los grupos 1 y 3 de tercer curso. Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 CN11 MD1 IN1 MD1 CI1 10 : 00 −10 : 30 EC03 EC03 CRAI1 EC03 EC03 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 IN1 ALG11 ALG11 CN11 12 : 30 −13 : 00 CRAI1 EC03 EC03 EC03 13 : 00 −13 : 30 CI1 13 : 30 −14 : 00 EC03 14 : 00 −14 : 30 Cuadro A.11: Horario del grupo 1 de primer curso para el segundo cuatrimestre Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 IN2 ALG12 CI2 ALG12 CI2 10 : 00 −10 : 30 LAB6 EC02 EC02 EC02 EC02 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 MD2 CN12 CN12 IN2 12 : 30 −13 : 00 EC02 EC02 EC02 LAB6 13 : 00 −13 : 30 MD2 13 : 30 −14 : 00 EC02 14 : 00 −14 : 30 Cuadro A.12: Horario del grupo 2 de primer curso para el segundo cuatrimestre 72 APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE A.4. HORARIOS DEL SEGUNDO CUATRIMESTRE Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 CN13 ALG13 CI3 CN13 MD3 10 : 00 −10 : 30 EC01 EC01 EC01 EC01 EC01 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 CI3 IN3 IN3 ALG13 12 : 30 −13 : 00 EC01 LAB6 LAB6 EC01 13 : 00 −13 : 30 MD3 13 : 30 −14 : 00 EC01 14 : 00 −14 : 30 Cuadro A.13: Horario del grupo 3 de primer curso para el segundo cuatrimestre Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 IN4 CN14 ALG14 IN4 MD4 10 : 00 −10 : 30 LAB5 EC04 EC04 LAB5 EC04 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 ALG14 CI4 CN14 CI4 12 : 30 −13 : 00 EC04 EC04 EC04 EC04 13 : 00 −13 : 30 MD4 13 : 30 −14 : 00 EC04 14 : 00 −14 : 30 Cuadro A.14: Horario del grupo 4 de primer curso para el segundo cuatrimestre Lunes Martes Miércoles Jueves Viernes 14 : 30 −15 : 00 IN5 IN5 ALG15 ALG15 15 : 00 −15 : 30 LAB2 LAB2 EC02 EC02 15 : 30 −16 : 00 16 : 00 −16 : 30 CI5 MD5 IN5 CI5 16 : 30 −17 : 00 EC06 EC02 LAB2 EC06 17 : 00 −17 : 30 17 : 30 −18 : 00 18 : 00 −18 : 30 18 : 30 −19 : 00 CN15 ALG15 CN15 MD5 19 : 00 −19 : 30 EC02 EC02 EC02 EC02 19 : 30 −20 : 00 Cuadro A.15: Horario del grupo 5 de primer curso para el segundo cuatrimestre APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE 73 A.4. HORARIOS DEL SEGUNDO CUATRIMESTRE Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 EDO1 TP1 FII1 CN21 IFVV1 10 : 00 −10 : 30 EC22 EC22 EC22 EC22 EC22 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 CN21 IFVV1 TP1 FII1 12 : 30 −13 : 00 EC22 EC22 EC22 EC22 13 : 00 −13 : 30 EDO1 13 : 30 −14 : 00 EC22 14 : 00 −14 : 30 Cuadro A.16: Horario del grupo 1 de segundo curso para el segundo cuatrimestre Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 IFVV2 TP2 CN22 EDO2 TP2 10 : 00 −10 : 30 EC06 EC06 EC06 EC06 EC06 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 FII2 EDO2 FII2 CN22 12 : 30 −13 : 00 EC06 EC06 EC06 EC06 13 : 00 −13 : 30 IFVV2 13 : 30 −14 : 00 EC06 14 : 00 −14 : 30 Cuadro A.17: Horario del grupo 2 de segundo curso para el segundo cuatrimestre Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 TP3 FII3 EDO3 FII3 EDO3 10 : 00 −10 : 30 EC11 EC11 EC11 EC11 EC11 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 IFVV3 CN23 CN23 TP3 12 : 30 −13 : 00 EC11 EC11 EC11 EC11 13 : 00 −13 : 30 IFVV3 13 : 30 −14 : 00 EC11 14 : 00 −14 : 30 Cuadro A.18: Horario del grupo 3 de segundo curso para el segundo cuatrimestre 74 APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE A.4. HORARIOS DEL SEGUNDO CUATRIMESTRE Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 PM1 TCYC PM1 MLDE MOM1 10 : 00 −10 : 30 EC05 CRAI1 EC05 EC05 LAB4 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 GTS1 MLDE TCYC 12 : 30 −13 : 00 EC05 CRAI1 EC05 13 : 00 −13 : 30 MOM1 13 : 30 −14 : 00 GTS1 EC05 GTS1 14 : 00 −14 : 30 EC05 EC05 Cuadro A.19: Horario del grupo 1 de tercer curso para el segundo cuatrimestre Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 GTS2 GTS2 MOM2 10 : 00 −10 : 30 H1.11 H1.11 LAB3 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 PM2 PM2 12 : 30 −13 : 00 H1.11 H1.11 13 : 00 −13 : 30 MOM2 13 : 30 −14 : 00 H1.11 14 : 00 −14 : 30 Cuadro A.20: Horario del grupo 2 de tercer curso para el segundo cuatrimestre Lunes Martes Miércoles Jueves Viernes 14 : 30 −15 : 00 MOM3 MOM3 PM3 PM3 15 : 00 −15 : 30 H1.11 H1.11 H1.11 H1.11 15 : 30 −16 : 00 PM3 MOM3 16 : 00 −16 : 30 H1.11 LMF CRAI1 LMF 16 : 30 −17 : 00 AF2 EC21 AF2 EC21 17 : 00 −17 : 30 EC21 EC21 17 : 30 −18 : 00 18 : 00 −18 : 30 18 : 30 −19 : 00 GTS3 AF1 GTS3 AF1 19 : 00 −19 : 30 EC05 EC12 EC05 EC12 19 : 30 −20 : 00 Cuadro A.21: Horario del grupo 3 de tercer curso para el segundo cuatrimestre APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE 75 A.5. CÓDIGO AMPL Lunes Martes Miércoles Jueves Viernes 9 : 00 −9 : 30 9 : 30 −10 : 00 ACC ADM VC ACC VC 10 : 00 −10 : 30 EC12 LAB1 EC12 EC12 EC12 10 : 30 −11 : 00 11 : 00 −11 : 30 11 : 30 −12 : 00 12 : 00 −12 : 30 CMON CV CV HS 12 : 30 −13 : 00 LAB5 EC12 EC12 EC12 13 : 00 −13 : 30 HS 13 : 30 −14 : 00 ADM CMON EC12 ADM CMON 14 : 00 −14 : 30 EC21 EC21 EC21 EC21 Cuadro A.22: Horario de cuarto curso para el segundo cuatrimestre A.5. Código AMPL A.5.1. Código del fichero de extensión ‘.mod’ # CONJUNTOS set D; # Conjunto de dias de la semana set H1; # Conjunto de franjas horarias de mañana set H2; # Conjunto de franjas horarias de tarde set H := H1 union H2; # Conjunto de todas las franjas horarias set C1G1; # Asignaturas del grupo 1 del primer curso set C1G2; # Asignaturas del grupo 2 del primer curso set C1G3; # Asignaturas del grupo 3 del primer curso set C1G4; # Asignaturas del grupo 4 del primer curso set C1G5; # Asignaturas del grupo 5 del primer curso set C2G1; # Asignaturas del grupo 1 del segundo curso set C2G2; # Asignaturas del grupo 2 del segundo curso set C2G3; # Asignaturas del grupo 3 del tercer curso set C3G1; # Asignaturas del grupo 1 del tercer curso set C3G2; # Asignaturas del grupo 2 del tercer curso set C3G3; # Asignaturas del grupo 3 del tercer curso set C4; # Asignaturas de cuarto curso set C43; # Asignaturas de cuarto en la franja horaria 3 set F; # Asignaturas optativas de tercer que pueden solapar con otras # de este mismo curso set GM := C1G1 union C1G2 union C1G3 union C1G4 union C2G1 union C2G2 union C4 union C2G3 union C3G1 union C3G2; # Grupos cuyas clases se impartiran en horario de mañana set GT := C1G5 union C3G3; # Grupos cuyas asignaturas se impartiran en horario de tarde set CF; # Asignaturas con clases consecutivas set G; # Asignaturas impartidas en la franja horaria 3 76 APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE A.5. CÓDIGO AMPL set OP3; # Conjunto formado por las optativas de tercer curso set C := GM union GT union OP3; # Todos los grupos de todos los cursos set AT; # Aulas para las clases teorico-practicas set AL; # Laboratorios set A := AT union AL; # Todas las aulas disponibles set C1 := C1G1 union C1G2 union C1G3 union C1G4 union C1G5; set C2 := C2G1 union C2G2 union C2G3; set C3 := C3G1 union C3G2 union C3G3; set A1; # Aulas para clases de teoria de primero. set A2; # Aulas destinadas a clases teoricas de segundo. set A3; # Aulas para la imparticion de clases teoricas de tercero. set A4; # Aulas para clases de teoria de cuarto. # PARAMETROS: param NE{C}; # Numero de estudiantes matriculados en la asignatura c de C param R{A}; # Capacidad del aula param NT{C}; # Numero de clases teorico-practicas semanales de la asignatura # c de C param NL{C}; # Numero de clases de laboratorio semanales de la asignatura c de C # VARIABLES DE DECISION: var x{D,H,C,A} binary; # 1 si la asignatura c se imparte en la hora h # el dia c en el aula a; 0 en cc. var z{D,H,C,A} binary; # 1 si la asignatura c tiene laboratorio en la hora h # el dia c en el aula a; 0 en cc var y1{C,AT} binary; # 1 si la asignatura c se imparte en el aula a; 0 en cc var y2{C,AL} binary; # 1 si la asignatura c se imparte en el laboratorio a; 0 en cc. # RESTRICCIONES: subject to restriccion1{d in D,h in H,c in C,a in AT}: x[d,h,c,a]*NE[c]<=R[a]; # El aula debe tener capacidad para todo el grupo restriccion2{d in D,h in H,c in C,a in AL}: z[d,h,c,a]*NE[c]<=R[a]; # El laboratorio debe tener capacidad para todo el grupo restriccion3{c in C}: sum{d in D,h in H,a in AT}x[d,h,c,a]=NT[c]; # Cada asignatura debe tener a # la semana el numero de clases teorico-practicas requerido. restriccion4{c in C}: sum{d in D,h in H,a in AL}(z[d,h,c,a])=NL[c]; # Cada asignatura debe tener a la semana el numero de clases APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE 77 A.5. CÓDIGO AMPL # de laboratorio requerido. restriccion5{d in D,h in H,a in A}: sum{c in C}(x[d,h,c,a]+z[d,h,c,a])<=1; # En cada aula/laboratorio, solo se dara # una clase en un dia y franja horarias dadas. # Las siguientes restricciones imponen que no coincidan asignaturas de un mismo # grupo a la misma hora, exeptuando cuarto curso: restriccion6{d in D, h in H}: sum{c in C1G1,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion7{d in D, h in H}: sum{c in C1G2,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion8{d in D, h in H}: sum{c in C1G3,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion9{d in D, h in H}: sum{c in C1G4,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion10{d in D, h in H}: sum{c in C1G5,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion11{d in D, h in H}: sum{c in C2G1,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion12{d in D, h in H}: sum{c in C2G2,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion13{d in D, h in H}: sum{c in C2G3,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion14{d in D, h in H}: sum{c in C3G1,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion15{d in D, h in H}: sum{c in C3G2,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion16{d in D, h in H}: sum{c in C3G3,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion17{d in D, h in H}: sum{c in OP3, a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; restriccion18{c in CM}: sum{d in D,h in H2,a in A}(x[d,h,c,a]+z[d,h,c,a])=0; # Los grupos de CM # solo tienen clase por la mañana 78 APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE A.5. CÓDIGO AMPL restriccion19{c in CT}: sum{d in D,h in H1, a in A}(x[d,h,c,a]+z[d,h,c,a])=0; # Los grupos de CT # solo tienen clase por la tarde restriccion20{c in CT}: sum{h in H,a in A}(x[5,h,c,a]+z[5,h,c,a])=0; # Los grupos de tarde no tienen clase # los viernes restriccion21{d in D, c in C}: sum{h in H,a in A}(x[d,h,c,a]+z[d,h,c,a])<=1; # A lo mas, habra una clase al dia # por asignatura # A continuacion escribimos ciertas condiciones, imponiendo # que ciertas asignaturas se impartan en la franja horaria 4: restriccion22: z[1,4,'IN5','LAB2']=1; restriccion23: z[2,4,'IN5','LAB2']=1; restriccion24: x[3,4,'ALG15','EC02']=1; restriccion25: x[4,4,'ALG15','EC02']=1; restriccion26: x[1,4,'MOM3','H11']=1; restriccion27: x[2,4,'MOM3','H11']=1; restriccion28: x[3,4,'PM3','H11']=1; restriccion29: x[4,4,'PM3','H11']=1; restriccion30{c in C diff {'GTS1'} diff C4}: sum{d in D,a in A}(x[d,3,c,a]+z[d,3,c,a])=0; # En la franja horaria 3, solo se # imparten asignaturas de cuarto curso o GTS1 restriccion31{c in C4}: sum{d in D,a in A}(x[d,4,c,a]+z[d,4,c,a])=0; # No se impartiran asignaturas de # cuarto curso en la franja horaria 4; APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE 79 A.5. CÓDIGO AMPL CI3 2 IN3 0 CN13 2 MD3 2 ALG14 2 CI4 2 IN4 0 CN14 2 MD4 2 ALG15 3 CI5 2 IN5 0 CN15 2 MD5 2 FII1 2 TP1 2 CN21 2 IFVV1 2 EDO1 2 FII2 2 TP2 2 CN22 2 IFVV2 2 EDO2 2 FII3 2 TP3 2 CN23 2 IFVV3 2 EDO3 2 GTS1 3 PM1 2 MOM1 1 GTS2 2 PM2 2 MOM2 1 GTS3 2 PM3 3 MOM3 2 ACC 2 ADM 2 CV 2 CMON 2 HS 2 VC 2 AF1 2 AF2 2 LMF 2 MLDE 1 86 APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE A.5. CÓDIGO AMPL TCYC 1 ; param NL := ALG11 0 CI1 0 IN1 2 CN11 0 MD1 0 ALG12 0 CI2 0 IN2 2 CN12 0 MD2 0 ALG13 0 CI3 0 IN3 2 CN13 0 MD3 0 ALG14 0 CI4 0 IN4 2 CN14 0 MD4 0 ALG15 0 CI5 0 IN5 3 CN15 0 MD5 0 FII1 0 TP1 0 CN21 0 IFVV1 0 EDO1 0 FII2 0 TP2 0 CN22 0 IFVV2 0 EDO2 0 FII3 0 TP3 0 CN23 0 IFVV3 0 EDO3 0 GTS1 0 PM1 0 MOM1 1 GTS2 0 PM2 0 APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE 87 A.5. CÓDIGO AMPL MOM2 1 GTS3 0 PM3 0 MOM3 1 ACC 0 ADM 1 CV 0 CMON 1 HS 0 VC 0 AF1 0 AF2 0 LMF 0 MLDE 1 TCYC 1 ; A.5.3. Código del fichero de extensión ‘.run’ reset; model segundocuatrimestre.mod # Llama al fichero de extension '.mod' data segundocuatrimestre.dat # Llama al fichero de extension '.dat' option solver cplex; solve; # Elige como optimizador CPLEX y resuelve display x,z; # Imprime por pantalla los valores de las variables de decision 88 APÉNDICE A. APÉNDICE: MODELO Y HORARIO DEL SEGUNDO CUATRIMESTRE Bibliografía Moustapha Abdellahi and Hussein Eledum. The university timetabling problem: Modeling and solution using binary integer programming with penalty functions. International Journal of Applied Mathematics and Statistics, 56(6):164–178, 2017. A.Saldaña, C.Oliva, and L.Pradenas. Modelos de programación entera para un problema de programación de horarios para universidades. Ingeniare. Revista chilena de ingeniería, 15(3):245–259, 2007. M.Akir Bakir and Cihan Aksop. A 0-1 integer programming approach to a university timetabling problem. Hacettepe Journal of Mathematics and Statistics, 37(1):41–55, 2008. M. Bazaraa and C.Shetty. Nonlinear Programming. Theory and Algorithms. John Wiley and Sons, first edition, 1943. Mokhtar S. Bazaraa. Programación Lineal y Flujo en Redes. Limusa, second edition, 2012. E.A.Akkoyunlu. A linear algorithm for computing the optimum university timetable. The Computer Journal, 16(4):347–350, 1973. David M. Gay, Robert Fourer, and Brian W. Kernighan. AMPL: a modeling language for mathematical programming. Pacific Grove California: Thomsons-Books/Cole, second edition, 2003. Johan Havas, Alfred Olsson, Jim Persson, and Mirjam Sophia Schierscher. Modeling and optimization of university timetabling, 2013. URL https://odr.chalmers.se/bitstream/ 20.500.12380/185558/1/185558.pdf. David G. Luenberger. Programación lineal y no lineal. Addison-Wesley Iberoamericana, S.A., second edition, 1989. Pedro L. Luque-Calvo. Lenguaje AMPL, 2002. URL http://destio.us.es/calvo/descargas/ ampl2a_modimp_subidoEV2.pdf. Pedro L. Luque-Calvo. Escribir un Trabajo Fin de Estudios con R Markdown, 2017. URL http://destio.us.es/calvo/memoriatfe/MemoriaTFE_PedroLuque_ 2017Nov_librodigital.pdf. N.L.Lawrie. An integer linear programming model of a school timetabling problem. The Computer Journal, 12:307–316, 1969. 89 Bibliografía R.A Ranga Prabodaine. An integer programming model for a complex university timetabling problem: A case study. Industrial Engineering and Management Systems, 16(1): 141–153, 2017. S.Daskalaki, T.Birbas, and E.Housos. An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153(1): 117–135, 2004. Wikipedia. Historia de la programación lineal. URL https://es.wikipedia.org/wiki/ Programación_lineal. O.Benli y A.Botsali. An optimization-based decision support system for a university timetabling problem: An integrated constraint and binary integer programming approach. California State University, Long Beach, pages 41–55, 2004. Nur A.H. Aizam y C.-Y.Liong. Mathematical modeling of university timetabling : A mathematical programming approach. International Journal of Applied Mathematics and Statistics, 37(7):110–122, 2013. J.Yáñez y J.Ramírez. The robust coloring problem. European Journal of Operational Research, 148:546–558, 2003. E.K.Burke y S.Petrovic. Recent research directions in automated timetabling. European Journal of Operational Research, 140:266–280, 2003. Z.Azimi. Hybrid heuristics for examination timetabling problem. Applied Mathematics and Computation, 163(2):705–733, 2005. 90