Programacion Entera

INSTITUTO TECNOLÓGICO DE TAPACHULA

INGENIERÍA INDUSTRIAL
MATERIA: INVESTIGACIÓN DE OPERACIONES I

CATEDRÁTICO: ING. RUBÉN REYES VELAZQUEZ

TEMA: *UNIDAD 5* PROGRAMACIÓN ENTERA

PRESENTA: GARCÍA DÍAZ PEDRO ANTONIO GUILLÉN RIVERA REYNA ISABEL

CURSO DE VERANO 2011

TAPACHULA DE CÓRDOVA Y ORDÓÑEZ, CHIAPAS. DOMINGO 31 DE JULIO DE 2011.

OBJETIVO
Conocer e identificar los modelos queintervienen en la programación entera, haciendo énfasis en la diferencia de un programa entero a los de tipo no entero, así también como dar algunos ejemplos de problemas de programación entera.

1

PROCEDIMIENTO
1. Coordinarnos para realizar la investigación (repartir temas). 2. Con un volado se tomó la decisión de quién escribiría el trabajo en la libreta y quién entregaba el documentoelectrónico. 3. Encender el ordenador, ingresar los nombres de los temas en el buscador, consultar varias páginas, de las cuales escogimos la información que más nos pareció. Asimismo, consultamos el libro Introducción a los Modelos Cuantitativos de Administración. 4. Hacer la estructura del trabajo y distribuir la información. 5. Redactar la conclusión. 6. Finalmente, revisar el trabajo final paracorregir errores.

2

DESARROLLO
5.1. INTRODUCCIÓN Y CASOS DE APLICACIÓN

Sus pioneros fueron Wagner (1950) y Manne (1959). Tradicionalmente estos modelos se han considerado como subclases de la programación lineal, sin embargo, las variables de decisión que aparecen en ellos sólo toman valores enteros, por lo que realmente deben considerarse como problemas de programación entera. Elnúmero de modelos lineales enteros y sus métodos de solución es en la actualidad bastante extenso, lo que nos ha llevado a hacer una selección considerando aquellos que creemos más interesantes y que aparecen con mayor frecuencia en la realidad. No siempre es admisible que las variables de un PL tomen valores continuos, existen: • • Decisiones dicotómicas (si-no) Decisiones que deben tomarse en unidadesdiscretas

Si se requiere que todas las variables sean enteras, se dice que se habla de Programación Lineal Entera Pura; si se necesita que algunas de las variables de decisión sean números enteros, se tiene un problema de Programación Lineal Entera Mixta. En algunas aplicaciones, sólo se permite que todas las variables tomen valores de cero o uno, hablamos en estos casos de Programación LinealEntera Binaria (Digital); si se requiere que solamente algunas de las variables tomen valores de cero o uno, se tiene un problema de Programación Lineal Entera Binaria Mixta. La PE tiene gran cantidad de aplicaciones en todos los campos.

3

Hay problemas que no pueden resolverse con las técnicas actuales por: • • Disponibilidad de tiempo de ordenador Capacidad de memoria

Para evitar estoparece sensato calcular la solución de un PE redondeando la solución continua. Pero el redondeo no es aconsejable debido a: • La solución redondeada no es necesariamente óptima. En muchos casos, ni siquiera estará cerca del óptimo. • La solución redondeada puede no ser factible.

5.2. DEFINICIÓN Y MODELOS DE PROGRAMACIÓN ENTERA

Un modelo de programación entera es un modelo que contienerestricciones y una función objetivo idénticas a las formuladas por planeación lineal. La única diferencia es que una o más de las variables de decisión tienen que tomar un valor entero en la solución final. Existen tres tipos de modelos de programación entera:    Pura Mixta Binaria

4

Programación Entera Pura Un modelo entero puro (PLE) es, como su nombre lo indica, un problema en el que seexige que todas las variables de decisión tengan valores enteros. Por ejemplo: Min 6x1 + 5x2 + 4x3 s.a. 108x1 + 92x2 + 58x3 >= 576 7x1 + 18x2 + 22x3 >= 83 x1, x2, x3 >= 0 y enteros Es un modelo entero puro. Sin las restricciones adicionales de que x1, x2, x3 sean enteros (o sea las condiciones de integralidad) sería un problema de programación lineal.

Programación Entera Mixta Algunas de las...