Ramificacion Y Acotamiento

RAMIFICACIÓN Y ACOTAMIENTO

IDEA: Como al resolver un modelo por método Simplex, casi siempre las soluciones son no enteras, se aproximan los valores no enteros de cada variable y se vuelve a resolver hasta encontrar una solución entera que satisfaga todas las condiciones.

VENTAJA: Sirve para todos los modelos PLEB y PLEG

DESVENTAJAS:

Tiempo: Toma tiempo resolver un solo modelo por método Simplex. Pero eso es solo en el mejor caso. En el peor caso no se puede determinar cuántos modelos se resuelven por método Simplex hasta llegar a una solución entera.

Valor menor al óptimo: El valor que se obtiene por el método de ramificación y acotamiento casi siempre es menor al valor obtenido en el método Simplex para el caso no entero.

PRODECIMIENTO:

1) Se tiene un modelo de programación lineal entera.

2) Escoja un criterio de selección del subproblema a resolver. Ese criterio será utilizado en toda la resolución por ramificación y acotamiento. Se tienen dos criterios:

a) Subproblema más reciente: Escoger siempre nodo correspondiente al último modelo resuelto.

b) Mejor cota: Escoger el nodo con el valor mayor de la cota. Si los dos nodos empatan en la cota, escoger uno arbitrariamente.

Para este caso, se escogió el criterio de mayor cota.

3) Escoja un criterio de selección de la variable no entera a acotar. Se tienen 3 criterios:

a) Orden natural: Desde la primera hasta la última variable de decisión, encontrar la primera ocurrencia de valor no entero y acotarla.

b) Valor con la parte decimal más cercana a 0.5. Si 2 o más variables empatan en tener la parte decimal más cercana a 0.5, escoger una arbitrariamente.

c) Variable que participa en la mayor cantidad de restricciones. Si 2 o más variables empatan en participar en la mayor cantidad de restricciones, escoger una arbitrariamente.

Para este caso, se escogió el criterio de “Orden Natural”.

4) Se resuelve el modelo por método Simplex tratándolo como si fuera un modelo de programación lineal no entera. Para ello se deben agregar las restricciones Xi > 0 y Xi < 1 i. La solución obtenida al modelo resultante para el caso del modelo de arriba es: X1 = 5/6, X2=1, X3=0, X4=1, Z* = 16 ½.

5) Se crea un nodo enumerado con un cero y al lado de él se anota:

a) El último valor óptimo PLEB o PLEG encontrado. Como en este caso no se ha encontrado una solución PLEB al modelo de arriba, se coloca z* = ∞.

b) Los valores de la solución obtenida en el modelo. En este caso, se debe anotar:

c) El valor de z obtenido con . En este caso es 16 ½

d) La cota, la cuál es el valor de z redondeado hacia abajo.

6) Si

...