Programación Lineal Entera

ALGORITMO DE BIFURCAICON Y ACOTAMIENTO O BRANCH AND BOUND

Se trata de un problema lineal con la misma función objetivo y restricciones que el modelo original, pero al que se han relajado la condición de que todas o algunas de las variables de decisión sean enteras. Si la solución así obtenida es entera, habremos encontrado la solución del modelo de programación lineal entera. En casocontrario (el más frecuente), la solución así obtenida es una primera aproximación a la solución del modelo.

Ramificación

Se trata de añadir restricciones al modelo que fuercen a que una de las variables sea entera. Esto se consigue añadiendo una de estas dos restricciones para alguna de las variables Xi que no sea entera en la solución obtenida inicialmente:

Redondeo por defecto:imponemos que la variable Xi sea inferior o igual a la parte entera del valor de esa variable lineal Xi con las restricciones obtenidas hasta el momento. Esto equivale a añadir la restricción:

Xi  XBi

Redondeo por exceso: imponemos que la variable Xi sea mayor o igual al entero inmediatamente superior del valor Xi. Esto equivale a añadir la restricción:

Xi XBi + 1

Seguidamente,procederemos a resolver mediante el método símplex dos problemas lineales. El primero, además de las restricciones que pudiera tener de etapas anteriores, llevará incorporada la restricción de redondeo por defecto incorporada en esta etapa. El segundo se diferenciará del primero en que incluirá la restricción de redondeo por exceso, en vez de la de redondeo por defecto.

Acotamiento

Más arribase mostró que la solución óptima del modelo de programación lineal entera se encuentra dentro de la región factible. Esto significa que, para un problema de máximo, el óptimo del programa entero será menor o igual que el óptimo del problema lineal asociado. Al hacer la ramificación, hemos encontrado dos alternativas posibles para obtener la solución entera. Los valores óptimos de la funciónobjetivo Z de cada uno de los programas lineales resueltos en la primera bifurcación serán una cota superior de las posibles soluciones que obtengamos mediante posteriores ramificaciones a partir de ese modelo. En consecuencia, sólo tendrá sentido continuar con el procedimiento de ramificación a partir del problema lineal que tenga la mayor Z de los dos. Siguiendo la otra ramificación,obtendremos soluciones enteras con valores de Z inferiores, con toda seguridad, a los que obtendríamos con la otra ramificación, y por tanto sub óptimos.

Este hecho nos marca, además, cuándo debemos detenernos en la exploración de soluciones enteras:

Cuando el problema escogido tenga una solución con todas las variables enteras. Por ser el valor de la función objetivo una cota superior delóptimo, cualquier otra solución entera que pudiéramos explorar sería sub óptima, y por lo tanto no vale la pena seguir explorando.

¿Cuál será la solución óptima del modelo de programación entera? No necesariamente la obtenida en la última etapa, sino la solución entera con mayor valor de función objetivo de las obtenidas en el proceso.

Puede suceder que alguna de las ramificaciones abandonadascondujera a una solución entera que en aquel momento tuviera un valor de Z inferior al de la otra ramificación, pero mayor que la Z obtenida al final.

Seguidamente se muestran los pasos a seguir.

Un primer paso para la resolución de un modelo de programación lineal entera es resolver, mediante el método símplex, el problema lineal asociado.

Escoger una variable básica cuyo valor enla solución no sea entero. Al ramificar, a los nuevos problemas al primero se le añade la restricción

Xi  XBi

Y al segundo

Xi XBi + 1

Para la acotación, de los dos problemas escoger aquel que de cómo resultado el mayor valor de la función objeto.

Se reinicia el proceso hasta dar con la solución óptima. Que será el que de cómo resultado el mejor valor de la función objeto....