Principios del método simplex

El principio del método simplex es el siguiente:

Primero intente encontrar una solución básica factible (inicial) y luego juzgue si esta solución básica factible es la solución óptima según La teoría de la optimización. Si es la solución óptima, se genera el resultado y el cálculo se detiene.

Si no es la solución óptima, intente generar una nueva solución básica factible con un mejor valor objetivo a partir de la solución básica factible actual y luego use la teoría de la optimización para juzgar la nueva solución básica factible obtenida. Ver si es la solución óptima, que constituye un algoritmo iterativo.

Dado que solo hay un número finito de soluciones básicas factibles y el valor objetivo mejora cada vez, se debe terminar en un paso finito. Si el problema original tiene una solución óptima, se puede alcanzar en un número limitado de pasos y la cantidad de cálculo es mucho menor que el método exhaustivo. Si el problema original no tiene una solución óptima, se puede descubrir a tiempo. De acuerdo con la teoría de la optimización, el cálculo se puede detener para evitar errores y operaciones no válidas. "

El método simplex es uno de los algoritmos más utilizados y eficaces para resolver problemas de programación lineal. El método simplex fue propuesto por primera vez por George Dantzig en 1947. En los últimos 70 años, aunque se han producido muchas deformaciones desarrollado, pero mantiene el mismo concepto básico. Si existe la solución óptima a un problema de programación lineal, debe encontrarse en el vértice de su región factible.

En base a esto, se desarrolla la idea básica de. el método simplex es: primero, encontrar un vértice en la región factible y juzgar si es óptimo de acuerdo con ciertas reglas; de lo contrario, cambiar a otro vértice adyacente y mejorar el valor de la función objetivo, y así sucesivamente; se encuentra.