OPU- informe

UNIVERSIDAD NACIONAL FEDERICO VILLARREAL

FACULTAD DE INGENIERÍA INDUSTRIAL Y DE SISTEMAS

ESCUELA PROFESIONAL DE INGENIERÍA INDUSTRIAL

[pic 1] 

PROGRAMACIÓN ENTERA

INVESTIGACIÓN DE OPERACIONES II - SECCIÓN MB

INTEGRANTES:

CHIPANA ENCISO, Sandra Yesenia

LOPEZ CODOVA, Kenia Dennis         

RAMOS HILASACA, Angie Nicole

RIVAS VELA, Rosa Alejandra

DOCENTE:

Ing. BENAVIDES MIRANDA, María Adelina

2023 - I

ÍNDICE

I.        RESUMEN        3

II. INTRODUCCIÓN        4

III. OBJETIVO        5

IV. MARCO TEÓRICO        5

4.1. LA PROGRAMACIÓN ENTERA        5

4.2. TIPOS DE MODELO DE PROGRAMACIÓN LINEAL        6

4.2.1. Programación Entera Pura        6

4.2.2. Programación Entera Mixta        6

4.2.3. Programación Entera Binaria (0-1)        7

4.3. CRITERIO DEL TIPO DEL PROBLEMA DE PE        7

4.3.1. Directos        7

4.3.2. Codificados        8

4.3.3. Transformados        8

V. MÉTODOS        8

5.1. Método de redondeo de la solución de Programación Lineal        8

5.2. Método de enumeración completa        10

5.3. Método de Ramificación y Acotamiento        13

5.4. Método de Planos de Corte        17

5.5. Algoritmo de balas        21

VI. APLICACIONES        24

VII. CONCLUSIÓN        24

BIBLIOGRAFÍA        24

1. RESUMEN

 La programación lineal entera es una técnica de optimización de forma matemática que es utilizada para resolver problemas donde la variable de decisión es entera. El objetivo es maximizar o minimizar una función lineal entera esta dependiente de las variables de decisión, comprendiendo los métodos y sus diversas aplicaciones.

Las variables enteras en comparación de la programación lineal solo deben ser enteras, estas calculadas mediante métodos para nuestro caso se utilizó cinco métodos de estudio: redondeo, plano cortante, ramificación y acotación, enumeración completa, algoritmo de balas.

A pesar de su naturaleza compleja de la programación entera, su análisis es de manera más exacta al optimizar.

En la actulidad la programación lineal entera tiene diversas aplicaciones en la logística, la industria, planificación, producción, asignación de recursos y entre otras áreas.

Palabras claves:

Programación lineal, algoritmo, variable

II. INTRODUCCIÓN

La programación lineal entera es una poderosa herramienta matemática utilizada para resolver problemas de optimización en los que las variables de decisión deben tomar valores enteros. A diferencia de la programación lineal pura, donde las variables pueden asumir valores fraccionarios, la programación lineal entera requiere que las soluciones sean números enteros. Esto hace que el proceso de resolución sea más desafiante, ya que la búsqueda de la mejor solución se realiza en un espacio de soluciones discretas.

Los pioneros de esta técnica fueron Wagner (1950) y Manne (1959), quienes desarrollaron varios métodos de solución. Uno de los primeros enfoques de solución al tipo de problemas que plantea la programación entera, fue el de evaluación de cada posible solución, es decir, cada una de las combinaciones de valores enteros para las variables del problema, conduciendo a una solución óptima exacta. A este tipo de resoluciones se les dio el nombre de métodos exactos. Por otro lado, se desarrollaron otro tipo de técnicas que recibieron el nombre de métodos heurísticos, los cuales hacen referencia a la intuición y conducen a una solución próxima a la óptima en un tiempo razonable.

La programación lineal entera encuentra una amplia gama de aplicaciones en diversas áreas, desde la planificación de la producción y distribución, hasta la asignación de recursos y la toma de decisiones en proyectos complejos.

III. OBJETIVO

Analizar y comprender los métodos de solución y diversas aplicaciones de la Programación Entera.

IV. MARCO TEÓRICO

4.1. LA PROGRAMACIÓN ENTERA

Existen muchos ejemplos de aplicaciones distintas de la programación lineal. Sin embargo, una limitación importante que impide muchas otras aplicaciones es el supuesto de divisibilidad que requiere que las variables de decisión puedan tomar valores no enteros (fraccionarios). En muchos problemas prácticos, las variables de decisión solo tienen sentido real si su valor es entero. Por ejemplo, con frecuencia es necesario asignar a las actividades cantidades enteras de personas, máquinas o vehículos. Si el hecho de exigir valores enteros es la única diferencia que tiene un problema con la formulación de programación lineal, entonces se trata de un problema de programación entera (PE).

4.2. TIPOS DE MODELO DE PROGRAMACIÓN LINEAL

Dependiendo del tipo de variable que tengan los problemas a resolver, estos se pueden clasificar de la siguiente manera:

4.2.1. Programación Entera Pura

Son aquellos en los que las variables únicamente pueden tomar valores enteros, así como los coeficientes que intervienen en el problema. (Vehículos, objetos, personas, etc.)

Por ejemplo:

[pic 2]

Un ejemplo de ello son las siguientes aplicaciones:

• Problema de Asignación
• Problema de Corte de Rollos
• Selección de Invitados a una Boda
• Programación de la Explotación Forestal
• Problema de la Mochila

4.2.2. Programación Entera Mixta

Son aquellos en los que hay, al mismo tiempo, variables continuas y variables que solo pueden tomar valores enteros. (Dinero, tiempo, volumen, peso, etc.)

...