Optimizacion

La programación entera se utiliza en caso de q alguna o todas las variables de decisión deban ser enteras existe un algoritmo, para resolver los problemas de programación entera, dicho algoritmo sedenomina, método de ramificación y acotamiento, el método consiste en lo siguiente:
1. Resolver el problema original mediante la programación lineal, método simplex, si la respuesta satisface lasrestricciones de enteros, el problema está solucionado, si no es así este valor proporciona un límite superior inicial.
2. Encontrar cualquier solución factible que satisfaga las restricciones deenteros y que se utilizara como límite inferior casi siempre el redondeo hacia abajo lograra este resultado
3. Convertir en rama una variable del paso 1 que no tenga un valor entero. dividir elproblema en dos subproblemas con base en valores enteros que estén inmediatamente arriba o abajo del valor no entero. Por ejemplo, si x2 =3.75 entonces se introduce la restricción de que x2 mayor oigual a 4 en el primer subroblema y la restricción x2 menor o igual a 3
4. Crear nodos en la parte superior de estas nuevas ramas para solucionar los problemas nuevos
5. Si una rama da unasolución del problema de programación lineal que no es factible, terminar la rama^ Si una rama da una solución el problema de programación lineal que es factible, pero no es una solución entera,proseguir al paso 6
6. Si la rama da una a una solución factible e SI ESTE VALOR ES IGUAL AL LIMITE SUPERIOR SE LLEGO A UNA SOLUCION OPTIMA.
Si no es igual al límite superior pero sobrepasa ellimite einferior fijarlo como el nuevo limite inferior y proseguir al paso 6
Si es menor que el límite inferior terminar con esta rama.
7. Examine de nuevo ambas ramas y fije el límitesuperior igual al valor máximo de la función objetivo en todos los nodos finales. Si el limite superior es igual al inferior detenerse y regresar al paso 3 .

Se ivide en 2 nuevos subproblemas...