3.3.
2 Detalles de calculo del algoritmo simplex
En esta seccion se explican los detalles de calculo de una iteracion simplex por medio
de un ejemplo numerico.
Ejemplo 3.3- 1
Considere el modelo de Reddy Mikks (ejemplo 2.1-1) expresado en forma de ecuacion:
Maximizar z — 5*i -1- 4 x2 + Osi + 0s2 + 0s3 -1- 0s4
sujeto a
6 x\ + 4*2 + si = 24 (materia prima Ml )
X\ + 2^2 + ^2 = 6 ( materia prima M 2 )
- xi + x2 + ^3 = 1 (Limite del mercado)
*2 + S4 = 2 ( Limite de la demanda )
xhx2 , sus2 ys3 , s4 0
Las variables sq , ^2, ^3 y ^4 son las holguras asociadas con las restricciones respectivas.
A continuacion escribimos la ecuacion objetivo como
z — 5 xi — 4 X2 =0
De esta manera , la tabla inicial simplex se representa como sigue:
Basica z X\
*2 S1
^2 ^3 S4 Solution
z 1 -5 -4 0 0 0 0 0 Fila z
si 0 6 4 1 0 0 0 24 Fila s1
S2 0 1 2 0 1 0 0 6 Fila s2
S3 0 -1 1 0 0 1 0 1 Fila s3
s4 0 0 1 0 0 0 1 2 Fila s4
El diseno de la tabla simplex provee automaticamente la solution en la iteracion inicial. La
solution se inicia en el origen (xi , x2) = (0 ,0) , por lo que (xi , x2 ) se definen como las variables no
basicas y ($1, s2 , s3, s4 ) como las variables basicas. La variable objetivo z y las variables basicas
aparecen en la columna de la extrema izquierda ( Basica ). Los lados derechos de las ecuaciones
del modelo dan sus valores, como se muestra en la columna de la extrema derecha (Solucion ) de
la tabla; es decir, z — 0, s\ = 24, s2 = 6, s2 = 1, S4 = 2. El resultado puede verse igualando las va-
riables no basicas (x 3, x2 ) a cero en todas las ecuaciones y tambien observando la configuration
de matriz identidad especial de los coeficientes de las variables basicas ( todos los elementos en
las diagonales son 1, y todos los elementos fuera de las diagonales son 0 ).
Es optima la solucion inicial? La funcion objetivo z = 5x3 + 4^2 muestra que la solucion
^
puede mejorarse si se incrementa el valor de la variable x\ o de la x2 no basica por encima de cero.
Siguiendo el argumento de la section 3.3.1, x\ tiene que incrementarse porque tiene el coeficien-
te objetivo mas positivo . De forma equivalente, en la tabla simplex donde la funcion objetivo
— —
aparece como z 5x3 4x2 = 0 , la variable seleccionada es la variable no basica con el coefi-
ciente mas negativo en la ecuacion objetivo. Esta regia define la llamada condicion de optimali-
dad simplex. En la terminologia del algoritmo simplex, x\ se conoce como la variable de entrada
porque ingresa la solucion basica .
Si x\ es la variable de entrada, una de las variables basicas actuales debe salir; es decir, se
vuelve no basica a un nivel cero ( recordemos que la cantidad de variables no basicas debe ser
—
siempre n m ). La mecanica para determinar la variable de salida implica calcular las relacio
nes del lado derecho de las ecuaciones ( columna Solucion ) con los coeficientes de restriccion es-
-
trictamente positivos (imposibilitando asi al cero) bajo la variable de entrada, xi, como se muestra
en la siguiente tabla:
Xi
Basica entrante Solucion Relation ( o intersection)
6 24 minimo
*2 1 6 *1 =
S3 -1 1 *1 = = 1 1 ( denominador negativo, ignorar )
9
s4 0 2 X\ = Q = 00 ( denominador cero, ignorar )
Conclusion: x\ entra (en el nivel 4) y X 2 sale (en el nivel cero )
Como determinan las relaciones calculadas la variable de salida y el valor de la variable de
^
entrada ? La figura 3.5 muestra que las relaciones calculadas son en realidad las intersecciones
de las lineas de restriccion con el eje x\ ( variable de entrada ). Podemos ver que el valor de x\
debe incrementarse hasta la interseccion no negativa minima con el eje x\ ( = 4) para alcanzar el
punto de esquina B . Cualquier incremento mas alia de B no es factible. En el punto B , la varia-
ble basica actual s\ asociada con la restriccion 1 asume un valor de cero y se transforma en la va-
riable de salida . La regia asociada con las relaciones calculadas se conoce como condicion de fac-
tibilidad simplex porque garantiza la factibilidad de la nueva solucion.
El nuevo punto de solucion B se determina “ intercambiando ” la variable de entrada x\ y la
variable de salida si en la tabla simplex para obtener
Variables no basicas (cero) en B: ( s\ , x2 )
Variables basicas en B: (xi, s2 , s3, ^4)
El proceso de intercambio se basa en las operaciones de filas de Gauss-Jordan. Identifica la co-
lumna de la variable de entrada como columna pivote y la fila de la variable de salida como fila pi-
*2
6 Maximizar z = 5 x ± + 4x2
sujeto a:
6 x1 + 4x 2 + s1 = 24 (l)
5
y Xi + 2X2 + s2 = 6 (5)
W
A® -*1 + *2 + s3 = 1 ©
4
X2 + 54 2 ©
x h x2 > 0
3 2
J!
2
^0
S4 =0
c
5
xi
-2 -1 0 1 2 3 4 5 6
24
<-
6 =4 >
1
- 6
-
1= 1 - 6 -
*
I “
FIGURA 3.5
Interpretacion grafica de las relaciones del metodo simplex en el modelo de Reddy Mikks
vote . La intersection de la columna pivote y la fila pivote se conoce como elemento pivote . La si-
guiente tabla es un replanteamiento de la tabla inicial con sus filas y columnas pivote resaltadas.
Entra
i
Basica z *i *2 *1 *2 ^3 54 Solucion
z 1 -5 -4 0 0 0 0 0
Sale si 0 6 4 1 0 0 0 24 Fila pivote
*2 0 1 2 0 1 0 0 6
*3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2
Columna
pivote
Los calculos de Gauss-Jordan necesarios para obtener la nueva solucion basica son de dos
tipos.
1. Fila pivote
a. Reemplace la variable de salida en la columna Basica con la variable de entrada.
b. Nueva fila pivote = Fila pivote actual Elemento pivote
.
2 Todas las demas filas, incluyendo z
—
Nueva fila = (Fila actual ) ( Coeficiente de la
columna pivote ) X ( Nueva fila pivote )
Estos calculos se aplican a la tabla anterior como sigue:
.
1 Reemplace si en la columna Basica con x\.
Nueva fila x\ = Fila si actual -F 6
=
^
= (0 1
(0 6 4 1 000 24 )
2 1
3 6 0 0 0 4)
2. Nueva fila z = Fila z actual - ( 5) — X Nueva fila x1
= (1 -5 -4 0 0 0 0 0 ) - ( -5 ) X ( 0 1 32 1
6 0 0 0 4)
2 5
= (1 0 3 6 0 0 0 20)
.
3 Nueva fila s2 = Fila s2 actual — (1) X Nueva fila x\
2 1
= (0 1 2 0 1 0 0 6 ) - (1) x (0 1 3 6 0 0 0 4)
=(00 I -i 1 0 0 2)
.
4 Nueva fila S3 = Fila s3 actual — ( — 1) X Nueva fila x1
2 1
= (0 -1 1 0 0 1 0 1) - (-1) X (0 1 3 6 0 0 0 4)
5 1
= (0 0 3 6 0 10 5)
.
5 Nueva fila s4 Fila 54 actual — (0 ) X Nueva fila x\
2 1
= (0 0 1 0 0 0 1 2)-(0)(0 1 3 6 0 0 0 4)
= (0 0 1 0 0 0 1 2)
La nueva solucion basica es ( x\ , s2 , 53, ^4) , y la nueva tabla es
I
Basica z *1 x2 Si S2 S3 54 Solucion
2 5
z 1 0 3 6 0 0 0 20
0 1 2 1 0 0 0 4
*1 3 6
4 1
*2 0 0 3 6
1 0 0 2
0 0 5 1 0 1 0 5
^3 3 6
s4 0 0 1 0 0 0 1 2
Observe que la estructura de la nueva tabla es similar a la de la tabla inicial, en el sentido de
que los coeficientes de las restricciones de la variable basica forman una matriz de identidad . Por
consiguiente, cuando igualamos las nuevas variables no basicas x2 y sq a cero, la columna
Solution de forma automatica da la nueva solucion ( jq = 4, s2 = 2, 53 = 5 , s4 = 2 )? Este “ acon-
dicionamiento ” de la tabla es el resultado de la aplicacion de las operaciones de filas de Gauss-
—
Jordan. El nuevo valor objetivo es z 20, el cual es consistente con
Nueva z = Anterior z + Nuevo valor de X su coeficiente objetivo
= 0 + 4 x 5 = 20
Por otra parte, z = 4 X valor de x\ + 0 X valor de s2 + 0 X valor de 5 3 + 0 X valor de x4 = 4 X 5
*
+ 0 X 2 + 0 X 5 + 0 X 2 = 20.
En la ultima tabla , la condition de optimalidad muestra que x2 es la variable de entrada. La
condition de factibilidad produce la siguiente information:
Entrante
Basica *2 Solucion Relation
—-
2
*1 3
4 *2 = 4 ^ 1 = 6
4
*2 3 2 * 2 = 2 |= 1.5 ( minima )
—
5
^3 3 5 *2 = 5 f = 3
s4 1 2 x2 = 2 1 = 2
Por lo tanto, s2 sale de la solucion basica, y el nuevo valor de x2 es 1.5. El incremento correspon-
diente en z es § x 2 = \
X 1.5 = 1, el cual da la nueva z = 20 + 1 = 21.
Si reemplazamos s2 en la columna Basica con la x2 de entrada , se aplican las siguientes ope-
raciones de filas de Gauss-Jordan:
1. Nueva fila pivote x2 Fila s2 actual
2. Nueva fila z = Fila z actual ( 3) X Nueva fila x2
— — -f
—
3. Nueva fila x 4 = Fila x 4 actual (3) X Nueva fila x2
— f
4. Nueva fila S3 = Fila S3 actual ( ) X Nueva fila x2
5. Nueva fila s4 = Fila s4 actual (1) X Nueva fila x2
—
Estos calculos producen la siguiente tabla:
Basica z Xl x2 Si S2 S3 S4 Solucion
3 1
z 1 0 0 4 2 0 0 21
1 1
*1 0 1 0 4 2 0 0 3
1 3 3
*2 0 0 1 8 4 0 0 2
3 5 5
S3 0 0 0 8 4 1 0 2
1 3 1
s4 0 0 0 8 4 0 1 2
3
A lo largo de mi experiencia academica, he notado que si bien los estudiantes son capaces de realizar los te-
diosos calculos del metodo simplex , al final algunos no pueden decir cual es la solucion . Para ayudar a ven-
eer esta dificultad potencial, se hace un esfuerzo por “ leer ” la solucion de la PL por la tabla.
Segun la condition de optimalidad , ninguno de los coeficientes de la fila z son negativos. De ahi
que la ultima tabla sea optima.
La solucion optima puede leerse en la tabla simplex de la siguiente manera. Los valores op-
timos de las variables en la columna Basic aparecen en la columna Solucion del lado derecho y
se interpretan como sigue:
Variable de decision Valor optimo Recomendacion
*i 3 Producir 3 toneladas diarias de pintura para exteriores
3
*2 2 Producir 1.5 toneladas diarias de pintura para interiores
z 21 La utilidad diaria es de $21,000
La solucion tambien da el estado de los recursos. Un recurso se designa como escaso si la
variable de holgura asociada es cero, es decir, las actividades ( variables ) del modelo consumie-
ron el recurso por completo. De lo contrario, si la holgura es positiva , entonces el recurso es
abundante . La siguiente tabla clasifica las restricciones del modelo:
Recurso Valor de holgura Estado
Materia prima, M l Escaso
Materia prima , M 2 Escaso
Lfmite del mercado Abundante
Lhnite de la demanda Abundante
Comentarios. La tabla simplex ofrece mucha information adicional que incluye lo siguiente:
1. Analisis de sensibilidad, el cual determina las condiciones que mantendran la solucion ac-
tual sin cambios.
.
2 Analisis postoptimo, el cual determina la nueva solucion optima cuando cambian los datos
del modelo.