UN MODULO DE INVESTIGACION DE OPERACIONES

MODULO

 DE INVESTIGACIÓN

 DE 

OPERACIONES II

INDICE

I. PROGRAMACIÓN ENTERA   

I.1 Ramificación y Acotamiento con Solver ……………………………..3  I.2 Ejemplo de Ramificación y acotamiento…………………………..….5  I.3 Árbol de solución……………………………………………………….6

II. TEORIA DE DECISIONES

II.1. Introducción a la Teoría de Decisiones………………………….……8      II.2  Fases en el enfoque de la T.O………………………………………. 8,9  II.3  Disponibilidad de Información Imperfecta………………………..  10  II.4  Decisiones con Riesgo…………………………………………….…. 10  II.5  Caso de Estudio: El Vendedor de  periódicos………………..     11,12

II.6  El criterio de valor esperado………………………………………. .13  II.7  Caso de Estudio: Venta de Fresas………………………………….. 13  II.8  Artículos que tienen Valor de Salvamento………………………… .6  II.9   Datos experimentales en decisiones con riesgo……………….….. .17  II.10 Decisiones bajo Incertidumbre………………………………….….19  II.11 Árboles de Decisión……………………………………………… ... 20

III. SISTEMAS DE INVENTARIOS

III.1  Introducción……………………….………………………………. 28

III.2 Técnica ABC………………………………………………………....29

III.3 Modelo d e Inventario generalizado………………………………..31

III.4 Modelos deterministas………………………………………..……..34

III.5 Modelos Probabilísticas……………………………………………..38

IV. PROYECTOS CON PERT_CPM

 IV.1Caso de Estudio: Construcción de un Complejo deportivo…………57

V. BIBLIOGRAFÍA  

 I. PROGRAMACIÓN LINEAL ENTERA

INTRODUCCION[pic 1]:

 El problema con la programación lineal entera, es que no existe un algoritmo rápido para hallar la solución. El método más frecuentemente utilizado, se llama el de ramificar y acotar y es una adaptación de la solución continua. Este algoritmo toma la solución del programa continuo y la divide en dos problemas si ésta no fue entera (si lo hubiera sido ya habríamos terminado, pero eso sólo sucede en las películas), cada uno con una restricción de más.  Por   ejemplo, si la solución continua fue X1 = 7.25, se dividiría en dos problemas, uno con la restricción X1<=7 y el otro con la restricción X1 >= 7 . Se encuentran las soluciones, para estos problemas y se comparan, le mejor gana; si no es entera se repite el proceso de nuevo. Como se puede ver, éste método consume muchos más recursos de máquina; en un problema de Planeación Agregada, con unas cien variables y unas sesenta restricciones, y algo de  mala suerte, se podrían estar resolviendo unos cuantos miles de problemas continuos asociados, y cada uno de estos podría consumir bastante tiempo. Tal vez con los nuevos estudios en métodos de punto interior, como el de Karmakar, se pueda derivar un método mucho más eficiente que el de ramificar y acotar.

A propósito, Solver utiliza ramificar y acotar para la programación lineal entera.

Resolver:

Max Z = 3 X1 + 4X2
               4 X1 + 2X2  <=  8
               2X1   + 5X2  <=  10       

X1, X2 enteros positivos.

Lo modelamos de igual manera que el ejemplo continuo, y en las restricciones especificamos que X1 y X2 son enteros. No es más.

[pic 2]

Y en las restricciones...

[pic 3]

Para los programas Lineales enteros es muy importante que Solver, esté debidamente configurado para un número suficiente de iteraciones, de tiempo,  de precisión y de convergencia, para esto ver los detalles de Solver.

[pic 4]EJEMPLO  DE RAMIFICACIÓN Y ACOTACIÓN

 A través d e un ejemplo de Programación Lineal entera mixta  aplicada a la Planeación Agregada se utilizara el siguiente  modelo matemático para explicar el algoritmo de Ramificar y Acotar:

Min Z = 800T1 +800T2 + 800T3+800T4+800T5+800T6 (el total de salarios en tiempo normal)

+200C1 +200C2+200C3+200C4+200C5+200C6 (el costo de contratar C empleados por mes)

+500D1 +500D2+500D3 +500D4 +500D5 +500D6 (el costo de despedir D empleados por mes)

+0.06i1 +0.06i2 +0.06i3 + 0.06i4 + 0.06i5+0.06i6 (costo de llevar inventario cada mes)

+7.5H1 +7.5H2 +7.5H3+7.5H4+7.5H5 +7.5H6 (costo de utilizar H horas extras en el mes)

Sujeto a:

   T1          - C1 +D1 = 70
    T2 - T1  -C2  +D2 = 0
    T3 - T2  -C3  +D3 = 0
    T4 - T3  -C4  +D4 = 0
    T5 - T4  -C5  +D5 = 0
    T6 - T5  -C6  +D6 = 0

I1 -  100T1  -  0.625 H1           =  1.000
I1 + 100T2  + 0.625 H2 - I2   = 10.000
I2 + 100T3  + 0.625 H3 - I3   = 12.000
I3 + 100T4  + 0.625 H4 - I4   =    8.000
I4 + 100T5  + 0.625 H5 - I5   =    6.000
I5 + 100T6  + 0.625 H6 - I6   =    5.000

H1 - 32T1 <= 0
H2 - 32T2 <= 0
H3 - 32T3 <= 0
H4 - 32T4 <= 0
H5 - 32T5 <= 0
H6 - 32T6 <= 0

En el contexto de este modelo las variables T representan el número de trabajadores que se deben tener en cada periodo (T1 en enero, T2 en febrero, ...), por lo tanto estas variables deben ser enteras. 

Árbol de Solución:

[pic 5]

Los números dentro de los círculos significan el orden de los pasos a seguir:

1. Resolver el problema Original Continuo. Z nos dio 332 620 pero las cuatro primeras variables nos dieron no enteras. Entonces toca ramificar por cualquiera de ellas... para no pensar mucho, escojamos siempre la primera de izquierda a derecha. En este caso ramificamos por T1 cuya respuesta original fue de 72.5 así es que resolveremos dos subproblemas, en uno le agregaremos a las restricciones que ya tiene la restricción T1<=72 y al otro la restricción T1 >= 73.  Podemos escoger cualquiera de las dos ramas para comenzar a solucionar y seguir... de nuevo para no pensar mucho, escojamos siempre la rama de la izquierda (no importa cuál se escoja, aunque el no de iteraciones es diferente según la rama, no hay forma de saber cuál es la más rápida, así es que aquí la escogimos por capricho esa).  Escogiendo la rama de la izquierda se solucionará el problema agregándole la restricción T1<=72 y se sigue en el paso 2.

2. Se solucionó el problema con Z =332 730 pero de la segunda a la cuarta variable no son enteras. Así es que debemos de nuevo ramificar... dijimos que escogeríamos primero la primera variable no entera de la izquierda a la derecha, en este caso T2. Si ramificamos por T2 resolveremos dos problemas uno con la restricción T2 <= 72 (rama izquierda) y el otro T2 >= 73 (rama derecha). Resolver rama izquierda

3. Resulta la rama izquierda Z = 332 958 y todas las variables enteras. Como todas las variables nos dieron enteras ya no se sigue ramificando por esa rama, es decir se agota esa rama, y como es la primera solución entera que hemos encontrado esta solución es la que va ganando con Z = 332 958 (anotamos en un papelito el valor de Z para que no se nos olvide). De ahora en adelante, cualquier rama que de un Z mayor que 332 958 no la seguimos ramificando, no nos interesaría por que como estamos minimizando no nos interesan valores más grandes del que ya obtuvimos. Claro que si llegamos a una solución entera más pequeña que esta, no nos dará ningún remordimiento olvidarla por completo y llevar esa como mejor. Como esta rama se agota pasemos a lo otra rama de T2>=73.

4. Se resuelve el problema con las restricciones que había en el paso 2  agregándole la restricción T2>= 73. Ojo! No las restricciones que habían en el paso 3, como la rama nace del paso 2 se tomarán esas más la de T2>= 73. Okay, al resolver da Z = 332 952 y todas las variables enteras. Como el Z es menor que el que teníamos como mejor de 332 958 nos olvidamos de ese otro y ahora tendremos como mejor el de 332 952 con T1=71, T2=73, T3=73, T4=73,T5=60,T6=50. Agotada toda la rama izquierda del problema original resolvemos la rama derecha agregándole la restricción T1>=73.

5. Se resolvió con Z = 332 976 y las variables de la 2 a la 4 dieron no enteras, pero no importa, no seguiremos ramificando por que el Z que dio es mayor que el que ya tenemos de 332 952.

Finalmente: 

Después de 5 iteraciones se encontró el óptimo con Z = 332 952 y T1=71, T2=73, T3=73, T4=73,T5=60,T6=50.

Este es un ejemplo minimizando. Para Maximizar lo único que cambia es que ya no se prefieren las Z más pequeñas sino las más grandes. 

                    II.    TEORÍA DE DECISIONES            

1.  INTRODUCCIÓN:

...