Programación entera (investigación de operaciones)

5.1 Introducción

La programación lineal entera se ocupa básicamente de programas lineales en los que algunas o todas las variables suponen valores enteros o discretos. Se dice que la PLE es mixta o pura si alguna o todas las variables están restringidas a tomar sólo valores enteros.

Aunque se han creado varios algoritmos para la programación entera, ninguno de ellos es totalmente confiabledesde el punto de vista del cálculo, sobre todo, cuando el número de variables enteras se incrementa.
La dificultad de cálculo con los algoritmos disponibles para la programación entera ha conducido a los usuarios a buscar otros medios para resolver el problema. Uno de tales medios es resolver el modelo como un problema lineal continuo y luego redondear la solución óptima a los valores enterosfactibles más cercanos. Sin embargo, en este caso no hay garantía de que la solución redondeada satisfaga las restricciones. Esto es siempre cierto si la programación entera original tiene una o más restricciones de igualdad.

Según la teoría de programación lineal, una solución redondeada en este caso no puede ser factible, ya que significa que la misma base (con todas las variables básicas anivel cero) puede generar dos soluciones distintas.
La infactibilidad creada por redondeo puede tolerarse ya que, en general, los parámetros de los problemas no son exactos. Pero existen restricciones de igualdad características en los problemas enteros donde los parámetros son exactos.
La restricción de elección múltiple x1+x2+…+xn=1 , donde xj=(0,1) para toda j, no es sino un ejemplo. Entales condiciones el redondeo no puede utilizarse y será esencial contar con un algoritmo exacto.
Para destacar además lo inadecuado del redondeo, observe que aunque las variables enteras comúnmente se piensa que representan un número discreto de objetos (por ejemplo, máquinas, hombres, barcos), otros tipos representan cuantificaciones de algunos códigos. Por consiguiente, una decisión parafinanciar o no un proyecto puede representarse por una variable binaria x=0 si el proyecto se rechaza, x=1 si el proyecto se acepta. En este caso no tiene sentido tratar con valores fraccionarios de x, y el uso del redondeo como una aproximación lógicamente es inaceptable.

5.2 Definición y Modelos de Programación Entera (PE)

Un modelo de Programación Entera (PE) permite abordar aplicaciones donde lasolución tiene sentido si una parte o todas las decisiones toman valores restringidos a números enteros.
Por ejemplo, consideremos que tenemos el siguiente problema de programación lineal:

Max cTx
s.a. Ax=b
x≥0

Si todas las variables restringen sus valores a números enteros, entonces estamos frente a un modelo de PE pura; por el contrario si al menos algún conjuntode variables no está acotado a adoptar valores o número enteros, se trata de un PE mixta.

Parte del problema de la programación entera radica en la diferencia esencial que existe entre este y la programación lineal. En la programación lineal se maximiza o minimiza una función sobre una región de factibilidad convexa, mientras que en la programación entera se maximiza una función sobre unaregión de factibilidad que generalmente no es convexa. Por lo tanto, la solución de problemas enteros, es de muchos órdenes de magnitud más complicada que la programación lineal.

A continuación se presentan los tres problemas de estructura entera:

1. Problema entero (PE)
Opt Z=cX
sujeto a AX≤b
X≥0, entero

2. Problema entero – mixto (PEM)Opt Z=cX+dY
sujeto a AX+BY⋛b
X≥0
Y≥0, entero

3. Problemas entero – cero – uno (PECU) o problema binario (PB)

Opt Z=cX
sujeto a AX⋚b
X=0 ó 1

Estos tres tipos de problemas requieren de técnicas especiales de solución, ya que los métodos de solución de los...