trabajo de io

Pág

ina 1

Instituto Tecnológico Superior de Lerdo

Temas: Inventarios, Líneas De Espera, Simulación, Teoría De Juegos, Cadenas De Markov Y Programación Dinámica.

Carrera: Informática

Materia: Investigación de operaciones II

Catedrático: 4F4B I.S.C. E.D. M.E. Ricardo de Jesús Bustamante González

Alumnos del equipo:

Andrea Alejandra De La Cruz Ortiz (09231073)

Yulma Carolina Camacho Medrano (09231132)

Sheila Lizeth Contreras Torres (09231285)

Manuel de Jesús Campos Sánchez (09231148)

Jafet Rubén Carrillo Bustamante (09231286)

Juan David Alvarado Balderas (09231214)

Pág

ina 2


Índice

Contenido1. INVENTARIOS.........................................................................................................................3

1.1. El costo total.....................................................................................................................3

1.2. FORMULARIO.................................................................................................................4

2. LÍNEAS DE ESPERA..............................................................................................................8

2.1. Modelos de una cola y un servidor................................................................................8

Nomenclatura de las fórmulas:.......................................................................................9

3. SIMULACIÓN........................................................................................................................17

4. TEORÍA DE JUEGOS...........................................................................................................18

4.1. ¿Qué es un juego?........................................................................................................18

4.1.1.Estrategias...............................................................................................................18

4.1.2. Juegos de suma cero para dos personas: estrategias aleatorias, dominación y solución gráfica......................................................................................18

4.1.3.........................................................Estrategias aleatorias o combinados20

4.1.4.Solución grafica de pares y nones...........................................................20

5. CADENA DE MARKOV........................................................................................................22

5.1.1.Problema de la cadena de Markov:.................................................................22

6. PROGRAMACIÓN DINÁMICA............................................................................................25

6.1. Problema de la diligencia:............................................................................................25

7. PROGRAMACIÓN DINÁMICA DETERMINÍSTICA.........................................................28

Pág

ina 3


1. INVENTARIOSEn este modelo se representan iguales el inventario máximo y la cantidad pedido.

Cabe mencionar que este no siempre es verdadero.

1.1. El costo total Para un periodo en este modelo está conformado por tres componentes de costo:

Costo unitario del producto (C1) Costo de ordenar una compra (C2) Costo de mantener un producto en almacén (C3)

Pág

ina 4


1.2. FORMULARIOEste formulario es de gran utilidad a la hora de tratar con problemas empleados en la teoría de inventarios.

EOQ = Cantidad optima de periodo:

Q=√2DC 2C3

Costo total por año:

TC (q)=(C1)(D)+(C2)D /Q+(C3)Q /2

Ó

TC (q )=C2Dq

+ (C 1 ) ( D )+C3q2

El número de periodos por año:

N=D /Q

Tiempo en pedidos (tiempo ÷ periodos)

T=Q /D

Inventario promedio:

Q /2

Costo de retención anual si la cantidad de pedidos es:

q

HC (q )=C 3q2

Costo de pérdida anual si la cantidad de pedido es:

q

OC (q )=C 2Dq

EOQ cuando costo de retención se expresa en términos del valor del

inventario en dólares: q∗¿ √2DC 2C1C3

Punto de reposición =LD

Pág

ina 5


Ejemplo 1: Inventario

La empresa servimedica vende agujas hipodérmicas a hospitales y desea reunir el costo de su inventario determinado el costo óptimo de agujas hipodérmicas de cada pedido. La demanda anual es de 1000 unidades, el costo de preparación por pedido es de $10 .00 y el costo de almacenamiento por unidad por año es de $0.50 cada aguja tiene un precio de $3.00.

Cantidad óptima:

Primero se reemplazan los datos en la primera fórmula, ésta es

utilizada para calcular la cantidad óptima de pedido:

Después se efectúan cada una de las operaciones indicadas iniciando por las

operaciones dentro del paréntesis, después la división y por último la raíz

cuadrada:


Ahora se reemplazaran los datos para calcular el costo total por año:

Q=√ (2DC 2 )(c3) Q=√ 2(1000)(10).50

Q=√ 2000.50 Q=200

CT=(C1∗D )+(C 2∗DQ )+(C 3∗Q

2)

CT=(3∗1000 )+( 10∗1000200 )+( .50∗2002

)

CT=(3000 )+(10∗5 )+(.50∗100)

CT=(3000 )+(50 )+(50) CT=3100

Pág

ina 6


Número de pedidos por año:

A continuación calcularemos el número de pedidos por año, de igual modo

remplazamos los datos en la fórmula, y se efectúa la operación.

Tiempo entre pedidos:

Por último reemplazamos los valores en la siguiente fórmula, y se realiza la operación.

Ejemplo 2: Inventario

Una empresa vende un artículo que tiene una demanda de 18,000 unidades por año, su costo de almacenamiento por unidad es de $1.20 y el costo de ordenar una compra es de $400.00. El costo total unitario del artículo es de $1.00 no se permite faltante de unidades y su tasa de reemplazo es instantáneo.

Cantidad óptima:

Al igual que el problema anterior se reemplazan los datos en la

primera fórmula y calcularemos la cantidad óptima de pedido:

Después se efectúan cada una de las operaciones indicadas.


N= DQ N=1000

200N=5

t=QD

t= 2001000

t=0.2

Q=√ (2DC2 )(iC1)

Q=√ 2(18,000)(400)(1.20∗1)

Q=√ 144000001.20 Q=3,465unidades

Pág

ina 7


Ahora se reemplazaran los datos para calcular el costo total por año:

Y se efectúan cada una de las operaciones indicadas, en orden jerárquico.

Número de pedidos por año:

A continuación calcularemos el número de pedidos por año, se sustituyen los

valores en la fórmula, y se realiza la operación.

Tiempo entre pedidos:

Para concluir; se calcula el tiempo entre pedidos, de igual modo se sustituyen los vales en la fórmula, y se realiza la operación correspondiente.

CT=(C1∗D )+(C 2∗DQ )+(C 3∗Q

2)

CT=(1.00∗18,000 )+( 400∗18,0003,465 )+( 1.20∗3,4652

)

CT=(18,000 )+(2077.92 )+(2079)

CT=22,156.92∗año

N= DQ

N=18,0003,465 N=5.19

t=QD

t= 3,46518,000

t=0.1925años

Pág

ina 8


2. LÍNEAS DE ESPERA Una cola es una línea de espera.

La teoría de colas es un conjunto de modelos matemáticos que describen sistemas de líneas de espera particulares.

El objetivo es encontrar el estado estable del sistema y determinar una capacidad de servicio apropiada.

2.1. Modelos de una cola y un servidor M/M/1 M/G/1 M/D/1 M/Ek/1

Pág

ina 9


M/M/1: Un servidor con llegadas de Poisson y tiempos de servicio exponenciales.

Fórmula M/M/1

Nomenclatura de las fórmulas: λ: Tasa media de llegadas o probabilidad de llegadas. µ: Es el número de clientes que puedo atender en un tiempo (n). p: Tasa media de llegadas/ número de clientes que puedo atender en un

tiempo (n). Ls: Número esperado de clientes en el sistema. Lq: Número esperado de clientes en la cola. Ws: Tiempo esperado de espera en el sistema. Wq: Tiempo esperado de espera en la cola. Pn: Probabilidad de tener “X” cantidad de clientes en el sistema. Pn+1: Probabilidad de tener una cola de “x”. P (Ws > t): Probabilidad de esperar más de “x” tiempo en el sistema. P (Wq > t9: Probabilidad de esperar más de “x” tiempo en la cola.

Lq=λ2

μ ( μ− λ )Ls=λ

λ−µ

Pn= (1−P ) Pn

W q=λ

μ ( μ−λ )W s=1

µ−λ

P=( LS>n ) Pn+1

P (W S>t )¿e−µ (1−p ) t P (W q> t ) pe−µ (1−p ) t

t ≥0 , p<1

Pág

ina 10


Ejemplo1. M/M/1

Un lavacar puede atender un auto cada 5 minutos y la tasa media de llegadas es de 9 autos por hora. Obtenga las medidas de desempeño de acuerdo con el modelo M/M/1. Además la probabilidad de tener 0 clientes en el sistema, la probabilidad de tener una cola de más de 3 clientes y la probabilidad de esperar más de 30min. En la cola y en el sistema.

Solución:

Ejemplo 2. M/M/1

A un supermercado llegan en promedio 80 clientes por hora que son atendidos entre sus 5 cajas. Cada caja puede atender en promedio a un cliente cada 3 minutos. Obtenga las medidas de desempeño de acuerdo con el modelo M/M/1. Además la probabilidad de tener 2 clientes en el sistema, la probabilidad de tener una cola de más de 4 clientes y la probabilidad de esperar más de 10 min. En la cola.

M/G/1: Un servidor con tiempos entre llegadas exponenciales y una distribución general de tiempos de servicio.

Lq=λ2

μ ( μ− λ )=2.25clientesLs=

λλ−µ

=3clientes

W q=λ

μ ( μ−λ )=0.25hrs .=15min .

W s=1

µ−λ=0.33hrs .=20min .

P=( LS>3 ) P3+1=0.32

P (W S>30/60 )¿e−µ (1−p )t=0.22 P (W q>30 /60 ) Pe−µ (1−p ) t=0.17

λ=9 ,µ=12 ,P= 912

=0.75

P0= (1−P ) P0=0.25

λ=8060

=1.33 μ=13=1.66 P=1.33

1.66=0.801

ws=1μ−λ

ws= 11.66

−1.33=−0.72

Ls= λλ−μ=1.33

1.33−1.66=−4.03clientes

Lq= λ2μ ( μ− λ )

=(1.33)2

1.66 (1.66−1.33 )= 1.76891.66(−1)

=0.665

Pág

ina 11


Fórmula M/G/1

Nomenclatura de las fórmulas:

(m): El tiempo esperado de servicio depende de la tasa media de servicio.

(l): El número esperado de llegadas por unidad de tiempo se llama tasa media de llegadas.

Lq: Número esperado de clientes en la cola.

Ls: Número esperado de clientes en el sistema.

Wq: Tiempo esperado de espera en la cola.

Ws: Tiempo esperado de espera en el sistema.

(s=0): Tiempos de servicio constantes.

1/m: El tiempo esperado de servicio.

(P0): Probabilidad de error.

Probabilidad de tiempo de espera (PW).

Ejemplo1. M/G/1

Un lavacar puede atender un auto cada 5 min. y la tasa media de llegadas es de 9 autos/hora, s = 2 min. Obtenga las medidas de desempeño de acuerdo con el

Ls=Lq+P Lq= λ2σ2+¿P2

2 (1−P )¿

W s=W q+1µ

W q=Lq

λ

P0=1−P PW=P

P<1

Pág

ina 12


modelo M/G/1. Además la probabilidad de tener 0 clientes en el sistema y la probabilidad de que un cliente tenga que esperar por el servicio.

Solución:

Ejemplo1. M/G/1

A un supermercado llegan en promedio 80 clientes por hora que son atendidos entre sus 5 cajas. Cada caja puede atender en promedio a un cliente cada 3 minutos. Suponga s = 5 min. Obtenga las medidas de desempeño de acuerdo con el modelo M/G/1. Además la probabilidad de tener 0 clientes en el sistema y la probabilidad de que un cliente tenga que esperar por el servicio.

Ls=Lq+P=1.31+.75=2.06clientes Lq= λ2σ2+¿ P2

2 (1−P )=1.31clientes ¿

W s=W q+1µ=0.228hrs .=13.7min .

W q=Lq

λ=0.145hrs .8.7min .

P0=1−P=0.25 PW=P=0.75 P<1

λ=1.33 μ=.05 P=26.6 σ=5

Ls=Lq+ p

Ls=9.94+4.03=13.97

Lq=λ2σ 2+ P22 (1−P )

Lq=(1.76 ) (25 )+ 16.24−6.06

Lq=9.94

ws=wq+ 1μ

ws=7.47+ 1.33

=10.50

Pág

ina 13


M/D/1: Un servidor con tiempos entre llegadas exponenciales y una distribución

degenerada de tiempos de servicio.

Fórmula M/D/1










Ls=λW sLq=

P2

2 (1−P )

W s=W q+1µ

W q=Lq

λ

P<1

Pág

ina 14


Ejemplo1. M/D/1

Un lavacar puede atender un auto cada 5 min. La tasa media de llegadas es de 9 autos/hora. Obtenga las medidas de desempeño de acuerdo con el modelo M/D/1.

Ejemplo1. M/D/1

A un supermercado llegan en promedio 80 clientes por hora que son atendidos entre sus 5 cajas. Cada caja puede atender en promedio a un cliente cada 3 minutos. Obtenga las medidas de desempeño de acuerdo con el modelo M/D/1.

Ls=λW s=1.875clientes Lq=P2

2 (1−P )=1.125clientes

W s=W q+1µ=0.21hrs .=12.5min .

W q=Lq

λ=0.125hrs .=7.5min .

µ=0.33λ=1.33 P=4.03

(1.33)(5.04)=6.70

Ls=6.70

Ls=λW s

Lq=P2(k+1)2k (1−P )

=(4.03 )2=8.06

2(1−4.03)

¿16.2409

−6.06

¿−2.688(−1)=2.68

W s=W q+1µ=2.01+1=.33=5.04

Pág

ina 15


M/Ek/1: Un servidor con tiempos entre llegadas exponenciales y una distribución Erlang de tiempos de servicio.

Fórmula M/Ek/1










Ls=λW s

Lq=P2¿¿

W s=W q+1µ

W q=Lq

λ

P<1

W q=Lq

λ=2.681.33

=2.01

Pág

ina 16


Ejemplo1. M/Ek/1

Un lavacar puede atender un auto cada 5 min. La tasa media de llegadas es de 9 autos/hora. Suponga s = 3.5 min (aprox.) Obtenga las medidas de desempeño de acuerdo con el modelo M/Ek/1

Ejemplo1. M/Ek/1

A un supermercado llegan en promedio 80 clientes por hora que son atendidos entre sus 5 cajas. Cada caja puede atender en promedio a un cliente cada 3 minutos. Suponga que k= 4. Obtenga las medidas de desempeño de acuerdo con el modelo M/Ek/1

Lq= 4.032 (4+1) = 16.24 (5) = 81.2 = -3.34 (-1) = 3.34

2(4) (1-4.03) 8(-3.03) -24.24

Ls=λW s=2.437clientes Lq=P2¿¿

W s=W q+1µ=0.2708hrs .=16.25min . W q=

Lq

λ=0.1875hrs .=11.25min

Ls=λW s

LS=1.33(5.54)

LS=7.36

µ=0.33 τ=1.33

W s=W q+1µ=¿2.51 + 1 / 0.33 = 2.51 + 3.03 = 5.54

Lq=P2¿¿

Pág

ina 17


3. SIMULACIÓN

La simulación es indispensable para la descripción y análisis de una amplia variedad de problemas reales. Proporciona considerables beneficios según el contexto en los que se use:

• Ahorro de tiempo.

• Ahorro de recursos económicos.

• Permite analizar la ocurrencia de ciertos fenómenos a través de la reconstrucción de escenas y un minúsculo análisis, que no podría llevarse a cabo en una situación real.

W q=Lq

λ=3.341.33

=2.51

Pág

ina 18


4. TEORÍA DE JUEGOS

4.1. ¿Qué es un juego? Un juego es una situación competitiva entre N personas o grupos, denominados jugadores, que se realiza bajo un conjunto de reglas previamente establecidas, con consecuencias conocidas. Las reglas definen las actividades elementales, o movimientos del juego. Pueden permitirse diferentes movimientos para los distintos jugadores, pero, cada jugador conoce los movimientos de que dispone los otros jugadores.

Si un jugador gana lo que otro jugador pierde , el juego se le denomina juego de suma 0. Un juego de dos personas es un juego que tiene solo dos jugadores.

4.1.1. EstrategiasUna estrategia pura es un plan previamente determinado que establece la secuencia de movimientos y contramovimientos que un jugador realizará durante un juego completo.

4.1.2. Juegos de suma cero para dos personas: estrategias aleatorias, dominación y solución gráfica.

En este tipo de juegos, lo que uno gana es igual a lo que otro pierde, entonces al

sumar la ganancia y la pérdida de uno y otro, el resultado obtenido es

exactamente cero.

Se analiza cómo determinar el valor y la estrategia óptima para un juego de suma

cero para dos personas que no tiene un punto silla. Se inicia con el juego sencillo

de pares y nones.

Pág

ina 19


Ejercicio 1

Dos jugadores (que se llaman Non y Par) escogen de manera simultánea el

número de dedos (1 o 2) que deben mostrar. Si la suma de los dedos que

muestran los jugadores en non, entonces, Non gana 1 dólar a Par. Si la suma de

los dedos es par, entonces Par gana 1 dólar a Non. Consideramos que el jugador

de los renglones es Non y que el jugador de las columnas es Par. Determine si

este juego tiene un punto silla.

Solución:

Este juego de suma cero cuya matriz de recompensas es la que se muestra en la

siguiente tabla. Puesto que Max (mínimo del renglón= =-1 y min (máximo de las

columnas)= +1, no se cumple la ecuación (1), y este juego no tiene punto silla.

Bueno todo lo que sabemos es que Non puede estar seguro de una recompensa

de por lo menos -1, y Par puede mantener a Non es una recompensa de cuando

mucho +1. Por lo tanto no es evidente como determinar el valor del juego y las

estrategias óptimas

Jugador de Jugador de las columnas (Par)

Los renglones

(Non) 1 dedo 2 dedos mínimo de los renglones

1 dedo -1 +2 -1

2 dedos +1 -1 -1

Pág

ina 20


Máximo de columnas +1 +1

4.1.3. Estrategias aleatorias o combinados

Debemos ampliar el conjunto de estrategias admisibles para cada jugador con el

fin de incluir las estrategias aleatorias. Hemos supuesto que hasta ahora que cada

vez que un jugador juega, aplica la misma estrategia. ¿Por qué no dejar que cada

jugador escoja una probabilidad de aplicar cada estrategia? Por ejemplo:

X1= probabilidad de que Non levante un dedo.

X2= probabilidad de que Non levante dos dedos.

y1= probabilidad de que Par levante un dedo.

y2= probabilidad de que Par levante dos dedos.

Por lo que se entendió si x1≥0, x2≥0 y x1+x2 = 1, entonces (x1, x2) es una

estrategia combinada o aleatoria a Non. Por ejemplo, Non puede seguir la

estrategia (1/2,1/2) si lanza una moneda antes de cada jugada del juego y levanta

un dedo si sale cara o dos dedos si sale cruz; de igual manera para Par.

4.1.4. Solución grafica de pares y nones

Con este es posible determinar la estrategia óptima de Non.

Como x1 + x2 = 1, sabemos que x2 = 1 – x1. Por lo tanto, cualquier

estrategia combinada puede ser (x1, 1 - x1) y solo basta determinar el valor

de x. Supóngase que Non selecciona una estrategia combinada [x1, (1 –

x1)]. ¿Cuál es la recompensa esperada de Non comparada con cada una

de las estrategias de Par? Si Par levanta un dedo, entonces Non recibirá

una recompensa de -1 con probabilidad x1 y una recompensa de +1 con

probabilidad de x2 = 1 – x1. Por lo tanto, si Par levanta un dedo y Non elige

Pág

ina 21


la estrategia combinada (x1, 1 – x1), entonces la recompensa esperada de

Non es:

(-1) x1 + (+1) (1 - x1) = 1 – 2x1

Como función de x1 esta recompensa esperada se traza como un

segmento de recta AC en que de igual manera, si Par muestra dos dedos y

Non elige la estrategia combinada (x1, 1 – x1), la recompensa esperada de

Non es:

(+1) x1 + (-1) (1 - x1) = 2x1 – 1

¿Qué es el segmento de la recta DE?

E (1,1)

A

B X1

1

D C (1,-1)

AC= recompensa de Non x1 si par escoge 1.

DE= recompensa de Non x1 si par escoge.

¿Cómo hacer que una estrategia no óptima recompense?

Estrategia de Non Par puede escoger Recompensa esperada

X1< ½ 2 dedos <0 (sobre BD)

X1 > ½ 1 dedo <0 (sobre BC)

Pág

ina 22


Y1< ½ 1 dedo >0 (sobre AB)

Y2> ½ 2 dedos > 0 (sobre BE)

5. CADENA DE MARKOVEs una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior. En efecto, las cadenas de este tipo tienen memoria. “Recuerdan” el último evento y esto condiciona las posibilidades de los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de Markov de las series de eventos independientes, como tirar una moneda al aire o un dado.

Una cadena de Markov es una secuencia X1, X2, X3,… de variables aleatorias. El

rango de estas variables, es llamado espacio estado, el valor de Xn es el estado

del proceso en el tiempo n. Si la distribución de probabilidad condicional de Xn+1

en estados pasados es una función de Xn por sí sola, entonces:

Donde xi es el estado del proceso en el instante i. La identidad mostrada es la

Propiedad de Markov.

5.1.1. Problema de la cadena de Markov:

Si hoy está nublado, para que pasado mañana esté nublado, podríamos tener un día de mañana soleado o nublado. Así tenemos las siguientes secuencias en orden de (hoy, mañana y pasado mañana):

(Nublado, soleado, nublado) o (nublado, nublado, nublado) donde pasado mañana es nublado.

Estas secuencias son mutuamente excluyentes, corresponden a caminos distintos en el árbol, así tenemos que:

= P (pasado mañana nublado | hoy nublado)

= P ((nublado, soleado, nublado) o (nublado, nublado, nublado))

=P (nublado,soleado,nublado)+P(nublado, nublado, nublado)=(.6 ´.3)+(.4´.4) =.34

Pág

ina 23


Este resultado se obtuvo multiplicando las probabilidades condicionales a lo largo de los caminos desde hoy nublado hasta pasado mañana nublado.

No es necesario que seamos tan específicos en términos de hoy, mañana o pasado mañana, podemos darnos cuenta que lo realmente importante es el número de días que pasa entre una predicción y otra.

EJERCICIO #1

El ascensor de un edificio con bajo y 2 pisos más realiza viajes de uno a otro piso. El piso en el que finaliza el viaje enésimo del ascensor, sigue una cadena de markov.

Se sabe que la mitad de los viajes que parten del bajo se dirigen a los otros 2 pisos, mientras que si un viaje comienza en el primer piso, sólo el 25% de las veces finaliza en el segundo.

Por último, si un trayecto comienza en el segundo piso, siempre finaliza en el bajo calcula la raíz de probabilidades de transición según la cadena de markov.

Nublado

Nublado

Nublado

Soleado

Pasado mañanaMañana

Nublado

Tiempo de hoy

*** 0 1 20 0 50 501 75 0 252 100 0 0

Pág

ina 24


1

2

Pa

0

2

1

0

Pb

1

Pm

2

1

2

Pa

0

2

1

0

0%

50%

50%

75%

0%

25%

100%

0%

0%

Pb

1

2

B

2

1

B

50%

75%

25%

100%

0%

50%

Pb

Pm

Pa

0

Pág

ina 25


6. PROGRAMACIÓN DINÁMICAEs un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro.

La programación dinámica no tiene formulación matemática estándar. Se trata de un enfoque de tipo general para la solución de problemas, y las ecuaciones se derivan de las condiciones individuales de los mismos.

El procedimiento general de resolución de estas situaciones se divide en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora. El análisis de la primera etapa finaliza con la obtención del óptimo del problema.

6.1. Problema de la diligencia: Es una manera de reconocer una situación que se puede formular como un problema de programación dinámica. Es encontrar la ruta que minimiza el costo total de un nodo específico.

6.1.1. Terminología y notación básica

Períodos o etapas: Sea N= {1, 2,....., n} un conjunto finito de elementos. Mediante el índice, representamos cada uno de ellos. N es el conjunto de períodos o etapas del proceso.

Espacio de estados: { } es una familia de conjuntos, uno para cada período n. S se denomina espacio de estados en el período n. Cada uno de sus elementos, que se representa mediante Sn, es un estado, que describe una posible situación del proceso en ese período.

Sea s: El estado de inicio; j: estado destino.

n: La fase, normalmente representa el número de arcos hasta el destino.

C(s, j): Costo o distancia de ir desde s hasta j.

Pág

ina 26


f(n, s): La política de costo mínimo cuando se encuentra en el estado s de la etapa n.

Ejemplo1. Programación dinámica

Un cazafortunas desea ir de Missouri a California en una diligencia, y quiere viajar de la forma más segura posible. Tiene los puntos de salida y destino conocidos, pero tiene múltiples opciones para viajar a través del territorio.

Se entera de la posibilidad de adquirir un seguro de vida como pasajero de la diligencia.

El costo de la póliza estándar (cij) se muestra en la tabla siguiente:

El objetivo es hallar y su ruta correspondiente. Cuando el cazafortunas tiene sólo una etapa por recorrer (n=4) su ruta de ahí en adelante, estará determinada por el estado actual (H o I) y su destino final X4 = J.

Luego

El cazafortunas tiene 2 etapas por recorrer (n=3). Suponga que sale de E.

f 1∗(A)

f 4∗(S )=C sj+f 5∗(J )=csj

f 4∗( H )=csj=3

f 4∗( H )=csj=4

Etapa n=3

+ f 4∗( H )=f 3 (E )=CE ,H+ f 4∗( H )=4

I

HE

C E, I =4

C E, H =1

Pág

ina 27


+ f 4∗( I )=f 3 ( E )=CE, I+ f 4∗(I )=8

Pág

ina 28


En la segunda etapa, el cazafortunas tiene 3 jornadas por recorrer (n=2). Suponga que sale de C.

En la primera etapa, el cazafortunas tiene todas las jornadas por recorrer (n=1). Necesariamente debe salir de A.

C, C E =3

C

E

F

G

Etapa n=2

C, C F =2

C, C G =4

+ f 3∗( E )=f 2 (C )=CC , E+f 3∗( E )=7

+ f 3∗( F )=f 2 (C )=CC , F+ f 3∗( F )=9

+ f 3∗(G )=f 2 (C )=CC ,G+ f 3∗(G )=10

Etapa n=1

C A, B =2

A

B

C

D

C A, C =4

C A, D =3

+ f 2∗( B )=f 1 ( A )=C A, B+ f 2∗( B )=13

+ f 2∗(C )=f 1 ( A )=C A,C+ f 2∗(C )=11

+ f 2∗( D )=f 1 ( A )=C A ,D+ f 2∗( D )=11

Características de la P.D

1. El problema se puede dividir por etapas, que requieren una política de decisión en cada una de ellas.

2. Cada etapa tiene un cierto número de estados asociados a su inicio. (Estados son las diferentes condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema).

Pág

ina 29


7. PROGRAMACIÓN DINÁMICA DETERMINÍSTICA

Una ruta crítica es la secuencia de los elementos terminales de la red de proyectos con la mayor duración entre ellos, determinando el tiempo más corto en el que es posible completar el proyecto.

La duración de la ruta crítica determina la duración del proyecto entero. Cualquier retraso en un elemento de la ruta crítica afecta a la fecha de término planeada del proyecto, y se dice que no hay holgura en la ruta crítica.

Un proyecto puede tener varias rutas críticas paralelas. El método de la ruta crítica usa ciertos tiempos (reales o determinísticos).

El método de la ruta crítica se basa en 2 procedimientos que recorren la red de las actividades de un proyecto: La pasada hacia atrás y la pasada hacia adelante, cada actividad de la red se representa con el diagrama siguiente:

Inicio más cercano IC: Es el tiempo más cercano en el que puede empezar una actividad, suponiendo que todas las actividades precedentes han concluido.

Tiempo más cercano TC: El tiempo más cercano en que una actividad puede terminar.

Inicio más lejano IL: Tiempo más lejano en que una actividad puede comenzar sin retrasar el tiempo de terminación del todo el proyecto.

Tiempo más lejano TL: El tiempo más lejano en que una actividad puede terminar sin retrasar el tiempo de terminación de todo el proyecto.

Pág

ina 30


Ejemplo1. Programación dinámica determinística.

Pág

ina 31


Personas que no trabajaron:

José de Jesús Castillo Molina

trabajo de io

Documents