Examen de Introducción a la Investigación de Operaciones

Fecha: 14 de diciembre de 1999

INDICACIONES

Duración del examen: 4 hrs.

Escribir las hojas de un solo lado.



Numerar las hojas.



Poner nombre y cédula de identidad en el ángulo superior derecho de cada hoja.



Escribir en la primera hoja el total de hojas entregadas.



Las partes no legibles del examen se considerarán no escritas.



Se requiere un mínimo del 60% de los puntos para aprobar el examen.



No se permite el uso de calculadora.

1
N
xN


1 1 1


n n 1
x x , x 1 nx , x 1 xn


 

2
 

n 0


1 x 

n 0 1 

x n 0 1 x

Pregunta 1 30 Puntos (10,10,10 )

A1) Demostrar el siguiente Resultado:

Para cualquier flujo A-Z, , y cualquier corte A-Z, (P,PC), en una red N, se cumple que;
   


=k(P,PC) sii 1) (u)=0, u (PC,P)  

2) (u)=k(u), u (P,PC)   

Nota: Si utiliza algún resultado previo, debe enunciarlo y demostrarlo.

A2) Dada la siguiente red, calcular mediante la aplicación del algoritmo de Ford-Fulkerson, el
flujo máximo y un corte mínimo.

5 6 8

3 3 5 7 9 8 6

A 4 7 4 4 7 Z

4 3 4 2 6 5 6 4

3 2 3
B) Dada la siguiente matriz de adyacencias, correspondiente a un grafo G, determinar mediante la
aplicación del método de Multiplicación Latina, todos los caminos hamiltonianos existentes en G.
Detallar cada paso realizado.




0 1 0 1 

 

0 0 1 0
M 
 


1 1 0 1 

1 0 1 0
 

Pregunta 2 31 Puntos (4, 3, 8, 8, 4, 4)

A una cabina telefónica llegan personas a hacer llamadas, según un proceso de Poisson, a una tasa
de 6 llegadas por hora. Cada persona habla durante un tiempo aleatorio exponencial, de media 5
minutos. Las personas que llegan y encuentran la cabina ocupada hacen fila afuera, y van pasando
en orden de llegada.
a) modelar como un proceso de nacimiento y muerte (dar tasas, y representación gráfica).
b) Modelar como una cadena de Markov de tiempo continuo (dar espacio de estados y generador
infinitesimal)
c) Estudiar la estabilidad del sistema (enunciar que propiedades se utilizan)
d) Calcular la distribución estacionaria de la fila
e) Calcular el tiempo medio en el sistema de los clientes
f) Calcular el porcentaje de tiempo durante el cual hay más de 4 personas en la fila (sin incluir a
la persona que esta ocupando la cabina) esperando para hablar.

Pregunta 3 19 Puntos (7,5,3,4)

a) Describir el metodo simplex para problemas con restricciones de <= .

b) Como varia la descripcion en la parte a) cuando solo hay restricciones de >= .
c) De a) y b), cuales son los criterios de STOP del metodo simplex.
d) Demostrar que los multiplicadores del simplex cumplen las condiciones necesarias para ser
soluciones optimas del problema dual.
Pregunta 4 12 Puntos

Para cada una de las siguientes afirmaciones, decir si son verdaderas o falsas.
Verdadero Falso
i Una secuencia de números aleatorios debe poseer distribución uniforme
ii Una de las principales ventajas de las secuencias de números
seudoaleatorios frente a los aleatorios es la velocidad de generación de
las mismas
iii Una de las principales ventajas de las secuencias de números aleatorios
frente a los seudoaleatorios es la posibilidad de utilizar exactamente la
misma secuencia en distintas ocasiones
iv No existe ningún método para generar números seudoaleatorios de
período infinito
v El método congruencial lineal es un método para sortear valores de
variables aleatorias continuas
vi El test serial permite estudiar la uniformidad de una secuencia de
números aleatorios.
vii Si en una secuencia de números aleatorios x0, x1, x2, ... aparece un valor
xn igual a x0, entonces los valores xn+1, xn+2, ...serán iguales a x1, x2, ...
viii Los métodos de generación de números seudoaleatorios se basan en
fórmulas de recurrencia.

Pregunta 5 8 Puntos

Dar un método para generar una variable aleatoria discreta N de distribución pj=P(N=j), 0<j n.
Preguntas adicionales para estudiantes libres

Pregunta 6 6 Puntos (3, 3)

a) Dar la definición de cadena de Markov de tiempo continuo.

b) Dar la definición de cadena de Markov de tiempo continuo homogénea.

Pregunta 7 9 Puntos

Para cada una de las siguientes afirmaciones, decir si son verdaderas o falsas.
Verdadero Falso
i Las variables aleatorias de distribución de Poisson cumplen la
propiedad de ausencia de memoria
ii Un proceso estocástico de tiempo y espacio de estado discreto queda
determinado si se conoce el espacio de estado E y las probabilidades
P(X1=j | X0=i)
iii La representación gráfica usual de una cadena de Markov de tiempo
continuo es el árbol de evoluciones del proceso.
iv La matriz de transiciones de una cadena de Markov de tiempo discreto
siempre es estocástica
v La matriz de transiciones de una cadena de Markov de tiempo discreto
siempre es bi-estocástica
vi Una cadena de Markov irreductible es aquella en la cuál todos los
estados comunican entre sí.

Pregunta 8 5 Puntos (2, 3)

a) Enunciar las ecuaciones de Chapman-Kolmogorov.

b) Utilizando estas ecuaciones, demostrar que P(n), la matriz de transición en n etapas, es igual a
Pn (la n-ésima potencia de la matriz de transición en una etapa).
 Examen de Introducción a la Investigación de Operaciones
Módulo Simulación
Fecha: 14 de diciembre de 1999

INDICACIONES
!

! Duración del examen: 1 hrs.

! Escribir las hojas de un solo lado.
! Numerar las hojas.
! Poner nombre y cédula de identidad en el ángulo superior derecho de cada hoja.
! Escribir en la primera hoja el total de hojas entregadas.
! Las partes no legibles del examen se considerarán no escritas.
Se requiere un mínimo del 60% de los puntos para aprobar el examen.

Pregunta 1 12 Puntos

Para cada una de las siguientes afirmaciones, decir si son verdaderas o falsas.
Verdadero Falso
i Una secuencia de números aleatorios debe poseer distribución uniforme
ii Una de las principales ventajas de las secuencias de números
seudoaleatorios frente a los aleatorios es la velocidad de generación de
las mismas
iii Una de las principales ventajas de las secuencias de números aleatorios
frente a los seudoaleatorios es la posibilidad de utilizar exactamente la
misma secuencia en distintas ocasiones
iv No existe ningún método para generar números seudoaleatorios de
período infinito
v El método congruencial lineal es un método para sortear valores de
variables aleatorias continuas
vi El test serial permite estudiar la uniformidad de una secuencia de
números aleatorios.
vii Si en una secuencia de números aleatorios x0, x1, x2, ... aparece un valor
xn igual a x0, entonces los valores xn+1, xn+2, ...serán iguales a x1, x2, ...
viii Los métodos de generación de números seudoaleatorios se basan en
fórmulas de recurrencia.

Pregunta 2 8 Puntos

Dar un método para generar una variable aleatoria discreta N de distribución pj=P(N=j), 0<j n. "
Soluciones:

Pregunta 2

a)
) )

PN y M E= Naturales. , #

n ' ' 6ll / hora $

n 0
& % (

n ' ( ' 12ll / hora $

n 1
&

g g

0 1 2 3 .......

h h

b)
E= Naturales
/ ,

5 5

-
1

0 4

5 5

( )
0

6 6

- *

- *

Q
5 5

-
0
3
6

( 1
0

) 4

- *

- *

. +

9
j ?

i 1 @

j i 1
C B

qij ?

( ) j i 0
78

B C
@ >

j i 0 < <

c) X

I
X

[ [

[
n
P M
R

o n 1
\

L K
P M

L K
D

T F

Z Z

1 n 1
X \

V H

PN y M estable 1
S S X E

n
TU F

Z Z

1 n
\

L K

PQR M

T F

L J K

[ [

NO

1 n 1
\

6 1
Y ^ ^

] Sistema estable.
_

12 2

c) Con ecuaciones de balance flujo

b

P1 P0 P1 P0
e

a
c

d d

2
P2 P1 P2 P1 Po
e

a a
c

d d d

n
Pn Pn Pn Pn Po
e

a a
c

d d d

1 f

1
d)
1 1 6 1
j

u u

n
Pn r

1 t

Po r

1 t

Po r

j
r r

1 s
v

1 s
r

n 0 k
u

v
n 1/1 s
v

12 2
n 0 k

n n 1
i

n
opq

1 l

1 opq

1 l

Pn r
v

Po r

mn
r

mn

2 2 2

e)

1
n nPn n (1 / 2) n 2
n(1 / 2) n 1 1 1 1 1 1
ts x x z x z x

(1 / 2) z { x

w w
x

w w
r

4 6 (1 1 / 2) 2
|

} }

6 6 y

4 6 1/ 4

1 / 6 hora 10 minutos x

f)

1
1 1 1 1 1 32 16 8 4 2 1 1
~

y y y y y

Pn x

1 Poy y

P1 y

P2 y

P3 y

P4 x

1 y y y y y
x x

n 5 

2 4 8 16 32 32 32

Pregunta 4

i ii iii iv v vi vii viii

V V F V F F F V