ESCUELA DE INGENIERÍAS INDUSTRIALES
UNIVERSIDAD DE MÁLAGA
Grado de Ingeniería de Organización Industrial
Métodos Cuantitativos de Gestión
Práctica Tema 4
Curso 23/24
MIRANDA GONZÁLEZ, ANTONIO
Contenido
1. Ejercicio 1. PLE....................................................................................................................... 3
1.1. Enunciado. ..................................................................................................................... 3
1.2. Modelo apartado I......................................................................................................... 3
1.3. Resultados apartado I. .................................................................................................. 4
1.4. Apartado II..................................................................................................................... 4
2. Ejercicio 2. Asignación. .......................................................................................................... 5
2.1. Enunciado. ..................................................................................................................... 5
2.2. Modelo estructurado. Apartado I. ................................................................................ 5
2.3. Resultados. Apartado I. ................................................................................................. 6
2.4. Modelo. Apartado II. ..................................................................................................... 6
2.5. Resultados. Apartado II. ................................................................................................ 7
3. Ejercicio 3. Autobuses. .......................................................................................................... 7
3.1. Enunciado. ..................................................................................................................... 7
3.2. Modelo estructurado. ................................................................................................... 8
3.3. Resultados. .................................................................................................................... 8
4. Ejercicio 3. Asignación tripulación......................................................................................... 8
4.1. Enunciado. ..................................................................................................................... 8
4.2. Modelo estructurado. ................................................................................................... 9
4.3. Resultados. .................................................................................................................. 10
1. Ejercicio 1. PLE.
1.1. Enunciado.
Resolver el siguiente problema de PLE:
max z = 8x1 + 5x2
s.a. x1 + x2 ≤ 6
9x1 + 5x2 ≤ 45
x1; x2 enteros Z+
a) Resuelva el ejercicio utilizando el algoritmo de ramificación y acotación (Branch and Bound)
indicando el modelo y las soluciones de cada uno de los subproblemas. Para ello cree una
estructura en árbol indicando en cada caja (valor función objetivo y de cada una de las variables)
y en cada rama la restricción utilizada. Indique las soluciones candidatas y la cota inferior.
b) Realice el problema en GAMS utilizando directamente programación lineal entera (MIP),
compruebe si las soluciones coinciden con la del problema relajado, en el caso de no ser así,
¿cuál es el GAP en cada una de las soluciones candidatas?
1.2. Modelo apartado I.
Variables:
Las variables del problema son x1, x2 y z.
Resolución:
Para resolver el problema por el método de Branch and Bound las variables se consideran
únicamente positivas, a esto se le llama problema relajado. Se resuelve el primer problema
relajado y a partir de la solución se va estructurando el árbol de soluciones, estableciendo
restricciones.
El árbol de soluciones es el siguiente:
1.3. Resultados apartado I.
El resultado final es x1=5; x2=0; z=40. El resultado final se encuentra entre las soluciones
candidatas y se elige la que tenga el mayor valor para la función objetivo.
Las soluciones que aparecen con una cruz roja son porque no se obtendrá ningún valor mejor si
seguimos por esa rama. En el primer caso la solución es igual que la anterior, por lo que se entra
en bucle. Y en el segundo caso el valor de z es menos que el del límite inferior, fijado por la
primera solución candidata en 39.
1.4. Apartado II.
Para resolver el problema utilizando programación lineal entera deben las variables x1 y x2
deben ser definidas como variables enteras, además se utiliza el resolutor MIP.
En función de los valores que tome la opción “OPTCR” el resolutor ofrece una u otra solución.
Para valores mayores a 0.1 la solución que entrega corresponde con la primera solución
candidata obtenida en el apartado a, es decir, x1=3; x2=3; z=39. Si el valor se reduce a 0.01 y en
adelante el valor obtenido es el mismo que el obtenido en el apartado a como valor final, x1=5;
x2=0; z=40.
2. Ejercicio 2. Asignación.
2.1. Enunciado.
Una universidad está programando las clases para el próximo cuatrimestre académico y requiere
buscar la mejor asignación posible de profesores a los distintos cursos que se deben impartir.
Considere que existen 5 profesores: A, B, C, D, E y 5 asignaturas: C1, C2, C3, C4, C5.
Adicionalmente, los profesores han manifestado sus preferencias por dictar los distintos cursos
en una escala de 1 a 10, donde 10 es la máxima puntuación y 1 la mínima puntuación o
preferencia. Se asume que cada profesor es apto para dictar cualquier asignatura,
independiente del puntaje de su preferencia. La siguiente tabla resume las puntuaciones que
asigna cada profesor a cada curso:
Se ha establecido como criterio que cada profesor debe dictar sólo un curso y a la vez que cada
curso obviamente debe tener un profesor.
• Modele el problema en anterior para determinar la asignación optima de profesores.
Resuelva en GAMS de modo estructurado.
Debido una baja del profesor E la dirección del centro estima que cada profesor podrá dictar
uno o dos cursos y a la vez cada curso obviamente debe tener un profesor.
• Modele el problema en base a lo anterior para determinar la asignación optima de
profesores. Resuelva en GAMS de modo estructurado.
2.2. Modelo estructurado. Apartado I.
Variables:
Se necesitan dos variables, la primera binaria, para realizar la asignación; la segunda,
corresponde a la función objetivo
• Xij: Variable binaria, asignación de profesores.
• Z: función objetivo.
i son las 5 asignaturas (C1, C2, …, C5)
j son los 5 profesores (A,B, …, E).
Valores intermedios:
• p (i, j): tabla con las puntuaciones que cada profesor le asigna a cada clase.
Una vez definidas las variables y los valores intermedios se puede construir el modelo
estructurado del problema.
• Función objetivo: Max 𝑧 = ∑𝐶5 𝐸
i=C1 ∑j=A 𝑥𝑖𝑗 ∗ 𝑝𝑖𝑗
• Un profesor por asignatura: ∑𝐸j=A 𝑥𝑖𝑗 = 1
• Una asignatura por profesor: ∑𝐶5
i=C1 𝑥𝑖𝑗 = 1
• Variable binaria: x
2.3. Resultados. Apartado I.
Al resolver el programa se asignan perfectamente un profesor con una asignatura. La puntuación
total que se obtiene de esta forma es de 44 puntos.
Sería interesante comprobar si se pudiera obtener una mejor puntación haciendo la asignación
más flexible, por ejemplo, permitiendo que un profesor tome todas las asignaturas posibles. En
este caso el profesor A no impartiría ninguna asignatura mientras que el profesor D impartiría
la número 1 y la número 5, la suma de las puntuaciones que se obtiene en este caso es mayor,
concretamente 46 puntos.
2.4. Modelo. Apartado II.
Variables:
Se necesitan dos variables, la primera binaria, para realizar la asignación; la segunda,
corresponde a la función objetivo
• Xij: Variable binaria, asignación de profesores.
• Z: función objetivo.
i son las 5 asignaturas (C1, C2, …, C5)
j son los 4 profesores (A,B, C, D).
Valores intermedios:
• p (i, j): tabla con las puntuaciones que cada profesor le asigna a cada clase.
Una vez definidas las variables y los valores intermedios se puede construir el modelo
estructurado del problema.
• Función objetivo: Max 𝑧 = ∑𝐶5 𝐷
i=C1 ∑j=A 𝑥𝑖𝑗 ∗ 𝑝𝑖𝑗
• Un profesor por asignatura: ∑𝐷
j=A 𝑥𝑖𝑗 = 1
• Asignatura/s por profesor: ∑𝐶5
i=C1 𝑥𝑖𝑗 ≥ 1
• Máximo 2 asig. por profesor: ∑𝐶5
i=C1 𝑥𝑖𝑗 ≤ 2
• Variable binaria: x
2.5. Resultados. Apartado II.
Al resolver el programa se asignan perfectamente un profesor con una asignatura. La puntuación
total que se obtiene de esta forma es de 45 puntos.
3. Ejercicio 3. Autobuses.
3.1. Enunciado.
En una ciudad se intenta disminuir la contaminación reduciendo la circulación interurbana. Un
primer estudio busca determinar el mínimo número de autobuses que satisfagan las
necesidades de transporte. Después de recoger la información se observa que este número varía
según la hora del día, pero se puede considerar constante en intervalos sucesivos de cuatro
horas:
Los turnos de autobuses funcionan durante ocho horas seguidas y pueden comenzar al principio
de cualquiera de los seis periodos descritos anteriormente. Además, si en el turno que comienza
a las 8:00 p.m. hay más de 4 autobuses, en el siguiente ha de haber también más de 4. Modelo
el sistema para determinar el número de autobuses que satisface las necesidades diarias.
Modele el problema para determinar la asignación óptima diaria de autobuses. Resuelva en
GAMS de modo estructurado.
3.2. Modelo estructurado.
Variables:
• Xij: Número de autobuses que entran en cada periodo.
• Z: coste total del transporte.
• Y: variable binaria para cumplir con la restricción que relaciona el último y el primer
periodo.
i Autobuses que entran en cada periodo(x1, x2, …, x6).
j periodos (P1, P2, …, P6).
Valores intermedios:
• A(i,j): grupos de autobuses activos en cada periodo .
• D(j): Demanda de autobuses en cada periodo.
Una vez definidas las variables y los valores intermedios se puede elaborar el modelo
estructurado.
• Función objetivo: Min 𝑧 = ∑𝑥6 𝑃6
i=x1 ∑j=P1 𝑥𝑖𝑗 ∗ 𝐴𝑖𝑗
• Req. de demanda (j): ∑𝑁6
i=N1 𝑥𝑖𝑗 ∗ 𝐴𝑖𝑗 ≥ 𝐷𝑗
• Restricción 6º periodo: x5 + x6 ≤ 4(1-y) + 20y
• Restricción 1º Periodo: x1 + x6 ≥ 4 + y
• No negatividad: x≥0
• Variable binaria y
3.3. Resultados.
La solución muestra cuantos autobuses debería entrar en cada periodo. En este caso el problema
se solucionaría de forma óptima si en el periodo 1 entraran 4 autobuses; en el periodo 2, 10
autobuses; en el periodo 4, 8 autobuses; y finalmente, en el periodo 5, 4 autobuses.
4. Ejercicio 3. Asignación tripulación.
4.1. Enunciado.
La línea aérea VIAJESFLY necesita asignar sus tripulaciones para cubrir todos los vuelos
programados. Se estudiará el problema de asignar el número mínimo de tripulaciones con base
en San Francisco (SF) a los vuelos enumerados en la tabla. Las 12 columnas muestran las
secuencias de vuelos factibles de una tripulación (los números en cada columna indican el orden
de los vuelos en la secuencia). El costo de asignar una tripulación a una secuencia de vuelos
específica se muestra (en miles de euros por tripulación) en la línea inferior de la tabla. Es
necesario determinar las secuencias de los vuelos de tal manera que se cubran todos los vuelos
programados, minimizando el costo.
Modele el problema para determinar la secuenciación óptima de vuelos. Resuelva en GAMS de
modo estructurado.
4.2. Modelo estructurado.
Variables:
• Xj: tripulaciones activas, variable binaria
• Z: coste total de las tripulaciones.
i tripulaciones (1, 2, …, 11).
j vuelos (1, 2, …, 12).
Valores intermedios:
• A(i,j): cobertura de vuelos por tripulación.
• c(j): coste de cada tripulación.
• M: número de tripulaciones (3).
Una vez definidas las variables y los valores intermedios se puede elaborar el modelo
estructurado.
• Función objetivo: Min 𝑧 = ∑12j=1 𝑥𝑗 ∗ 𝑐𝑗
• Req. de demanda (i): 12
∑j=1 𝑥𝑖𝑗 ∗ 𝐴𝑖𝑗 ≥ 1
• Restricción tripulaciones: ∑12
j=1 𝑥𝑗 = 𝑀
• Variable binaria x
4.3. Resultados.
Para obtener el resultado óptimo se ha de ir reduciendo el valor de M. Un método podría ser
fijar el valor inicial de M en 11 e ir reduciendo hasta que no exista una solución, en este caso
ocurriría con 2. Eso nos indica que el valor anterior es el menor número de tripulaciones con las
que podemos contar, es decir 3.
