ALGORITMO ADITIVO DE EGON BALAS
Enviado por sandy.dwt • 14 de Septiembre de 2020 • Ensayos • 643 Palabras (3 Páginas) • 1.331 Visitas
UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS
(Universidad del Perú Decana de América)
FACULTAD DE CIENCIAS MATEMÁTICAS
Escuela Académico Profesional de Investigación Operativa
[pic 1]
ALGORITMO ADITIVO DE EGON BALAS
Profesor(a):
Mg. Esther Berger Vidal
LIMA – PERÚ
2020
Algoritmo aditivo de Balas
Aspectos teóricos
Su nombre es debido originalmente a Elong Balas (1965). Se llama aditivo porque todas las operaciones matemáticas que se realizan consisten en sumar o restar.
El procedimiento consiste en generar una secuencia de soluciones parciales añadiendo en cada iteración una variable y considerando las soluciones complementarias (resto de soluciones posibles). De esta forma podemos por enumeración implícita, eliminar conjuntos de soluciones sin necesidad de evaluarlos exhaustivamente.
La selección de la variable añadida se hace en función e reducir al máximo la factibilidad en la solución actual y eliminar la redundancia
[pic 2]
El problema requiere que se presente en una forma estándar:
- La función objetivo tiene la forma: Min Z=[pic 3]
- Si la función objetivo es Max se usa la regla de equivalencia -Max z =Min z
- Las restricciones m son todas desigualdades de la forma , i=1,2,…,m[pic 4]
- En caso <0 entonces se sustituye por , es su complemento.[pic 5][pic 6][pic 7][pic 8]
- Todos las , j=1, 2, …, n son variables binarias (solo pueden tener un valor de 0 o 1).[pic 9]
- Todos los coeficientes de la función objetivo no son negativos
- Las variables están ordenadas de acuerdo a sus coeficientes de la función objetivo de modo que [pic 10]
El algoritmo consta del siguiente procedimiento
[pic 11]
Ejercicio 1
[pic 12]
s.a
[pic 13]
[pic 14]
[pic 15]
[pic 16]
Se nos da una función de maximización donde Y3 y Y4 tiene coeficientes negativos y la tercera restricción es ≥; entonces se pasaría a multiplicar por -1 los coeficientes para pasar a minimización
[pic 17]
s.a
[pic 18]
[pic 19]
[pic 20]
[pic 21]
Como aún hay coeficientes negativos Y1, Y2 y Y5, Se le hace un cambio de variable
[pic 22]
[pic 23]
s.a
[pic 24]
[pic 25]
[pic 26]
[pic 27]
[pic 28]
Se llega al problema de minimización con los coeficientes positivos y las restricciones con los términos de ≤
[pic 29]
[pic 30]
s.a
[pic 31]
[pic 32]
[pic 33]
[pic 34]
En vez de analizar 2nen este ejemplo 25=32 opciones de 0,1 para las variables como en el método de enumeración implícita, en el método aditivo solo analizamos algunas de ellas, comenzando con todas las variables igual a 0.
...