Método simplex: lectura de notas

Método simplex. se basa en un procedimiento algebraico y su explicación geométrica puede ser interpretada por el método gráfico.

Resumen

[ hide ]

  • 1 Conceptos básicos del método simplex
  • 2 Para crear la tabla del método simplex
  • 3 Procedimiento de cálculo para el método símplex
  • 4 casos máximo
  • 5 Caso mínimo
  • 6 Fuente

Conceptos básicos del método simplex

  • La aplicación del método símplex supone que tiene un sistema de restricción lineal formado solo por ecuaciones lineales. Esta transformación se puede realizar de forma muy sencilla introduciendo variables adicionales, denominadas variables de desviación. Estas variables se definen una para cada restricción y si tiene el signo ≤ se suma la variable de margen y el signo es ≥ se resta la variable de margen.
  • Después de haber tenido un problema de programación lineal estándar, es decir, todas las restricciones tienen signos iguales, es necesario determinar la Solución Básica Factible Inicial (SBFI).
  • Dado un sistema de m ecuaciones lineales con n variables (AX = b) con m
  • Las variables que forman parte de la matriz B se denominan variables básicas (XB) y las que forman parte de la matriz W se denominan variables no básicas (XW), por lo que el vector X está compuesto por el conjunto de variables básicas y no básicas. , es decir, X = (XB, XW).
  • Entonces, el sistema de restricciones del problema de programación lineal AX = b se puede escribir como: AX = BXB + WXW = b. Si asumimos que las variables no fundamentales tomarán un valor de cero, la expresión anterior sería BXB = b. La expresión XB = B-1 b que se obtiene de la anterior, permitiría calcular la solución básica factible inicial.

Para crear la tabla del método simplex

El método simplex se desarrolla en la tabla simplex. Cada iteración requiere una tabla.

En la primera columna se escribirán los coeficientes de la función objetivo correspondientes a las variables básicas, escribiendo dichas variables en la segunda columna. La tercera columna indica los valores que toman las variables básicas en la solución representada por la tabla simplex. El resto de columnas representan los vectores Pj correspondientes a cada uno de los vectores aj de la matriz A (Pj es el vector coordenado de cada vector aj con respecto a la base considerada). Los valores Zj -Cj correspondientes a cada vector aj aparecen en la última fila de la tabla. Los coeficientes Zj se determinan mediante la siguiente expresión: Zj = CBPj

Procedimiento de cálculo para el método simplex

El procedimiento iterativo en el que se basa el método símplex se puede resumir en los siguientes pasos:

  • Paso 1: Convierta las desigualdades en ecuaciones usando las variables de brecha.
  • Paso 2: Determine la solución básica factible inicial XB *, los valores Z *, Pj y Zj – Cj y construya la tabla simplex que resume toda la información sobre esta solución inicial. La solución base inicial debe tener la característica de que la matriz base debe ser unitaria. Esto facilita el cálculo de la matriz inversa.
  • Paso 3: Examine los valores de los coeficientes Zj – Cj en la tabla simplex.

Pueden ocurrir las siguientes situaciones: Caso máximo y Caso mínimo.

Caso máximo

  • Todo Zj – Cj 0. En este caso, se ha alcanzado la solución óptima. (criterio de optimalidad)
  • Uno o más Zj – Cj <0. En este caso, se debe calcular una nueva solución base determinando el vector ak que entra en la base usando la siguiente expresión:

ZK –CK = MIN (Zj – Cj) para cualquier aj con Zj – Cj <0 (1)

Si se obtiene este valor mínimo para uno o más vectores, se puede elegir cualquiera como vector de entrada. Una vez elegido el vector ak, pueden surgir dos casos:

  • Caso 1: Los valores Pik≤0 para cada i. Esto indica la existencia de una solución ilimitada.
  • Caso 2: Tenemos Pik> 0 para al menos una i. En este caso, se puede encontrar una nueva solución básica en la que el valor de Z mejora o es óptimo.

Caso mínimo

  • Todo Zj – Cj 0. En este caso, se ha alcanzado la solución óptima. (Criterio de optimalidad)
  • Uno o más Zj – Cj> 0. En este caso, se debe calcular una nueva solución base determinando el vector ak que entra en la base usando la siguiente expresión (1).

Paso 4: Si tenemos Pik> 0 para al menos una i, determinamos el vector que sale de ella usando la expresión:

Θ = XBr / Prk = MIN {X * Bi / Pik, Pik> 0}

El vector ar debe extraerse de la base y reemplazarse por el vector ak. Si se obtiene el mismo valor de obtención para 2 o más vectores, se puede elegir cualquiera como vector de salida.

Paso 5: Los nuevos valores XB, Z, Pj y Zj-Cj se calculan insertando estos valores en la nueva tabla simplex. Después de completar este paso, vuelva al paso 3 repitiendo el procedimiento hasta que se alcance la solución óptima.

Deja un comentario