Expo 7 programación entera (algoritmo de gomory)

1. PROGRAMACIÓN ENTERA “ Año del Centenario de Machu Picchu para el Mundo” CURSO: INVESTIGACIÓN DE OPERACIONES I JOSÉ FAUSTINO SÁNCHEZ CARRIÓN Facultad de Ingeniería EAP INGENIERÍA INDUSTRIAL ALUMNAS: BELLON PACHECO, GERALDINE MARLENI RAMIREZ MONTALVO , AYDA MARIBEL

2. PROGRAMACIÓN ENTERA EL MÉTODO DE PLANO CORTANTE O ALGORITMO DE GOMORY Igual que en el algoritmo de Ramificación y Acotamiento, el algoritmo de plano cortante también empieza en la solución óptima de la Programación Lineal. Ejemplo : Maximizar Z = 7X 1 + 10X 2 s.a : - X 1 + 3X 2 ≤ 6 7X 1 + X 2 ≤ 35 X 1 , X 2 ≥ 0 y entero

3. PROGRAMACIÓN ENTERA PASO 1: Resolver la solución optima primal: SOLUCIÓN: V. Básica X 1 X 2 X 3 X 4 Solución Z 63/22 31/22 66 1/2 X 1 1 7/22 1/22 3 1/2 X 2 1 -1/22 3/22 4 1/2 Así, las soluciones optimas para el problema serían: X 1 = 3 ½ X 2 = 3 ½ Z = 66 1/2 Pero esta solución no es óptima para el modelo de programación lineal entera.

4. PROGRAMACIÓN ENTERA PASO 2: Aplicando el Algoritmo : Tomamos arbitrariamente la Ecuación de X 2 : X 2 + 7 X 3 + 1 X 4 = 3 1 22 22 2 Se factoriza : Entonces el corte asociado es : X 2 + ( 0 + 7 ) X 3 + ( 0 + 1 ) X 4 = 3 + 1 22 22 2 - 7 X 3 - 1 X 4 + 1 ≤ 0 22 22 2 Agregando S 1 : - 7 X 3 - 1 X 4 + S 1 = - 1 22 22 2 , S 1 ≥ 0 (CORTE I)

5. PROGRAMACIÓN ENTERA Entonces la nueva tabla sería: V. Básica X 1 X 2 X 3 X 4 S 1 Solución Z 63/22 31/22 66 1/2 X 1 1 7/22 1/22 3 1/2 X 2 1 -1/22 3/22 4 1/2 S 1 -7/22 -1/22 1 -1/2 PASO 3: Aplicamos Dual Simplex para volver factible la solución : V. Básica X 1 X 2 X 3 X 4 S 1 Solución Z 1 9 62 X 2 1 1 3 X 1 1 1/7 - 1/7 4 4/7 X 3 1 1/7 - 22/7 1 4/7

6. Así, las soluciones optimas para el problema serían: X 1 = 4 4/7 X 2 = 3 Z = 62 Pero esta solución no es óptima para el modelo de programación lineal entera. Porqu e sigue existiendo variables fraccionarias. PASO 4: Aplicando otr a vez el Algoritmo : Seleccionamos X 1 : Entonces el corte asociado es : X 1 + ( 0 + 1 ) X 4 + ( -1 + 6 ) S 1 = 4 + 4 7 7 7 - 1 X 4 - 6 S 1 + S 2 = - 4 7 7 7 X 1 + 1 X 4 - 1 S 1 = 4 + 4 7 7 7 Se factoriza : , S 2 ≥ 0 (CORTE II) Agregando S 2 : - 1 X 4 - 6 S 1 + 4 ≤ 7 7 7

7. PROGRAMACIÓN ENTERA Entonces la nueva tabla sería: V. Básica X 1 X 2 X 3 X 4 S 1 S 2 Solución Z 1 9 62 X 2 1 1 3 X 1 1 1/7 - 1/7 4 4/7 X 3 1 1/7 - 22/7 1 4/7 S 2 - 1/7 6/7 1 - 4/7 PASO 5: Aplicamos Dual Simplex para volver factible la solución :

8. PROGRAMACIÓN ENTERA Con el Método Dual Simplex se obtiene el cuadro final: V. Básica X 1 X 2 X 3 X 4 S 1 S 2 Solución Z 3 7 58 X 2 1 1 3 X 1 1 -1 1 4 X 3 1 -4 1 1 S 2 1 6 -7 4 Así, las soluciones optimas para el problema serían: X 1 = 4 X 2 = 3 Z = 58