Programación entera

INTRODUCCION
En algunos casos se requiere que la solución óptima se componga de valores enteros para algunas de las variables. La resolución de este problema se obtiene analizando las posiblesalternativas de valores enteros de esas variables en un entorno alrededor de la solución obtenida considerando las variables reales. Muchas veces la solución del programa lineal truncado está lejos de serel óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta.
El más famoso es el método de 'Ramificar y Acotar' o Branch and Bound por su nombre eninglés. El método de Ramificar y Acotar parte de la adición de nuevas restricciones para cada variable de decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo entero.La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas deprogramación lineal.
Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas losuficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos de problemas deoptimización constituyen casos particulares de la más amplia técnica de la programación lineal.




5.1 METODO DE PLANOS
En matemática, y más en concreto en optimización, el método de los planosde corte es un procedimiento para encontrar soluciones enteras de un problema lineal. Fue introducido por Gomory.
Funciona resolviendo un programa lineal no entero, después comprobando si laoptimización encontrada es también una solución entera. Si no es así, es añadida una nueva restricción que corta la solución no entera pero no corta ningún otro punto de la región factible. Esto se repite...