Bioquima

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 objetivopor -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:
Min z'=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+3x5
Sujeta 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 la minimización de una función objetivo con todos los coeficientes positivos, una solución inicial lógicadebe consistir en variables binarias todas cero. En este caso, las holguras actuarán como variables 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
Si todas las variables fueran no negativas, concluiríamos que la solución binaria toda cero es óptima. Sin embargo, debido a que algunas de las variables son no factibles (negativas), necesitamos elevar una o másvariables binarias al nivel 1 para lograr la factibilidad (o concluimos que el problema no tiene una solución factible).
La elevación de una (o de algunas) de las variables binarias cero al nivel 1 ocurre en el algoritmo aditivo una a la vez. La variable elegida se llama variable de ramificación y su selección se basa en el empleo de pruebas especiales.
La variable de ramificación debe tener elpotencial de reducir la no factibilidad de las holguras. Si venos la tabla anterior x3 no se puede seleccionar como una variable de ramificación, debido a que sus coeficientes de restricción en la segunda y tercera restricciones son no negativos. Por tanto, la determinación de x3=1 solo puede empeorar la no factibilidad de s2 y s3. A la inversa, cada una de las variables restantes tiene por lo menosun coeficiente de restricción negativo en las restricciones 2 y 3, de allí que una combinación de estas variables puede producir holguras factibles. Por consiguiente, podemos excluir a x3 ya a considerar x2, x3, x4 y x5 como las únicas candidatas posibles para la variable de ramificación.
La selección de la variable de ramificación entre las candidatas x2, x3, x4 y x5 se basa en el empleo de lamedida de no factibilidad de holgura. Esta medida, que se basa en la suposición de que una variable cero xj se elevará al nivel 1, se define como
Ij = " min {0,si-aij}
Donde s1 es el valor actual de la variable i y aij es el coeficiente de restricción de la variable x1 en la restricción i.
De hecho, Ij no es más que la suma de las variables negativas resultantes de elevar xj al nivel 1. Lafórmula, aparentemente complicada, se puede simplificar a:
Ij = " (negativos sj valor dado xj=1)
Por ejemplo, cuando determinamos x1=1, obtenemos s1=1-(-1)=2, s2= -2-(-7)=5 y
s3= -1-11= -12. Así I1= -12. De manera similar I2=-2, I4=-1 y I5=0 (recordando que x3 se excluyó como no prometedora). Debido a que I5 produce la medida más pequeña de no factibilidad, se selecciona x5 como la variable de...