Método Simplex.

UNIVERSIDAD POLITÉCNICA DE TECÁMAC

GARCÍA CAMPOS CECILIO
1821 ITM
GARCÍA REYES JORGE ALEXIS
GONZÁLEZ LEÓN ABIGAIL
PÉREZ BUENO OMAR FERNANDO
ENERO – ABRIL 2021
 ¿QUÉ ES EL MÉTODO SIMPLEX?

• El Método Simplex es un método iterativo que permite ir

mejorando la solución en cada paso.
• El método consiste en caminar del vértice de un poliedro a un
vértice vecino de manera que aumente o disminuya (según el
contexto de la función objetivo, sea maximizar o minimizar), dado
que el número de vértices que presenta un poliedro solución es
finito siempre se hallará solución.
EL MÉTODO PARTE DE DOS AFIRMACIONES
IMPORTANTES:
• El conjunto de posibles
soluciones o conjunto factible de
cualquier problema de
programación lineal puede
representarse mediante un
poliedro convexo.
• Si un problema de programación
lineal tiene una solución óptima y
finita, ésta estará en un vértice
del poliedro convexo que
representa al problema.
PASOS DEL MÉTODO
SIMPLEX.
1.- Definir el problema en la forma estándar y generar
matriz.
Para convertir las restricciones en igualdades va a depender de su signo.
• Si la restricción es menor igual (≤): Para este tipo de restricciones
debemos introducir una variable no negativa llamada de holgura y
que son auxiliares para el problema.
• Cuando la restricción es mayor igual (≥): En este tipo de restricciones
se debe restar una variable de exceso y así mismo agregar una
variable artificial.
• Si la restricción es igual (=): En este tipo de restricciones debemos
agregar una variable artificial.
Una vez convertidas las restricciones en ecuaciones se procede a generar la
matriz, en la cual se identifica:
• Vector de Costes: Es el vector que contiene los coeficientes de todas las
variables de la función objetivo.
• Vector Solución: En esta columna se coloca la solución básica inicial y se va
actualizando conforme se realizan las iteraciones. En la columna Cb se
indica el coeficiente que corresponde a cada variable en el vector de
costes. Así mismo siempre se iniciará con las variables de holgura en la
base cuando el problema no tenga variables artificiales.
• Coeficientes Restricciones: Se colocan los coeficientes de las restricciones
en el mismo orden en que fueron formuladas. La columna R contiene a los
términos independientes también conocido como vector de recursos.
• Vector de costes reducidos: Este vector se calcula multiplicando el vector
solución por los coeficientes de las restricciones y se resta el vector de
costes, donde se presentan variables artificiales, al no existir variables
artificiales, el vector de costes será igual al vector de costes multiplicado
por “-1”.
 2.-Determinar la solución básica inicial:
• El método simplex parte de un vértice de la región factible, es decir,
un punto extremo. Con cada iteración se avanza de vértice en vértice
hasta llegar a la solución óptima.
• ¨Cada variable del vector solución se iguala al valor que se encuentra
en la columna R. Estas variables se denominan variables básicas.¨
 3.-Seleccionar la variable de entrada utilizando la
condición de optimalidad
Consiste en verificar si la solución actual que tenemos en nuestra matriz
es la óptima o si se puede mejorar. Se verifica de la siguiente manera:
• En un problema de MAXIMIZACIÓN si todos los coeficientes del
vector de costes reducidos son mayores o iguales que cero, quiere
decir que estamos en el punto óptimo y finaliza el problema.
• En un problema de MINIMIZACIÓN si todos los coeficientes del vector
de costes reducidos son menores o iguales que cero, quiere decir que
estamos en el punto óptimo y finaliza el problema.
Si no se esta en lo óptimo, se debe iniciar las iteraciones seleccionando
la variable de entrada.
La variable de entrada hace referencia a una de las variables no básicas
que ingresará a la base y formará parte de la solución del problema. La
cual depende si el problema es de maximización o minimización:
• Para problemas de MAXIMIZACIÓN, la variable de entrada será la
variable no básica con el coeficiente más negativo en el vector de
costes reducidos.
• Para problemas de MINIMIZACIÓN, la variable de entrada será la
variable no básica con el coeficiente más positivo en el vector de
costes reducidos.
4. Seleccionar la Variable de Salida con la Condición de
Factibilidad.
• La condición de factibilidad, para cualquier problema ya sea de
maximización o minimización, se verifica evaluando los valores de los
coeficientes de la matriz de restricciones que se encuentran en la columna
que corresponde a la variable de entrada. Se debe verificar que al menos
uno de sus valores sea mayor que 0 para obtener nuestra variable de
salida. Si no se cumple esa condición significa que el problema tiene
solución ilimitada no acotada.
• Para determinar la variable que sale de la base se debe dividir el valor
correspondiente a la columna R con su respectivo coeficiente en la
columna de la variable de entrada (siempre y cuando este coeficiente sea
estrictamente positivo). De los resultados obtenidos, el menor valor
corresponde a la fila que contiene a la variable de salida. A esta fila se le
llama fila pivote.
 5. Actualizar la Matriz.
Una vez determinado el elemento pivote, se realiza las operaciones de Gauss-
Jordan para formar la matriz identidad. El nuevo valor de cada fila se calcula de la
siguiente manera:
• Para la fila pivote: El nuevo valor se obtendrá dividiendo el valor actual entre el
elemento pivote.
Nuevo Valor Fila Pivote = Valor Actual Fila Pivote / Elemento Pivote
• Para las otras filas: El nuevo valor se calcula restando del valor actual, la
multiplicación del elemento de la fila que se encuentra en la columna pivote por
el nuevo valor calculado en la fila pivote.
Nuevo Valor = Valor Actual – (Elemento Fila Columna Pivote*Nuevo Valor Fila
Pivote).
• Volver al paso número 3: Con este último resultado, se regresa al paso 3 y se
repite el proceso.
 EJEMPLO DEL
MÉTODO SIMPLEX.
 Sujeto a:
PROBLEMA DE • X1 + 6X2 ≤ 20
MAXIMIZACIÓN:
• X1 + X2 ≤ 60
• X1 ≤ 40
Función Objetivo
• X1, X2 ≥ 0
• Maximizar: Z = 2X1 +
5X2
 SOLUCIÓN.
• Se agregan las variables de holgura, exceso y/o artificiales en cada
una de las restricciones:
• Restricción 1: Tiene signo “≤” (menor igual) por lo que se agrega la
variable de holgura S1.
• Restricción 2: Tiene signo “≤” (menor igual) por lo que se agrega la
variable de holgura S2.
• Restricción 3: Tiene signo “≤” (menor igual) por lo que se agrega la
variable de holgura S3.
Después se colocará el coeficiente 0 (cero) donde corresponda para
crear la matriz.
• Para encontrar la variable que
entra a la base elegimos el
valor más negativo del vector
de costes reducidos: -5. Por lo
tanto la variable de entrada
sería X2.
• El elemento pivote se
encuentra en el cruce de X2 y
S1: 6.
• Se realiza las reducciones de Gauss-Jordan.
• Se ingresa la variable X1 y sale
de la base la variable X2.
• El elemento pivote es 1/6.
• Se repite las operaciones de
Gauss-Jordan y obtenemos la
siguiente matriz:
• En la matriz, todos los valores del vector de costes
reducidos son positivos lo que indica que se encontró
el punto óptimo.
• Por tanto el resultado sería:
Z = 40
X1= 20, X2= 0, S1= 0, S2= 40, S3= 20
 CONCLUSIÓN.
• El método simplex, emplea básicamente, la estrategia de resolver los
problemas de programación lineal por medio de sistemas de
ecuaciones lineales simultáneas, ya que es una manera fácil, practica
y rápida de dar soluciones optimas en los diferentes campos laborales
a todos los problemas en el desarrollo de la industria siendo
satisfactorias y eficaces las respuestas, permitiendo establecer y
generar una producción optima.