métodos de adyacentes

Método Simplex.

En el año 1947 el doctor George Dantzig presentó el algoritmo que desarrolló y que denominó SIMPLEX. A partir de este logro se pudieron resolver problemas que por más de un siglopermanecieron en calidad de estudio e investigación con modelos formulados pero no resueltos. El desarrollo paralelo de la computación digital, hizo posible su rápido desarrollo y aplicaciónempresarial a todo tipo de problemas.

El método simplex disminuye sistemáticamente un número infinito de soluciones hasta un número finito de soluciones básicas factibles. El algoritmo simplex utiliza elconocido procedimiento de eliminación en la solución de ecuaciones lineales de Gauss- Jordan y, además aplica los llamados criterios del simplex con los cuales se asegura mantener la búsqueda dentro deun conjunto de soluciones factibles al problema; así valora una función económica Z, exclusivamente en vértices FACTIBLES (posibles). También se consigue con eficiencia, debido a que se dirige labúsqueda haciendo cambios a una solución básica factible adyacente, que se distingue al tener m-1 variables básicas iguales; es decir, dos vértices adyacentes sólo difieren en una variable básica;seleccionando la ruta de mayor pendiente, para mejorar el valor de Z, o por lo menos conservarlo.

Primero se presenta el método simplex, específico para un modelo de PL en forma canónica de máximo, aplicadocon la conocida tabla matricial, (también identificada como tableau), lo cual se resume mediante el diagrama funcional de la Figura 2-1, que muestra los fundamentos del algoritmo contenidos enniveles o bloques numerados para la referencia en la descripción del mismo.

Nivel 1.- Forma estándar.-El modelo de PL en forma canónica de máximo que se desea resolver, tiene m ecuaciones obtenidas alconvertir las restricciones de desigualdad a igualdad, agregando m variables de holgura, que sumadas a las n variables de decisión, hacen un total de (m + n) incógnitas.

Las m restricciones con...