Ayudantía4-ModelaciónDinámica_ConPauta_

Vista previa del material en texto

PONTIFICIA UNIVERSIDAD CATÓLICA DE CHILE
ESCUELA DE ADMINISTRACIÓN
Primer Semestre 2018
Ayudantía 4 – Modelación Dinámica
EAA251A Métodos de Optimización
18 y 19 de Abril de 2018
Profesores: Marcos Singer
 Christian Villalobos
Antonio Aninat
Ayudante: Juan Pablo Aranguiz
Mail Ayudante: jparanguiz@uc.cl
	Ayudante Jefe Cátedra: Miguel Pérez
Ejercicio 1 
En la Región Metropolitana existe una gran cantidad de colegios municipales y particulares subvencionados. Muchos de ellos cuentan con escaso presupuesto ya que los aportes estatales dependen de los alumnos matriculados que asisten, y los colegios no logran llenar su capacidad. Como consecuencia de esto y de otros factores, el desempeño de los colegios también es deficiente en muchos casos; lo que se refleja en los resultados de la prueba SIMCE. En resumen, hay más colegios de los necesarios y hay colegios de baja calidad.
El Ministerio de Educación ha decidido que la solución para esto es copar la capacidad de los buenos colegios, de manera de focalizar mejor los recursos asignados, y cerrar los colegios más deficientes. Para esto, se deberá reagrupar a los alumnos en los colegios, llenando los de mejor calidad y dejando sin matrícula a los de peor resultado ya que serán cerrados. Este movimiento de alumnos debe hacerse de manera gradual; cada colegio puede recibir de un año a otro a un máximo de alumnos nuevos equivalente a un 10% de la matrícula del año anterior.
El proceso de transferencia de alumnos tiene un plazo de 10 años. Asumiremos que el parámetro de calidad actual es el mejor predictor del futuro, es decir, se puede usar un parámetro del periodo actual (t=0) para evaluar todo el proceso de transferencia ya que no se conocen actualmente los resultados futuros. Se busca obtener según este parámetro el mejor resultado ponderado en la distribución de los alumnos en los colegios en el año 10.
El proceso de transferencia de alumnos debe cumplir con otros requisitos. La razón entre alumnos hombres y mujeres de los colegios debe mantenerse durante todo el proceso, más menos un rango del 10%. 
 Cuando un alumno es cambiado de un colegio a otro, se entiende que aumenta la distancia desde su casa al colegio en la mitad de la distancia entre los dos colegios. El aumento promedio de distancia de todos los alumnos transferidos no puede superar un cierto umbral cada año.
Se debe mantener un estándar en los colegios de al menos 30 m2 por alumno más 10m2 por profesor. Esto debe cumplirse al final del periodo de 10 años. Durante el proceso, cada comuna tiene un presupuesto limitado con el que puede crecer para aumentar la superficie de los colegios que estime conveniente, a un costo por m2 adicional que depende de la comuna en que se encuentre el colegio.
Al final del proceso, por cada 30 alumnos que transfiera un cierto colegio a cierto otro, debe transferir a un profesor de su planta. Si el resultado es una fracción debe transferir jornadas de trabajo de horas equivalentes. El promedio SIMCE ponderado de la nueva combinación de alumnos en cada colegio no puede disminuir más de un 20% del resultado del colegio previo a la transferencia.
Cada colegio tiene un indicador de retención porque un número de alumnos deserta al sistema particular. En cambio, no hay un flujo de entrada desde el sistema particular.
1. Defina conjuntos, parámetros y variables.
1. Escriba el programa lineal de optimización.
Respuesta
a) Conjuntos:
Colegios = {establecimientos}
Años = {1, 2, 3… 10}
Comunas = {A, B,… }
Variables:
 : alumnas mujeres transferidas del colegio e al colegio f en el periodo t
 : alumnos hombres transferidas del colegio e al colegio f en el periodo t
 : alumnas mujeres en el colegio e al final del periodo t
 : alumnos hombres en el colegio e al final del periodo t
 : profesores transferidos del colegio e al colegio f en el periodo 10
 : superficie adicional construida en el colegio e en el periodo t
Parámetros:
: puntaje SIMCE del colegio e en el periodo t=0 [puntos]
 matrícula inicial de mujeres en el colegio e en t=0 [n]
 matrícula inicial de hombres en el colegio e en t=0 [n]
 distancia entre el colegio e y el colegio f [km]
: parámetro de aumento promedio máximo de la distancia de los alumnos al colegio
 superficie del colegio e []
: inventario inicial de profesores en el colegio e
b) Función Objetivo:
Restricciones:
	Traspaso anual menor al 10%
 		Razón hombres/mujeres 
 		Aumento máximo de distancia
 	Estándar de m2 por alumno
  				Presupuesto para construcción de superficie
  			Transferencia de profesores
 				Inventario de profesores
			Inventario final de profesores
 Resultado SIMCE final del colegio
  				Inventario inicial mujeres
  				Inventario inicial hombres
 	Ecuación de inventario mujeres
 	 Ecuación de inventario hombres
 ; ; ; ; ; 0 	No negatividad de las variables
Ejercicio 2 (Propuesto) 
Usted desea optimizar los viajes ofrecidos durante un día, por una flota de buses expresos del GranSantiago. En lo que sigue, usted puede trabajar al nivel de horas, de modo que el modelo tiene T periodos, donde cada periodo representa una hora del día (por ejemplo, de 6:00 a 23:00, serían 18 periodos).
La flota de buses expresos cuenta con R tipos de buses y se dispone de Sr buses de cada tipo (donde r es el tipo de bus). Los distintos tipos de buses se diferencian solamente en la cantidad de asientos que posee cada bus y todos los asientos son iguales. Cada tipo de bus de tipo r cuenta con Ur asientos. Esta flota de buses realiza recorridos directos entre distintos paraderos de la ciudad. La ciudad cuenta con N paraderos. Dado que los buses son expresos, todos los viajes son directos (sin escalas). El tiempo de viaje entre el paradero i y el paradero j es Tij (no depende del tipo de bus) y los viajes pueden tomar 1, 2 o 3 horas (cada Tij puede tomar uno de estos valores) Además, los buses pueden esperar en cada paradero tanto tiempo como sea necesario. Los buses pueden viajar con o sin pasajeros (puede ser conveniente viajar sin pasajeros si es que es necesario reposicionar un bus en un paradero de origen de viajes donde exista alta demanda en un periodo particular) y el costo para GranSantiado de proveer cada viaje depende del tipo de bus y del par donde viaja. Además, existe un costo de tripulación del bus distinto para cada tipo de bus, que depende de la cantidad de buses de cada tipo que se tenga en circulación, independiente si estos buses están viajando o en espera.
Por otro lado, se tiene demandas por viajes entre paraderos a distintas horas del día: entre el paradero i y el paradero j y la hora t, se demandan Dijt viajes. La tarifa cobrada a cada pasajero por cada viaje sólo depende del par en que viaja. Los viajeros tienen un alto nivel de insatisfacción, de modo que sólo viajaran si es que hay un recorrido directo entre el par en que ellos desean viajar (no hay trasbordos) y sólo si es que el bus pasa en la hora t en que ellos llegan al paradero.
A usted se le pide optimizar los servicios ofrecidos por la empresa de buses expresos, de modo de maximizar la utilidad neta, dada por la diferencia entre los ingresos por venta de boletos y los costos de flota necesarios para proveer estos viajes. Para ello, considere una red para cada tipo de bus, donde en cada nodo (paradero y periodo) la suma de la cantidad de buses que están esperando en el paradero desde el periodo anterior y los buses que llegan de un viaje; sea igual a la suma de la cantidad de buses que parten en un viaje y los buses que esperan en el paradero hasta el periodo siguiente. Vincule los viajes de buses con los viajes realizados por los pasajeros, de modo que estos últimos no superen la cantidad de asientos disponibles en cada tipo de bus, ni la cantidad de viajes demandados. Para que el plan de viajes de los buses sea implementable al día siguiente (suponiendo que todos los días tienen iguales valores de los parámetros), exija que la cantidad de buses de cada tipo, en cada paradero, sea igual al principio y al final del día. Además,exija que los viajes no pueden llegar a su destino más allá del final del día (al final del día todos los buses quedan en espera en algún paradero). Para contabilizar los buses utilizados de cada tipo, puede sumar los buses en espera al final (o al principio) del día.
a) Defina los conjuntos, variables y parámetros necesarios para optimizar la utilidad neta de la empresa de buses.
b) Formule un problema de optimización lineal que le permita maximizar la utilidad neta de la empresa de buses, sujeto a las distintas restricciones operativas de la misma. 
c) ¿Cómo cambiaría el modelo si es que los viajes pueden estar viajando durante al final del horizonte de planificación, de modo que su viaje en el horizonte siguiente (por ejemplo, usted tiene un horizonte de planificación desde las 1 horas hasta las 24 horas y tiene un viaje que empieza a las 23 y termina a las 2 del otro día) y, además, usted exige que los viajes empiecen y terminen a la misma hora entre los distintos horizontes de planificación (en el ejemplo, si se realiza el viaje de las 23 que termina a las 2, éste debe ser realizado todos los días)? 
Hints: 
· Usted ya no tendría condiciones de borde en las restricciones de balance de buses, sino una restricción que exige que todos los viajes que comiencen antes del inicio del horizonte de planificación sean iguales a los que comiencen más adelante, pero desfasados en el largo del horizonte de planificación. En el ejemplo, los viajes que empiecen en deben ser iguales a los viajes que empiecen en .
· Al final o principio del horizonte de planificación no todos los buses están estacionados, por lo que al contabilizarlos se debe considerar los buses estacionados y los que están viajando y atraviesan el horizonte de planificación.
Respuesta:
a)
Conjuntos:
	R = tipos de bus
N = paraderos
T = periodos
Parámetros:
Pi,j	: tarifa del pasaje entre el paradero i y el paradero j
Cr,i,j	: costo de viaje de un bus entre el paradero i y el paradero j, para el tipo de bus r. 
Er	: costo de tripulación por bus (en [$/bus] ) para el tipo de bus r
Sr	: cantidad de buses disponibles del tipo r
Ur	: cantidad de asientos que tiene el bus tipo r.
Di,j,t	: demanda por viajes entre el paradero i y el paradero j, en el instante t.
Tij	: tiempo de viaje desde el paradero i al paradero j.
Variables: 
z	: utilidad neta de la empresa de transportes
xr,i,j,t	: cantidad de buses del tipo r, que salen del paradero i, con dirección al paradero j, en el instante t.
yr,i,t	: cantidad de buses del tipo r, que quedan en espera en el paradero i, en el periodo t, hasta el periodo siguiente.
wi,j,t	: cantidad de pasajeros que viajan desde el paradero i, hacia el paradero j, en el instante t.
b) 
Maximizar: z = –– 
Sujeto a:
1. Balance en los nodos de las redes de buses
+++ yr,i,t-1 = + yr,i,t	r, j ,t		
2. Condición de borde (viajes iniciales)
xr,i,j,t = 0		 r,i,j,t | t<1
3. Condición de borde (viajes finales)
xr,i,j,T-2 = 0		 r,i,j | Ti,j > 3
4. Condición de borde (viajes finales)
xr,i,j,T-1 = 0		 r,i,j | Ti,j > 2
5. Condición de borde (viajes finales)
xr,i,j,T = 0		 r,i,j			
6. Disponibilidad de buses
 Sr		r
7. Implementabilidad
yr,i,T = yr,i,0		 r,i
8. Capacidad de los buses
wi,j,t 	i,j,t
9. Demanda por viajes
wi,j,t Di,j,t		i,j,t
10. No negatividad
xr,i,j,t, yr,i,t, wi,j,t 0	 r,i,j,t
c) Ahora no es necesario colocar las condiciones de borde, sino que colocar la restricción cíclica:
xr,i,j,t = xr,i,j,t+T	 r,i,j,t | t<1
 
y no todos los buses estarán estacionados al final del horizonte de planificación, sino que pueden estar viajando, de modo que la cantidad de buses utilizada estará dada por la expresión:
+
Así, la restricción de disponibilidad de buses cambia a:
+ Sr	r
Y en la función objetivo, el costo de tripulación cambia a:
å
i
r
T
i
r
r
y
,
,
,
E
å
=
-
3
|
)
,
(
3
,
,
,
ji
T
i
j
t
i
j
r
x
å
=
-
2
|
)
,
(
2
,
,
,
ji
T
i
j
t
i
j
r
x
å
=
-
1
|
)
,
(
1
,
,
,
ji
T
i
j
t
i
j
r
x
å
)
,
(
,
,
,
j
i
t
j
i
r
x
å
i
T
i
r
y
,
,
å
r
t
j
i
r
r
x
U
,
,
,
å
i
i
r
y
0
,
,
å
<
1
 
|
 
,
,
,
,
,
t
t
i
j
t
i
j
r
x
å
i
i
r
y
0
,
,
å
<
1
 
|
 
,
,
,
,
,
t
t
j
i
t
j
i
r
x
÷
÷
ø
ö
ç
ç
è
æ
+
å
å
å
<
1
 
|
 
,
,
,
,
,
0
,
,
E
E
t
t
j
i
t
j
i
r
i
i
r
r
r
r
x
y
å
t
j
i
t
j
i
j
i
w
,
,
,
,
,
P
å
t
j
i
r
t
j
i
r
j
i
r
x
,
,
,
,
,
,
,
,
C