El Algoritmo De Plano De Corte

EL ALGORITMO DEL PLANO DE CORTE.

Para aplicar el método del algoritmo del corte:

Paso 1. Se encuentra el tableau óptimo para la relajación de la programación lineal. Si todas las variables de la solución optima asumen valores enteros, entonces a encontrado una solución optima para el PE (programación entera); en caso contrario se sigue el paso 2.

Paso 2. Se elige una restricción en el tableau óptimo de la relajación del PL (programación lineal) cuyo lado 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, escribir su lado derecho y cada coeficiente de las variables en la forma [x] + f, donde 0 ≤ f < 1.

Paso 2b. se vuelve a escribir la restricción generada por el corte como:

Todos los términos con coeficiente entero = todos los términos con coeficiente fraccionario.

Entonces el corte es: todos los términos con coeficiente fraccionario ≤ 0

Paso 3. Encuentre la solución óptima para el PL, con el corte como una restricción adicional, mediante el algoritmo simplex dual. Si todas las variables asumen valores enteros en la solución optima, ha encontrado una solución óptima para el PE.

En caso contrario, escoja la restricción cuyo lado derecho tenga la fracción mayor cercana a ½ y usarla para generar otro corte, el cual se suma el tableau. Continuar este proceso hasta obtener una solución en la cual las variables sean enteros. Esta será una solución óptima para el PE.

POR EJEMPLO:

z X1 X2 S1 S2 id

1 0 0 1.25 0.75 41.25

0 0 1 2.25 -0.25 2.25

0 1 0 -1.25 0.25 3.75

Se elige de modo arbitrario la segunda restricción, que es:

Se escribe los coeficientes de las variables y el lado derecho de las restricciones en la forma [x] + f, donde 0 ≤ f < 1.

Si todos los términos con coeficientes enteros se acomodan en el lado izquierdo y todos los términos con coeficientes fraccionarios en el lado derecho se tiene:

El algoritmo del plano de corte recomienda entonces sumar las restricciones siguientes al tableau óptima de la relajación del PL:

Lado derecho de:

O bien,

Esta restricción se llama un corte y tiene dos propiedades.

1. cualquier punto factible para el PE satisface el corte.

2. La solución óptima actual para la relajación del PL, no satisface el corte.

El efecto del corte se puede ver en la siguiente grafica:

Todos los puntos factibles para el (x1 = 3.75 y x2 = 2.25). Para obtener la grafica de corte se remplaza

...