Investigacion

ALGORITMO ADITIVO DE BALAS
Ejemplo de Algoritmo Aditivo:
Resolver el siguiente problema 0-1:
Max w=3y1+2y2-5y3-2y4+3y5
Sujeta a:
y1 + y2 + y3 + 2y4 - y5 " 4
7y1 +3y3 - 4y4 - 3y5" 8
11y1 -6y2 +3y4 - 3y5 " 5
y1,y2,y3,y4,y5 = (0_1)
El problema se puede poner en la forma inicial requerida por el algoritmo aditivo, utilizando las siguientes operaciones:
Multiplique la función objetivo por -1.
 Multiplique la tercera restricción por -2.
 Añada las variables s1,s2 y s3 para convertir las tres restricciones en ecuaciones.
Sustituya y1=1-x1 , y2=1-x2 , y5=1-x5 , y3=x3 , y y4=x4 para producir todos los coeficientes objetivo positivos.
La conversión da por resultado la siguiente función objetivo:
Minz'=3x1+2x2+5y3-2x4+3x5-8
Para mayor facilidad, ignoremos la constante -8 y reemplazaremos z' +8 con z, de manera que el problema convertido resultante se lee como:
Min z=3x1+2x2+5y3-2x4+3x5Sujeta a: x1 - x2 + x3 + 2x4 - x5 -s1 = 1
-7x1 +3x3 - 4x4 - 3x5 -s2 = -2
11x1 -6x2 -3x4 - 3x5 -s3 = 5
x1,x2,x3,x4,x5 = (0_1)
Debido a que el problema modificado busca laminimización de una función objetivo con todos los coeficientes positivos, una solución inicial lógica debe consistir en variables binarias todas cero. En este caso, las holguras actuarán comovariables básicas y sus valores los dan los lados derechos de la ecuación. La solución se resume en la siguiente tabla:
Solución básica factible | X1 | X2 | X3 | X4 | X5 | S1 | S2 | S3| Solución |
S1 | -1 | -1 | 1 | 2 | -1 | 1 | 0 | 0 | 1 |
| | | | S1 | -7 | 0 | 3 | -4 | -3 | 0 | 1 | 0 | -2 |
| | | | S1 | 11 | -6 | 0 | -3 | -3 | 0 | 0 | 1 | -1 |
|| | | Coeficientes objetivo | 3 | 2 | 5 | 2 | 3 | | | | |
Dada una solución binaria inicial toda cero, la solución de holgura asociada es:
(s2 ,s2 ,s3 ) = (1,-2,-1) , z=0