MÉTODO SIMPLEX

El método Simplex fue desarrollado por George B. Danzig en EEUU, en 1947, y es muy utilizado
debido a su amplio uso y versatilidad para resolución de problemas de programación lineal
(Gallagher & Watson, 1992).

Es un procedimiento matricial iterativo basado en la metodología de Gauss Jordán (Landeta,

1998) para manejar variables no negativas, de fácil implantación en computadora y lo que
permite solucionar problemas de variables y restricciones de una manera ágil y eficiente al
igual que el método gráfico, este método parte del problema de programación lineal
debidamente planteado, es decir, con las ecuaciones de la función objetivo y las restricciones
definidas matemáticamente.

El método simplex toma siempre como aquella posible solución a un punto correspondiente a
uno de los vértices de la región factible de solución, siendo la primera aproximación el origen.
“De aquí, en las siguientes iteraciones el simplex se moverá hacia los otros vértices hasta que
alguno de ellos sea el óptimo, lo cual sucede cuando un vértice tiene mejor valor de la función
objetivo que los dos vértices adyacentes a él, es decir, el anterior y el posterior, siendo entonces
cuando se ha logrado la solución del problema de programación lineal”. (Davis, McKeown, &
Diaz Mata, 1986).

Es una técnica para dar soluciones a problemas a través de la programación lineal, que permite
encontrar una solución óptima en un problema de Maximización o minimización, a través de
esto permite ir mejorando la solución en cada paso, el proceso del método simplex termina
cuando ya no hay como seguir mejorando más dicha solución. Para un problema de
programación lineal estándar, se empieza con la Solución Básica Factible (SBF), en la que todas
las variables de decisión son 0. Sin embargo, para un problema de maximización que no esté
en la forma estándar, tal SBF podría no existir.
Se dice que un Problema de Programación Lineal está en la forma estándar si: Es un problema
de maximización y todas las restricciones estructurales son de menor (menor o igual).

Como en todo problema de programación lineal, han de cumplirse las siguientes etapas:

➢ Definir las variables del problema

 ➢ Escribir conceptualmente el sistema de inecuaciones asociado a las restricciones del
problema
➢ Definir conceptualmente la función objetivo
➢ 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:

o x pasa a ser 𝒙𝟏

o y pasa a ser 𝒙𝟐

o Si fuese el caso de tener más variables entonces: 𝒙𝟑 , 𝒙𝟒 , … , 𝒆𝒕𝒄.

El algoritmo simplex sigue los siguientes pasos:

1. Tener en cuenta que en las restricciones estructurales los términos independientes

de las mismas son positivos. En caso de no serlo 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).

𝒙𝟏 − 8 𝒙𝟐 > 52 Conservamos la misma

expresión
2 𝒙𝟏 − 3 𝒙𝟐 > −12 Multiplicamos por -1

−2 𝒙𝟏 + 3 𝒙𝟐 < 12
2. Normalizar las restricciones.

Se convierten las inecuaciones en ecuaciones agregando variables de holgura, y/o

artificiales según la tabla siguiente:

Tipo de
Tipo de variable que aparece
desigualdad

Restamos una variable de holgura (s) y sumamos una variable

≥, >
artificial(t)

= Sumamos una variable artificial t

≤, < Sumamos una variable de holgura s

EJEMPLOS:

Tipo de desigualdad Tipo de variable que aparece

- holgura + artificial
2 𝒙𝟏 − 3 𝒙𝟐 > 12
2𝑥 − 3 𝒙𝟐 − 𝑠1 + 𝑡1 = 12

+ artificial
20 𝒙𝟏 + 54 𝒙𝟐 = 100
20 𝒙𝟏 + 54𝒙𝟐 + 𝑡2 = 100

+ holgura
2 𝒙𝟏 − 3 𝒙𝟐 ≤ 120
2 𝒙𝟏 − 3 𝒙𝟐 + 𝑠2 = 120
 3+4<10 5+6<12

3+4+s1=10 5+6 s2=12

3+4+3=10 5+6+1=12

2𝒙𝟏 + 𝒙𝟐 ≤ 𝟏𝟖

2𝒙𝟏 + 𝟑𝒙𝟐 ≤ 𝟒𝟐

3𝒙𝟏 + 𝒙𝟐 ≤ 𝟐𝟒

𝒙𝟏 , 𝒙 𝟐 ≥ 𝟎

En este caso se introduce una variable de holgura (𝒔𝟏 , 𝒔𝟐 , 𝒔𝟑 ) en cada una de las
restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones
lineales:

2𝒙𝟏 + 𝒙𝟐 + 𝒔𝟏 = 𝟏𝟖

2𝒙𝟏 + 𝟑𝒙𝟐 + 𝒔𝟐 = 𝟒𝟐

3𝒙𝟏 + 𝒙𝟐 + 𝒔𝟑 = 𝟐𝟒

3. Igualar la función objetivo a cero.

𝒁 = 𝒄𝟏 𝒙𝟏 + 𝒄𝟐 𝒙𝟐 + ⋯ + 𝒄𝒏 𝒙𝒏

−𝒄𝟏 𝒙𝟏 − 𝒄𝟐 𝒙𝟐 − ⋯ 𝒄𝒏 𝒙𝒏 + 𝒁 = 𝟎

4. Escribir la tabla inicial del método Simplex.

 La tabla inicial del método Simplex colocamos todas las variables, primero las variables
de decisión 𝒙𝒊 , seguidamente todas las variables de holgura 𝒔𝒊 , a continuación las
variables artificiales 𝒕𝒊 si fuese el caso, luego Z y finalmente los valores independientes
b. En la columna extrema izquierda A colocamos las variables agregadas (únicamente
las positivas) y Z.

La tabla la completamos con todos los coeficientes de las variables de decisión, holgura,
artificiales y Z. Los valores independientes en la columna b.

5. Elección de la variable entrante y saliente.

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.

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.

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 (valores de la columna b) entre el elemento
correspondiente de la columna pivote, siempre que ambos elementos sean
estrictamente positivos (mayores que cero, no se admiten las divisiones negativas ni las
indeterminaciones). 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 esta condición se habría
cumplido la condición de parada y el problema tendría una solución no acotada.

6. Actualizar la tabla.

Los nuevos coeficientes de la tabla se calculan de la siguiente manera:

o En la fila del elemento pivote cada nuevo elemento se calcula como:

 Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote

o 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).

7. Comprobar la condición de parada: Se observa que en la última fila todos los

coeficientes son positivos entonces llegamos al paso 8; si no se cumple el proceso
nuevamente regresa al paso 5.

8. Fin del algoritmo.

9. La solución óptima viene dada al asociar la columna extrema izquierda A y la columna

extrema derecha b.

APLICACIÓN PRÁCTICA

Maximizar

Z= 3𝒙𝟏 + 𝟐𝒙𝟐 -3𝒙𝟏 − 𝟐𝒙𝟐 + 𝒁 = 𝟎

Sujeta A

𝟐𝒙𝟏 + 𝒙𝟐 ≤ 8 𝟐𝒙𝟏 + 𝒙𝟐 + 𝒔𝟏 = 8

𝟐𝒙𝟏 + 𝟑𝒙𝟐 ≤ 12 𝟐𝒙𝟏 + 𝟑𝒙𝟐 + 𝒔𝟐 = 12

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎 -3𝒙𝟏 − 𝟐𝒙𝟐 + 𝒁 = 𝟎
 variable entrante

Variable saliente

TABLA SIMPLEX I

A 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 Z b
𝒔𝟏 2 1 1 0 0 8
𝒔𝟐 2 3 0 1 0 12
Z -3 -2 0 0 1 0
INDICADORES

Pivote

TABLA SIMPLEX II variable entrante

A 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 Z b
Divisiones la
𝒔𝟏 2 1 1 0 0 8 8/2
menor (no:
𝒔𝟐 2 3 0 1 0 12 12/2 negativos, ind.)
Z -3 -2 0 0 1 0

Indicadores (el menor de los negativos)

Variable saliente
VARIABLE ENTRANTE X1

A 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 Z b

VARIABLE SALIENTE 𝒔𝟏 𝒔𝟏 2/2 ½ ½ 0 0 8/2

𝒔𝟐 2 3 0 1 0 12
Z -3 -2 0 0 1 0
 3F1+F3
A 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 Z b
𝒙𝟏 1 1/2 1/2 0 0 4
𝒔𝟐 2 3 0 1 0 12
-2F1+F2
Z -3 -2 0 0 1 0
3F1+F3
Se ha realizado el cambio entre la variable entrante(𝒙𝟏 ) y saliente(𝒔𝟏 )

TABLA SIMPLEX II

A 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 Z b
𝒙𝟏 1 1/2 1/2 0 0 4
𝒔𝟐 0 2 -1 1 0 4
Z 0 -1/2 3/2 0 1 12

TABLA SIMPLEX III

A 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 Z b RESPUESTA
𝒙𝟏 1 0 3/4 -1/4 0 3
X1= 3
𝒙𝟐 0 1 -1/2 1/2 0 2
X2= 2
Z 0 0 5/4 1/4 1 13
Z= 13

Z Se maximiza en 13 cuando 𝒙𝟏 = 𝟑 y 𝒙𝟐 = 2