• Author / Uploaded
• Jackson Cardenas

Citation preview

EJERCICIO PROGRAMACIÓN ENTERA BINARIA RICHARD MONTILLA JORGE RIVEROS JUAN DAVID FRANCO MIGUEL MOJICA

20031020121 20041020039 20042020031 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 Paso1. La función objetivo debe ser del tipo minimización, con todos los coeficientes no negativos

PROCEDIMIENTO MIN W = -3Y1 – 2Y2 + 5Y3 + 2Y4 – 3Y5 Reemplazamos: Y1= 1 – X1; Y2 =1 – X2; Y3 = X3; Y4 = X4; Y5=1-X5 Y nos queda:

Paso2. Todas las restricciones deben ser del tipo ≤, con los lados derechos negativos de ser necesario. Luego, estas restricciones se convierten a ecuaciones, usando las variables auxiliares en el lado izquierdo de las restricciones.

MIN W’ = 3X1 + 2X2 + 5X3 +2X4 +3X5 – 8 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) Reemplazando como en el paso anterior nos 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 funcion objetivo no quede con una constante suelta y ademas se añade a las restricciones unas variables de holgura con respecto a este cambio.

Paso 4. 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, esta corresponde a la solución óptima; si encontramos varias infalibilidades iguales a cero, reemplazamos en la función objetivo y la respuesta será la que haga esta función mínima. Paso 5. Teniendo la solución óptima para la función modificada hallamos el de la función objetivo original.

MIN W = 3X1 + 2X2 + 5X3 +2X4 + 3X5 Con sus restricciones: 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)  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 ≤ 1; 0 ≤ -2; 0 ≤ 5; Infactibilidad 2  X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0 0 ≤ 0; 0 ≤ -5; 0 ≤ -1; Infactibilidad 6  X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0 0 ≤ -1; 0 ≤ 2; 0 ≤ 2; Infactibilidad 1  X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0 0 ≤ 2; 0 ≤ 1; 0 ≤ 2; Infactibilidad 0 Solución Optima Unica: 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.