407242
Description
Mind Map by karycastro1226, updated more than 1 year ago
|
Created by karycastro1226
almost 11 years ago
|
|
PROGRAMACIÓN LINEAL ENTERA Y BINARIA
- 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.
- 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.
- Algoritmo
- Éste método sirve para solucionar
problemas de más de dos (2) variables
- 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.
- 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.
- 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
- SE BASA
- 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).
- 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
- 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
- Algoritmo
- Es una estrategia sistemática, que reduce
mucho el número de combinaciones que se
deben examinar.
- 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
- Si X1 = 1 y X2 = X3 = X4 = X5 = 0
- EJEMPLO
- 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.
Want to create your own Mind Maps for free with GoConqr? Learn more.