TRABAJO DE INVESTIGACIÓN: PROGRAMACIÓN ENTERA”

TECNOLÓGICO NACIONAL DE MÉXICO[pic 1][pic 2]

INSTITUTO TECNOLÓGICO SUPERIOR DE HUETAMO

DIVISIÓN DE INGENIERÍA INDUSTRIAL

TRABAJO DE INVESTIGACIÓN: PROGRAMACIÓN ENTERA”

PRESENTA:

REYES GARCÍA ALONDRA                                18070068

DOCENTE: ING. REYES MORENO GONZÁLEZ

MATERIA: INVESTIGACIÓN DE OPERACIONES

TEMA: PROGRAMACIÓN ENETERA.

UNIDAD: 3

SEMESTRE: 4to

HUETAMO, MICH., A 18 DE MAYO DE 2020

INDICE

RESUMEN……………………………………………………………………1

INTRODUCCIÓN…………………………………………………………….2

3.1. INTRODUCCIÓN Y CASOS DE APLICACIÓN…………………….3

3.2. DEFINICIÓN Y MODELOS DE PROGRAMACIÓN ENTERA……5

3.3. MÉTODO GRÁFICO DE PROGRAMACIÓN ENTERA….………..8

3.4. MÉTODO DE RAMIFICACIÓN Y ACOTACIÓN…….……………..9

3.5. MÉTODO HEURÍSTICO PARA PROBLEMAS BINARIOS……..14

3.6. USO DE SOFTWARE………………………………………………..17

CONCLUSIÓN……………………………………………………………..18

REFERENCIAS BIBLIOGRÁFICAS…………………………………….19

Resumen

En la investigación presente se aborda el tema de programación entera, el cual habla sobre la solución de problemas de programación matemática. Se utiliza para resolver problemas en que las variables deben ser enteras y para problemas enteros mixtos, es decir, los que tienen algunas variables enteras y algunas continuas.

 Esta es una técnica de optimización ya que lleva a la mejor solución posible. En la unidad anterior se desarrolló el método simplex de programación lineal, el cual supone que todas las variables son continuas y generalmente da soluciones no enteras.

 El redondeo de una solución óptima es peligroso, ya que no es seguro el hecho de que la solución que resulte sea óptima o siquiera posible. Por lo tanto, se tienen que emplear otros métodos cuantitativos que permitan sólo el uso de variables enteras y que generen soluciones enteras. Entonces, los estudiosos de la investigación de operaciones han desarrollado varias técnicas que cumplen con dichas características, entre las que se pueden citar el algoritmo branch and bound y el método de variables binarias, entre otros.

Existen tres tipos de programación entera:

• Pura
• Mixta
• Binaria

[pic 3]

INTRODUCCIÓN

La programación entera tiene que ver con la solución de problemas de programación matemática en las cuales alguna o todas las variables solo pueden tomar valores enteros o negativos. Un programa entero recibe el nombre de mixto o puro, dependiendo de si en ausencia de las condiciones de integridad o totalidad. Uno de las dificultades principales en los procedimientos del cálculo de la programación entera es el efecto que tiene el error de redondeo que se genera a partir del uso inevitable de la computadora digital para resolver problemas enteros.

En algunos casos se requiere que la solución óptima se componga de valores enteros para algunas de las variables. La resolución de este problema se obtiene analizando las posibles alternativas de valores enteros de esas variables en un entorno alrededor de la solución obtenida considerando las variables reales. Muchas veces la solución del programa lineal truncado este lejos de ser el óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta. El más famoso es el método de 'Ramificar y Acotar' o Branch and Bound por su nombre en inglés. El método de Ramificar y Acotar parte de la adición de nuevas restricciones para cada variable de decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo entero.

Uno de los aportadores y un personaje muy importante en Investigación de operaciones fue Ralph Gomory.

En esta investigación se abordarán temas tales como:

• Introducción y casos de aplicación.
• Definición y modelos de programación entera.
• Método gráfico de programación entera.
• Método de ramificación y acotación.
• Método heurístico para problemas binarios.
• Uso de software

Esta investigación se hace con el fin de aprender sobre los temas abordados, para posteriormente poder realizar problemas matemáticos.[pic 4]

3.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. El nú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.

Una gran cantidad de líneas aéreas alrededor del mundo han logrado ahorros significativos en años recientes mediante el uso de modelos PEB para obtener soluciones óptimas a dichos problemas. Una de estas aerolíneas es Air New Zealand, que es la línea aérea nacional e internacional más grande con base en este país. Emplea a más de 2 000 miembros de la tripulación y opera vuelos a Australia, Asia, Norteamérica y Europa, así como entre los centros más importantes de Nueva Zelanda. Por lo general, los modelos PEB usados por la Air New Zealand cuentan con cientos de restricciones funcionales y muchos miles de variables binarias, en los que se utilizan técnicas avanzadas para resolver dichos modelos. Una estimación conservadora del ahorro que resulta del uso de estos modelos es de alrededor de 6.7 millones de dólares al año, lo cual representa 11% de la ganancia operativa de la compañía en un año reciente. Asimismo, se presentaron muchos beneficios intangibles en los que se incluye una rápida implantación, la eficiente reprogramación de cambios de última hora y una mejora del servicio a los pasajeros.

...