Algoritmo aditivo y de plano cortante

ALGORITMO ADITIVO
Este tipo de algoritmo fue desarrollado por Balas para resolver problemas de programación lineal entero con variables binarias puras. Siendo un procedimiento de enumeración en elque se encuentra el óptimo de manera más rápida, evaluando solo algunas soluciones.
El método inicia colocando todas las variables iguales a cero y luego por un procedimiento sistemático de formaconsecutiva se asigna a una por una de las variables el valor 1; luego se reemplaza en cada una de las restricciones y se averigua la infactibilidad. Para describir el algoritmo se toma la forma generalde un problema de programación lineal con variables cero-uno, también se debe tener en cuenta que la función objetivo debe ser del tipo minimización, con todos los coeficientes no negativos.
Ahorabien, para entender adecuadamente este método, se realizará el siguiente ejemplo:

Sujeto a: (1)
(2)
(3)

En primera instancia, hay que volver la función objetivo unaminimización, lo cual se obtiene multiplicándola por menos uno (-1)

Y como no se deben dejar coeficientes negativos en la función objetivo, se realiza el siguiente reemplazo





Obteniendo asíFunción objetivo

Ahora se pasa a las restricciones, a las cuales se debe añadir variables para volverlas ecuaciones, y se reemplazan las (según se hizo para dejar la función objetivo concoeficientes positivos). Hay que tener en cuenta que en la ecuación (3) se debe multiplicar por (-1) ya que esta no tiene el signo de igualdad adecuado para realizar la solución del ejercicio.(1)



(2)



(3)



Como ya se encontraron los coeficientes positivos y es una minimización la función objetivos, la solución inicial lógica debe consistir en variablesbinarias todas cero. Obteniendo la siguiente tabla:



Si todas las variables fueran no negativas, se concluiría que la solución binaria cero es óptima. Pero como algunas de las variables con...