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 → Programación lineal ↓


Dualidad en la programación lineal


La programación lineal (LP) es un método para lograr los mejores resultados en modelos matemáticos cuyos requisitos se representan mediante relaciones lineales. Es una técnica utilizada para la optimización, donde se busca minimizar o maximizar una función objetivo lineal sujeta a un conjunto de restricciones lineales. Un aspecto esencial de la programación lineal es el concepto de dualidad, que proporciona un profundo conocimiento sobre el comportamiento de las funciones de optimización.

Fundamentos del dualismo

En la programación lineal, para cada problema de optimización, existe un problema dual correspondiente. Si el problema original se llama 'problema primal', su contraparte se conoce como 'problema dual'. La dualidad proporciona una perspectiva poderosa: la solución óptima de un problema se puede encontrar examinando la solución del otro.

Hay dos resultados principales respecto a la dualidad en la programación lineal:

  • Dualidad débil: El valor de la función objetivo de la dualidad en cualquier solución factible es siempre mayor o igual al valor de la función objetivo del original en cualquier solución factible.
  • Dualidad fuerte: Si tanto un primitivo como una dualidad tienen soluciones óptimas, entonces el valor óptimo de la función objetivo del primitivo es igual al de la dualidad.

Problema primal y dualidad

Problema primario

Maximizar: 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

             x 1 , x 2 , ..., x n ≥ 0

Problema dual

Minimizar: b 1 y 1 + b 2 y 2 + ... + b m y m
Sujeto a: a 11 y 1 + a 21 y 2 + ... + a m1 y m ≥ c 1
             a 12 y 1 + a 22 y 2 + ... + a m2 y m ≥ c 2
             ,
             a 1n y 1 + a 2n y 2 + ... + a mn y m ≥ c n

             y 1 , y 2 , ..., y m ≥ 0

Interpretación y significado económico

En el problema principal, el objetivo es determinar el máximo beneficio (o ganancia) que se puede obtener mientras se satisfacen las restricciones impuestas por las limitaciones de recursos. Cada variable de decisión representa una posible actividad o estrategia, y las restricciones representan los límites en los recursos necesarios para estas actividades.

El problema de la dualidad, por otro lado, busca el costo mínimo necesario para alcanzar o superar un nivel deseado de beneficio total. Aquí, las variables de decisión se pueden interpretar como precios sombra: el precio de minimizar cada restricción en el problema de optimización primario. La dualidad proporciona un tipo de sistema de precios de equilibrio.

Interpretación geométrica

Considere un espacio bidimensional para facilitar la visualización. Para ambos problemas primal y dual, las soluciones se encuentran en los vértices (esquinas) de sus regiones factibles. Las desigualdades primal y dual correspondientes definen regiones geométricas, y su intersección puede potencialmente contener la solución óptima para ambos problemas primal y dual.


    
    
    
    
    X
    Y
    Obstáculo 1
    Obstáculo 2

El principio de la holgura complementaria

Un componente integral que conecta las formulaciones primal y dual es el concepto de holgura complementaria. Consiste en las condiciones que deben cumplirse si tanto el primal como su dual tienen soluciones óptimas. Para cada par de restricciones primal y dual, deben cumplirse las condiciones de holgura complementaria:

Si x j > 0, entonces las condiciones de dualidad de la j th son estrictas;
Si se relaja el i-ésimo límite, entonces la variable fundamental en el i-ésimo debe ser cero.

Así, si alguna restricción en el problema original se relaja, entonces la variable correspondiente en la dualidad debe tener un valor de cero en la optimalidad, y viceversa.

Ejemplo de dualismo

Problema elemental de muestra

Maximizar z = 2x 1 + 3x 2
sujeto a
             x 1 + 2x 2 ≤ 10
             2x 1 + x 2 ≤ 8
             x 1 , x 2 ≥ 0

Problema dual compatible

Minimizar w = 10y 1 + 8y 2
sujeto a
             y 1 + 2y 2 ≥ 2
             2y 1 + y 2 ≥ 3
             y 1 , y 2 ≥ 0

Aplicaciones y significado

El concepto de dualidad no es solo teórico, sino que también tiene importantes implicaciones prácticas. Permite derivar la solución de un problema a partir de la solución de otro problema, potencialmente más simple. La dualidad se utiliza en una variedad de campos como la economía, la ingeniería, la ciencia militar y el transporte.

Por ejemplo, en economía, el problema dual proporciona información sobre la optimización de precios y la asignación de recursos. Las soluciones duales indican qué valor se debe asignar a recursos adicionales, proporcionando información valiosa sobre precios a los responsables de la toma de decisiones.

Conclusión

La dualidad en la programación lineal cierra la brecha entre diferentes enfoques de optimización, permitiendo una comprensión más profunda y eficiencia en la resolución de problemas complejos. Ya sea por interés académico o para soluciones prácticas, es importante entender el concepto de dualidad para aprovechar al máximo las técnicas de programación lineal.


Posgrado → 9.1.2


U
username
0%
completado en Posgrado

← Anterior (9.1.1)
Método simplex
Siguiente (9.1.3) →
Análisis de sensibilidad en programación lineal

Comentarios 



Dualidad en la programación lineal

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