UNIDAD 2 (2024)

• MÉTODO SIMPLEX REGULAR
• MÉTODO M
• METODO DE LAS DOS FASES
• TAREA DE LA UNIDAD 2

El método simplex es un procedimiento sistemático y eficiente para encontrar y probar soluciones de problemas de programación lineal localizadas en los vértices de optimidad. El método termina una vez que se haya encontrado la solución óptima.

La base del método simplex está formada por 2 condiciones fundamentales:

1. La condición de optimidad asegura que nunca se encontrará una solución inferior relativa al punto de solución actual.

2. La condición de factibilidad que garantiza que partiendo de una solución básica factible solamente se encontrarán soluciones básicas factibles.Un problema de programación lineal siempre tiene una solución que está localizada en uno de los vértices del conjunto de soluciones factibles.

REGRESO AL INICIO DE LA UNIDAD

PROCEDIMIENTO PARA EL MÉTODO SIMPLEX REGULAR

1. El método requiere que las restricciones sean ecuaciones (relaciones de igualdad). Cualquier inecuación puede ser convertida en una ecuación agregando una cantidad negativa en el lado de menor valor de la inecuación.Esta variable se llama variable de holgura y también se introduce en la función objetivo con coeficiente cero ya que no influye en el valor de la función objetivo.

2. Encontrar una solución básica factible inicial para el sistema de ecuaciones.En muchos casos, las variables de holgura representan una solución obvia de inicio porque sus coeficientes forman una matriz identidad, donde los elementos diagonales son unos y los elementos restantes son ceros. Además, los valores del lado derecho de las ecuaciones siempre son negativos.

Una forma conveniente de registrar la información sobre la solución de inicio es utilizar una tabla.En esta tabla la función objetivo se expresa como una ecuación igualada a cero. En esta tabla existe la columna variable básica que contiene la identificación de cuales son las variables básicas de la solución actual. Las variables no básicas actuales no aparecen en esta columna y sus valores son cero.

3. Encontrar una solución básica factible mejor.Esta es una fase iterativa donde se busca una solución mejor que la actual. En este paso se busca identificar una variable básica que mejore la función objetivo. Esta variable se llama "variable básica entrante" y reemplazarla por otra variable básica llamada "variable básica saliente".La condición de optimidad estipula que la variable que entra será elegida como la variable no básica que tenga un coeficiente negativo más grande en la ecuación de la función objetivo (Z) de la tabla para problemas de maximización y el coeficiente positivo más grande para minimización.La variable básica que sale es la que representa la relación mínima positiva de cocientes entre la columna solución y la columna variable básica entrante.

4. Formar una nueva tabla con la solución mejorada para crear la nueva tabla de soluciones se identifica la columna pivote que está señalada por la variable básica que entra. También se identifica el renglón pivote que está indicado por la variable básica que sale. El valor que forma el cruce de la columna pivote y el renglón pivote se llama elemento pivote. Se obtiene el nuevo renglón pivote dividiendo el renglón anterior por el coeficiente del elemento pivote. Se generan ceros en todos los valores de la nueva columna pivote realizando operaciones entre los renglones anteriores y el renglón pivote nuevo.

5.Buscar una solución básica factible mejor.Si existe una solución básica factible mejor, se vuelve a formar una nueva tabla de soluciones. Si no se puede encontrar una solución, la solución obtenida es óptima. El criterio de búsqueda de mejores soluciones ya se señaló en el paso 3.

REGRESO AL INICIO DE LA UNIDAD