Рrogramacion lineal entera (PLE)

PROGRAMACION LINEAL ENTERA

La programación linean entera (PLE) 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 la variables están restringidas a tomar solo valores enteros.

Aunque se han creado varios algoritmos para la PLE, ninguno de ellos es totalmente confiable desde el punto de vista del calculo, sobre todo, cuando el numero de variables enteras incrementa. A diferencia de la PL, donde problemas con miles de variables y miles de restricciones se pueden resolver en un tiempo razonable, la experiencia de calculo con la PLE, después de mas de 30 años de haberse creado, permanece imprecisa.

La dificultad de calculo con los algoritmos disponibles para la PLE ha conducido a los usuarios a buscar otros medios para “resolver” el problema. Uno de tales medios es resolver el modelo como PL continuo y luego redondearla solución optima a los valores enteros factibles mas cercanos. Sin embargo, en este caso no hay garantía de que la solución redondeada resultante satisfaga las restricciones. Esto es siempre cierto si la PLE original tiene una o mas restricciones de igualdad. Según la teoría de la 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 no básicas a nivel cero) pueden generar dos soluciones distintas.

La infactibilidad creada por redondeo puede tolerarse ya que, en general, los parámetros (estimados) de los problemas no son exactos, pero existen restricciones de igualdad características en problemas enteros donde los parámetros son exactos. Las restricciones de elección múltiple x1 + x2 + … + xn = 1, donde x1 = (0,1) para toda j, no es sino un ejemplo. En tales condiciones, el redondeo no puede utilizarse y será esencial contar con un algoritmo exacto.

Para descartar además lo inadecuado del redondeo en general, observe que aunque las variables enteras comúnmente se piensa que representan un numero discreto de objetos (por ejemplo, maquinas, hombres, barcos), otros tipos representan cuantificaciones de algunos códigos. Por consiguiente, una decisión para financiar o no un proyecto puede representarse por la variable binaria x = 0 si el proyecto se rechaza, o x = 1 si 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.

A fin de acentuar la importancia de los problemas en los cuales se utilizan las variables “codificadas”, la sección siguiente presenta aplicaciones comunes en esta área. Esto servirá también para ilustrar la importancia de la programación en general.

APLICACIONES ILUSTRATIVAS DE LA PROGRAMACION ENTERA

En esta sección se presentan aplicaciones de programación entera. Algunas de estas aplicaciones se refieren a la formulación directa del problema. Una contribución mas importante será el uso de esta programación para reformular modelos “mal construidos”, dentro del formato aceptable de modelos de programación matemática. En este caso, las técnicas disponibles pueden utilizarse para resolver problemas que, de otra manera, pueden ser difíciles.

PROBLEMA DEL PRESUPUESTO DEL CAPITAL

Se ha considerado la ejecución de cinco proyectos en los próximos 3 años. Las entradas esperadas de cada proyecto y los gastos anuales (en miles de unidad monetaria) se encuentran tabulados mas adelante.

Se trata de decidir cual de los cinco proyectos debe ejecutarse en el periodo de planeación de 3 años. En este sentido, el problema se reduce a una decisión del tipo “si-no” en casa proyecto. Esta decisión esta codificada en forma numérica con una variable binaria, donde el valor 1 representa “si” y el valor 0 representa “no”. El problema de decisión lo formalizamos definiendo la variable x1 para que represente al proyecto j. el modelo asociado resulta entonces:

Maximizar z = 20x1 + 40x2 + 20x3 + 15x4 30x5

Sujeto

...