Método Simplex

MÉTODO
SIMPLEX
METODO ANALÍTICO
Integrantes
del equipo
Julian Alexander Ortíz May
Luis Kevin Muñoz Romero
Michael Guadalupe Pino Hernández

Introducción
El Método Simplex es un algoritmo utilizado para resolver problemas de
programación lineal, una rama de la optimización matemática que busca
maximizar o minimizar una función lineal sujeta a un conjunto de restricciones
lineales. Desarrollado por George Dantzig en 1947, el Método Simplex es
ampliamente utilizado debido a su eficacia en la resolución de problemas
complejos.
El objetivo fundamental del Método Simplex es encontrar la solución óptima al

ajustar sistemáticamente los valores de las variables de decisión. A través de
iteraciones sucesivas, el algoritmo se desplaza de una solución a otra, mejorando
continuamente la función objetivo hasta alcanzar la solución óptima.
¿Qué es el método simplex y
para qué sirve?
El Método Simplex es un método analítico de solución de
problemas de programación lineal, capaz de resolver modelos
más complejos que los resueltos mediante el método gráfico,
sin restricción en el número de variables.
El Método Simplex es un método iterativo que permite ir

mejorando la solución en cada paso.
Este método es esencial en la toma de decisiones en áreas

como la planificación de recursos, la gestión de inventarios, la
asignación de personal y otros problemas que involucran la
optimización de recursos limitados.
Breve historia del método simplex
La programación lineal surgió durante la Segunda Guerra
Mundial con el objetivo de reducir los costes del ejército
y aumentar las bajas del enemigo. Uno de los algoritmos
clave para este tipo de programación es el «algoritmo
Simplex».
Este popular método fue creado en el año de 1947 por el

estadounidense George Bernard Dantzig y el ruso
Leonid Vitalievich Kantorovich, con el ánimo de crear un
algoritmo capaz de solucionar problemas de m
restricciones y n variables.
Conceptos clave del MS
Para comprender mejor el método simplex es importante estar
familiarizado con algunos conceptos
1. Programación Lineal
2. Variables de Decisión (x, y, t, u, v)
3. Función Objetivo
4. Restricciones
5. Solución Factible
6. Solución Óptima
7. Variables de Holgura
8. Solución Básica
9. Solución Básica Factible
10. Tabla Simplex
11. Pivoteo
12. Variables de entrada y salida
13. Solución Degenerada
Conceptos definidos
Variables de Holgura:
Son variables artificiales introducidas en el Método Simplex para
convertir desigualdades en igualdades en el sistema de restricciones.
Estas variables representan la "holgura" o exceso en cada restricción y
ayudan en la solución del problema de programación lineal.
Solución Básica:
Una solución básica es un conjunto de valores para las variables de
decisión en el cual un cierto número de variables son fijas en cero, y las
restantes son variables básicas, es decir, no nulas y determinadas por las
ecuaciones que definen las restricciones del problema. En otras palabras,
las variables no básicas se establecen en cero, y las variables básicas se
determinan a partir de las ecuaciones de restricción.
Solución Básica Factible:

Una solución básica factible es una solución básica que cumple con todas
las restricciones del problema, incluyendo las restricciones de no
negatividad. En este caso, no solo se cumplen las ecuaciones que definen
las restricciones, sino que también todas las variables de decisión son no
negativas. Por lo tanto, una solución básica factible es una solución que
satisface tanto las ecuaciones de restricción como las restricciones de
no negatividad (Movimiento entre vértices).
Tabla Simplex:
Es una tabla utilizada en el Método Simplex que organiza la información
durante cada iteración del algoritmo. La tabla contiene coeficientes,
variables básicas y no básicas, y proporciona una representación
estructurada de la solución actual en cada paso del proceso.
Pivoteo:
Es el proceso central en el Método Simplex donde se seleccionan
variables de entrada y salida en cada iteración para mejorar la solución
actual. Consiste en realizar operaciones algebraicas en la tabla simplex
para cambiar las variables básicas y no básicas y avanzar hacia una
solución óptima.
La esencia del método símplex consiste en seleccionar primero una SBF
particular como punto de inicio y entonces a partir de ahí transformar
ésta a otra SBF, de tal manera que la función objetivo esté más cercana a
ser óptima. Este proceso de transformación se denomina pivoteo y se
continua hasta que la solución básica óptima se determina.
Variables de Entrada y Salida:

En el contexto del Método Simplex, las variables de entrada son aquellas
que entran en la base (se vuelven variables básicas) en una iteración
específica, mientras que las variables de salida son aquellas que salen de
la base (se vuelven no básicas). La elección adecuada de estas variables
es crucial para mejorar la solución.
Solución Degenerada:
En el contexto del Método Simplex, una solución degenerada ocurre
cuando una variable básica alcanza el valor de cero durante el proceso de
pivoteo. Esto puede complicar el algoritmo y requiere consideraciones
especiales para evitar ciclos infinitos. La degeneración a menudo se
aborda utilizando reglas específicas durante el pivoteo.
Problemas:
1. Posible Ciclo Infinito:
La degeneración puede hacer que el algoritmo Simplex entre en ciclos
infinitos si no se maneja adecuadamente. Esto es un desafío, ya que el
método se basa en la mejora gradual de la solución, y la degeneración
puede impedir que el algoritmo avance correctamente.
2. Reglas Especiales de Selección:
Se deben aplicar reglas especiales de selección durante el pivoteo
para evitar ciclos infinitos en caso de soluciones degeneradas. Estas
reglas pueden incluir la elección de la variable de salida de manera
específica para garantizar el progreso adecuado.
PASOS DEL MÉTODO SIMPLEX SEGÚN ARYA JAGDISH
Paso 1: Definimos las variables de holgura no negativas que transformen las desigualdades en
ecuaciones.
Paso 2: Construimos la tabla símplex.
Paso 3: Seleccionamos la variable de entrada con base en el indicador positivo más grande.
Paso 4: Calculamos las razones de los elementos de la última columna de la tabla a los elementos
de la columna de la variable de entrada. El cociente no negativo más pequeño determina la
variable de salida.
Paso 5: Efectuamos operaciones entre renglones de la tabla para transformar la columna
encabezada por la variable de entrada a la forma que la columna de la variable de salida tenía
antes. Esto debe realizarse sin alterar las columnas encabezadas por las otras variables básicas.
Paso 6: Repetimos los pasos 3, 4 y 5 hasta que ninguno de los indicadores sea positivo. El valor
máximo de la función objetivo estará dado entonces por el elemento inferior izquierdo de la tabla.
PASOS DEL MÉTODO SIMPLEX FORMA ALTERNATIVA
Paso 1: Realizar un cambio de variables y normalizar el signo de los términos independientes.
Paso2: Normalizar las restricciones. Definimos las variables de holgura no negativas que transformen las
desigualdades en ecuaciones.
Paso 3: Igualar la función objetivo a cero.
Paso 4: Construimos la tabla inicial del método símplex.
Paso 5: Seleccionamos la variable de entrada con base en el indicador más negativo de la función
objetivo.
Paso 6: Calculamos las razones de los elementos de la última columna de la tabla a los elementos de la
columna de la variable de entrada. El cociente no negativo más pequeño determina la variable de salida.
Paso 7: Determinamos el elemento pivote con la intersección de la columna pivote con la fila pivote.
Paso 8: Efectuamos operaciones entre renglones de la tabla para convertir en 1 el elemento pivote y en
cero los números que están por encima y debajo del elemento pivote.
Paso 9: Repetimos los pasos 5, 6, 7 y 8 hasta que ninguno de los indicadores sea positivo. El valor
máximo o mínimo de la función objetivo estará dado entonces por el elemento superior derecho de la
tabla.
¡Muchas
gracias!

Método Simplex

Cargado por

Copyright:

Formatos disponibles

Método Simplex

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Método Simplex

Cargado por

Copyright:

Formatos disponibles

MÉTODO

Luis Kevin Muñoz Romero

Michael Guadalupe Pino Hernández

El objetivo fundamental del Método Simplex es encontrar la solución óptima al

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

Este método es esencial en la toma de decisiones en áreas

Este popular método fue creado en el año de 1947 por el

Solución Básica Factible:

Variables de Entrada y Salida:

También podría gustarte