PROGRAMACIÓN ENTERA

PROGRAMACIÓN ENTERA

INTRODUCCIÓN:                                                                                                                                           En nuestro quehacer diario, casi siempre debemos tomar decisiones: una decisión puede ser clasificada en estructurada si envuelve una serie de factores que puedan ser cuantificados y luego formulados en términos matemáticos. La Investigación de Operaciones es una herramienta de apoyo a la decisión estructurada.

CLASIFICACIÓN DE UN MODELO DE PROGRAMACIÓN ENTERA:

Comenzaremos por decir que un problema de Programación Lineal Entera se puede clasificar en:

a. Programación Entera Pura

Es un caso particular de un problema de programación lineal, en la cual las variables sólo pueden asumir valores enteros (o discretos).

b. Programación Entera Mixta

Es otro caso particular de la programación lineal, en el cual apenas una parte de las variables está restricta a valores enteros.

c. Programación Entera Binaria o Programación Binaria

Cuando las variables del problema están restrictas a apenas dos valores (0 y 1), constituyendo la programación binaria ó 0-1.

Diferentemente de la Programación Lineal, en la cual pocos algoritmos se muestran eficaces para toda la gama de problemas, la optimización entera se destaca por presentar un número expresivo de abordajes, generalmente, especializadas en función de su aplicación. Tales abordajes se dividen en dos familias, con características y resultados distintos:

OPTIMIZACIÓN CLÁSICA.

En los problemas convexos, se tiene la garantía de que la solución obtenida es óptima.

·         Enumeración total (para problemas de pequeñas dimensiones)

·         Branch-and-Bound (para problemas enteros y enteros mixtos)

·         Enumeración implícita cero-uno (para problemas binarios).

OPTIMIZACIÓN HEURÍSTICA.

Permiten obtener buenos resultados (la optimalidad no es garantizada) en problemas en los cuales los métodos de la optimización clásica pueden fallar (generalmente en función del elevado número de variables enteras o de la complejidad de las restricciones y de la función objetivo).

·         Algoritmos genéticos.

·         Busca tabú.

·         Simulated anneling.

·         Otros.

Considerando apenas los problemas con función objetivo y restricciones lineales, la programación entera y la programación entera mixta, presentan importantes diferencias teóricas en comparación con la programación lineal

 En la programación lineal, existen condiciones necesarias y suficientes de optimalidad teóricamente probadas que pueden ser utilizadas para verificar eficientemente si una solución viable dada es una solución óptima o no. Estas condiciones de optimalidad han sido utilizadas para desarrollar métodos algébricos tales como el método simplex y otros métodos.

 En la programación entera y entera-mixta, no existen condiciones de optimalidad conocidas para verificar si dada una solución factible es óptima o no ser a través de la comparación explícita o implícita de esta solución con cada una de las soluciones factibles del problema. Este es el motivo por el cual los problemas enteros de optimización son resueltos por intermedio de métodos de enumeración que buscan la solución óptima en el conjunto de las soluciones factibles.

También tenemos como una diferencia de un problema de programación entera y un problema de programación lineal, el espacio de búsqueda, mientras que en un problema entero el espacio de búsqueda es discreto, en un problema lineal es continuo.