programacion lineal

PROGRAMACION LINEAL ENTERA BINARIA
 
 
Las situaciones en las que las decisiones aparecen como alternativas son las más frecuentes con las que nos enfrentamos. La noción de tipo binario la utilizamos en nuestros razonamientos y en nuestras acciones: todo o nada, blanco o negro, abierto o cerrado, existe o no existe, 0 o 1, verdadero o falso, prendido o apagado, muerto o vivo, entre otros. Los dos métodos más usuales para solucionar problemas de Programación Lineal Entera Binaria son Enumeración Implícita Cero – Uno y Método Aditivo de Egon Balas.

MÉTODO DE ENUMERACIÓN IMPLÍCITA CERO – UNO
 
El método de Enumeración Implícita Cero – Uno consiste en enumerar todas las soluciones y analizarlas; se entiende que este proceso es bastante dispendioso, sobre todo si se tiene un númeroapreciable de variables, ya que el número de combinaciones corresponde a 2n, donde n es el número de variables del problema. Ejemplo:
MAX Z = 3 Y1 + 2 Y2– 5 Y3 – 2 Y4 + 3 Y5
Con sus restricciones:

Para nuestro caso el número de combinaciones es 2 = 32, que corresponde a la cantidad de soluciones posibles:
 
Y1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
00
0
0
0
0
0
Y2
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
Y3
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
Y4
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
Y5
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
01
0
1
0
1
0
 
En el tablero anterior algunas soluciones son válidas, mientras que otras no porque en algunos casos violan una, unas o todas las restricciones. Solución Optima: Y*1 = 1; Y*2 = 1; Y*3 = ; Y*4 = 0; Y*5 = 0; Z* = 5

METODO ADITIVO (ENUMERACION) DE EGON BALAS
 
Este método es un procedimiento de enumeración que encuentra el óptimo en forma más rápida; en el método de Balas,la eficacia consiste en la evaluación solo de unas soluciones. El método empieza poniendo todas las variables iguales a cero y luego por medio de un procedimiento sistemático de forma consecutiva se asigna a una por una de las variables el valor 1. Luego se reemplaza en cada una de las restricciones y se averigua la infactibilidad. Por esta razón el método es algunas veces llamado el algoritmoaditivo.
Para describir el algoritmo, se considera la forma general siguiente de un problema de Programación Lineal con variables cero – uno:
Paso 1. La función objetivo debe ser del tipo minimización, con todos los coeficientes no negativos.
Paso 2. Todas las restricciones deben ser del tipo £, con los lados derechosnegativosde ser necesario. Luego, estas restricciones se convierten aecuaciones, usando las variables auxiliares en el lado izquierdo de las restricciones. Ejemplo:
MAX Z = 3 Y1 + 2 Y2– 5 Y3 – 2 Y4 + 3 Y5
Sujeta a:

MIN W = – 3 Y1 – 2 Y2 + 5 Y3 + 2 Y4– 3 Y5
Con sus restricciones:

Reemplazamos: Y1 = 1 – X1; Y2 = 1 – X2; Y3 = X3; Y4 = X4; Y5 = 1 – X5
MIN W´ = 3 X1 + 2 X2 + 5 X3 + 2 X4 + 3 X5 – 8
Sujeta a:

Sustituimos W´ + 8 = W
MIN W = 3 X1 + 2 X2 + 5 X3 + 2 X4+ 3 X5
Con sus restricciones:

Siempre el problema nuevo a resolver consiste en la minimización de la función objetivo, teniendo en cuenta la medida de la no factibilidad de la holgura. Cuando la infactibilidad da el menor valor, continuamos con el siguiente paso; en el caso de una infactibilidad cero, ésta corresponde a la solución óptima; si encontramos varias infactibilidades iguales a cero,reemplazamos en la función objetivo y la respuesta será la que haga esta función mínima.
 
X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0 1; 0 – 2; 0 – 1; Infactibilidad 3
X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0 2; 0 5; 0 – 12; Infactibilidad 12
X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0 2; 0 – 2; 0 5; Infactibilidad 2
X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0 0; 0 – 5; 0 – 1; Infactibilidad...