Metodos planos cortantes.

METODOS PLANOS CORTANTES.
Algoritmo de planos de corte
El concepto de plano de corte lo ilustraremos primero con un ejemplo. Considere el problema de progrmacion lineal entera:
Maximizar z = 7×1 + 9×2
Sujeto a:
-x1 + 3×2 <=6
7×1 + x2 <=35
x1, x2 enteros no negativos

La solución óptima (ignorando la condición discreta)se demuestra gráficamente en la siguiente figura.
Estadada por z = 63, x1 = 9/2 y x2 = 7/2, la cual no es entera.
La idea del algoritmo de planos de corte es cambiar el conjunto convexo del espacio de soluciones, de tal manera que los puntos extremos apropiados lleguen a ser todos enteros. Tales cambios en las fronteras del espacio de soluciones, deben proporcionar todavía conjuntos convexos. También este cambio deberá hacerse sin “partir” ningunade las soluciones enteras factibles del problema original. La figura muestra como dos restricciones secundarias (arbitrariamente elegidas) se agregan al problema proporcionando la solución óptima entera en el punto extremo nuevo (4, 3). Note que el área cortada del espacio de soluciones original no incluye ningún valor entero.

METODO DE RAMIFICAR Y ACOTAR.
Algoritmo de Ramificar y Acotar
Eneste momento será más conveniente explicar los fundamentos del algoritmo de ramificar y acotar (R y A), por medio de un ejemplo numérico:
Consideremos el siguiente problema de Programación lineal Entera:
Max z = 5×1 + 4×2
Sujeto a
x1 + x2 <=5
10×1 + 6×2 <=45
x1, x2 >= 0 y entero
En la siguiente figura se muestra el espacio de soluciones de la programación lineal enterarepresentado por los puntos. El espacio de soluciones de programación lineal asociado, programación lineal óptima, se define por cancelación de las restricciones enteras. La solución programación lineal óptima se da como x1 = 3,75, x2 = 1,25 y z = 23,75.
El procedimiento de Ramificar y Acotar se basa en tratar solo con el problema programación lineal. Como la solución óptima (x1 = 3,75, x2 = 1,25 yz = 23,75) pero no satisface la necesidad de valores enteros, el algoritmo de R y A exige “modificar” el espacio de soluciones lineales de forma tal que nos permita identificar, finalmente, para conseguir la solución óptima entera.
Primero seleccionaremos una de las variables cuyo valor corriente en la solución óptima no cumple el requisito de valor entero. Seleccionando x1=3,75 arbitrariamente,observamos que la región ( 3 < x1 < 4 ) del espacio de soluciones lineales, no puede incluir ninguna espacio solución factible entera. Entonces podemos modificar el espacio de soluciones lineales eliminando esta región no prometedora, lo que, en realidad, es equivalente a reemplazar el espacio original por dos espacios los PL1 y PL2, definidos de la manera siguiente:
1. Espacio PL1 =espacio PLO + (x1 <= 3)
2. Espacio PL2 = espacio PLO + (x1 >= 4)
Esta figura muestra los espacios PL1 y PL2 en forma grafica. Se ve que los dos espacios contienen los mismos puntos enteros factibles del modelo PLE. Esto significa que, desde el punto de vista del problema original de PLE, tratar con PL1 y PL2 es igual que tratar con el original PLO. La diferencia principal es que la selecciónde las nuevas restricciones e acotamiento ( x1 >= 3 y x1 <= 4 ) mejoraran la oportunidad de forzar a los puntos extremos óptimos de PL1 y PL2 hacia la satisfacción del requisito de valor entero. Además el hecho que las restricciones de acotamiento están en la “vecindad inmediata” del optimo continuo del PLO, incrementara las posibilidades de producir “buenas” soluciones enteras.
Lasnuevas restricciones x1 >= 3 y x1 <= 4 son mutuamente excluyentes, PL1 y PL2 deben tratarse como dos programas lineales separados. Esta dicotomía da lugar al concepto de ramificación en el algoritmo de R y A. En efecto, ramificar significa subdividir un espacio de soluciones corrientes en subespacios mutuamente excluyentes.
Aquí vemos las ramas PL1 y PL2 y x1 llamada variable de ramificación...