IO I (Método Símplex) MS Teams PDF

Preview

Summary

apuntes...

Description

Investigación de Operaciones I. Ing. Juan Carlos Espinosa Velasco, M.C.

Método Simplex El método simplex consiste en un algoritmo que realiza un estudio secuencial de la Función Objetivo por distintas soluciones básicas factibles de forma que, a partir de una solución inicial, en cada iteración se considera una nueva solución básica factible, la cual es adyacente a la anterior y mejora el valor de la función objetivo. Se trata de un proceso iterativo que finaliza cuando se alcanza el Valor Óptimo de dicha función. Fue desarrollado por George Dantzig en el año 1947 aproximadamente, y es utilizado para la resolución de manera tabular de modelos matemáticos de cualquier tamaño, sin importar el Número de Variables o el Número de Restricciones que contenga. La ventaja principal de este método en comparación con el Método Gráfico, es que podemos tratar de resolver problemas donde utilicemos 2 o más variables de decisión (Xj). El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El método Simplex se basa en la siguiente propiedad: “si la función objetivo Z no toma su valor máximo en el vértice A, entonces existe una arista que parte de A y a lo largo de la cual el valor de Z aumenta.” El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones). A continuación se presenta el algoritmo del método, partiendo desde su tabla inicial, hasta obtener la solución óptima.

Algoritmo Método Simplex: 1.- Plantear el problema matemáticamente. 2.- Desarrollar el modelo matemático en su forma estándar; es decir, transformar las desigualdades () en igualdades (=). Considerando que: Variables de Holgura : (+Sj) que se agrega de forma POSITIVA a todas las Restricciones de la Forma (=). Variable Artificial : (+Aj) que se agrega de forma POSITIVA a todas las Restricciones de la Forma (>=) y (=), de tal forma que ayude a la estructura en el modelo que forme una Diagonal Principal con valores 1, de forma positiva.

Investigación de Operaciones I. Ing. Juan Carlos Espinosa Velasco, M.C. 3.- Elaborar la Tabla Simplex; esto es vaciar los datos correspondientes y determinar la SOLUCIÓN INICIAL BÁSICA. Considere el Modelo de Tabla que se menciona a continuación, junto a un ejemplo, de cómo se vacían los datos del Modelo en su Forma Estándar. Ejemplo: Considere el Modelo Matemático: Modelo Original

Modelo en su Forma Estándar.

Max Z = 60X1 + 75X2 Sujeto a: 6X1 + 4X2 = 0 S1, S2 >= 0

TABLA INICIAL SIMPLEX Cj

CB VB Coeficie ntes de las Variable Variable s s Básicas Básicas

Coeficientes de las variables en la función objetivo Variables de la Función Objetivo en su Forma Estándar.

B

Coeficientes de cada Variable En cada una de las restricciones.

Valores de las restricciones

Zj

Valores que toman cada unas de las variables de acuerdo a los coeficientes de las variables básicas

VALOR Zj.

Cj - Zj

Diferencia que existe entre los Coeficientes de la Función Objetivo (Cj) y los Valores Resultantes del Renglón (Zj)

Y considere los siguientes conceptos: * Variables básicas.- Son aquellas variables que intervienen en el proceso de solución del problema.

Investigación de Operaciones I. Ing. Juan Carlos Espinosa Velasco, M.C.

* Solución Factible.- Es toda solución que satisface las restricciones del problema, aún sin optimizar la función objetivo.

4.- Iniciar el Proceso de Mejora: a) Criterio de Optimalidad: determina la Variable que Entra a la solución , eligiendo la variable que tiene el valor más positivo en el renglón Cj-Zj, para problemas de Maximizar y el valor más negativo en el Renglón Cj-Zj, para problemas de Minimizar. b) Criterio de Factibilidad: determinar la Variable que sale y que será sustituida por la variable identificada en el paso anterior, dividiendo el Vector de recursos B entre el Vector de coeficientes positivos de la variable que entra, elegir como variable que sale aquella cuyo cociente sea el menor

positivo. c) Identificar el Elemento Pivote: el cual estará ubicado

en la intersección de la variable

que entra y la que sale, y este debe ser igual a uno. Los elementos restantes del mismo vector del donde se encuentra el elemento pivote deben ser ceros. Esta operación se realiza a través del Método de eliminación de Gauss – Jordán*. *El método de eliminación de Gauss-Jordán es utilizado para determinar si una determinada matriz es invertible y encontrar su inversa por medio del uso de elementos llamados “pivotes”. “Utilizando el método de Gauss-Jordán se coloca a la izquierda una matriz dada y a la derecha una matriz identidad; siendo el objetivo de este método; intentar formar en la parte izquierda la matriz identidad y la matriz que quede en la parte derecha será la matriz inversa a la dada”.

d) Verificar si la nueva solución obtenida es óptima. Esto es, cuando todos los valores del renglón Cj-Zj son negativos y ceros, para MAXIMIZAR. Esto es, cuando todos los valores del renglón Cj-Zj son positivos y ceros, para MINIMIZAR. OJO Si llegará a existir algún valor positivo en este renglón , significa que se debe seguir iterando (repetir los pasos del punto 4) hasta que todos los valores de este renglón cumplan con las características de haber encontrado una solución óptima, es decir, encontrar ceros y negativos en el renglón Cj-Zj.

e) Comprobar los resultados en el sistema de ecuaciones. Los resultados serán las variables básicas que hayan resultado en la última iteración hecha y sus respectivos valores generados en el vector B....