Universitario
  1. Álgebra  1.1. Álgebra lineal  1.1.1. Matrices  1.1.2. Determinantes  1.1.3. Sistemas de ecuaciones lineales  1.1.4. Comprender los espacios vectoriales en álgebra lineal  1.1.5. Transformaciones lineales  1.1.6. Valores propios y vectores propios  1.1.7. Diagonalización  1.1.8. Espacio de producto interior  1.1.9. Ortogonalidad y base ortonormal  1.1.10. Descomposición en valores singulares  1.2. Álgebra abstracta  1.2.1. Grupo  1.2.2. Subgrupos  1.2.3. Grupos cíclicos  1.2.4. Grupo de permutaciones  1.2.5. Homeomorfismo  1.2.6. Subgrupos normales  1.2.7. Introducción a los anillos en álgebra abstracta  1.2.8. Campo  1.2.9. Ideales y anillos cocientes  1.2.10. Anillos de polinomios  1.2.11. Espacio vectorial sobre un campo  1.2.12. Módulo  1.2.13. Introducción a la teoría de Galois
  2. Cálculos  2.1. Cálculo diferencial  2.1.1. Comprender los límites en el cálculo diferencial  2.1.2. Comprendiendo el continuo en cálculo diferencial  2.1.3. Derivadas  2.1.4. Comprendiendo la regla de la cadena en el cálculo diferencial  2.1.5. Diferenciación implícita  2.1.6. Aplicaciones de derivadas  2.1.7. Problemas de optimización  2.1.8. Comprendiendo el teorema del valor medio  2.2. Cálculo integral  2.2.1. Integral definido  2.2.2. Integral indefinido  2.2.3. Técnicas de integración  2.2.4. Integrales impropias  2.2.5. Aplicaciones de la integración  2.2.6. Longitud del arco y área de la superficie  2.3. Cálculo multivariable  2.3.1. Derivada parcial  2.3.2. Gradiente en cálculo multivariable  2.3.3. Divergencia y rotacional  2.3.4. Introducción a la integración múltiple  2.3.5. Comprender las integrales de línea  2.3.6. Integrales de superficie  2.3.7. Explicación del teorema de Green  2.3.8. Teorema de Stokes  2.3.9. Teorema de la divergencia  2.3.10. Jacobiano
  3. Ecuaciones diferenciales  3.1. Ecuación diferencial ordinaria  3.1.1. Ecuaciones diferenciales de primer orden  3.1.2. Ecuaciones diferenciales de orden superior  3.1.3. Sistemas de ecuaciones diferenciales  3.1.4. Solución en serie  3.1.5. Métodos numéricos para EDOs  3.2. Ecuaciones diferenciales parciales  3.2.1. Entendiendo la ecuación del calor  3.2.2. Ecuación de onda  3.2.3. Ecuación de Laplace  3.2.4. Separación de variables  3.2.5. Métodos de transformada de Fourier en ecuaciones diferenciales parciales
  4. Análisis Real  4.1. Sucesiones y series  4.1.1. Convergencia de secuencias  4.1.2. Pruebas de series  4.1.3. Series de potencias  4.1.4. Convergencia uniforme  4.2. Funciones de variables reales  4.2.1. Límites y continuidad  4.2.2. Comprendiendo la continuidad uniforme  4.2.3. Diferenciación de funciones de variables reales  4.2.4. Integración de Riemann  4.2.5. Integración de Lebesgue
  5. Introducción al Análisis Complejo  5.1. Números complejos  5.1.1. Forma polar  5.1.2. Forma exponencial en números complejos  5.2. Funciones de una variable compleja  5.2.1. Funciones analíticas  5.2.2. Ecuaciones de Cauchy–Riemann  5.2.3. Integrales de contorno  5.2.4. Teorema de integración de Cauchy  5.2.5. Teorema del residuo en análisis complejo  5.2.6. Mapeo conformal
  6. Probabilidad y estadística  6.1. Teoría de la probabilidad  6.1.1. Conceptos Básicos de Probabilidad  6.1.2. Variables aleatorias  6.1.3. Comprendiendo Distribuciones de Probabilidad  6.1.4. Expectativa y variación  6.1.5. Probabilidad condicional y el teorema de Bayes  6.2. Figuras  6.2.1. Estadísticas descriptivas  6.2.2. Estadística inferencial  6.2.3. Prueba de hipótesis  6.2.4. Análisis de regresión  6.2.5. Comprendiendo ANOVA: Análisis de Varianza
  7. Métodos numéricos  7.1. Algoritmo para encontrar raíces  7.2. Integración numérica  7.3. Diferenciación numérica  7.4. Soluciones numéricas de ecuaciones diferenciales  7.5. Cálculos de matrices  7.6. Interpolación y extrapolación
  8. Introducción a las matemáticas discretas  8.1. Argumentos y pruebas  8.2. Compañerismo  8.3. Teoría de grafos  8.4. Álgebra booleana  8.5. Relación de recurrencia
  9. Programación lineal y optimización  9.1. Comprendiendo el método del simplex en programación lineal y optimización  9.2. Dualidad en programación lineal y optimización  9.3. Programación entera  9.4. Optimización no lineal
  10. Comprendiendo la topología: un viaje a través de formas y espacios  10.1. Espacio métrico  10.2. Espacios topológicos  10.3. Continuidad y homeomorfismos  10.4. Densidad  10.5. Asociatividad en topología
  11. Introducción a la geometría  11.1. Geometría euclidiana  11.2. Geometría diferencial  11.3. Geometría no euclidiana  11.4. Geometría proyectiva
  12. Física matemática  12.1. Series de Fourier  12.2. Transformada de Laplace  12.3. Aplicaciones de ecuaciones diferenciales  12.4. Funciones especiales
  13. Teoría de conjuntos y lógica  13.1. Conjuntos y subconjuntos  13.2. Relaciones y funciones  13.3. Entendiendo la cardinalidad en teoría de conjuntos y lógica  13.4. Comprendiendo la lógica formal en la teoría de conjuntos y la lógica  13.5. Teoría de conjuntos de Zermelo–Fraenkel
  14. Introducción al análisis funcional  14.1. Ubicación estándar  14.2. Espacios de Banach  14.3. Comprender el espacio de Hilbert en análisis funcional  14.4. Operadores lineales

Universitario → Programación lineal y optimización ↓


Programación entera


La programación entera es una rama de la optimización o programación matemática. Significa encontrar la mejor solución de un conjunto de soluciones posibles. Mientras que la programación lineal trata con ecuaciones lineales y algunas restricciones, la programación entera es un tipo especial donde las variables de solución deben ser enteros. Esta restricción hace que la programación entera sea más compleja y desafiante, pero también más aplicable en escenarios reales donde algunos recursos pueden ser solo unidades enteras.

¿Qué es la programación entera?

La programación entera involucra problemas matemáticos que tienen como objetivo optimizar una función objetivo dada. A primera vista puede parecer programación lineal, pero hay una diferencia importante: en la programación entera, la probabilidad de que se optimice una función es constante a menos que algunas o todas las variables sean enteros. están limitados solamente.

La programación entera puede ser utilizada para resolver una variedad de problemas de optimización. Algunos ejemplos incluyen planificación y programación, asignación de recursos y toma de decisiones en industrias como la logística, manufactura, telecomunicaciones y finanzas.

Formulación matemática

La forma general de un problema de programación lineal puede expresarse de la siguiente manera:

Max o Min: c1*x1 + c2*x2 + ... + cn*xn

Sujeto a:

a11*x1 + a12*x2 + ... + a1n*xn (<=, =, o >=) b1
a21*x1 + a22*x2 + ... + a2n*xn (<=, =, o >=) b2
,
am1*x1 + am2*x2 + ... + amn*xn (<=, =, o >=) bm

x1, x2, ..., xn >= 0

Aquí, c denota los coeficientes de la función objetivo, a denota los coeficientes de las restricciones y b denota las constantes del lado derecho. El objetivo es encontrar los valores de x1, x2, ..., xn que maximicen o minimicen la función objetivo. Hacer el mínimo.

En la programación entera, una o más de las variables x1, x2, ..., xn están restringidas a tomar solo valores enteros. Cuando todas las variables están restringidas a ser enteros, el problema se denomina un problema de programación entera pura. Cuando solo algunas de las variables son enteros, se trata de un problema de programación mixta entera.

Ejemplo

Problema simple de programación entera

Veamos un ejemplo simple de programación entera para entender estos conceptos. Supongamos que una empresa quiere decidir cuál es la cantidad óptima de productos A y B a producir. La ganancia de una unidad de producto A es de $3, y es de $5 del producto B. La empresa no puede producir más de 7 unidades de A y 4 unidades de producto B conjuntamente.

El modelo de programación entera se puede configurar de la siguiente manera:

Max: 3A+5B

Sujeto a:

a + b <= 7
b <= 4
A, B >= 0 y enteros

Aquí, tanto A como B deben ser enteros porque la empresa no puede fabricar una fracción de un producto. Este requisito es donde la programación entera se vuelve más compleja que la programación lineal simple.

Visualización de soluciones enteras

Para nuestro ejemplo, visualicemos la región factible y la solución. Considere las restricciones trazadas en el gráfico marcando especialmente los enteros:

A B 2,4 3,4 4,3

En el ejemplo SVG, la línea A + B = 7 y la línea B = 4 están dibujadas con puntos íntegros. Estos puntos tienen (2,4), (3,4) y (4,3) incluidos.

Puesto que nuestro objetivo es maximizar nuestra función objetivo 3A + 5B para los puntos de solución (3,4) y (4,3), los valores objetivos son:

  • Para el punto (3,4): 3 * 3 + 5 * 4 = 9 + 20 = 29
  • Para el punto (4,3): 3 * 4 + 5 * 3 = 12 + 15 = 27

Por lo tanto, la máxima ganancia se obtiene en (3,4), produciendo 3 unidades de A y 4 unidades de B.

Desafíos en la programación entera

La programación entera tiene dificultades inherentes que la programación lineal general no tiene. Los problemas de programación lineal pueden resolverse utilizando métodos como el algoritmo símplex, que navega eficientemente a través de las regiones factibles.

Sin embargo, agregar restricciones de enteros complica la búsqueda de una solución. Dado que los espacios matemáticos involucrados en la programación entera no son agradables formas convexas, se necesitan algoritmos especiales para la visualización y el cálculo como:

  • Rama y acotar: divide repetidamente el problema en subproblemas ("ramas"), encuentra regiones factibles y resuelve programas lineales más fáciles.
  • Plano de corte: Esto es una adición a la relajación estándar de programación lineal. Agrega restricciones para crear una región factible que muestre solo soluciones enteras.
  • Rama y corte: Combina los métodos anteriores, proporcionando eficiencia y mayor practicidad en la resolución de programas mixtos e enteros.

Aplicaciones de la programación entera

Debido a su naturaleza, la programación entera encuentra amplias aplicaciones en diversos campos. Estas funciones resuelven problemas en lugar de explorar partes teóricas.

A continuación se presentan algunas de las principales áreas de aplicación:

  • Manufactura: contratación, utilización de máquinas, mezcla y distribución.
  • Telecomunicaciones: asignación de ancho de banda, diseño de red y enrutamiento.
  • Logística: gestión de inventario, enrutamiento de vehículos y programación de personal.
  • Finanzas: selección de cartera y presupuesto de capital.

Cada área hace uso de factores que favorecen la programación entera, como la naturaleza discreta y la optimización de elección explícita entre posibilidades finitas.

Conclusión

La programación entera sirve como un activo clave en el campo de la optimización. Su funcionalidad agrega a la practicidad, ya que las restricciones que se ven a menudo en la realidad son naturalmente abordadas por sus soluciones discretas. Siendo de naturaleza compleja y de cálculo, la programación entera es un proceso muy simple y costoso. No obstante, los métodos existentes la hacen factible y ampliamente aplicable. El potencial de la optimización continúa creciendo en adopción a medida que las industrias avanzan, impulsadas en parte por los avances y el entendimiento de la programación entera.


Universitario → 9.3


U
username
0%
completado en Universitario

← Anterior (9.2)
Dualidad en programación lineal y optimización
Siguiente (9.4) →
Optimización no lineal

Comentarios 



Programación entera

https://www.buddymath.com/ug/9.3?bmal=es