Fases De Estudio De La Investigacion De Operaciones

5.1 PROGRAMACIÓN ENTERA

Un problema de programación lineal entera es cualquier problema de optimización en el cual las variables de decisión todas o algunas de ellas toman valores enteros. La formulación general de un problema de programación lineal entera es la siguiente:

Siendo c ∈ Rn y b ∈ Rm los vectores de costes y recursos respectivamente, y A una matriz de orden m x n denominadausualmente matriz de coeficientes tecnológicos.
Si N = N1 el problema recibe el nombre de programación lineal entero puro.
Si N ≠ N1, el citado problema se le denomina problema lineal entero mixto.
En este tema se presenta un tipo de problemas formalmente similares a los problemas de programación lineal, ya que en su descripción sólo se establecen expresiones lineales.
Sin embargo no responden aproblemas lineales ya que algunas (o todas) las variables del problema toman valores que no están en un conjunto continuo. Por ejemplo, pueden ser variables que toman valores 0 o 1 (binarias), o variables que toman valores enteros no negativos (0,1, 2, 3,...) etc.
Según el tipo de problemas se presentar las posibilidades de modelado que dicha herramienta proporciona: problemas binarios, problemasde carga fija, problemas con restricciones condicionales o con dicotomías, etc.
Una parte importante son las herramientas de modelado y a plantear numerosos problemas, ya que con ellas se muestran métodos de resolución. Uno de ellos dedicado a problemas en los que todas las variables son binarias y otro para problemas generales. Ambos métodos tienen en común que desarrollan un proceso deenumeración que permite comprobar explícita o implícitamente todas las soluciones del problema hasta encontrar la optima, y entran dentro del tipo de métodos de ramificación y acotación.
Existen 3 tipos de variables en lo problemas de programación entera:
* Variables no enteras o reales.- Algunas de las variables son enteras, las otras no.

* Variables enteras.- Todas las variables de decisiónson enteras.

* Variables binarias.- Las variables solo toman los valores 0 ó 1.

La posibilidad de usar variables enteras o binarias amplia notablemente las posibilidades de modelización matemática. Las variables binarias xj Є {0,1} pueden utilizarse para modelar situaciones en las que se decide si una acción se realiza, xj = 1, o si no se realiza, xj = 0. Un ejemplo típico deutilización de este típico de variables es el problema de inversiones.
A partir de tres situaciones se pueden generar muchas otras, por ejemplo: si se invierte en el proyecto i entonces no se puede invertir en el proyecto j. En términos de las variables se dice que si xi = 1 entonces xj = 0 que podríamos escribir que si xi = 1 entonces yj = 1 – xj = 1, es decir, si se invierte en el proyecto i entonces seinvierte en un nuevo proyecto j’. Esto queda de la siguiente manera: xi≤ 1 – xj.
Por lo tanto si en lugar de invertir, está el “no invertir” solo basta con buscar la restricción que tiene la misma forma y se debe cambiar en donde aparece la variable por su valor complementario 1 – x.
Si consideramos que estamos a un modelo de programación lineal entera (puro o mixto) y resolvemos el modelo deprogramación lineal asociado (esto es, admitiendo valores continuos para las variables), se estarán obteniendo la solución de la relajación contínua del modelo entero. Para un modelo de maximización, la relajación continua nos proporciona una cota superior del valor óptimo del modelo de programación lineal entera asociado.
Existen múltiples aplicaciones de modelos de programación lineal enteracomo apoyo a la toma de decisiones. Algunas aplicaciones típicas son problemas de localización de instalaciones, inclusión de costos fijos, problemas de asignación, problemas de ruteo vehicular, etc. Se han desarrollado metodologías que permiten estudiar de forma más eficiente que la enumeración el conjunto de soluciones posibles.

5.2 DEFINICIÓN Y MODELOS DE PROGRAMACIÓN ENTERA

Las variables...