Programación lineal entera pura: Algoritmo fraccional de gomory - Algoritmo totalmente entero de gomory

Abstract

El objetivo de la presente es implementar dos de los Algoritmos para solucionar Programas Lineales Enteros Puros ambos de GOMORY basados en los Planos de Corte como son: - Algoritmo Fracciona! - Algoritmo Totalmente Entero Respecto al Algoritmo Fraccional éste genera Planos de Corte (nueva restricción) con coeficientes fraccionarios si al aplicar el Método Simplex la Solución Óptima no es entera (no negativa); pues de serlo resulta ser la solución buscada. E! Algoritmo Totalmente Entero parte de una tabla Dual Admisible si la tabla no es Primal Admisible entonces se añade el Plano de Corte (nueva restricción) con coeficientes enteros, de lo contrario se obtiene la tabla óptima deseada. Además se presenta una comparación con otro algoritmo (Ramificación y Acotación) que soluciona el mismo tipo de problema. Finalmente se presenta en el ANEXO los dos Algoritmos escritos en Lenguaje C, con una pequeña aplicación. ¿Para qué se utilizan estos algoritmos? Pues en muchas situaciones prácticas los valores no enteros pueden carecer de sentido. Así, por ejemplo, para una Empresa que fabrica pantalones de los tipos A y B el saber que para maximizar la ganancia necesita fabricar semanalmente 45.3 pantalones del tipo A y 55.7 pantalones del tipo B, aunque constituya una solución óptima, no resulta una solución útil. Lógicamente la Empresa necesitará tener una solución expresada en números enteros.