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 ↓


Comprendiendo el método del simplex en programación lineal y optimización


Introducción a la programación lineal

La programación lineal es una técnica matemática para optimizar una función objetivo lineal, sujeta a restricciones de igualdad e desigualdad lineales. Es una manera de lograr el mejor resultado en un modelo matemático cuyos requerimientos están representados por relaciones lineales. Este tipo de optimización es importante en diversos campos como la economía, la ingeniería, el ámbito militar y la planificación empresarial.

Función objetivo y restricciones

En la programación lineal, nuestro objetivo es maximizar o minimizar una función objetivo lineal. Un problema general de programación lineal se puede expresar como:

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

Aquí, x 1 , x 2 , ..., x n son variables, c 1 , c 2 , ..., c n son los coeficientes de la función objetivo, a ij son los coeficientes de las restricciones, y b i son constantes en las ecuaciones de restricción.

El método del simplex: Una visión general

El método del simplex es un algoritmo popular utilizado para resolver problemas de programación lineal. Fue desarrollado por George Dantzig en 1947. Este método consta de los siguientes pasos principales:

  • Convertir un problema de programación lineal a la forma estándar.
  • Encontrar una solución factible inicial.
  • Trabajar de manera iterativa para mejorar la función objetivo hasta que se alcance la solución óptima.

Convirtiendo a la forma estándar

Antes de aplicar el método del simplex, se debe transformar el problema de programación lineal dado en forma estándar. Esto implica asegurar que todas las restricciones estén en forma de igualdad y agregar variables de holgura, superposición o variables artificiales si es necesario.

Supongamos que tenemos una restricción como:
a 11 x 1 + a 12 x 2 ≤ b 1

Para convertir esto en igualdad, introducimos una variable de holgura s 1 :

a 11 x 1 + a 12 x 2 + s 1 = b 1

Encontrando la solución factible inicial

Una vez que el problema está en forma estándar, necesitamos encontrar una solución básica factible. Esto implica establecer las variables no básicas en cero y resolver el sistema de ecuaciones para encontrar los valores de las variables básicas.

Proceso iterativo

El propósito básico del método del simplex es mejorar el valor de la función objetivo procesando a través de las soluciones factibles para identificar la solución óptima. Esto se hace mediante pivoteo.

Ejemplo

Veamos un ejemplo visual de un problema de programación lineal. Supongamos que tenemos el siguiente problema:

Maximizar: Z = 3x 1 + 5x 2
sujeto a:
x 1 + 2x 2 ≤ 8
3x 1 + 2x 2 ≤ 12
x 1 , x 2 ≥ 0
x 1 x 2 x 1 + 2x 2 = 8 3x1 + 2x2 = 12

En el ejemplo anterior, las restricciones x 1 + 2x 2 = 8 y 3x 1 + 2x 2 = 12 se dibujan como líneas. La región factible delimitada por el polígono verde muestra donde se cumplen todas las condiciones.

Pivoteo en el método del simplex

Para mejorar la función objetivo, elegiremos elementos de pivote. Los criterios de entrada y salida ayudan a identificar cuál variable entra en la base y cuál sale. El pivoteo modifica nuestra base para que se desplace a una solución factible adyacente con un valor más alto (en caso de maximización) para la función objetivo.

Pasos involucrados en el pivoteo

El proceso de pivoteo incluye estos pasos principales:

  1. Identificar la variable de entrada:
    • Mira la fila del objetivo (también llamada fila de costos) en el tableau del simplex. Elige la variable cuyo coeficiente sea más positivo (para problemas de maximización). Esta es nuestra variable de entrada.
  2. Determinar la variable saliente:
    • Para encontrar la variable saliente, calcula el mínimo cociente del lado derecho a los coeficientes positivos de la variable de entrada en cada línea de restricción.
  3. Realizar operaciones en filas:
    • Ajusta la tabla para reflejar esta nueva base. Esto implica la operación de fila del elemento de pivote para establecer los otros elementos en la columna de la variable de entrada en cero.

Continuación del ejemplo

Apliquemos estos pasos a nuestro ejemplo anterior.

Tableau del simplex para la base inicial

La tabla inicial para convertir desigualdades en igualdades se establece con variables de holgura s 1 y s 2 para cada restricción:

| x 1 | x 2 | s 1 | s 2 | lado derecho |
,
, 1 | 2 | 1 | 0 | 8 |
, 3 | 2 | 0 | 1 | 12 |
,
, -3 | -5 | 0 | 0 | 0 |

Identifiquemos las variables de entrada y salida:

Para maximización, el coeficiente más negativo en la fila del objetivo es -5 (debajo de x 2). Esto significa que x 2 es nuestra variable de entrada.

Para encontrar la variable de salida, calculamos el cociente del RHS al coeficiente positivo de x 2 :

8/2 = 4 (para la primera fila)
12/2 = 6 (para la segunda fila)
El cociente mínimo es 4, lo que indica que la primera fila será la saliente.

Realiza operaciones en filas para crear la variable original x 2 en la primera fila.

Actualiza el resto de la tabla en consecuencia.

Solución óptima

Continúa con pasos de pivoteo similares hasta que no haya coeficientes negativos en la fila del objetivo (para maximización), indicando que se ha encontrado la solución óptima.

Conclusión

El método del simplex es un algoritmo eficiente que funciona iterando sobre los vértices de la región factible de manera sistemática. Es particularmente eficiente para problemas lineales que involucran un gran número de variables y restricciones, demostrando su utilidad tanto en el ámbito de las matemáticas teóricas como en escenarios prácticos de toma de decisiones. A través de una implementación cuidadosa y la comprensión de cada paso, los estudiantes pueden aprovechar efectivamente el poder del método del simplex para encontrar soluciones óptimas a problemas complejos.


Universitario → 9.1


U
username
0%
completado en Universitario

← Anterior (9)
Programación lineal y optimización
Siguiente (9.2) →
Dualidad en programación lineal y optimización

Comentarios 



Comprendiendo el método del simplex en programación lineal y optimización

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