PROGRAMACIÓN LINEAL ENTERA Y BINARIA

PROGRAMACIÓN LINEAL ENTERA Y BINARIA

1. Método de los planos cortantes de Gomory

   • Éste método sirve para solucionar problemas de más de dos (2) variables
     • Algoritmo
       • 1. Encontrar la solución, empleando el método simplex. 2. Si la solución es entera, entonces estamos en el óptimo. 3. Si no es entera, introducir una restricción nueva para la variable no entera, que tenga la mayor parte fraccional (Quebrar empates arbitrariamente) y resolver el nuevo problema mediante el método dual simplex.

2. Método Aditivo de Egon Balas para problemas binarios (0,1)

   • No confundir éste método para solucionar problemas de asignaciones, aquí el problema de programación lineal tiene la forma general y lo diferente es que las variables solo pueden tomar valores binarios (0,1).
     • SE BASA
       • pensar que si se tiene una función objetiva minimizando y todos sus términos so positivos, entonces, entre menos variables tomen el valor de uno (1), la función objetiva será minimizar
         • 1. La función objetivo se minimiza, en caso de maximización, use la regla de equivalencia: Maximizar (Z) = Minimizar (-Z). 2. Se requiere que Cj > 0 , ∀j . En caso de que Cj < 0 , entonces Xj se sustituye por: XJ = 1 - X j , es decir X j es el complemento.

3. Método de Bifurcación y Acotación (Branch And Bound)

   • Es una estrategia sistemática, que reduce mucho el número de combinaciones que se deben examinar.
     • Algoritmo
       • 1..Encontrar la solución mediante el Método Simplex. Si la solución no es entera, pase al segundo punto. 2. Comienza con la solución óptima del simplex en donde se ignoran las restricciones de variables enteras

4. Aplicación del Método de Egon Balas

   • Evaluamos cada restricción, primeramente suponiendo que todas las variables valgan cero, y después, alternativamente a cada variable le asignamos el valor de uno (1) y al resto de variables el valor de cero (0). Cada vez que una solución no satisfaga una restricción, el que tan lejos está de satisfacerla, lo llamamos infactibilidad.
     • EJEMPLO
       • Si X1 = 1 y X2 = X3 = X4 = X5 = 0