Método simplex en su forma tabular
Inicialización
Se introducen las variables de holgura, superávit o artificiales, según sea el caso, al
modelo original. Se seleccionan las variables de decisión como las variables no
básicas iniciales (es decir, iguales a cero) y las variables de holgura, superávit o
artificial introducidas anteriormente, como las variables básicas iniciales.
Con la información anterior se construye la tabla simplex (ver Tabla1).
Al terminar realizamos la Prueba de Optimalidad que plantea: La solución básica
factibles actual es óptima si y solo si todos los coeficientes en el renglón 0 son no
negativos (≥ 0), es decir, no existen variables que puedan aumentar la tasa de
mejoramiento en Z. Si es así el proceso se detiene, de otra manera, sigue a una
iteración para obtener la siguiente solución básica factible, que incluye cambiar una
variable no básica a básica (Paso 1) y viceversa (Paso 2) y después despejar la nueva
solución (Paso 3).
Iteración
Paso 1:
Se determina la variable básica entrante: para esto se selecciona la variable no básica
con el coeficiente negativo que tiene el mayor valor absoluto en la ecuación (0). Se
pone un recuadro alrededor de la columna debajo de este coeficiente y se le da el
nombre de columna pivote.
Paso 2:
Se determina la variable básica que se sale aplicando la prueba del cociente mínimo.
Prueba del cociente mínimo
1. Se elijen los coeficientes de la columna pivote que son estrictamente positivos
(>0).
2. Se divide cada coeficiente entre el elemento del lado derecho en el mismo
renglón.
3. Se identifica el renglón que tiene el menor de estas razones.
4. La variable básica para ese renglón es la variable básica que sale, por lo que
se sustituye esta variable por la variable básica entrante en la columna de la
variable básica de la siguiente tabla.
Ponga un recuadro en este renglón que se llana renglón pivote. El coeficiente que
pertenece a los dos recuadros se conoce como pivote.
Paso 3:
Obtención de la nueva tabla.
1. El renglón de la nueva variable básica es el resultado de dividir cada elemento
del renglón pivote entre el pivote.
2. La columna de la nueva variable básica pasa a ser el vector correspondiente
de la eliminación gaussiana, con el número 1 en la posición del pivote.
3. El resto de los elementos se halla pivoteando, para ellos denotaremos la
columna pivote con “k”, al renglón pivote con “r”, al pivote con “X rk” y al resto
de los elementos como Xij donde “i” refiere al número de la ecuación y “j” a la
variable en cuestión, ej. X12 hace referencia al coeficiente en la ecuación 1 que
posee la variable X2. Indicaremos con un superíndice el elemento nuevo a
diferencia del que le da origen, ej. X, X’. Entonces el nuevo elemento se
determina:
𝐗 𝐫𝐣
𝑿′ 𝐢𝐣 = 𝐗 𝐢𝐣 – 𝐗 𝐢𝐤 𝐢≠𝐣
𝐗 𝐫𝐤
Veamos el siguiente ejemplo:
1. MAX Z=3x1 + 2x2
s.a:
𝑥1 ≤ 4
𝑥1 + 3𝑥2 ≤ 15
2𝑥1 + 𝑥2 ≤ 10
𝑥1 ≥ 0, 𝑥2 ≥ 0
Inicialización
Convertiremos las restricciones funcionales de desigualdad en restricciones de
igualdad equivalentes. Esta conversión se mediante la introducción de variables de
holgura.1
Z-3x1 - 2x2 = 0
x1 + x3 =4
x1 + 3x2 + x4 = 15
2x1 + x2+ x5 = 10
𝑥𝑗 ≥ 0 ∀𝑗 = 1,2,3,4,5
1
Las variables de holguras no se muestran en la función objetivo porque sus coeficientes son cero.
Eligiendo las variables de decisión como las variables no básicas (iguales a cero) y
las variables de holgura como variables básicas iniciales, el sistema de ecuaciones
posee la forma apropiada de eliminación gaussiana, en donde cada variable básica
inicial (resaltadas en negritas) está eliminada de todas las ecuaciones menos una (su
ecuación) y en esa ecuación tiene coeficiente +1.
La tabla del ejercicio en cuestión queda:
Iteración VB Coeficiente de PD
Z x1 X2 X3 X4 X5
0 Z 1 -3 -2 0 0 0 0
X3 0 1 0 1 0 0 4
X4 0 1 3 0 1 0 15
X5 0 2 1 0 0 1 10
Tabla 1. Tabla simplex
Una vez concluida la tabla pasamos a la Prueba de Optimalidad. ¿Es óptima la
solución básica (0,0,4,15,10) con Z = 0 ? No, existen variables en el renglón 0 con
coeficientes negativos, lo que indica que pueden aumentar la tasa de mejoramiento en
Z por lo tanto damos paso a una iteración.
Iteración 1
Paso 1: Determinar la variable que entra a la base.
Iteración VB Coeficiente de PD
Z x1 X2 X3 X4 X5
0 Z 1 -3 -2 0 0 0 0
X3 0 1 0 1 0 0 4
X4 0 1 3 0 1 0 15
X5 0 2 1 0 0 1 10
Tabla 2. Identificación de la variable que entra a la base.
Teniendo en cuenta que X1 posee el coeficiente negativo en el renglón cero con el
mayor valor absoluto (3 > 2) es seleccionada como la variable básica entrante.
Nota: Cada vez que se realice una iteración y por ende se complete la tabla simplex,
estaremos en presencia de una solución básica factible para el ejercicio en cuestión.
Donde cada variable básica (las que pertenecen a la columna VB) es igual al valor
correspondiente en la columna PD (Parte Derecha).
Paso 2: Determinar la variable que sale de la base.
Iteración VB Coeficiente de PD
Z x1 X2 X3 X4 X5
0 Z 1 -3 -2 0 0 0 0
X3 0 1 0 1 0 0 4
X4 0 1 3 0 1 0 15
X5 0 2 1 0 0 1 10
Tabla 3. Tabla simplex indicando la variable que sale de la base.
Aplicando la prueba del cociente mínimo:
X3: 4/1 = 4 X4: 15/1 = 15 X5: 10/2 = 5 (4 < 5 < 15)
Seleccionamos a X3 como la variable que sale de la base. Esto indica que X3 es la
variable que más rápido llega a cero cuando X1 entra a la base, por lo que si X1 toma
valores mayores que el cociente de X3 obligaría a esta a violar la restricción de no
negatividad.
Paso 3: Obtención de la nueva tabla. En este paso nos apoyaremos totalmente en la
Tabla 3.
1. El renglón de la nueva variable básica es el resultado de dividir cada elemento
del renglón pivote entre el pivote.
Iteración VB Coeficiente de PD
Z x1 X2 X3 X4 X5
1 Z 1
X1 0 1 0 1 0 0 4
X4 0
X5 0
Tabla 4. Tabla simplex con los coeficientes del renglón de X1
Evidentemente como el pivote es 1, el nuevo renglón resulta ser idéntico al anterior.
2. La columna de la nueva variable básica pasa a ser el vector correspondiente
de la eliminación gaussiana, con el número 1 en la posición del pivote.
Iteración VB Coeficiente de PD
Z x1 X2 X3 X4 X5
1 Z 1 0 0 0
X1 0 1 0 1 0 0 4
X4 0 0 1 0
X5 0 0 0 1
Tabla 5. Tabla simplex con la columna de X1
Las columnas de las variables que se encuentran en la base mantienen el
patrón por lo tanto su columna es idéntica a la de la Tabla 3.
3. El resto de los elementos se halla pivoteando, utilizando la expresión:
𝐗 𝐫𝐣
𝑿′ 𝐢𝐣 = 𝐗 𝐢𝐣 – 𝐗 𝐢𝐤 𝐢≠𝐣
𝐗 𝐫𝐤
Sustituyendo la expresión anterior en la Tabla 3 obtenemos:
X12 = -2 – (-3*0/1) = -2 X23 = 0 – (1*1/1) = - 1
X13 = 0 - (-3*1/1) = 3 X33 = 0 – (2*1/1) = -2
PD0 = 0 - (-3*4/1) = 12 PD2 = 15 – (1*4/1) = 11
X22 = 3 – (1*0/1) = 3 PD3 = 10 – (2*4/1) = 2
X32 = 1 – (2*0/1) = 1
Iteración VB Coeficiente de PD
Z x1 X2 X3 X4 X5
1 Z 1 0 -2 3 0 0 12
X1 0 1 0 1 0 0 4
X4 0 0 3 -1 1 0 11
X5 0 0 1 -2 0 1 2
Tabla 6. Tabla simplex resultante de la iteración 1.
Una vez concluida la tabla pasamos a la Prueba de Optimalidad. ¿Es óptima la
solución básica (4,0,0,11,2)2 con Z = 12? No, existe una variable en el renglón 0 con
coeficientes negativos, lo que indica que pueden aumentar la tasa de mejoramiento en
Z por lo tanto damos paso a otra iteración.
Iteración 2
Realice los pasos expuestos anteriormente y compruebe el resultado. Aquí quedan las
tablas resultantes de las iteraciones 2 y 3.
Iteración VB Coeficiente de PD
2
Las variables que no se encuentran en la base tienen valor cero.
Z x1 X2 X3 X4 X5
2 Z 1 0 0 -1 0 2 16
X1 0 1 0 1 0 0 4
X4 0 0 0 5 1 -3 5
X2 0 0 1 -2 0 1 2
Iteración VB Coeficiente de PD
Z x1 X2 X3 X4 X5
3 Z 1 0 0 0 0.2 1.4 17
X1 0 1 0 0 -0.2 0.6 3
X3 0 0 0 1 0.2 -0.6 1
X2 0 0 1 0 0.4 -0.2 4
Como puede observar en la última tabla hemos llegado a la solución óptima del
ejercicio. No existen coeficientes negativos en el renglón cero, lo que indica que no
hay variables que provoquen un aumento en la tasa de mejoramiento de Z. La solución
óptima es (3, 4, 1, 0, 0) con Z = 17
