Instituto Tecnológico de Ciudad Madero

Ingeniería en Gestión Empresarial

Alumno:

Pérez Juárez Antonio 22070232

Materia: Investigación Operaciones

Profesora: Guillermo Cruz Garza

Horario: 17:00 – 18:00 hrs

Cd. Madero, Tamaulipas a 06 de Octubre de 2024.

Método simplex
Este es uno de los métodos más utilizados para resolver problemas de programación lineal
con varias variables. En este método se construye una tabla que muestra las variables y las
restricciones, y se realiza una serie de iteraciones para encontrar la solución óptima.
Cuáles son las ventajas de utilizar el método simplex?
El método simplex tiene varias ventajas que lo convierten en una herramienta de gran
utilidad. Algunas de ellas son:
 Aplicable a problemas de gran escala: El método simplex puede aplicarse a
problemas con un gran número de variables y restricciones. Aunque su eficiencia
puede disminuir a medida que aumenta el tamaño del problema, sigue siendo una
opción viable para resolver problemas complejos.
 Solución óptima: Si se sigue correctamente, el método simplex garantiza encontrar
la solución óptima para un problema de programación lineal. Esto significa que
obtendrás el mejor resultado posible dentro de las restricciones y objetivos
establecidos.
 Flexibilidad en la formulación del problema: El método simplex permite
formular problemas en términos de maximización o minimización de una función
objetivo. Esto significa que puedes adaptar el problema a tus necesidades
específicas, ya sea maximizando ganancias, minimizando costos o cualquier otro
objetivo deseado.
 Permite identificar soluciones no factibles o ilimitadas: Durante el proceso de
resolución, el método simplex puede detectar si el problema no tiene solución
factible o si tiene múltiples soluciones óptimas. Esto es útil para comprender mejor
la naturaleza del problema y tomar decisiones adecuadas.
 Interpretación geométrica: El método simplex se basa en conceptos geométricos y
utiliza un espacio de soluciones factibles para encontrar la solución óptima. Esto
proporciona una visualización intuitiva del problema y las restricciones, lo que
facilita la comprensión y el análisis de los resultados.
 Puede incorporar variables no lineales: Aunque el método simplex está diseñado
para problemas de programación lineal, se puede extender para abordar problemas
con variables no lineales utilizando técnicas de programación lineal entera o
programación no lineal.
Resolver mediante el método simplex el siguiente problema:
Maximizar Z = f(x,y) = 3x + 2y

sujeto a: 2x + y ≤ 18

2x + 3y ≤ 42

3x + y ≤ 24

x≥0,y≥0
Se consideran las siguientes fases:
1. Realizar un cambio de variables y normalizar el signo de los términos
independientes.
Se realiza un cambio en la nomenclatura de las variables. Estableciéndose la
correspondencia siguiente:
 x pasa a ser X1
 y pasa a ser X2
Como los términos independientes de todas las restricciones son positivos no es necesario
hacer nada. En caso contrario habría que multiplicar por "-1" en ambos lados de la
inecuación (teniendo en cuenta que esta operación también afecta al tipo de restricción).
2. Normalizar las restricciones.
Se convierten las inecuaciones en ecuaciones agregando variables de
holgura, exceso y artificiales según la tabla siguiente:

Tipo de
Tipo de variable que aparece
desigualdad

≥ - exceso + artificial

= + artificial

≤ + holgura

En este caso se introduce una variable de holgura (X3, X4 y X5) en cada una de las
restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones
lineales:
2·X1 + X2 + X3 = 18

2·X1 + 3·X2 + X4 = 42
 3·X1 + X2 + X5 = 24
3. Igualar la función objetivo a cero.
Z - 3·X1 - 2·X2 - 0·X3 - 0·X4 - 0·X5 = 0
4. Escribir la tabla inicial del método Simplex.
La tabla inicial del método Simplex está compuesta por todos los coeficientes de las
variables de decisión del problema original y las de holgura, exceso y artificiales agregadas
en el paso 2 (en las columnas, siendo P0 el término independiente y el resto de variables
Pi coinciden con Xi), y las restricciones (en las filas). La columna Cb contiene los
coeficientes de las variables que se encuentran en la base.
La primera fila está formada por los coeficientes de la función objetivo, mientras que la
última fila contiene el valor la función objetivo y los costes reducidos Zj - Cj.
La última fila se calcula como sigue: Zj = Σ(Cbi·Pj) para i = 1..m, donde si j = 0, P0 = bi y
C0 = 0, y en caso contrario Pj = aij. Aunque al tratarse de la primera tabla del método
Simplex y ser todos los Cb nulos se puede simplificar el cálculo, y por esta vez disponer
Zj = -Cj.

Tabla I . Iteración nº 1

3 2 0 0 0

Base Cb P0 P1 P2 P3 P4 P5

P3 0 18 2 1 1 0 0

P4 0 42 2 3 0 1 0

P5 0 24 3 1 0 0 1

Z 0 -3 -2 0 0 0

5. Condición de parada.
Si el objetivo es la maximización, cuando en la última fila (fila indicadora) no existe ningún
valor negativo entre los costes reducidos (columnas P1 en adelante) se alcanza la condición
de parada.
En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor
de Z (columna P0) es la solución óptima del problema.
Otro caso posible es que en la columna de la variable entrante a la base todos los valores
son negativos o nulos. Esto indica que el problema no se encuentra acotado y su solución
siempre resultará mejorable. Ante esta situación no es necesario continuar iterando
indefinidamente y también se puede dar por finalizado el algoritmo.
De no ser así, se ejecutan los siguientes pasos de forma iterativa.
6. Elección de la variable entrante y saliente de la base.
Se determina en primer lugar la variable que entra en la base. Para ello se escoge la
columna cuyo valor en la fila Z sea el menor de entre todos los negativos. En este caso sería
la variable X1 (P1) de coeficiente -3.
Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de
empate), entonces se optará por aquella variable que sea básica.
La columna de la variable que entra en la base se llama columna pivote (en color verde).
Una vez obtenida la variable que entra en la base, se procede a determina cual será la
variable que sale de la misma. La decisión se toma en base a un sencillo cálculo: dividir
cada término independiente (columna P0) entre el elemento correspondiente de la columna
pivote, siempre que ambos elementos sean estrictamente positivos (mayores que cero). Se
escoge la fila cuyo resultado haya resultado mínimo.
Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente. En caso de que
todos los elementos de la columna pivote fueran de ésta condición se habría cumplido la
condición de parada y el problema tendría una solución no acotada (ver teoría del método
Simplex).

En este ejemplo: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]

El término de la columna pivote que en la división anterior dio lugar al menor cociente
positivo indica la fila de la variable de holgura que sale de la base. En este caso resulta ser
X5 (P5), de coeficiente 3. Esta fila se llama fila pivote (en color verde).
Si al calcular los cocientes, dos o más resultados cumplen la condición para elegir el
elemento saliente de la base (caso de empate), se escoge aquella que no sea variable básica
(siempre que sea es posible).
La intersección de la fila pivote y columna pivote marca el elemento pivote, en este caso el
3.
7. Actualizar la tabla.
Los nuevos coeficientes de la tabla se calculan de la siguiente manera:
 En la fila del elemento pivote cada nuevo elemento se calcula como:
Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote
 En el resto de las filas cada elemento se calcula:
Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna
Pivote * Nuevo Elemento Fila Pivote)
Con esto se normaliza el elemento pivote y su valor pasa a ser 1, mientras que el resto de
elementos de la columna pivote se anulan (análogo al método de Gauss-Jordan).
Se muestran a continuación los cálculos para la fila P4:
Anterior fila P4 42 2 3 0 1 0

- - - - - -

Anterior Elemento Fila en Columna Pivote 2 2 2 2 2 2

x x x x x x

Nueva fila pivote 8 1 1/3 0 0 1/3

= = = = = =

Nueva fila P4 26 0 7/3 0 1 -2/3

La tabla correspondiente a esta segunda iteración es:

Tabla II . Iteración nº 2

3 2 0 0 0

Base Cb P0 P1 P2 P3 P4 P5

P3 0 2 0 1/3 1 0 -2/3

P4 0 26 0 7/3 0 1 -2/3

P1 3 8 1 1/3 0 0 1/3

Z 24 0 -1 0 0 1

8. Al comprobar la condición de parada se observa que no se cumple ya que entre los

elementos de la última fila hay uno negativo, -1. Se continúa iterando nuevamente
los pasos 6 y 7.
 6.1. La variable que entra en la base es X2 (P2), por ser la variable que
corresponde a la columna donde se encuentra el coeficiente -1.
 6.2. Para calcular la variable que sale, se dividen los términos de la columna
P0 entre los términos correspondientes de la nueva columna pivote: 2 / 1/3
 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=24]. Como el menor cociente positivo es 6,
la variable que sale de la base es X3 (P3).
 6.3. El elemento pivote es 1/3.
 7. Actualizando nuevamente los valores de la tabla se obtiene:

Tabla III . Iteración nº 3

3 2 0 0 0

Base Cb P0 P1 P2 P3 P4 P5

P2 2 6 0 1 3 0 -2

P4 0 12 0 0 -7 1 4

P1 3 6 1 0 -1 0 1

Z 30 0 0 3 0 -1

9. Una nueva comprobación de la condición de parada revela que entre los elementos
de la fila indicadora vuelve a haber uno negativo, -1. Significa que aun no se ha
llegado a la solución óptima y hay que seguir iterando (pasos 6 y 7):
 6.1. La variable que entra en la base es X5 (P5), por ser la variable que
corresponde al coeficiente -1.
 6.2. Se escoge la variable que sale calculando el cociente entre los términos
de la columna de términos independientes y los términos correspondientes
de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6/1 [=6]. En esta
ocasión es X4 (P4).
 6.3. El elemento pivote es 4.
 7. Después de actualizar todas las filas, se obtiene la tabla siguiente:

Tabla IV . Iteración nº 4

3 2 0 0 0

Base Cb P0 P1 P2 P3 P4 P5

P2 2 12 0 1 -1/2 1/2 0
 Tabla IV . Iteración nº 4

P5 0 3 0 0 -7/4 1/4 1

P1 3 3 1 0 3/4 -1/4 0

Z 33 0 0 5/4 1/4 0

10. Fin del algoritmo.

Se observa que en la última fila todos los coeficientes son positivos cumpliéndose, por
tanto la condición de parada.
La solución óptima viene dada por el valor de Z en la columna de los términos
independientes (P0), en este ejemplo: 33. En la misma columna se puede ver el punto
donde se alcanza, observando las filas correspondientes a las variables de decisión que han
entrado en la base: X1 = 3 y X2 = 12.
Deshaciendo el cambio de variables se obtiene x = 3 e y = 12.
Elementos a considerar para utilizar el método simplex
Para utilizar el método simplex de manera efectiva, debes tener en cuenta los siguientes
elementos:
1. Formulación del problema
Debes formular correctamente el problema en términos de una función objetivo a
maximizar o minimizar, así como las restricciones que limitan las variables del problema.
Es esencial identificar las variables y restricciones relevantes y establecer correctamente los
coeficientes y las desigualdades en la formulación del problema.
2. Restricciones lineales
El método simplex es aplicable a problemas de programación lineal, lo que implica que
todas las restricciones deben ser lineales.
Si hay restricciones no lineales, deberás transformarlas en su equivalente lineal utilizando
técnicas de linealización o considerar otros métodos de optimización más adecuados.
3. Forma estándar o canónica
El método simplex funciona mejor cuando el problema se formula en su forma estándar o
canónica. Esto implica que la función objetivo debe ser de maximización, todas las
restricciones deben ser desigualdades de tipo «<=» y todas las variables deben ser no
negativas. Si el problema no está en forma estándar, deberás realizar las transformaciones
necesarias para convertirlo a esta forma.
4. Matriz de coeficientes
Debes construir la matriz de coeficientes que representa las restricciones del problema. Esta
matriz se utiliza en cada iteración del método simplex para determinar las variables básicas
y no básicas, y para calcular las mejoras en la función objetivo.
Asegúrate de organizar correctamente los coeficientes de las variables y las restricciones en
la matriz.
5. Método de selección de variables
El método simplex utiliza un método de selección de variables para determinar qué variable
básica debe ingresar o salir del conjunto básico en cada iteración. Existen diferentes reglas
de selección, como la regla del costo reducido o la regla de la razón mínima, que te
indicarán qué variable modificar en cada paso del algoritmo.
6.Condición de parada
Debes establecer una condición de parada para finalizar el algoritmo. Por lo general, esto
implica verificar si se ha alcanzado una solución óptima o si no se pueden realizar más
mejoras en la función objetivo. Puedes establecer criterios como la optimalidad de la
solución, la estabilidad de las variables básicas o un número máximo de iteraciones.
Bibliografía.
https://www.questionpro.com/blog/es/metodo-simplex/
https://www.phpsimplex.com/ejemplo_metodo_simplex.htm