Algoritmo De Plano De Corte

Algoritmo del Plano Cortante
Resumen del algoritmo.
Paso1: Encuentre el tablero optimo para la relajación de la programación lineal. Si todas las variables de las variables de la solución optimaasumen valores enteros, entonces ha encontrado una solución optima para el PE; en caso contrario, siga con el paso 2.
Paso 2: Elija una restricción en el tablero optimo de la relajación del PL cuyolado derecho tiene la parte fraccionaria mas cercana a ½. Esta restricción se usa para generar un corte.
Paso 2a: En el caso de la restricción identificada en el paso 2, escriba su lado derecho ycada coeficiente de las variables en la forma [x] + ƒ , donde 0 ≤ ƒ < 1.
Paso 2b: Vuelva a escribir la restricción usada para generar corte como:
Todos los términos con coeficientes entero = todoslos términos con coeficiente fraccionario
Entonces el corte es
Todos los términos con coeficiente fraccionario ≤ 0
Paso 3: Encuentre la solución optima para la relajación optima del PL, con, conel corte como una restricción adicional, mediante el algoritmo simplex dual. Si todas las variables asumen valores enteros en la solución optima para el PE. En caso contrario, escoja la restriccióncuyo lado derecho tenga la fracción mayor cercana a ½ y úsela para generar otro corte, el cual se suma al tablero. Continúe con este proceso hasta que obtenga una solución en la cual todas lasvariables sean enteros. Esta será una solución optima para el PE.
Ejemplo:
Maximizar Z = 7x1 + 10x2
Sujeto a: -x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x1, x2 ≥ 0 y entero

Desarrollo AlgebraicoMaximizar Z = 7x1 + 10x2
Sujeto a: -x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x1, x2 ≥ 0 y entero

Resolución:
Estandarizando:Maximizar Z = 7x1 + 10x2 + 0x3 + 0x4
Sujeto a: -x1 + 3x2 + x3 = 6
7x1 + x2 + x4 = 35
x1, x2, x3, x4 ≥ 0 y entero...