Programacion Lineal

Programación lineal entera
En muchos problemas prácticos, las variables de decisión solo tienen un sentido real si su valor es entero. Por ejemplo, con frecuencia es necesario asignar personas, maquinas o vehículos a las actividades, en cantidades enteras. Si el hecho de exigir valores enteros es la única diferencia que tiene un problema con la formulación de programación lineal, entonces setrata de un problema de programación entera (PE). (El nombre completo es programación lineal entera, pero por lo general el adjetivo lineal se omite, excepto cuando se hace una comparación con el problema más misterioso de programación no lineal entera.)
El modelo matemático para programación entera es sencillamente el modelo de programación lineal con la restricción adicional de que las variablesdeben tener valores enteros. Si solo es necesario que algunas de las variables tengan valores enteros (y la suposición de divisibilidad se cumple para el resto), el modelo se conoce como uno de programación entera mixta (PEM). Cuando se hace la distinción entre un problema con todas las variables enteras y este caso mixto, el primero se llama de programación entera pura.
Se han desarrolladonumerosas aplicaciones de programación entera que involucran una extensión directa de programación lineal en la que debe eliminarse la suposición de divisibilidad. Sin embargo, existe otra área de aplicación que puede ser mucho más importante, como el problema que incluye cierto número de “decisiones sí o no” interrelacionadas. En las decisiones de este tipo, las únicas dos elecciones posibles son síy no. Por ejemplo, ¿debe emprenderse un proyecto fijo específico? ¿Debe hacerse una inversión fija dada? ¿Debe localizarse una instalación en un sitio en particular?.
Con solo dos posibilidades, este tipo de decisiones se puede representar mediante variables de decisión restringidas a solo dos valores, por ejemplo 0 y 1. Así la j-esima decisión sí o no se puede representar por Xj, tal que.
Xj=1si la desicion j es si.o si la desicion j es no.
Las variables de este tipo se llaman variables binarias ( o variables 0-1). En consecuencia, algunas veces se hace referencia a los problemas de programación entera que contienen solo variables binarias como programación entera binaria (PEB) (o problemas 0-1 de programación entera).
Los problemas PE surgen con frecuencia cuando los valores dealgunas o todas las variables de decisión deben restringirse a valores enteros. Existen también muchas aplicaciones que necesitan decisiones si o no (incluyendo las relaciones combinatorias que pueden expresarse en términos de tales decisiones) que se pueden representar por variables binarias (0-1). Estos factores han hecho que la programación entera sea una de las técnicas de IO de mayoraplicación.
Los problemas de PE son más difíciles de lo que serian sin la restricción de valores enteros, de manera que los algoritmos disponibles para programación entera, en general, son mucho menos eficientes que el método simplex. Los factores que determinan el tiempo de cálculo son el numero de variables enteras y el hecho de que el problema tanga una estructura especial que puede explotarse. Para unnúmero fijo de variables enteras, casi siempre es más fácil resolver problemas de PEB que problemas con variables enteras generales; pero agregar variables continuas (PEM) puede no significar un incremento sustancial en el tiempo de cálculo. Para problemas especiales de PEB que contienen alguna estructura especial que puede aprovechar un algoritmo especial, es posible resolver problemas muygrandes (muy por encima de mil variables binarias) en forma rutinaria. Puede ser que otros problemas mucho mas pequeños sin estructura especial no se pueden resolver.
En la actualidad es común que se disponga de paquetes de computadora para algoritmos de PE es el software de programación matemática. Estos algoritmos casi siempre se basan en la técnica de ramificación y acotamiento o en alguna...