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 ↓


Método simplex


El método simplex es un algoritmo utilizado para resolver problemas de programación lineal, que implica encontrar el valor máximo o mínimo de una función lineal sujeta a restricciones lineales. La programación lineal es una importante herramienta de optimización en diversos campos como la economía, la ingeniería, el militar, los negocios y la ciencia.

Introducción a la programación lineal

La programación lineal implica un conjunto de ecuaciones y desigualdades que representan un modelo matemático cuya solución óptima se busca. Para un problema de programación lineal, el objetivo es optimizar (maximizar o minimizar) una función objetivo lineal sujeta a restricciones de igualdad y/o desigualdad lineales. La forma general de un problema de programación lineal se da como:

Máximo (o mínimo): 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

¿Qué es el método simplex?

El método simplex es un procedimiento iterativo que examina sistemáticamente los puntos de esquina (o vértices) de la región factible para encontrar el valor óptimo de la función objetivo. Este procedimiento implica moverse de un vértice a otro, mejorando el valor de la función objetivo en cada paso, hasta que se logra el mejor valor posible.

Procedimiento del método simplex

  1. Convertir el problema a forma estándar.
  2. Identificar una solución inicial viable.
  3. Seguir trabajando para encontrar una mejor solución hasta que no sea posible más mejora.
  4. Evaluar e interpretar la solución.

Paso 1: Convertir a forma estándar

Para aplicar el método simplex, el problema de programación lineal debe transformarse en la forma estándar. Esto implica:

  • Asegurar que todas las restricciones estén en forma de ecuaciones lineales.
  • Introducir variables de holgura para convertir desigualdades en igualdades.
  • Asegurar que todas las variables sean no negativas.

Considera el siguiente ejemplo:

Máximo: 3x 1 + 5x 2

sujeto a:
x 1 + 2x 2 ≤ 8
3x 1 + 2x 2 ≤ 12

x 1 , x 2 ≥ 0

Introducción a las Variables de Holgura:

x 1 + 2x 2 + s 1 = 8
3x 1 + 2x 2 + s 2 = 12

x 1 , x 2 , s 1 , s 2 ≥ 0

Las variables de holgura s 1 y s 2 representan recursos no utilizados de las restricciones.

Paso 2: Identificar la solución inicial

Al establecer las variables de decisión (aquí, x 1 y x 2 ) igual a cero, al mismo tiempo que se permiten las variables de holgura igual a los valores de restricción, se identifica una solución básica factible inicial.

En nuestro ejemplo, la solución inicial es:

x 1 = 0, x 2 = 0, s 1 = 8, s 2 = 12

Paso 3: Iterar para mejorar la solución

Para realizar la recursión, se crea una tabla. La fila del objetivo contiene los coeficientes negativos de la función objetivo. La recursión implica:

  • El objetivo es seleccionar la variable de entrada que tiene el coeficiente más negativo en la fila.
  • Seleccionar variables de eliminación utilizando la prueba de mínima proporción.
  • Pivoteo para actualizar la solución.
Tableau inicial:
| base | x 1 | x 2 | s 1 | s 2 | lado derecho |
| S 1 | 1 | 2 | 1 | 0 | 8 |
| S 2 | 3 | 2 | 0 | 1 | 12 |
| z | -3 | -5 | 0 | 0 | 0 |

Iteración 1:

La variable ingresada es x 2 (coeficiente más negativo en la fila z: -5 ).

Para proporción mínima: RHS / Coeficiente de x 2 = min(8/2, 12/2) = 4, por lo tanto s 1 es la variable de eliminación.

Pivoteo para reemplazar s 1 con x 2.

Tableau pivoteado:
| base | x 1 | x 2 | s 1 | s 2 | lado derecho |
| x 2 | 0.5 | 1 | 0.5 | 0 | 4 |
| S2 | 2.0 | 0 | -1 | 1 | 4 |
| z | -0.5 | 0 | 2.5 | 0 | 20 |

Iteración 2:

El coeficiente más negativo en la nueva fila z es -0.5 (para x 1 ).

Utilizando la proporción mínima: RHS / Coeficiente de x 1 = min(4/0.5, 4/2) = 2, por lo que s 2 es la variable de eliminación.

Pivoteo para reemplazar s 2 con x 1.

Tableau pivoteado:
| base | x 1 | x 2 | s 1 | s 2 | lado derecho |
| x 2 | 0.5 | 1 | 0.5 | 0 | 4 |
| x1 | 1 | 0 | -0.5 | 0.5 | 2 |
| Z | 0 | 0 | 3 | 0.5 | 22 |

El valor de la función objetivo ha mejorado a 22, y ya no hay más coeficientes negativos, por lo que la solución actual es óptima.

Ejemplo visual

La región sombreada en el gráfico representa la región factible donde todas las restricciones se superponen. El círculo marca el punto de solución óptima donde se logra el valor máximo de la función objetivo.

Paso 4: Evaluar e interpretar la solución

El método simplex proporciona los mejores valores posibles para las variables de decisión dentro de la región factible. A partir de la tabla final, podemos determinar la solución óptima:

x 1 = 2, x 2 = 4

Valor de la función objetivo: 22

Esto significa que el valor máximo de la función objetivo 3x 1 + 5x 2 es 22 cuando x 1 = 2 y x 2 = 4.

Propiedades del método simplex

  • El método simplex se mueve a lo largo del borde de la región factible, asegurando que la solución mejore o se mantenga igual en cada paso hasta que se encuentre la solución óptima.
  • Maneja eficientemente funciones objetivo lineales con restricciones, haciéndolo adecuado para problemas de programación lineal a gran escala.
  • Aunque el método generalmente comienza desde cero, todavía se requiere algún preprocesamiento para convertir cualquier problema en una forma estándar.
  • El algoritmo es finito; converge a la solución óptima o reconoce que no existe una solución para las restricciones dadas.

Beneficios y limitaciones

Las ventajas del método simplex incluyen su capacidad para proporcionar soluciones óptimas exactas a problemas de programación lineal y su aplicabilidad a una amplia gama de problemas más allá de solamente restricciones del tipo ≤. Sin embargo, este método tiene algunas limitaciones:

Beneficio

  • Proporciona una solución precisa.
  • Puede manejar problemas complejos de manera eficiente.
  • Es ampliamente entendido y utilizado, y hay muchas bibliotecas y software para soportarlo.

Limitaciones

  • Puede ser computacionalmente costoso en conjuntos de datos muy grandes.
  • No funciona directamente con problemas no lineales.
  • El ciclo puede ser problemático (a veces, pero esto se puede abordar con estrategias anti-ciclo).

Conclusión

El método simplex sigue siendo una herramienta poderosa para la optimización, especialmente en el campo de la investigación de operaciones. Proporciona un enfoque estructurado para encontrar soluciones óptimas para problemas que requieren maximización o minimización con restricciones lineales. Comprender tanto sus fortalezas como sus limitaciones permite a los profesionales aplicar efectivamente este método para resolver problemas del mundo real con fiabilidad y precisión.


Posgrado → 9.1.1


U
username
0%
completado en Posgrado

← Anterior (9.1)
Programación lineal
Siguiente (9.1.2) →
Dualidad en la programación lineal

Comentarios 



Método simplex

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