Método Símplex

Vista previa del material en texto

Investigación de Operaciones I. 
Ramirez Ramirez Jesus Guadalupe. 
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 (<) o 
(>) en igualdades (=). Considerando que: 
 
Variables de Holgura : (+Sj) que se agrega de forma POSITIVA a todas las Restricciones de la Forma (<=). 
 
Variables de Excedencia : (-Ej) que se agrega de forma NEGATIVA 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. 
Ramirez Ramirez Jesus Guadalupe. 
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. 
 
 
 
 
 
 
 
 
TABLA INICIAL SIMPLEX 
 
 
Cj Coeficientes de las variables 
en la función objetivo 
 
 
CB 
 
VB 
 
Variables de la Función Objetivo en su Forma Estándar. 
 
B 
Coeficie
ntes de 
las 
Variable
s 
Básicas 
 
 
Variable
s 
Básicas 
 
 
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. 
Max Z = 60X1 + 75X2 
Sujeto a: 
 6X1 + 4X2 <= 800 
 X1 + 2X2 <= 480 
 X1,X2 >= 0 
Max Z = 60X1 + 75X2 + 0S1 + 0S2 
Sujeto a: 
 6X1 + 4X2 + S1 = 800 
 X1 + 2X2 +S2 = 480 
 X1, X2 >= 0 
 S1, S2 >= 0 
 
 
Investigación de Operaciones I. 
Ramirez Ramirez Jesus Guadalupe. 
 
* 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 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. 
 
 
 
 
 
 
 
http://es.wikipedia.org/wiki/Eliminaci%C3%B3n_de_Gauss-Jordan