Posgrado
  1. Introducción al análisis real  1.1. Teoría de conjuntos y lógica en el análisis real  1.1.1. Conjuntos y operaciones en teoría de conjuntos y lógica en análisis real  1.1.2. Relaciones y funciones  1.1.3. Lógica y cuantificadores  1.1.4. Cardinalidad de conjuntos  1.2. Espacio métrico  1.2.1. Introducción a conjuntos abiertos y cerrados en espacios métricos  1.2.2. Convergencia de secuencias en un espacio métrico  1.2.3. Función continua en un espacio métrico  1.2.4. Compacidad y completitud en espacios métricos en análisis real  1.3. Secuencias y series  1.3.1. Convergencia de secuencias  1.3.2. Series infinitas  1.3.3. Convergencia uniforme  1.3.4. Serie de potencias  1.4. Discriminación  1.4.1. Teorema del valor medio  1.4.2. Serie de Taylor  1.4.3. Funciones de varias variables  1.4.4. Derivada parcial  1.5. Integración  1.5.1. Integración de Riemann y Lebesgue  1.5.2. Integrales impropias  1.5.3. Teoría de la medida: una herramienta fundamental en la integración  1.5.4. Teorema de Fubini  1.6. Análisis funcional  1.6.1. Comprendiendo los espacios de Banach  1.6.2. Espacios de Hilbert  1.6.3. Operadores en espacios  1.6.4. Teoría espectral
  2. Álgebra abstracta  2.1. Entendiendo los grupos en el álgebra abstracta  2.1.1. Definiciones y ejemplos de grupos en álgebra abstracta  2.1.2. Homomorfismos de grupos  2.1.3. Introducción a los subgrupos normales  2.1.4. Teorema de Sylow  2.2. Anillos y campos  2.2.1. Ideales y anillos cociente  2.2.2. Extensiones de campos  2.2.3. Teoría de Galois  2.2.4. Anillos de polinomios  2.3. Introducción a los módulos en álgebra abstracta  2.3.1. Homomorfismo de módulos  2.3.2. Módulos libres  2.3.3. Introducción a los productos tensoriales  2.3.4. Secuencia exacta en módulos  2.4. Álgebra lineal  2.4.1. Espacio vectorial  2.4.2. Autovalores y autovectores  2.4.3. Espacio de producto interior  2.4.4. Diagonalización
  3. Topología  3.1. Topología general  3.1.1. Conjuntos abiertos y cerrados  3.1.2. Compacidad y conexión  3.1.3. Mapas continuos  3.1.4. Axioma de separación  3.2. Topología algebraica  3.2.1. Comprensión de los grupos fundamentales en la topología algebraica  3.2.2. Homotopía y homología  3.2.3. Complejo simplicial  3.2.4. Secuencias exactas en homología  3.3. Topología diferencial  3.3.1. Comprendiendo las variedades en topología diferencial  3.3.2. Funcionamiento suave  3.3.3. Espacio tangente y cotangente  3.3.4. Fibrados vectoriales
  4. Ecuaciones diferenciales  4.1. Ecuación diferencial ordinaria  4.1.1. Ecuaciones de primer orden  4.1.2. Ecuaciones lineales de segundo orden  4.1.3. Sistemas de ecuaciones diferenciales  4.1.4. Análisis de estabilidad en ecuaciones diferenciales ordinarias  4.2. Ecuaciones en derivadas parciales  4.2.1. Clasificación de EDP  4.2.2. Entendiendo las series de Fourier en ecuaciones diferenciales parciales  4.2.3. Introducción a las funciones de Green  4.2.4. Método de caracterización  4.3. Sistemas dinámicos en ecuaciones diferenciales  4.3.1. Teoría de la sostenibilidad  4.3.2. Ciclos límite en sistemas dinámicos  4.3.3. Teoría del caos  4.3.4. Teoría de bifurcación
  5. Probabilidad y estadística  5.1. Teoría de la probabilidad  5.1.1. Variables aleatorias  5.1.2. Distribuciones de probabilidad  5.1.3. Ley de los grandes números  5.1.4. Teorema del límite central  5.2. Inferencia estadística  5.2.1. Pruebas de hipótesis  5.2.2. Intervalo de confianza  5.2.3. Métodos bayesianos  5.2.4. Estimación de máxima verosimilitud  5.3. Procesos estocásticos  5.3.1. Cadenas de Markov  5.3.2. Movimiento browniano  5.3.3. Comprendiendo los procesos de Poisson  5.3.4. Martingalas: Un estudio integral en probabilidad y estadística
  6. Análisis numérico  6.1. Soluciones numéricas de ecuaciones  6.1.1. Descubrimiento original  6.1.2. Métodos iterativos  6.1.3. Análisis de convergencia  6.1.4. Cotas de error en soluciones numéricas de ecuaciones  6.2. Álgebra lineal numérica  6.2.1. Factorización de matrices  6.2.2. Cálculo de valores propios  6.2.3. Matrices dispersas  6.2.4. Técnicas de preacondicionamiento  6.3. Integración y diferenciación numérica  6.3.1. Métodos de cuadratura  6.3.2. Introducción a las diferencias finitas  6.3.3. Análisis de errores en la integración y diferenciación numérica  6.3.4. Métodos adaptativos en integración y diferenciación numérica
  7. Análisis complejo  7.1. Números complejos  7.1.1. Forma polar  7.1.2. Conjugados complejos  7.1.3. Forma exponencial de los números complejos  7.1.4. Raíces de la unidad  7.2. Funciones analíticas  7.2.1. Ecuaciones de Cauchy–Riemann  7.2.2. Series de potencias  7.2.3. Mapeo conforme  7.2.4. Funciones armónicas  7.3. Integración en el plano complejo  7.3.1. Teorema de Cauchy  7.3.2. Teorema del residuo  7.3.3. Integración de contornos  7.3.4. Transformaciones integrales
  8. Lógica matemática y fundamentos  8.1. Lógica proposicional  8.1.1. Tablas de verdad  8.1.2. Equivalencia lógica en la lógica proposicional  8.1.3. Técnicas de demostración en lógica proposicional  8.1.4. Solución en lógica proposicional  8.2. Lógica de predicados  8.2.1. Cuantificadores en lógica de predicados  8.2.2. Sistemas formales en lógica de predicados  8.2.3. Integridad y solidez  8.2.4. Teoría de modelos  8.3. Teoría de conjuntos  8.3.1. Cardinalidad y ordinalidad  8.3.2. Sistemas axiomáticos  8.3.3. Comprender la teoría de conjuntos de Zermelo-Fraenkel  8.3.4. Fuerzas en la teoría de conjuntos
  9. Personalización  9.1. Programación lineal  9.1.1. Método simplex  9.1.2. Dualidad en la programación lineal  9.1.3. Análisis de sensibilidad en programación lineal  9.1.4. Métodos de punto interior  9.2. Programación no lineal  9.2.1. Descenso de gradiente  9.2.2. Multiplicadores de Lagrange  9.2.3. Optimización convexa  9.2.4. Programación cuadrática  9.3. Optimización Combinatoria  9.3.1. Algoritmos de grafos  9.3.2. Programación entera  9.3.3. Flujo de red  9.3.4. Algoritmos de aproximación
  10. Matemáticas discretas  10.1. Teoría de grafos  10.1.1. Representación de grafos  10.1.2. Llanura y color  10.1.3. Algoritmo de camino más corto  10.1.4. Flujo de red  10.2. Compañerismo  10.2.1. Permutación y combinación  10.2.2. Función generadora  10.2.3. Relación de recurrencia  10.2.4. Comprendiendo el Principio de Inclusión-Exclusión  10.3. Criptografía  10.3.1. Aplicaciones de la teoría de números en criptografía  10.3.2. Criptografía Simétrica y Asimétrica  10.3.3. RSA y criptografía de curvas elípticas  10.3.4. Criptografía post-cuántica

Posgrado → Personalización → Optimización Combinatoria ↓


Programación entera


La programación entera es una rama de la optimización matemática o programación matemática. En este contexto, "optimización" significa seleccionar el mejor elemento de un conjunto dado de alternativas disponibles, con respecto a algún criterio. La programación entera trata específicamente problemas de optimización donde algunas o todas las variables están restringidas a ser enteras.

Tipos de programación entera

  • Programación entera pura (PIP): Todas las variables de decisión deben tomar valores enteros.
  • Programación entera mixta (MIP): Solo algunas de las variables deben ser enteras, mientras que otras pueden no ser enteras.
  • Programación entera binaria: Caso especial de programación entera donde las variables están limitadas a 0 o 1. A menudo se utiliza para decisiones de sí/no.

Importancia en la optimización combinatoria

Muchos problemas en optimización combinatoria pueden formularse como problemas de programación entera. La optimización combinatoria se centra en objetos que son discretos o que pueden contarse. Dado que los valores enteros son discretos, la programación entera es la mejor manera de resolver esos problemas y se vuelve importante en su resolución.

Formulación del problema de programación entera

El problema de programación entera generalmente se formula de la siguiente manera:

Maximizar (o Minimizar): c 1 x 1 + c 2 x 2 + ... + c n x n 
Sujeto a: 
a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1 
a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2 
... 
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m 
Donde: x 1 , x 2 , ..., x n son enteros

Aquí, c i denota los coeficientes de la función objetivo que desea maximizar o minimizar, a ij denota los coeficientes de las restricciones y b i denota los límites de las restricciones.

Ejemplo: el problema de la mochila

Consideremos un ejemplo clásico de programación entera: el problema de la mochila. El objetivo es maximizar el valor total de los artículos colocados en la mochila, sin exceder su capacidad de carga.

Ejemplo de un problema de mochila:

  • Artículos: 4 artículos con pesos w = [2, 3, 4, 5] y valores v = [3, 4, 5, 6]
  • Capacidad: Esta bolsa puede transportar el peso de máximo 5 personas.

Formule el problema de la mochila utilizando la programación entera:

Maximizar: 3x 1 + 4x 2 + 5x 3 + 6x 4 
Sujeto a: 2x 1 + 3x 2 + 4x 3 + 5x 4 ≤ 5 
Donde: x 1 , x 2 , x 3 , x 4 ∈ {0, 1}

La restricción x i ∈ {0, 1} asegura que cada artículo pueda incluirse o no en la bolsa.

Representación visual

5 (peso) 4 (peso) 3 (peso) 2 (peso)

Esta vista muestra un modelo simplificado de una bolsa con el peso empaquetado en orden descendente.

Resolución de problemas de programación entera

Los problemas de programación entera son generalmente NP-duros, lo que significa que no se conocen algoritmos que puedan resolver todos esos problemas de manera eficiente (en tiempo polinómico). Sin embargo, se pueden adoptar varios enfoques para resolver problemas específicos.

1. Método de ramificación y acotación

Es un método ampliamente utilizado para resolver problemas de programación entera. La idea básica es dividir el problema en problemas más pequeños (ramificaciones) y encontrar la solución óptima evaluando los límites de estos subproblemas, mientras que los subproblemas deben eliminarse sistemáticamente si sus límites indican que no pueden contener una mejor solución (límite).

2. Método de planos de corte

Este método mejora la relajación lineal del problema de programación entera al insertar iterativamente restricciones lineales (planos de corte) en el problema, con el objetivo de filtrar las regiones del espacio de soluciones que no tienen soluciones enteras.

Aplicaciones prácticas de la programación entera

  • Asignación de recursos: asignación de recursos limitados entre actividades competitivas.
  • Programación: Asignar marcos de tiempo a tareas, como horarios de trabajo, horarios de transporte, etc.
  • Diseño de redes: diseño de rutas de redes, especificación de ancho de banda, etc.
  • Planificación de producción: Planificación de actividades de producción, como la cantidad de productos a producir.

Ejemplo de problema: programación de tareas

Considere un conjunto de algunas tareas, cada una de las cuales tiene un tiempo de procesamiento y una fecha límite específicos. El objetivo es programar las tareas de tal manera que se minimice la latencia total, que es la cantidad en que se retrasan las tareas para completar y tardan más que la fecha límite.

Ejemplo:

  • Trabajos: Trabajo 1, Trabajo 2, Trabajo 3, tiempos de procesamiento 2, 4, 3 y fechas límite 2, 6, 5 respectivamente.

Formule este problema de programación utilizando la programación entera:

Minimizar: T 1 + T 2 + T 3 
Sujeto a: 
x 1,1 + x 1,2 + x 1,3 = 1 
x 2,1 + x 2,2 + x 2,3 = 1 
x 3,1 + x 3,2 + x 3,3 = 1 
Restricciones de finalización: 
C 1 = 2x 1,1 + 4x 2,1 + 3x 3,1 
C 2 = C 1 + 2x 1,2 + 4x 2,2 + 3x 3,2 
C 3 = C 2 + 2x 1,3 + 4x 2,3 + 3x 3,3 
Donde: 
T i = max(0, C i - plazo i ) 
x i,j ∈ {0, 1}

Ventajas de la programación entera

La programación entera proporciona un marco poderoso para resolver muchos problemas complejos de toma de decisiones, debido a su capacidad para modelar requisitos lógicos dentro de problemas de optimización. Esto es particularmente beneficioso cuando:

  • Las decisiones pueden representarse naturalmente en términos de encendido/apagado (por ejemplo, si invertir o no).
  • Su solución debe adherirse a restricciones lógicas estrictas.
  • Deberá resolver problemas donde algunas de las variables requieran valores diferentes.

Conclusión

La programación entera juega un papel vital no solo en el amplio campo de la optimización sino también en muchas aplicaciones prácticas en diversas industrias. A pesar de su complejidad e intensidad computacional, existen estrategias y heurísticas efectivas que pueden usarse para obtener soluciones factibles a problemas del mundo real. A medida que el poder de cálculo continúa aumentando, la programación entera se está volviendo más útil y generalizada en la gestión de desafíos complejos de toma de decisiones.


Posgrado → 9.3.2


U
username
0%
completado en Posgrado

← Anterior (9.3.1)
Algoritmos de grafos
Siguiente (9.3.3) →
Flujo de red

Comentarios 



Programación entera

https://www.buddymath.com/g/9.3.2?bmal=es