Introduccion a la programacion entera

Introducción a la programación entera

Los problemas de programación lineal en que se requiere que algunas o todas las variables tomen valores enteros, son de programación entera. La programación entera a llegado a ser un área muy especializada de la ciencia de la administración.

Un enfoque práctico:

Una empresa que fabrica costales para alimento de ganado y una solución lineal requiereque se fabriquen 3000,472 costales, carecerá de sentido. En tales situaciones, a menudo se adopta la solución no entera al requerimiento de enteros simplemente redondeando los resultados al entero más próximo. Esto produce lo que se llama la “solución redondeada”. Mediante ese recurso se obtienen soluciones aceptables para el administrador en aquellas situaciones en las que, con sentido practico,sencillamente no importa el redondeo. Por ejemplo, no hay diferencia significativa, ya sea en la función objetivo o en las restricciones, entre producir 19.283,64 y 19.283 costales de alimento para ganado, En realidad, probablemente baste para el ajuste de los datos del modelo que satisfaga al administrador una producción cercana a los 19.000 costales.

Cuando tienen importancia lassoluciones enteras

Existen muchos problemas importantes en los que la “solución redondeada” simplemente no funciona. Esta complicación puede deberse a la escala de las variables por considerar. Por ejemplo, si la solución de un modelo de programación lineal recomienda que la Boeing construya 11,6 aparatos 747 y 6,8 aparatos 727, el administrador probablemente no quedara contento con la simple medida detomar la decisión de construir 11 de los primeros y 6 de los segundos, o cualquier otra solución redondeada. La magnitud del rendimiento y la asignación de recursos asociados con cada unidad del problema aconsejan determinar la mejor solución entera posible. Con otro ejemplo, sé vera que muchos modelos usan variables enteras para indicar decisiones lógicas. Por ejemplo, veremos que problemas enlos que queramos que una variable “x” sea igual a 1 si vamos a construir un almacén o x sea igual a cero (si-no). Supóngase que la solución de una versión de programación lineal de este problema produce un valor no entero, por ejemplo, x = 0,38. Vemos que este valor no contiene información aprovechable como solución al problema real.
Es claro que no podemos construir 0,38 de un almacén. Es ciertoque podemos elegir almacenes de diversos tamaños, pero en todo caso, o bien tenemos un almacén o no lo tenemos. Se podría suponer que en un caso como este se trataría de redondear al entero más próximo (0 en este caso) como forma de salvar la dificultad. Por desgracia, esto no garantiza que se obtenga una buena (y no digamos óptima) solución.
En realidad, veremos que el redondeo no siempreconduce a solucione factibles en casos como este.
El fondo del asunto es que existen muchos problemas administrativos importantes que serian de programación lineal si no fuese por el requerimiento de que sean enteros los valores de algunas variables de decisión, en los que no se puede encontrar una buena solución mediante el uso del método Simplex seguido del redondeo de los valores óptimosresultantes para variables de decisión. Estos problemas deben ser resueltos mediante algoritmos especialmente diseñados para resolver problemas de programación entera.

Programación Lineal contra Programación Entera

A pesar del impresionante avance en nuestra capacidad para resolver problemas de programación entera, la tecnología aun dista mucho de la que hay disponible para manejar problemas en losque no es necesario que las variables de decisión sean enteras. Muchos problemas que se resuelven fácilmente como problemas de programación lineal llegan a ser irresolubles para propósitos prácticos cuando se exige que las variables de decisión sean enteras (es decir, que el tiempo y el costo necesario para los cálculos resultan demasiado grandes)

Tipos de modelos de Programación Entera:...