Ramificar y Acotar: Programación Lineal Entera Ejemplo 1

Algoritmo de Branch And Bound  (Ramificar y Acotar) Para la Programación Lineal Entera

 

En la sección de Programación Matemática en Excel se dio un ejemplo de Programación Lineal Mixta aplicada a la Planeación Agregada, aquí utilizaremos el mismo modelo matemático pata explicar el algoritmo de Ramificar y Acotar.
 
Resolver el Programa Matemático:
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                    :

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.

Hemos acabado.

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. Obvioooooooo.

 

Bueno, espero ser lo suficientemente claro.
Saludos,
- Jairo.


Contenido :

Social