motul

Programación entera:
Algoritmo de corte
En cada etapa de bifurcación, en el algoritmo de bifurcación y acotación, la región factible actual (para el programa actual, no tomando en cuenta las restricciones de enteros) se corta en dos regiones mas pequeñas (una de las cuales puede ser vacía), debido a la imposición de dos nuevas restricciones derivadas de la primera aproximación al programaactual. Esta división es tal, que la solución optima al programa actual debe aparecer como la solución optima a uno de los dos nuevos programas (problema 6-8).Los algoritmos de corte del presente capitulo operan esencialmente de este modo, con la única diferencia de que se agrega solo una nueva restricción en cada etapa, por lo que la región factible disminuye sin dividirse.

Algoritmo de GomoryLas nuevas restricciones se determinan mediante el siguiente procedimiento de 3 pasos-
Paso 1.- en el tableau simplex final actual, selecciónese una cualquiera de las variables no enteras y sin asignar valores cero a las variables que no sean básicas considérese la ecuación de restricción representada por el renglón de la variable elegida.
Paso 2.- rescríbase cada coeficiente y constantefraccionarios de la ecuación de restricción obtenida en el paso 1. Como la suma de un entero y una fracción positiva entre 0 y 1. Escríbase ahora la ecuación en formar que el lado izquierdo contenga solamente términos con coeficientes fraccionarios ( y una constante fraccionaria), mientras que el lado derecho contendrá solo los términos con coeficientes enteros ( y una constante entera)
Paso 3.- hágaseque el lado izquierdo de la nueva expresión de la ecuación no sea negativo. La desigualdad resultante es la nueva restricción.

Consideraciones para los cálculos
Se ahorra tiempo en los cálculos, si se anexa la nueva desigualdad de restricción obtenida en el paso 3 a las ecuaciones de restricción descritas en el trableau simplex final actual, en vez de hacerlo con las restriccionesalgebraicamente equivalentes dadas en el programa original.
El algoritmo de corte de Gomory puede no ser convergente; es decir, que puede no obtenerse una solución entera a pesar del número de iteraciones. Sin embargo, por lo general el algoritmo converge y esto sucede razonablemente rápido, por este motivo, a menudo se establece, antes de iniciar los cálculos, un limite superior al numero de iteracionesque se realizara. Si no se obtiene la solución entera dentro de esta cota, se abandonara el algoritmo.
No existe razones teóricas para elegir el algoritmo de Gomory y bifurcación y acotación, el algoritmo de bifurcación y acotación es el mas favorecido en la practica.

Problemas Resueltos
Maximícese Z= 2X1 + X2
Con las Condiciones: 2X1 + 5X2 ≤ 17
3X1 +2X2 ≤ 10
Con: X1 y X2 no negativos y enteros


X1
X2
X3
X4


X3
0
11/3
1
-2/3

31/3
X1
1
2/3
0
1/3

10/3
ᵶ
0
1/3
0
2/3

20/3
Tableau 1

X1
X2
X3
X4
X5


X3
0
0
1
-5/2
11/6

17/2
X1
1
0
0
0
1/3

3
X2
0
1
0
½
-1/2

½
ᵶ
0
0
0
1/21/6

13/2
Tableau 2
La primera aproximación al programa (1), por lo tanto, es X1 =10/3, X3 =31/3, X2 =X4 =0, X1 yX3 son ambas, no enteras. Seleccionando arbitrariamente X1, se considera la restricción representada por el segundo renglón del tableau 1, renglón que define a X1, esto es:
X1 + ⅔ x2 + ⅓ x4 = 10/3
Escribiendo cada fraccióncomo la suma de un entero y una fracción entre 0 y 1, se tiene:
X1 + (0 + ⅔ ) X2 + (0 + ⅓ ) x4 = 3 + ⅓ o ⅔ X2 + ⅓ X4 - ⅓ - X1
Haciendo que ele lado izquierdo de esta ecuación sea no negativa, se obtiene:
⅔ x2 + ⅓ x4 - ⅓ ≥ 0 o 2x2 + x4 ≥ 1
Como la nueva restricción. Escribiendo ahora las restricciones...