Programacion Lineal Entera

1.- Introducción

2. Tipos De De Modelos
2.1 Modelo Entero Puro
2.2 Modelo Entero Mixto
2.3 Modelo Entero Binario

3. Clasificación De Planteamientos
3.1 Tabla De Clasificación De Planteamientos
3.1.1 Tipo Mochila
3.1.2 Asignación de Capital.
3.1.3 Asignación de Capital con Horizonte.
3.1.4 Cobertura de Conjuntos.
3.1.5Asignación de Horarios.
3.1.6 Agente Viajero.
3.1.7 Cargo Fijo.
3.1.8 Si entonces.
3.1.9 Si y solo si.
3.1.10 Restricciones o bien
3.1.11 Modelo de Dicotomía
3.1.12 Problema de Asignación
3.1.13 Problema de Transporte
3.1.14 Problema de Transbordo
3.1.15 Ruta más corta
3.1.16 Flujo máximo3.1.17 Flujo mínimo

INTRODUCCIÓN

La Programación Lineal Entera (PLE). En principio, un problema de PLE es uno de programación lineal; en él, al menos una de sus variables debe tomar valores enteros y positivos (restricción de integralidad o integridad). Estos problemas son de gran interés pues hay aplicaciones de PLE en todos los sectores y mercados. Considere un ejemplo en elcual la variable representa la cantidad de vehículos fabricados; por su interpretación física, esta variable no contempla valores que no sean enteros positivos.
Cuando la restricción de integralidad se impone a todas las variables, se denomina problema de programación lineal entera pura. Cuando la restricción de integralidad se impone a algunas de sus variables, se denomina problema deprogramación lineal entera mixta. Un problema de programación lineal entera en el que todas sus variables tienen valor igual a 0 o 1, se denomina problema de programación lineal entera binaria.
Los problemas de PLE son, a priori, so más complicados que los de PL. En la mayoría de los algoritmos utilizados para la resolución de los problemas de PLE, es de interés “relajar” todas las restricciones deintegralidad de la PLE y entonces resolver el problema de PL resultante (este proceso se denomina relajación lineal del problema de PLE). La región factible del problema original siempre estará incluida en la región factible del problema relajado. Hay una propiedad que debe cumplirse y es que, en un problema de maximización, el valor de la solución optima de la relajación lineal de ser mayor o igual queel valor de la solución optima del problema original de PLE. Esta propiedad se utilizara en la resolución de los problemas.

2. Tipos de de Modelos
De acuerdo al tipo de variables que tienen los modelos de programación entera pueden definirse los siguientes tipos:
2.1 Modelo Entero Puro
Son aquellos modelos en los que todas las variables son enteras incluyendo variables de holgura o deexceso
Ejemplo de Modelos:

Ejemplo de planteamiento: El problema de transporte
Un planteamiento que genera un entero puro puede ser el siguiente:
Una empresa fabrica tres tipos de tenis: de lujo, normal y económico. Las contribuciones a las utilidades son $270, $200 y $230 respectivamente. Las necesidades en el departamento de ensamble en minutos son 1, 2 y 3 respectivamente. El departamento depaquetería para cada tipo de tenis es: 2, 2 y 3 minutos respectivamente. Se tienen 1000 minutos en el depto de ensamble y 1200 minutos en el departamento de paquetería.

Para la resolución de este tipo de modelos tenemos:
-Método de Plano de Corte
- Algoritmo Fraccional de Gomory
- Algoritmo Entero Puro de Gomory
- Método de Ramificación y Acotamiento
- Algoritmo de Land – Doig.

2.2Modelo Entero Mixto
Se tendrán tantas variables continuas como variables enteras. Cuando la restricción de integralidad se impone a algunas de sus variables.
Ejemplo de modelo:

Ejemplo de planteamiento: El modelo de Dicotomía, el problema de cargo fijo.
Un ejemplo de planteamiento que genera este tipo de modelos mixtos es:
He sido abordado por tres compañías de teléfonos para que me...