UNJFSC- FACULTAD DE INGENIERIA-INVST. OPERACIONES

EJEMPLO APLICATIVO DE RAMIFICACIN Y ACOTAMIENTOUna oficina de correos necesita un nmero diferente de empleados de tiempo completo, para diferentes das de la semana. El nmero de empleados de tiempo completo requeridos para cada da, se da en la tabla adjunta. Las reglas sindicales sealan que cada empleado de tiempo completo, tiene que trabajar durante cinco das consecutivos y, despus descansar dos das. Por ejemplo, un empleado que trabaja de lunes a viernes, tiene que descansar el sbado y domingo. L a oficina de correos requiere cumplir con sus requerimientos diarios y utilizar solamente empleados el tiempo completo. Formule un PL que pueda utilizar la oficina de correos para minimizar el nmero de empleados de tiempo completo que hay que contratar.N EMPLEADOS DE TIEMPO COMPLETO

Dia 1= Lunes17

Dia 2= Martes13

Dia 3= Miercoles15

Dia 4= Jueves19

Dia 5= Viernes14

Dia 6= Sabado 16

Dia 7= Domingo11

PASO 1:Definir las variables Xi= el numero de empleaddos que trabajan el dia i.Este razonamiento lleva a la siguiente funcion obejtiva:Min Z= X1+X2+X3+X4+X5+X6+X7Para que la oficina de correos tenga sufiientes empleados de tiempo completo trabajando cada dia, simplemente aade las restricciones xi0 (i=1,2,.7) tenemos el siguiente P.L.Min Z= X1+X2+X3+X4+X5+X6+X7s.a.X1 17 X213 X315 X4 19 X514 X616 X711 Xi0 (i=1,2,,7)Hay por menos dos fallas en este planteamiento. Primero, la funcion objetivo no es el numero de empleados de tiempo completo de la oficina de correos. La funcion objetivo actual cuenta cinco veces al mismo empleado, no una sola vez. Por ejemplo cada empleado que empieza a trabajar el lunes, tambien trabajara del martes al viernes, y esta incluido en X1,X2,X3,X4,X5. Segundo, las variables X1, X2. X7, se relacionan entre si, y la interrelacion entre las variables no se expresa en el conjunto actual de restricciones. Por ejemplo, algunas personas que trabajan el lunes (la gente X1) tambien trabajaran el martes. Esto implica que X1 y X2 estan relacionadas, pero nuestras restricciones no indican que el valor de X1 influye en el valor de X2.Xi= numero de empleados que empiezan a trabajar el dia i.La solucion optima para este PLZ= 67/3X1=4/3X2=10/3X3=2X4=22/3X5=0X6=10/3X7=5

Sin embargo, ya que solamente se admiten empleados de tiempo completo, las variables tienen que ser numeros enteros, con lo que la suposicion de la divisibilidad no se satisface. Al inentar obtener una respuesta razonable usaremos la programacion entera.

PROGRAMACION ENTERAEJEMPLO APLICATIVO DE RAMIFICACIN Y ACOTAMIENTOMin Z= X1+X2+X3+X4+X5+X6+X7S.A.X1 +X4+X5+X6+X717 ( Restriccion del lunes)X1+X2 +X5+X6+X713( Restriccion del martes)

X1+X2+X3 +X6+X715( Restriccion del miercoles)

X1+X2+X3+X4+ X719( Restriccion del jueves)

X1+X2+X3+X4+X5 14( Restriccion del viernes)

X2+X3+X4+X5+X616( Restriccion del sabado)

X3+X4+X5+X6+X711( Restriccion del domingo)PASO: 1Solucin del problema relajado.Z= 22.33X1=6.33X2=5.33X3=2X4=22/3X5=0X6=10/3X7=5Observamos que no todas las variables son enteras, as que procedemos con el mtodo.PASO: 2Elegimos la variable no entera.X1=6.33PASO: 3Ahora es ramificado en 2 nuevos problemas con la restriccin adicional de respecitvamente.Ahora veremos de forma grfica en la siguiente hoja para que se pueda apreciar mejor.P0

Z= 22.33X1=6.33X2=5.33X3=2X4=22/3X5=0X6=10/3X7=5

P2

P1

Observamos que la solucin no entera P1 sale 22.33 pero la solucin entera P2 sale 23 como se busca minimizar, tenemos que volver a ramificar para obtener el resultado ms aproximado a P0, escogemos el que tiene el mximo valor de la funcin objetivo en este caso P1.P1

P4

No factibleP3

P3

P6

No factibleP5

P5

P8

P7

P9

NO FACTIBLEP12

NO FACTIBLEP11

NO FACTIBLEP10

P10

P14

No factibleP13

No factible

1Garboza Gonzalo rosa