Algunas perspectivas sobre la solución de problemas de programación entera (VI)

Como, en general, es mucho más difícil resolver los problemas de programación entera que los de programación lineal, a veces es tentador usar el procedimiento aproximado y aplicar el método símplex a la soltura de PL y después redondear los valores no enteros a enteros en la solución obtenida. Este enfoque puede ser adecuado en algunas aplicaciones, en especial si los valores de las variables son tan grandes  que el redondeo causa un error muy pequeño; pero debe tenerse cuidado al hacer esto, pues hay dos riesgos que se corren

Un problema es que la solución óptima de programación lineal no necesariamente es factible después de redondearla. Con frecuencia es difícil decidir en qué sentido redondear para conservar la factibilidad. Puede ser necesario incluso cambiar el valor de algunas variables en una o más unidades después de redondear. Para ilustrar esto, supóngase que algunas restricciones son:

-x1 + x2 ≤ 3(1/2)

x1 + x2 ≤ 16(1/2)

y que el método símplex ha identificado la solución óptima para la soltura de PL como x1 = 6(1/2), x2 = 10. Nótese que es imposible redondear x1 a 6 o a 7 ( o a ningún otro entero) y conservar la factibilidad. Esta factibilidad sólo se puede conservar si también se cambia el valor entero de x2. Es fácil imaginar la complejidad a la que se puede llegar con este tipo de dificultades cuando se tienen decenas o cientos de restricciones y variables.