¿Qué es el método simplex en la investigación de operaciones?

Método simplex

Método simplex

Un método general para resolver problemas de programación lineal. El simplex fue propuesto por primera vez por el matemático estadounidense G.B. Danzik en 1947. Su base teórica es: el dominio factible de un problema de programación lineal es un conjunto convexo poligonal en un espacio vectorial n-dimensional Rn, y su valor óptimo debe alcanzarse en un cierto vértice del conjunto convexo si existe. La solución factible correspondiente al vértice se llama solución factible básica. La idea básica del método simplex es: primero encontrar una solución básica factible, identificarla para ver si es la solución óptima; de lo contrario, cambiar a otra solución básica factible mejorada de acuerdo con ciertas reglas y luego identificarla; sigue siendo la solución óptima. Si no, convierta nuevamente y repita este proceso. Dado que el número de soluciones básicas factibles es limitado, la solución óptima del problema debe obtenerse después de un número finito de transformaciones. Este método también se puede utilizar para determinar si no existe una solución óptima al problema.

Según el principio del método simplex, en problemas de programación lineal, los valores de las variables de decisión (variables de control) x1, x2,...x n se denominan solución, y la solución que satisface todas las restricciones se llama solución factible. La solución factible que hace que la función objetivo alcance el valor máximo (o valor mínimo) se llama solución óptima. De esta forma, una solución óptima puede hacer que la función objetivo alcance el valor máximo (o valor mínimo) dentro de toda la región factible determinada por las restricciones. El propósito de resolver problemas de programación lineal es encontrar la solución óptima.

La solución óptima puede ocurrir en una de las siguientes situaciones: ① Hay una solución óptima; ② Hay infinitas soluciones óptimas; ③ No hay una solución óptima. Esto solo ocurre en dos casos. es decir, no existe una solución factible o varias restricciones no impiden que el valor de la función objetivo aumente infinitamente (o aumente infinitamente en la dirección negativa).

Los pasos generales de resolución de problemas del método simplex se pueden resumir de la siguiente manera: ① Expresar las ecuaciones de restricción del problema de programación lineal en un sistema canónico de ecuaciones y encontrar la solución básica factible como solución básica inicial. solución factible. ② Si la solución básica factible no existe, es decir, las restricciones son contradictorias, entonces el problema no tiene solución. ③Si existe una solución básica factible, comience desde la solución básica factible inicial e introduzca variables no básicas para reemplazar una determinada variable básica de acuerdo con las condiciones de optimización y las condiciones de viabilidad para encontrar otra solución básica factible con un mejor valor de función objetivo. ④ Siga el paso 3 para iterar hasta que el número de prueba correspondiente cumpla con la condición de optimidad (en este momento el valor de la función objetivo no se puede mejorar), es decir, se obtiene la solución óptima al problema. ⑤ Si se encuentra que el valor de la función objetivo del problema no está limitado durante el proceso de iteración, la iteración finalizará.

El número de iteraciones necesarias para resolver problemas de programación lineal utilizando el método simplex depende principalmente del número de restricciones. Hoy en día, los problemas generales de programación lineal se resuelven en computadoras utilizando software estándar del método simplex. Los problemas de programación lineal con 106 variables de decisión y 104 restricciones ya se pueden resolver en computadoras.

Método simplex mejorado

El método simplex original no es un algoritmo muy económico. En 1953, el matemático estadounidense G.B Danzik propuso un método simplex mejorado para mejorar el error de acarreo acumulado en cada iteración del método simplex. Sus pasos básicos son aproximadamente los mismos que los del método simplex, la principal diferencia es que ya no se basa en el método de eliminación gaussiano en iteraciones sucesivas, sino que calcula directamente la inversa de la nueva matriz base a partir de la inversa de la base anterior. matriz y luego determina el número de prueba. Hacerlo puede reducir el error acumulativo en las iteraciones, mejorar la precisión de los cálculos y también reducir la cantidad de almacenamiento en la computadora.

Método dual simplex

En 1954, el matemático estadounidense C. Lemki propuso el método dual simplex. El método simplex consiste en iterar desde una solución factible del problema original a otra solución factible hasta que el número de prueba satisfaga la condición de optimización. La regla dual simplex consiste en buscar gradualmente la solución óptima al problema original mediante iteración comenzando por satisfacer las condiciones de viabilidad dual. En el proceso de iteración, la doble viabilidad de la solución básica siempre se mantiene y la inviabilidad desaparece gradualmente. Supongamos que el problema original es min{cx|Ax=b, x≥0}, entonces su problema dual es max{yb|yA≤c}. Cuando una solución básica del problema original satisface la condición de optimización, su número de verificación cBB-1A-c≤0. Es decir, se sabe que y=cBB-1 (llamado operador simplex) es una solución factible al problema dual. Se cumple la llamada viabilidad dual, lo que significa que el número de prueba satisface la condición de optimización.

Por lo tanto, bajo la premisa de mantener la doble viabilidad, una vez que la solución básica se convierte en una solución factible, también es la solución óptima.

En optimización matemática, el método simplex inventado por George Dantzig es una técnica popular para la solución numérica de problemas de programación lineal. Existe un algoritmo que no tiene nada que ver con esto, pero que tiene un nombre similar: es el método Nelder-Mead o método simplex descendente, descubierto por Nelder y Mead (1965). Este es un método numérico utilizado para optimizar múltiples. Problemas dimensionales sin restricciones. Una categoría más general de algoritmos de búsqueda.

Ambos utilizan el concepto de simplex, que es la cáscara convexa de N 1 vértices en N dimensiones. Es un politopo: un segmento de recta, un triángulo en un plano y un. tridimensional un tetraedro en el espacio, etc.