3.
3 Método simplex 79
5. Para cada una de las funciones objetivo dadas y el espacio de soluciones de la figura 3.4,
seleccione la variable no básica que conduce al siguiente punto de esquina simplex, y de-
termine la mejora asociada de z.
*(a) Maximizar z = x1 - 2x2 + 3x3
(b) Maximizar z = 5x1 + 2x2 + 4x3
(c) Maximizar z = - 2x1 + 7x2 + 2x3
(d) Maximizar z = x1 + x2 + x3
3.3.2 Detalles de cálculo del algoritmo simplex
En esta sección se explican los detalles de cálculo de una iteración simplex por medio
de un ejemplo numérico.
Ejemplo 3.3-1
Considere el modelo de Reddy Mikks (ejemplo 2.1-1) expresado en forma de ecuación:
Maximizar z = 5x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0s4
sujeto a
6x1 1 4x2 1 s1 5 24 (materia prima M1)
x1 1 2x2 1 s2 5 6 (materia prima M2)
2 x1 1 x2 1 s3 5 1 (Límite del mercado)
x2 1s4 5 2 (Límite de la demanda)
x1, x2, s1, s2, s3, s4 Ú 0
Las variables s1, s2, s3 y s4 son las holguras asociadas con las restricciones respectivas.
A continuación escribimos la ecuación objetivo como
z - 5x1 - 4x2 = 0
De esta manera, la tabla inicial simplex se representa como sigue:
Básica z x1 x2 s1 s2 s3 s4 Solución
z 1 -5 -4 0 0 0 0 0 Fila z
s1 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 diseño de la tabla simplex provee automáticamente la solución en la iteración inicial. La
solución se inicia en el origen (x1, x2) 5 (0,0), por lo que (x1, x2) se definen como las variables no
básicas y (s1, s2, s3, s4) como las variables básicas. La variable objetivo z y las variables básicas
www.FreeLibros.com
80 Capítulo 3 Método simplex y análisis de sensibilidad
aparecen en la columna de la extrema izquierda (Básica). Los lados derechos de las ecuaciones
del modelo dan sus valores, como se muestra en la columna de la extrema derecha (Solución) de
la tabla; es decir, z 5 0, s1 5 24, s2 5 6, s3 5 1, s4 5 2. El resultado puede verse igualando las va-
riables no básicas (x1, x2) a cero en todas las ecuaciones y también observando la configuración
de matriz identidad especial de los coeficientes de las variables básicas (todos los elementos en
las diagonales son 1, y todos los elementos fuera de las diagonales son 0).
¿Es óptima la solución inicial? La función objetivo z 5 5x1 1 4x2 muestra que la solución
puede mejorarse si se incrementa el valor de la variable x1 o de la x2 no básica por encima de cero.
Siguiendo el argumento de la sección 3.3.1, x1 tiene que incrementarse porque tiene el coeficien-
te objetivo más positivo. De forma equivalente, en la tabla simplex donde la función objetivo
aparece como z 2 5x1 2 4x2 5 0, la variable seleccionada es la variable no básica con el coefi-
ciente más negativo en la ecuación objetivo. Esta regla define la llamada condición de optimali-
dad simplex. En la terminología del algoritmo simplex, x1 se conoce como la variable de entrada
porque ingresa la solución básica.
Si x1 es la variable de entrada, una de las variables básicas actuales debe salir; es decir, se
vuelve no básica a un nivel cero (recordemos que la cantidad de variables no básicas debe ser
siempre n 2 m). La mecánica para determinar la variable de salida implica calcular las relacio-
nes del lado derecho de las ecuaciones (columna Solución) con los coeficientes de restricción es-
trictamente positivos (imposibilitando así al cero) bajo la variable de entrada, x1, como se muestra
en la siguiente tabla:
x1
Básica entrante Solución Relación (o intersección)
24
s1 6 24 x1 = 6 = 4 ; mínimo
6
s2 1 6 x1 = 1 = 6
1
s3 -1 1 x1 = -1 = - 1 (denominador negativo, ignorar)
2
s4 0 2 x1 = 0 = q (denominador cero, ignorar)
Conclusión: x1 entra (en el nivel 4) y x2 sale (en el nivel cero)
¿Cómo 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 líneas de restricción con el eje x1 (variable de entrada). Podemos ver que el valor de x1
debe incrementarse hasta la intersección no negativa mínima con el eje x1 (5 4) para alcanzar el
punto de esquina B. Cualquier incremento más allá de B no es factible. En el punto B, la varia-
ble básica actual s1 asociada con la restricción 1 asume un valor de cero y se transforma en la va-
riable de salida. La regla asociada con las relaciones calculadas se conoce como condición de fac-
tibilidad simplex porque garantiza la factibilidad de la nueva solución.
El nuevo punto de solución B se determina “intercambiando” la variable de entrada x1 y la
variable de salida s1 en la tabla simplex para obtener
Variables no básicas (cero) en B: (s1, x2)
Variables básicas en B: (x1, s2, s3, s4)
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-
www.FreeLibros.com
3.3 Método simplex 81
x2
6 Maximizar z 5x1 4x2
sujeto a:
6x1 4x2 s1 24 1
5
x1 2x2 s2 6 2
s1
1 x1 x2 s3 1 3
0
4
3
0 x2 s4 2 4
s3 x1, x2 0
3 2
s2
0
4
2
s4 0
C
A B
x1
2 1 0 1 2 3 4 5 6
24
4
1 6
1 1
6
1 6
FIGURA 3.5
Interpretación gráfica de las relaciones del método simplex en el modelo de Reddy Mikks
vote. La intersección 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
T
Básica z x1 x2 s1 s2 s3 s4 Solución
z 1 -5 -4 0 0 0 0 0
Sale ; s1 0 6 4 1 0 0 0 24 Fila pivote
s2 0 1 2 0 1 0 0 6
s3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2
Columna
pivote
Los cálculos de Gauss-Jordan necesarios para obtener la nueva solución básica son de dos
tipos.
1. Fila pivote
a. Reemplace la variable de salida en la columna Básica con la variable de entrada.
b. Nueva fila pivote 5 Fila pivote actual 4 Elemento pivote
www.FreeLibros.com
82 Capítulo 3 Método simplex y análisis de sensibilidad
2. Todas las demás filas, incluyendo z
Nueva fila 5 (Fila actual) 2 (Coeficiente de la
columna pivote) 3 (Nueva fila pivote)
Estos cálculos se aplican a la tabla anterior como sigue:
1. Reemplace s1 en la columna Básica con x1:
Nueva fila x1 5 Fila s1 actual 4 6
1
= 6 (0 6 4 1 0 0 0 24)
2 1
= (0 1 3 6 0 0 0 4)
2. Nueva fila z 5 Fila z actual 2 (25) 3 Nueva fila x1
= (1 - 5 - 4 0 0 0 0 0) - (- 5) * (0 1 23 1
6 0 0 0 4)
= (1 0 - 23 56 0 0 0 20)
3. Nueva fila s2 5 Fila s2 actual 2 (1) 3 Nueva fila x1
2 1
= (0 1 2 0 1 0 0 6) - (1) * (0 1 3 6 0 0 0 4)
4
= (0 0 3 - 16 1 0 0 2)
4. Nueva fila s3 5 Fila s3 actual 2 (21) 3 Nueva fila x1
2 1
= (0 - 1 1 0 0 1 0 1) - ( -1) * (0 1 3 6 0 0 0 4)
5 1
= (0 0 3 6 0 1 0 5)
5. Nueva fila s4 5 Fila s4 actual 2 (0) 3 Nueva fila x1
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 solución básica es (x1, s2, s3, s4), y la nueva tabla es
T
Básica z x1 x2 s1 s2 s3 s4 Solución
z 1 0 - 23 5
6 0 0 0 20
x1 0 1 2 1 0 0 0 4
3 6
4
; s2 0 0 3 - 16 1 0 0 2
s3 0 0 5 1 0 1 0 5
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 básica forman una matriz de identidad. Por
consiguiente, cuando igualamos las nuevas variables no básicas x2 y s1 a cero, la columna
www.FreeLibros.com
3.3 Método simplex 83
Solución de forma automática da la nueva solución (x1 5 4, s2 5 2, s3 5 5, s4 5 2).3 Este “acon-
dicionamiento” de la tabla es el resultado de la aplicación de las operaciones de filas de Gauss-
Jordan. El nuevo valor objetivo es z 5 20, el cual es consistente con
Nueva z 5 Anterior z 1 Nuevo valor de x1 3 su coeficiente objetivo
= 0 + 4 * 5 = 20
Por otra parte, z 5 4 3 valor de x1 1 0 3 valor de s2 1 0 3 valor de s3 1 0 3 valor de x4 5 4 3 5
1 0 3 2 1 0 3 5 1 0 3 2 5 20.
En la última tabla, la condición de optimalidad muestra que x2 es la variable de entrada. La
condición de factibilidad produce la siguiente información:
Entrante
Básica x2 Solución Relación
2 2
x1 3
4 x2 = 4 , 3 = 6
4 4
s2 3 2 x2 = 2 , 3 = 1.5 (mínima)
5 5
s3 3 5 x2 = 5 , 3 = 3
s4 1 2 x2 = 2 , 1 = 2
Por lo tanto, s2 sale de la solución básica, y el nuevo valor de x2 es 1.5. El incremento correspon-
diente en z es 32 x2 = 23 * 1.5 = 1, el cual da la nueva z 5 20 1 1 5 21.
Si reemplazamos s2 en la columna Básica con la x2 de entrada, se aplican las siguientes ope-
raciones de filas de Gauss-Jordan:
1. Nueva fila pivote x2 5 Fila s2 actual 4 43
2. Nueva fila z 5 Fila z actual 2(- 23) 3 Nueva fila x2
3. Nueva fila x1 5 Fila x1 actual 2(32 ) 3 Nueva fila x2
4. Nueva fila s3 5 Fila s3 actual 2(53 ) 3 Nueva fila x2
5. Nueva fila s4 5 Fila s4 actual 2 (1) 3 Nueva fila x2
Estos cálculos producen la siguiente tabla:
Básica z x1 x2 s1 s2 s3 s4 Solución
3 1
z 1 0 0 4 2 0 0 21
1
x1 0 1 0 4 - 12 0 0 3
x2 0 0 1 - 18 3
4 0 0
3
2
3
s3 0 0 0 8 - 54 1 0
5
2
1
s4 0 0 0 8 - 34 0 1
1
2
3
A lo largo de mi experiencia académica, he notado que si bien los estudiantes son capaces de realizar los te-
diosos cálculos del método simplex, al final algunos no pueden decir cuál es la solución. Para ayudar a ven-
cer esta dificultad potencial, se hace un esfuerzo por “leer” la solución de la PL por la tabla.
www.FreeLibros.com
84 Capítulo 3 Método simplex y análisis de sensibilidad
Según la condición de optimalidad, ninguno de los coeficientes de la fila z son negativos. De ahí
que la última tabla sea óptima.
La solución óptima puede leerse en la tabla simplex de la siguiente manera. Los valores óp-
timos de las variables en la columna Basic aparecen en la columna Solución del lado derecho y
se interpretan como sigue:
Variable de decisión Valor óptimo Recomendación
x1 3 Producir 3 toneladas diarias de pintura para exteriores
3
x2 2 Producir 1.5 toneladas diarias de pintura para interiores
z 21 La utilidad diaria es de $21,000
La solución también 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, M1 s1 = 0 Escaso
Materia prima, M2 s2 = 0 Escaso
Límite del mercado s3 = 52 Abundante
1
Límite de la demanda s4 = 2 Abundante
Comentarios. La tabla simplex ofrece mucha información adicional que incluye lo siguiente:
1. Análisis de sensibilidad, el cual determina las condiciones que mantendrán la solución ac-
tual sin cambios.
2. Análisis postóptimo, el cual determina la nueva solución óptima cuando cambian los datos
del modelo.
La sección 3.6 se ocupa del análisis de sensibilidad. El análisis postóptimo se trata en el capítulo 4.
Momento de TORA.
Los cálculos de Gauss-Jordan son tediosos, voluminosos y, sobre todo, aburridos. No obstante,
esto no tiene importancia porque en la práctica la computadora realiza estos cálculos. Lo impor-
tante es que entienda cómo funciona el método simplex. La opción interactiva guiada para el
usuario de TORA (con retroalimentación instantánea), puede ser de ayuda porque le permite
especificar el curso de los cálculos simplex (es decir, determinar las variables de entrada y de sa-
lida) sin el agobio de los cálculos de Gauss-Jordan. Para utilizar TORA con el problema de
Reddy Mikks, ingrese el modelo y luego, en el menú SOLVE/MODIFY seleccione los coman-
dos Solve Q Algebraic Q Iterations Q All-Slack . (La selección All-Slack indica que la so-
lución básica inicial se compone de sólo variables de holgura. Las opciones restantes se pre-
sentarán en las secciones 3.4, 4.3, y 7.4-2). A continuación, haga clic en el botón
Go To Output Screen . Puede generar una o todas las iteraciones haciendo clic en las opciones
Next Iteration o bien All Iterations . Si opta por generar las iteraciones de una en una, puede es-
www.FreeLibros.com
