EJERCICIO PROGRAMACIÓN ENTERA BINARIA
RICHARD MONTILLA 20031020121
JORGE RIVEROS 20041020039
JUAN DAVID FRANCO 20042020031
MIGUEL MOJICA 20042020060
OBJETIVO:
Reconocer, plantear y solucionar problemas sobre programación entera binaria, teniendo en cuenta
los conceptos básicos de la teoría facilitando el aumento de la capacidad en la resolución de
problemas sobre programación entera.
ENUNCIADO:
Resolver el siguiente problema de PEB a través del método aditivo de Egon Balas.
MAX Z = 3Y1+ 2Y2- 5Y3- 2Y4+3Y4
Sujeta a:
1. Y1 + Y2 + Y3 + 2Y4 + Y5 ≤ 4
2. 7Y1 + 3Y3 – 4Y4 + 3Y5 ≤ 8
3.11Y1 – 6Y2 + 3Y4 – 3Y5 ≥ 3
Y1, Y2, Y3, Y4, Y5 = (0 o 1)
CONCEPTOS CLAVE:
Programación entera binaria, método aditivo de Egon balas.
SOLUCIÓN:
PASOS PROCEDIMIENTO
Paso1. La función objetivo debe ser del tipo MIN W = -3Y1 – 2Y2 + 5Y3 + 2Y4 – 3Y5
minimización, con todos los coeficientes no
negativos Reemplazamos: Y1= 1 – X1; Y2 =1 – X2; Y3 =
X3; Y4 = X4; Y5=1-X5
Y nos queda:
MIN W’ = 3X1 + 2X2 + 5X3 +2X4 +3X5 – 8
Paso2. Todas las restricciones deben ser del 1. Y1 + Y2 + Y3 + 2Y4 + Y5 ≤ 4
tipo ≤, con los lados derechos negativos de 2. 7Y1 + 3Y3 – 4Y4 + 3Y5 ≤ 8
ser necesario. Luego, estas restricciones se 3.-11Y1 + 6Y2 - 3Y4 + 3Y5 ≤ 3
convierten a ecuaciones, usando las Y1, Y2, Y3, Y4, Y5 = (0 o 1)
variables auxiliares en el lado izquierdo de Reemplazando como en el paso anterior nos
las restricciones. queda:
1. –X1 - X2 + X3 + 2X4 - X5 ≤ 1
2. -7X1 + 3X3 – 4X4 – 3X5 ≤ -2
3. 11X1 – 6X2 -3X4 – 3X5 ≤ -1
X1, X2, X3, X4, X5 = (0 o 1)
Paso 3. Sustituimos W’ + 8 = W, para que la MIN W = 3X1 + 2X2 + 5X3 +2X4 + 3X5
funcion objetivo no quede con una constante
suelta y ademas se añade a las restricciones Con sus restricciones:
unas variables de holgura con respecto a
este cambio. 1. –X1 – X2 + X3 + 2X4 – X5 + S1 ≤ 1
2. –7X1 + 3X3 – 4X4 – 3X5 +S2 ≤ -2
3. 11X1– 6X2 –3X4 – 3X5 +S3 ≤ -1
X1, X2, X3, X4, X5 = (0 o 1)
Paso 4. Siempre el problema nuevo a X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
resolver consiste en la minimización de la 0 ≤ 1; 0 ≤ -2; 0 ≤ -1; Infactibilidad 3
función objetivo, teniendo en cuenta la X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
medida de la no factibilidad de la holgura. 0 ≤ 2; 0 ≤ 5; 0 ≤ -12; Infactibilidad 12
Cuando la infactibilidad da el menor valor, X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
continuamos con el siguiente paso; en el 0 ≤ 1; 0 ≤ -2; 0 ≤ 5; Infactibilidad 2
caso de una infactibilidad cero, esta X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
corresponde a la solución óptima; si 0 ≤ 0; 0 ≤ -5; 0 ≤ -1; Infactibilidad 6
encontramos varias infalibilidades iguales a X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
cero, reemplazamos en la función objetivo y 0 ≤ -1; 0 ≤ 2; 0 ≤ 2; Infactibilidad 1
la respuesta será la que haga esta función X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
mínima. 0 ≤ 2; 0 ≤ 1; 0 ≤ 2; Infactibilidad 0
Paso 5. Teniendo la solución óptima para la Solución Optima Unica:
función modificada hallamos el de la función
objetivo original. X*1 = 0; X*2 = 0; X*3 = 0; X*4 = 0; X*5 = 1; W* = 3
Solución Optima Única para el problema original:
Y*1 = 1; Y*2 = 1; Y*3 = 0; Y*4 = 0; Y*5 = 0; Z* = 5
CONCLUSIÓN: El método aditivo de Egon Balas permite resolver de forma eficiente los problemas
de programación entera binaria, los cuales son de aparición frecuente en el campo de la ingeniería.
BIBLIOGRAFÍA
CASTILLO. Enrique, Formulación y Resolución de Modelos de Programación Matemática en
Ingeniería y Ciencia, Pág. 574, 2002.
