Metodo de planos cortantes

Método de planos cortantes.

Como en el algoritmo de ratificación y acotamiento, el del plano cortante también se inicia en la solución optima del programa lineal continuo. Al espacio desoluciones se agregan restricciones especiales, llamadas cortes, en una forma que produzca un punto extremo entero.

Maximizar Z = 7 X1 + 10 X2
S.A. - X1 + 3 X2 ≤ 6
7 X1 + X2≤ 35
X1, X2 ≥ 0 y enteras.

El algoritmo del plano de corte modifica el espacio de soluciones agregando cortes que producen un punto extremo entero óptimo. La siguientefigura muestra un ejemplo de dos cortes de esos. Se parte del óptimo del programa lineal continuo, Z = 66 ½, X1 = 4 ½ , X2 = 3 ½, a continuación se agrega el corte I, que produce la solución linealoptima continua Z= 62, X1 = 4 [pic], X2 = 3. A continuación se agrega el corte II, que junto con el corte I y las restricciones originales, llega al optimo del programa lineal Z = 58, X1 = 4, X2 =3. La última solución es entera, que era lo que se buscaba.

Los cortes agregados no eliminan alguno de los puntos enteros factibles originales, pero deben pasar por al menos un punto entero,factible o no factible. Estos son los requisitos básicos de cualquier corte.
Ahora se usara el mismo ejemplo para indicar como se determinan los cortes y se implementan algebraicamente.
Dadas las holgurasX3 y X4 para las restricciones 1 y 2, el cuadro óptimo del problema lineal es:

|Básica |X1 |X2 |X3 |X4 |Solución.|
|Z |0 |0 |63/22 |31/22 |66 ½ |
|X2 |0 |1|7/22 |1/22 |3 ½ |
|X1 |1 |0 |-1/22 |3/22 |4 ½ |...