Unidad 5
5.1. Algoritmo en modelos de maximización
El primer tipo de modelo que vamos a resolver por el método símplex
es el que tiene como objetivo maximizar a una función lineal, la cual
está sujeta a una serie de restricciones de la forma menor igual que. El
modelo tiene la forma:
Z máx c1 x1 c2 x2 … cn xn
s. a.: a11 x1 a12 x2 … a1n xn b1
a21 x1 a22 x2 … a2 n xn b2
# # ##
am1 x1 am 2 x2 … amn xn bm
xi 0 i 1, 2, … n
Que se representa en forma matricial por:
Z máx = CX
AX < B
X>0
Donde:
C = (c1, c2, ...cn) matriz de costos
A = matriz de coeficientes
B = matriz columna de términos independientes
X = matriz columna de las variables x1, x2, x3, ..., xn
Algoritmo símplex
1. El primer paso consiste en convertir las desigualdades en igualdades al
sumarles una variable de holgura h. Esta variable representa la cantidad
que le falta a la desigualdad para ser igualdad. Las variables de holgura
son siempre positivas.
a11 x1 a12 x2 … a1n xn h1 b1
a21 x1 a22 x2 … a2 n xn h2 b2
# # ##
am1 x1 am 2 x2 … amn xn hm bm
180
Investigación de operaciones
2. Formamos la tabla símplex.
Se construye una tabla como la que se muestra a continuación:
En la primera celda escribimos la etiqueta variables básicas,
en la siguiente la etiqueta Z , en la última colocamos la etiqueta solución
y en las intermedias escribimos los nombres de las variables originales,
seguidas de las variables de holgura.
El segundo renglón contiene la función objetivo, escrita de
la siguiente manera: Z máx–c1x1–c2 x2–...–cnxn –0h1–0h2–0h3=0, esto es, se
agregan las variables de holgura h, colocándoles como coeficiente cero
(–0 = +0) y después todas las variables se pasan del lado izquierdo de la
igualdad.
A partir del tercer renglón escribimos cada una de las
restricciones, en la columna de la variable básica colocamos las variables
que forman la base ortogonal más simple (las componentes de la matriz
identidad) que corresponden a las variables de holgura:
181
Unidad 5
De esta manera se forma la tabla inicial símplex.
La primera solución asociada a esta tabla símplex es:
h1 = b1
h2 = b2
...
hm = bm
Z=0
Esta solución se obtiene al observar que si en la tabla tomamos las
columnas asociadas a las variables básicas, entonces tenemos la matriz
identidad aumentada. El valor de Z se lee directamente del coeficiente
que está en el renglón de Z, debajo de la columna solución.
Una vez que obtuvimos la tabla inicial símplex asociada al modelo de P. L.
se continúa para encontrar la solución óptima (si es que existe) o bien
determinar que el problema no tiene solución óptima.
3. Verificamos si todos los coeficientes asociados al renglón de Z son
mayores o iguales a cero, si es así entonces la solución en la tabla es
la óptima. Termina. Si no es así, se continúa con el proceso.
4. Del conjunto de columnas se toma la que tenga el mayor valor
negativo (número menor). Ésta es la variable que entra al sistema
(pasa a ser básica) de manera que una variable tiene que salir para dar
paso a la nueva.
5. Se divide el coeficiente de la columna seleccionada entre los elementos
de la columna solución, de la operación se selecciona el menor valor
positivo. Ésta es la variable que sale de la base (pasa a ser no básica).
Nota. Las divisiones entre cero o entre números negativos no se
toman en cuenta. Si todas son negativas o indeterminadas el problema
no tiene solución. Termina.
6. La celda que se encuentra en la intersección de la columna
seleccionada con el renglón seleccionado contiene al que llamaremos
elemento pivote, por medio de operaciones elementales entre
columnas el elemento pivote se convierte en 1 y sus elementos
restantes en su columna en ceros; se obtiene una nueva columna
componente de matriz identidad.
182
Investigación de operaciones
7. Se repite el proceso desde el paso 3 operando sobre matrices.
Para entender mejor el algoritmo vamos a resolver el siguiente modelo de P. L.
Ejemplo 1
Z m á x 3 x1 5 x2
s. a.: 3x1 2 x2 18
x1 4
x2 6
x1 , x2 0
1. Lo primero es sumar a cada una de las desigualdades una variable de
holgura, lo cual nos permite escribir:
Z máx 3 x1 5 x2
s. a.: 3 x1 2 x2 h1 18
x1 h2 4
x2 h3 6
x1 , x2 , h1 , h2 , h3 0
2. Creamos la tabla símplex:
El segundo renglón contiene la función objetivo, escrita como:
Z máx – 3x1 – 5x2 – 0h1 – 0h2 – 0h3 = 0
183
Unidad 5
A partir del tercer renglón escribimos cada una de las restricciones, en la
columna de las variables básicas colocamos las variables de holgura que
aparecen en las restricciones:
Función objetivo
Primera restricción
Segunda restricción
Tercera restricción
De la tabla símplex inicial, la solución asociada es:
h1 = 18
h2 = 4
h3 = 6
Z=0
Esta solución se obtiene al tomar sólo las columnas asociadas a las
variables básicas y los términos independientes que forman una matriz
identidad aumentada:
184
Investigación de operaciones
3. Observamos que los coeficientes de x1 y x2 en el renglón Z son
negativos. Se tendrá la solución óptima cuando los valores en Z sean
todos positivos.
4. Seleccionamos la columna que tiene como coeficiente a –5, ya que es
el mayor valor negativo. Entrará la variable x2 a formar parte de la base.
5. Realizamos la división de los elementos de la columna solución entre
los elementos de la columna seleccionada y se elige el valor menor.
El menor de los resultados positivos es 6, por lo tanto la variable que sale
es h3.
6. El elemento pivote es 1 por lo tanto su inverso multiplicativo es 1.
Multiplicamos R3 1 y el resultado lo escribimos en una nueva tabla.
7. Ahora se toma el elemento pivote para hacer cero los coeficientes de su
misma columna. Empezamos con R0. El coeficiente de este renglón en la
columna seleccionada es –5, por lo tanto su inverso aditivo es 5, entonces
multiplicamos R3 (actual) por 5 y el resultado se lo sumamos a R0.
185
Unidad 5
Este resultado lo escribimos en la nueva tabla.
Continuamos con el renglón R1, el cual tiene como coeficiente 2, su
inverso aditivo es –2. Multiplicamos R3 por –2 y el resultado se lo
sumamos a R1.
Este resultado lo escribimos en la nueva tabla.
Como R2 ya tiene como coeficiente cero en la columna seleccionada,
simplemente se transcribe a la nueva tabla:
8. Ésta es la tabla símplex que se obtiene después de una iteración. La
solución asociada a esta tabla es:
h1 = 6
h2 = 4
x2 = 6
Z = 30
186
Investigación de operaciones
Regresamos al punto 1.
3. El coeficiente asociado a la columna de x1 es negativo, por lo tanto la
solución actual no es óptima y pasamos al punto 2.
4. La columna de x1 es la única con coeficiente negativo en R0, por lo
tanto, ésta es la variable que pasará a formar parte de la base.
5. Realizamos la división de los elementos de la columna solución entre
los elementos de la columna seleccionada.
El menor de los resultados positivos es 2, por lo tanto la variable que sale
es h1.
6. El elemento pivote es 3, para convertirlo en 1 multiplicamos por su
inverso multiplicativo que es 1/3. Multiplicamos R1 (1/3) y el resultado lo
escribimos en una nueva tabla:
7. Usamos el elemento pivote 1 para hacer cero los coeficientes que están
arriba y debajo de él. Empezamos con R0. El coeficiente de este renglón en
la columna seleccionada es –3, por lo tanto su inverso aditivo es 3, entonces
multiplicamos R1 (actual) por 3 y el resultado se lo sumamos a R0.
187
Unidad 5
Este resultado lo escribimos en la nueva tabla.
Continuamos con el renglón R2, el cual tiene como coeficiente 1, su inverso
aditivo es –1. Multiplicamos R1 por –1 y el resultado se lo sumamos a R2.
Este resultado lo escribimos en la nueva tabla:
Como R3 ya tiene como coeficiente cero en la columna seleccionada,
simplemente se transcribe a la nueva tabla.
8. Esta es la tabla símplex que se obtiene después de la segunda iteración.
La solución asociada a esta tabla es:
x1 = 2, h2 = 2, x2 = 6, Z = 36, h1 = h3 = 0 (por tener valores múltiples).
188
Investigación de operaciones
Regresamos al punto 1.
Como todos los coeficientes del renglón R0 son positivos, entonces hemos
llegado a la solución óptima del problema donde el valor de z máxima es 36.
Ejercicio 1
Selecciona la respuesta que completa de manera correcta los siguientes
enunciados:
1. Para poder convertir una desigualdad de la forma menor o igual que
en una igualdad, se debe sumar una variable de:
a) Superávit.
b) Holgura.
c) Complementaria.
d) Global.
2. La solución del método símplex es óptima si todos los coeficientes del
renglón asociado con la función objetivo en la tabla símplex son:
a) Cero.
b) Negativos.
c) Positivos.
d) Mayores o iguales a cero.
3. La variable que entra a formar parte de la base es la que en el renglón
asociado con la función objetivo en la tabla símplex tiene el coeficiente:
a) Positivo.
b) Cero.
c) Menor negativo.
d) Mayor negativo.
4. Para hacer 1 el elemento pivote, multiplicamos por:
a) Su inverso aditivo.
b) El elemento neutro.
c) El mismo.
d) Su inverso multiplicativo.
189
Unidad 5
5. Los elementos que están arriba y abajo del elemento pivote deben
convertirse en:
a) Positivos.
b) Negativos.
c) Cero.
d) Uno.
6. Resolver por método símplex el siguiente modelo de P. L.
Z m á x 5 x1 4 x2
s. a.: 6 x1 4 x2 24
x1 2 x2 6
x2 2
x1 , x2 0
5.2. Soluciones básicas factibles
La forma de trabajar del método símplex puede variar en relación con
otras lecturas del área, pero los resultados de optimización tendrán que
ser siempre iguales para un mismo problema sin importar el método.
En este libro tratamos que la enseñanza del algoritmo símplex sea lo más
natural posible, partiendo desde la elaboración de la tabla inicial hasta
la localización de las variables básicas entrantes y salientes, así como la
interpretación de los resultados de la última tabla.
En la sección anterior aprendimos el algoritmo del método símplex, el
cual es una herramienta poderosa para resolver modelos de programación
lineal. En esta sección explicamos cómo es que este método encuentra la
solución óptima.
Lo primero es escribir las restricciones del modelo en forma de
igualdades (sumamos las variables de holgura). Esto se hace porque la
solución del modelo (si es que existe) siempre está en un vértice del
polígono de soluciones factibles, el cual se forma como la intersección
de n restricciones (n es el número de variables del modelo).
190
