• Author / Uploaded
• Jason Brody

Citation preview

Universidad Distrital Francisco José de Caldas Proyecto Curricular Ingeniería de Sistemas Investigación de Operaciones II Grupo 9 1 de septiembre de 2016 Investigación de operaciones 2 Programación Entera Binaria (PEB) Objetivo Obtener una solución óptima mediante el uso del método Aditivo de Egon Balas, describiendo todo el proceso que implica su desarrollo. Practicar el método aditivo de Egon Balas para que cuando en un futuro tengamos la necesidad de tomar una decisión podamos utilizar el método de programación entera binaria. Enunciado:

Min: Z=2 X 1 +3 X 2 +4 X 3 +4 X 4 +5 X 5+ ¿

6 X 6 +7 X 7+ 8 X 8

s . a. 4 X 1 +4 X 2 +3 X 3 +4 X 4 +6 X 5 +8 X 6 +5 X 7 + 9 X 8 ≥ 3 2 X 1+ 2 X 2+ 3 X 3+ 2 X 4 +5 X 5 + 4 X 6 +3 X 7 + X 8 ≥ 2 X6+ X8≥ 1 X 1− X 2−X 7 ≤ 0 −X 3 + X 5

≤0

X i= { 0,1 }∨i=1,2,3,4,5,6,7,8 Método utilizado: Aditivo de Egon Balas. Conceptos Claves Programación entera Binaria: En algunas situaciones nos encontramos con problemas que requieren la toma de decisiones, como por ejemplo construir o no una fábrica, tomar o no cierto riesgo, etc. Es en esos casos donde se debe formular el problema en forma de programación lineal binaria. Egon Balas: Consiste en resolver un modelo de minimización con coeficientes positivos en la función objetivo, de manera que se utilice el menos número de variables a fin de minimizar el valor óptimo de la función objetivo. Infactibilidad: Se llamará infactibilidad el intervalo que produce una solución aplicada sobre una restricción, o un conjunto de éstas, y mide la distancia de la solución sobre un resultado factible. El intervalo será infactible si es negativo.

PASOS Lo primero que hay que verificar es que la función objetivo sea de tipo Minimización de lo contrario se deben aplicar reglas de equivalencia, en ese orden de ideas para las restricciones que no sean de tipo

≤

SOLUCIÓN PROCEDIMIENTO Nuevas restricciones:

−4 X 1 −4 X 2−3 X 3−4 X 4−6 X 5−8 X 6−5 X 7−9 X 8 ≤−3 −2 X 1 −2 X 2−3 X 3−2 X 4−5 X 5−4 X 6−3 X 7−X 8 ≤−2 −X 6− X 8 ≤−1 X 1− X 2−X 7 ≤ 0

se deben aplicar estas reglas

−X 3 + X 5 ≤0

(cosa que en éste caso ocurre con las tres primeras restricciones).

X i= { 0,1 }∨i=1,2,3,4,5,6,7,8 Restricciones reescritas:

Luego se procede a expresar las desigualdades de las restricciones de tal forma que todas sean de la forma

−4 X 1 −4 X 2−3 X 3−4 X 4−6 X 5−8 X 6−5 X 7−9 X 8 +3 ≤ 0 −2 X 1 −2 X 2−3 X 3−2 X 4−5 X 5−4 X 6−3 X 7−X 8 +2 ≤ 0

≤ 0 . Con lo anterior ya se puede proceder a desarrollar el Algoritmo que consiste en ir asignando el valor de 1 a cada variable con las demás en cero, las que tengan infactibilidad de 0 serán las candidatas a solución y las demás se descartan.

−X 6− X 8+ 1≤ 0 X 1− X 2−X 7 ≤ 0 −X 3 + X 5 ≤0 X i= { 0,1 }∨i=1,2,3,4,5,6,7,8 X 1= X 2=X 3 =X 4 =X 5 =X 6 =X 7= X 8=0

Para empezar se hacen todas las variables iguales a 0.



3 ≤ 0



2 ≤ 0



1 ≤ 0



0 ≤ 0



0 ≤ 0

Infactibilidad =3+2+1+0+0=6

X 1=1 X 2= X 3=X 4= X 5=X 6=X 7 =X 8 =0

Ahora se hace

X 1=1 y las demás

variables se igualan a 0.



7 ≤ 0



4 ≤ 0



1 ≤ 0

Infactibilidad

=7+4+1+0+0=12 

-1 ≤ 0



0 ≤ 0

X 2=1 X 1= X 3=X 4= X 5=X 6=X 7 =X 8=0 Ahora se hace

X 2=1 y las demás

variables se igualan a 0.



-1 ≤ 0



0 ≤ 0



1 ≤ 0

Infactibilidad

=0+0+1+0+0=1 

-1 ≤ 0



0 ≤ 0

X 3=1 X 1= X 2=X 4= X 5=X 6 =X 7 =X 8=0

Ahora se hace

X 3=1 y las demás

variables se igualan a 0.



0 ≤ 0



-1 ≤ 0



1 ≤ 0

Infactibilidad

=0+0+1+0+0=1 

0 ≤ 0



-1 ≤ 0

X 4 =1 X 1= X 2=X 3 =X 5= X 6= X 7=X 8=0 Ahora se hace

X 4 =1 y las demás

variables se igualan a 0.



-1 ≤ 0



0 ≤ 0



1 ≤ 0

Infactibilidad

=0+0+1+0+0=1 

-1 ≤ 0



0 ≤ 0

X 5=1 X 1= X 2=X 3 =X 4 =X 6 =X 7 =X 8=0 Ahora se hace

X 5=1 y las demás

variables se igualan a 0.



-3 ≤ 0



-3 ≤ 0



1 ≤ 0

Infactibilidad

=0+0+1+0+1=2 

0 ≤ 0



1 ≤ 0

X 6 =1 X 1= X 2=X 3 =X 4 =X 5 =X 7= X 8=0 Ahora se hace

X 6 =1 y las demás

variables se igualan a 0.



-5 ≤ 0



-2 ≤ 0



0 ≤ 0 =0+0+0+0+0=0



0 ≤ 0



0 ≤ 0

∴ Z=6

Infactibilidad

X 7 =1 X 1= X 2=X 3 =X 4 =X 5 =X 6 =X 8=0 Ahora se hace

X 7 =1 y las demás

variables se igualan a 0.



-2 ≤ 0



-1 ≤ 0



1 ≤ 0

Infactibilidad

=0+0+1+0+0=1 

-1 ≤ 0



0 ≤ 0

X 2=1 X 1= X 3=X 4= X 5=X 6=X 7 =X 8=0 Ahora se hace

X 8 =1 y las demás

variables se igualan a 0.



-6 ≤ 0



1 ≤ 0



0 ≤ 0

Infactibilidad

=1+0+0+0+0=1

Ahora escogemos la solución más pequeña, ya que es un problema de minimización, en este caso es cuando

Z =6 .

0 ≤ 0



0 ≤ 0

Solución Óptima:

X 1= X 2=X 3 =X 4 =X 5 =X 7= X 8=0 X 6 =1

Sólo tuvieron que revisarse 9 soluciones, a diferencia de enumeración implícita donde se hubiera requerido revisar



∴ Z=6

8

2

soluciones posibles. A continuación se muestra de una forma general el procedimiento explicado anteriormente Enunciado:

Min: Z=2 X 1 +3 X 2 +4 X 3 +4 X 4 +5 X 5+ ¿

6 X 6 +7 X 7+ 8 X 8

s . a. 4 X 1 +4 X 2 +3 X 3 +4 X 4 +6 X 5 +8 X 6 +5 X 7 + 9 X 8 ≥ 3 2 X 1+ 2 X 2+ 3 X 3+ 2 X 4 +5 X 5 + 4 X 6 +3 X 7 + X 8 ≥ 2 X6+ X8≥ 1 X 1− X 2−X 7 ≤ 0 −X 3 + X 5

≤0

X i= { 0,1 }∨i=1,2,3,4,5,6,7,8 Min: Z=2 X 1 +3 X 2 +4 X 3 +4 X 4 +5 X 5+ ¿

6 X 6 +7 X 7+ 8 X 8

s . a. 4 X 1−4 X 2 −3 X 3−4 X 4−6 X 5 −8 X 6 −5 X 7−9 X 8 ≤−3 2 X 1−2 X 2−3 X 3−2 X 4 −5 X 5−4 X 6 −3 X 7− X 8 ≤−2 −X 6− X 8 ≤−1 X 1− X 2−X 7 ≤ 0 −X 3 + X 5 ≤0 X i= { 0,1 }∨i=1,2,3,4,5,6,7,8 Min: Z=2 X 1 +3 X 2 +4 X 3 +4 X 4 +5 X 5+ ¿

6 X 6 +7 X 7+ 8 X 8

s . a. 4 X 1−4 X 2 −3 X 3−4 X 4−6 X 5 −8 X 6 −5 X 7−9 X 8+ 3≤ 0 2 X 1−2 X 2−3 X 3−2 X 4 −5 X 5−4 X 6 −3 X 7− X 8 +2≤ 0 −X 6− X 8+ 1≤ 0

R3

X 1− X 2−X 7 ≤ 0

R4

−X 3 + X 5 ≤0

R1 R2

R5

X i= { 0,1 }∨i=1,2,3,4,5,6,7,8 VARIABLES X1 X2 X3 X4 X5 X6 X7 X8

R1 3

R2 2

0 7

0 4

≤

0 1

0 0

0 0

0 0

0 0

0 0

0 0

0 0

≤

RESTRICCIONES R3 R4 R5 1 0 0

≤

≤

≤

0 1

0 -1

0 0

Infactibilidad

6 12

0

1

0

0

0

0

0

0

≤

≤

≤

≤

≤

0 -1

0 0

0 1

0 -1

≤

0 0

≤

0 0

0 -1

1

0 0

1

≤

≤

≤

0 0

0 -1

≤

0 1

≤

≤

0 -1

0 0

0 1

0 0

≤ 0

0

0

0

1

0

0

1

0

0

0

0

0

0

0

0

≤

≤

≤

≤

≤

0 -3

0 -3

≤

0 0

≤

0 1

1

≤

0 1

≤

0 -5

0 -2

≤

0 0

≤

0 0

2

≤

0 0

≤

0 -2

0 -1

≤

0 -1

≤

0 0

0

≤

0 1

≤

0 -6

0 1

0 0

0 0

0 0

1

1

≤

0

0

0

0

1

0

0

0

≤

0

0

0

0

0

1

0

0

≤

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

1

≤

≤

≤

≤

≤

≤

0

0

0

0

0

X 1= X 2=X 3 =X 4 =X 5 =X 7= X 8=0 X 6 =1∴ Z=6

Conclusión: Se aprendió y practico el método Egon Balas para en un futuro poderlo aplicar para tomar decisiones. Integrantes: Daniel Alejandro Pulgarin Cód. 20131020091 Diego Alexander Muñoz Reyes Cód. 20131020078 Brayan Vargas Vargas Cód. 20132020054 Referencias: 1. Programación Lineal Entera (Hecho por P.M. Mateo y David Lahoz el 2 de julio de 2009) http://ocw.unizar.es/ocw/ensenanzas-tecnicas/modelos-de-investigacionoperativa/ficheros/OCWProgEntera.pdf

2. Formato tomado de un ejercicio del semestre anterior (Hecho por Kevin Steven Gordillo Orjuela). 3. Notas de Clase (Investigación de Operaciones II tomadas el día 18 de Agosto de 2015).