3.

EL MÉTODO SIMPLEX

3.1 DESARROLLO ANALÍTICO

El método Simplex es un procedimiento iterativo que partiendo de un punto extremo se va
moviendo sucesivamente hacia otros puntos extremos, mejorando en cada uno de ellos el valor
de la función objetivo (o en el peor de los casos, manteniéndolo), hasta llegar al óptimo o a la
conclusión que la solución no está acotada.
Tal desplazamiento se hace siempre a través de los lados del polígono o de las aristas del
poliedro (es decir, entre vértices adyacentes) en base a la verificación de dos condiciones
fundamentales:
 La condición de factibilidad, que garantiza que partiendo de una solución básica
factible sólo serán generadas sucesivas soluciones básicas factibles.
 La condición de optimización, que permite reconocer cuándo se ha llegado al óptimo y
asegura que cada nueva solución generada no empeorará el actual valor de la función
objetivo.
En la siguiente exposición sobre los fundamentos del método se supondrá que las soluciones
básicas factibles son no degeneradas (hipótesis de no degeneración). No obstante, como
veremos, la no verificación de esta hipótesis no altera la validez de las conclusiones.
Consideremos un programa lineal en su forma estándar
Max z  cx
s. a
Ax  b
x0
donde A es de orden m x n, con m < n, y rango máximo (igual a m). Sean Aj con j = 1, 2, …, n,
los vectores columna de A. Supongamos, sin pérdida de generalidad, que los m primeros de tales
vectores son linealmente independientes, es decir constituyen una base que denominaremos con
B (siendo B una matriz cuadrada de orden m).
De esta forma, cualquier Aj no perteneciente a la base puede escribirse como combinación
lineal de los vectores de B:
A j  y1 j A1  y 2 j A 2  ...  y mj A m (3-1)
Aj  B; Ai  B, yij  , i = 1, 2, …, m. Designando con Yj al vector cuyas componentes son (y1j,
y2j, …, ymj)T, la ecuación anterior se traduce a
A j  BYj
puesto que B tiene inversa, resulta
Y j  B 1A j
Conocer el vector Yj nos permite expresar Aj como combinación lineal de los vectores de B.
Notemos que el subíndice j se refiere al vector Aj y el subíndice i se refiere al subíndice del
vector básico al cual multiplica yij en (3-1).

45
Capítulo 3

Sabemos que el sistema Ax = b puede expresarse en términos de la base B como7

Bx B  Nx N  b
y que B determina una solución básica dada por
x B  B 1b
entendiéndose implícitamente que las n – m variables no básicas que constituyen el vector xN son
nulas.
Supongamos que las m variables básicas de xB son estrictamente positivas, es decir
x  (x1 , x 2 , ..., x r , ..., x m , 0, ..., 0)T es una solución básica factible no degenerada, luego
x 1A1  x 2 A 2  ...  x r A r  ...  x m A m  b (3-2)
y el valor de la función objetivo calculada en este punto será z  cx  c B x B  c N x N  c B x B  z 0
donde cB es el vector de los coeficientes económicos que acompañan a las variables básicas y cN
el correspondiente a las no básicas.
Si el punto extremo x no es óptimo, nos moveremos a un punto extremo adyacente con el
objeto de mejorar el valor de z.8 Tal movimiento se realiza cambiando un vector de la base; para
ello removemos una columna de B y la reemplazamos por algún vector de N (matriz
correspondiente a la “no base”).

LA CONDICIÓN DE FACTIBILIDAD
Si a (3-2) le restamos (3-1) multiplicada por j  0 obtenemos
( x 1   j y1 j )A1  ( x 2   j y 2 j )A 2  ...  ( x r   j y rj )A r  ...  ( x m   j y mj )A m   j A j  b (3-3)

consecuentemente los valores (x1  θ j y1j ), (x 2  θ j y 2j ), ..., (x r  θ j y rj ), ..., (x m  θ j y mj ), θ j con el

agregado de n – m – 1 ceros, constituyen una solución del sistema Ax = b. Si además todas sus
componentes son no negativas, es una solución posible.
Si j = 0, la nueva solución coincide con la anterior. Ahora bien, como el número máximo
de vectores linealmente independientes es m, para que este punto sea un punto extremo debemos
conseguir que alguna de las (xi – jyij) se anule y que las restantes sigan siendo no negativas. Esto
se logra haciendo
x 
θ j  min  i , con yij  0, i  1, 2, ..., m (3-4)
 y ij 
Supongamos que al menos uno de los yij es mayor que cero y que el mínimo se produce para
i = r, o sea j = xr/yrj, entonces la nueva solución resultará
y ij
x i'  x i   j y ij  x i  x r para todo i  r, i  1, 2, ..., m
y rj
y rj x
x 'r  x i   j y rj  x r  x r  0; x 'j   j  r ; 0 para las restantes n - m variables
y rj y rj

7
Véase Definición 2-21 en Capítulo 2.
8
Para cualquier programa lineal con m restricciones, dos soluciones básicas factibles se dicen adyacentes si sus
respectivas variables básicas tienen m – 1 variables en común.

46 Norma Torrent
 El Método Simplex

que es a su vez, una solución básica factible puesto que satisface el sistema Ax = b
m y ij xr
 (x
i 1
i  xr
y rj
)A i 
y rj
A j  b (y rj  0)
ir

Se dice entonces, que el vector Aj ingresa a la base y sale Ar. La variable xr es ahora no
básica (xr = 0) y xj pasa a ser básica con valor j = xr/yrj.
Observemos que todo Aj  B puede reemplazar a cualquier vector Ar de la base para el cual
yrj sea distinto de cero, y el nuevo conjunto de vectores seguirá siendo linealmente
independiente.9
La expresión (3-4) recibe el nombre de condición de factibilidad y nos garantiza que cada
nueva solución encontrada será una solución básica factible.
Notemos que:
 Si en la (3-4) ninguno de los yij es mayor que cero, la solución no está acotada, es
decir, el programa lineal no tiene solución óptima finita. En efecto, si yij ≤ 0  i = 1, 2,
…, m los valores (x1  θ j y1j ), (x 2  θ j y 2j ), ..., (x r  θ j y rj ), ..., (x m  θ j y mj ), θ j que
satisfacen (3-3) serán todos estrictamente positivos y pueden crecer tanto como se
desee escogiendo un j lo suficientemente grande.
 Puede haber dos o más columnas de B para las cuales se tiene el mismo valor mínimo
dado por (3-4) en cuyo caso, la nueva solución básica factible será degenerada. Por
ejemplo, si en (3-4) el mínimo se produce para xr/yrj = xt/ytj podremos optar por
remover la columna Ar o la At de la base actual. Si decidimos que Ar abandone la base,
At integrará la nueva base siendo la variable básica xt igual a cero.
 En estos casos si bien resulta indistinta la elección del vector que abandonará la base,
convendremos en hacer salir al de mayor índice.

LA CONDICIÓN DE OPTIMIZACIÓN
Pretendemos ahora que cada nueva solución básica encontrada por el procedimiento anterior sea
capaz de mejorar el valor de la función objetivo o, de no ser posible, mantenerlo.
El valor de la función económica para la nueva solución obtenida mediante (3-4) es
m
yij x y rj
z  ci (xi  x r )  c j r . En esta sumatoria podemos incluir el término c r (x r  x r ) ya
i 1 y rj y rj y rj
ir

y rj
que al ser nulo el valor de x r  x r , el valor de z no se altera. De este modo,
y rj
m
y ij x
z  c (x i i  xr )  cj r
i 1 y rj y rj
desarrollando y agrupando términos
m m
x x
z ci x i  c j r  r c y i ij
i 1 y rj y rj i 1

9
Véase Teorema 2-3 en Capítulo 2.

47
Capítulo 3

m
Denominando con zj a c y
i 1
i ij y teniendo en cuenta que el valor de z para la solución

m
básica inicial correspondiente a (3-2) es z 0   c x , la expresión anterior se traduce a
i 1
i i

xr
z  z0  (c j  z j )  z 0   j (c j  z j ) (3-5)
y rj
Lo cual nos indica que el nuevo valor de la función objetivo es el valor original más la
cantidad θ j (c j  z j ) .
Dado que θ j  0, si c j  z j  0 resultará z > z0 siendo la nueva solución mejor que la
anterior. Lógicamente, si hubiese dos o más vectores no básicos para los cuales
c j  z j  0, debería ingresar a la base aquél al que corresponda el mayor valor de θ j (c j  z j ) .
Sin embargo, este último cálculo nos obligaría a determinar θ j para todos los vectores no básicos
con c j  z j  0 optándose, a efectos de simplificar la tarea, por ingresar a la base al vector que
posea el mayor valor positivo de los c j  z j . Si este último valor se da para más de un vector
puede escogerse indistintamente a cualquiera de ellos como integrante de la nueva base. No
obstante, se conviene en hacer entrar al de menor subíndice.
En base a lo expuesto, dada una solución básica factible, siempre que haya un vector Aj no
básico con c j  z j  0 y al menos un yij > 0 con i = 1, 2, …, m, existe otro punto extremo para el
cual el valor de la función objetivo es la menos tan grande como el valor anterior (z ≥ z0).
De esta forma el nuevo punto extremo puede ser usado como solución básica original,
repitiendo el procedimiento hasta que la solución no pueda mejorarse más, o sea hasta que
c j  z j  0  Aj con j = 1, 2, …, n.
Cuando una solución es degenerada y escogemos un vector Aj para el cual c j  z j  0 y al
menos un yij > 0 , podemos tener o no un aumento en z.
En efecto, al examinar (3-4), j = xr/yrj será igual a cero sólo si xr tiene valor nulo, es decir,
si la solución básica original es degenerada. En este caso, la nueva solución básica factible
también será degenerada y los valores de las variables comunes a ambas soluciones no
cambian ( xi'  xi  θ j yij  xi para todo i  r, x'j  θ j  x r /y rj  0 ) . Sin embargo, no se puede
decir que la nueva solución básica siempre será degenerada si la actual lo es. Si yij ≤ 0 para cada
xi igual a cero en la solución actual, ninguna de tales variables es considerada en el cálculo de (3 -
4), el valor de j será entonces positivo y la nueva solución resultará no degenerada.
En cualquier caso, cuando (c j  z j )  0 , estamos seguros que z no es menor que z0.
La pregunta que surge ahora es ¿si c j  z j  0  Aj, significa que alcanzamos el óptimo? Es
fácil demostrar que, efectivamente, cuando se verifica dicha condición la función objetivo
alcanza su valor máximo.
Supongamos que para el sistema Ax = b tenemos una base B y una solución básica factible
x B  B 1b ; que el valor de la función objetivo para esta solución es z0 y que c j  z j  0  Aj
con j = 1, 2, …, n.
Sea x’ cualquier solución factible y z el correspondiente valor de la función objetivo. Para x’
se verifica
x 1' A1  x '2 A 2  ...  x 'n A n  b 3-6

48 Norma Torrent
 El Método Simplex

Sabemos que todo vector Aj de A puede expresarse como combinación lineal de B en la

forma A j  BY j  
yij Ai , siendo IB el conjunto de subíndices de los vectores de B.
iI B
Evidentemente, para un Aj básico yij será igual a uno si i =j e igual a cero si i  j.
Sustituyendo en (3-6) obtenemos
n    n 
x1'  yi1A i  x '2  yi2 A i  ...  x 'n  yin A i    x 'j  yijA i   
 x y ' 
j ij A i b
   
iI B iI B iI B j1  iI B  iI B  j1 
Comparando el último término con el que se obtiene al aplicar la solución básica factible x
n
al sistema, es decir x
j 1
j Aj  x A
iI B
i i  b, resulta inmediato que

n
xi  x yj1
'
j ij para todo i  I B (3-7)

n
Ahora bien, para x’ el valor de la función objetivo es z  c
j 1
'
jxj y, por hipótesis

n n
c j  z j  0  Aj con j = 1, 2, …, n, o sea c j  z j  j, luego z  
j 1
c j x'j  z
j 1
'
jxj. Si en esta

última expresión reemplazamos z j por c y

iI B
i ij vemos que

n   n
z  x 'j  c i y ij  
 ci  x y '
j ij
 
j1  iIB  iIB j1

y sustituyendo (3-7)
z c x
iI B
i i  z0

Esto demuestra que si se satisface la condición c j  z j  0  Aj, entonces x es la solución

óptima sin tener en cuenta si es o no degenerada. Tal condición recibe el nombre de condición
de optimización.10
En síntesis, dada una solución básica factible:
 Si c j  z j  0  Aj, estamos en el óptimo.
 Si c j  z j  0 para algún Aj y el vector Yj contiene al menos alguna componente
positiva, generamos una nueva solución básica.
 Si c j  z j  0 para algún Aj y el vector Yj no contiene ninguna componente positiva,
concluimos con una solución no acotada.
Para problemas de minimización tendremos que tener en cuenta que se ha alcan zado el
óptimo cuando c j  z j  0  Aj, los restantes pasos son idénticos.

10
Observemos que la expresión 3-5 puede también escribirse como z = z0 – j(zj – cj). De esta forma la condición de
optimización se traduciría a zj – cj ≥ 0  Aj (caso de maximización).

49
Capítulo 3

CONVERGENCIA FINITA DEL MÉTODO EN AUSENCIA DE DEGENERACIÓN

En ausencia de degeneración la diferencia entre la función objetivo de la solución básica factible
inmediata anterior y la actual es x j (c j  z j )  0 . De esta forma, z crece estrictamente en cada
nuevo punto extremo generado y, puesto que hay sólo un número finito de puntos extremos, el
método terminará en un número limitado de pasos (generalmente la cantidad de iteraciones
oscila entre una y dos veces el número de restricciones). Concretamente, el supuesto de no
degeneración garantiza la convergencia de las soluciones hacia un óptimo o una solución no
acotada.
Como se discutiera en párrafos previos, cuando la degeneración se presenta no estamos
seguros de que el ingreso a la base de un nuevo vector Aj con (c j  z j )  0 mejore el actual valor
de z, dado que puede ocurrir que la nueva solución sea también degenerada, en cuyo caso el
valor de la función objetivo permanecerá inalterado, o bien, la nueva solución puede resultar no
degenerada con la consiguiente mejora de z.
Si la nueva solución es degenerada, al no modificarse el valor de la función objetivo una de
las bases puede repetirse lo cual significa que no tendremos la certeza de que la condición de
optimización se alcance en un número finito de pasos. Es más, podemos entrar en un loop
infinito, repitiéndose la misma sucesión de bases, sin cambiar el valor de z, por lo cual el
programa se denomina cíclico.
Existen procedimientos específicos para evitar la degeneración. 11 Sin embargo es de
destacar, que la mayoría de las aplicaciones reales que presentan soluciones degeneradas
convergen al óptimo. En general el fenómeno cíclico no se observa en la práctica, los programas
cíclicos se construyen intencionalmente a los efectos de evidenciar la posibilidad algebraica de
su existencia.

3.2 ALGORITMO DEL SIMPLEX

Para resolver un programa lineal mediante el método Simplex los pasos a seguir son:
1. Se expresa el problema en su forma estándar, se busca una solución básica factible
inicial y se obtiene z = cx.
2. Se calculan los coeficientes yij que permiten expresar a los vectores no básicos como
combinación lineal de los básicos.
 Designando con IN al conjunto de subíndices de los vectores de N y con Y a la matriz
compuesta por los vectores Yj con j  IN, resulta Y  B 1 N .
3. Se determinan los z j   ci yij  j  IN.
iI B
4. Se calculan las diferencias c j  z j  j  IN.
 Si c j  z j  0  j  IN (caso de maximización), la solución actual es la óptima.
Notemos que los c j  z j correspondientes a los vectores básicos serán siempre nulos,
por lo tanto c j  z j  0  j  IN  c j  z j  0  j.
 Si c j  z j  0 para algún Aj con j  IN y el vector Yj no contiene ninguna componente
positiva, concluimos que la solución no está acotada.

11
Tales procedimientos no serán objeto de nuestro estudio. Puede obtenerse información detallada de los mismos en
Bazaraa, M. S., J. J. Jarvis y H. D. Sherali, Linear Programming and Network Flows, 2ª ed., New York: John Wiley
& Sons, Inc., 1990.

50 Norma Torrent
 El Método Simplex

 Si c j  z j  0 para algún Aj con j  IN y el vector Yj contiene al menos alguna

componente positiva, Aj debe ingresar a la base. Si c j  z j  0 para más de un Aj, entra
a la base el que haga máxima la diferencia c j  z j ; en caso de empate convendremos
en escoger el Aj de menor subíndice.
5. Se determina el vector que sale de la base.
 Si ingresa Aj, saldrá el vector Ar para el cual resulte
x  x
 θ j  min  i , con yij  0, i  I B   r
 y ij  y rj
 Si el mínimo se da para más de un Ai convendremos en hacer salir al de mayor
subíndice.
6. Se obtiene la nueva solución,
y ij
 x i'  x i   j y ij  x i  x r para todo i  r, con i  I B
y rj
y rj x
 x 'r  x i   j y rj  x r  x r  0; x 'j   j  r ; 0 para las restantes n - m variables
y rj y rj
 Se calcula el z asociado y se vuelve al punto 2.

Ejemplo 3-1 Algoritmo del Simplex

Resolveremos el Ejemplo 3-1 mediante el algoritmo.
1. Se busca una solución básica inicial.
Max z  20 x1  45x 2  0x 3  0x 4  0x 5
s. a
x1  2x 2  x 3  40
3x1  1,5x 2  x4  75
x2  x 5  15
x j  0 j  1; 2; ...; 5

 1 0 0 1 2
B  A 3 , A 4 , A 5    0 1 0 ; N  A1 , A 2    3 3 / 2 
 0 0 1 0 1
  
x B  x 3 , x 4 , x 5 T  40; 75; 15T ; x N  x 1 , x 2 T  0; 0T
z  c B x B  0; 0; 040; 75; 15T  0
2. Se calculan los yij.
 1 0 0
B 1   0 1 0 
 0 0 1
 
1 2   y 31 y 32 
Y  B N   3 3 / 2    y 41 y 42 

1
0 1  y 51 y 52 


51
Capítulo 3

3. Se determinan los zj.

z1  c y i i1  c 3 y 31  c 4 y 41  c 5 y 51  0 1 2
iI B
o bien, z1 , z 2   c B Y  0; 0; 0  3 3 / 2   0; 0
z2  c y i i2  c 3 y 32  c 4 y 42  c 5 y 52 0 0 1
iI B


4. Se calculan las diferencias c j  z j .

c1  z1  20  0  20
c 2  z 2  45  0  45  entra A 2
5. Se determina el vector que sale.
x  x x x   40 75 15 
θ 2  min  i , con y i2  0  min  3 , 4 , 5   min  ; ;   15  sale A 5
i
 y i2   y 32 y 42 y 52   2 3/ 2 1 
6. Se calcula la nueva solución, el z asociado y se vuelve al punto 2.
3
x '2  θ 2  15; x 3'  x 3  θ 2 y 32  40  15  2  10; x '4  x 4  θ 2 y 42  75  15  105 / 2
2
x 1'  x 1  0; x 5'  x 5  θ 2 y 52  15  15  1  0
T T T T
x B  x 2 , x 3 , x 4   15; 10; 105/2  ; x N  x 1 , x 5   0; 0 
z  c B x B  45; 0; 0 15; 10; 105/2 T  675

 2 1 0  1 0
B  A 2 , A 3 , A 4    3/2 0 1; N  A1 , A 5    3 0 
 1 0 0  0 1
   
Primera iteración
2. Se calculan los yij.
0 0 1
B 1 
 1 0  2 
0 1  3 / 2
 
0 0 1 1 0   0 1  y 21 y 25 
Y  B 1 N   1 0  2  3 0    1  2    y 31 y 35 
 0 1  3 / 2  0 1  3  3 / 2   y 
      41 y 45 
3. Se determinan los zj.
0 1
z1 , z 5   c B Y  45; 0; 0  1  2   0; 45

 3  3 / 2
 
4. Se calculan las diferencias c j  z j .
c1  z1  20  0  20  entra A1
c 5  z 5  0  45  45

52 Norma Torrent
 El Método Simplex

5. Se determina el vector que sale.

x x  10 105 / 2 
θ1  min  3 , 4   min  ;   10  sale A 3 (observemos que y21 = 0)
 y 31 y 41  1 3 
6. Se calcula la nueva solución, el z asociado y se vuelve al punto 2.
x 1'  θ1  10; x '2  x 2  θ1 y 21  15  10  0  15; x '4  x 4  θ1 y 41  105 / 2  10  3  45 / 2
x 3'  x 3  θ1 y 31  10  10  1  0; x 5'  0
T T T T
x B  x 1 , x 2 , x 4   10; 15; 45/2  ; x N  x 3 , x 5   0; 0 
z  c B x B  20; 45; 0 10; 15; 45/2 T  875

1 2 0  1 0
B  A1 , A 2 , A 4    3 3/2 1; N  A 3 , A 5    0 0 

0 1 0   0 1
  
Segunda iteración
2. Se calculan los yij.
 1 0  2
B 1   0 0 1
  3 1 9 / 2
 
 1 0  2  1 0   1  2   y13 y15 
Y  B N   0 0
1
1 0 0    0 1   y 23 y 25 
  3 1 9 / 2  0 1   3 9 / 2   y 
      43 y 45 
3. Se determinan los zj.
 1  2
z 3 , z 5   c B Y  20; 45; 0  0 1  20; 5
  3 9 / 2
 
4. Se calculan las diferencias c j  z j .
c 3  z 3  0  20  20
c 5  z 5  0  5  5
Puesto que se verifica la condición de optimización , resulta
x 1*  10; x 2 *  15; x 3*  0; x 4 *  22,5; x 5 *  0; z *  875

3.3 EL MÉTODO SIMPLEX EN FORMATO TABLA

La tabla Simplex es una representación compacta y ordenada de la información disponible, que
facilita la sistematización de los cálculos correspondientes a cada iteración.
Existen distintos formatos de tablas siendo todos ellos variantes muy similares, aceptados y
utilizados en la práctica. Adoptaremos el que se describe a continuación y explicaremos su
funcionamiento basándonos en el Ejemplo 3-1.

53
Capítulo 3

Max z  20 x 1  45x 2  0x 3  0x 4  0x 5
s. a
x 1  2x 2  x 3  40
3x 1  1,5x 2  x4  75
x2  x 5  15
x j  0 j  1; 2; ...; 5
Tabla 3-1
20 45 0 0 0 xi/yij
ci Ai A1 A2 A3 A4 A5 xi (yij>0)
0 A3 1 2 1 0 0 40 20
0 A4 3 3/2 0 1 0 75 50
0 A5 0 1 0 0 1 15 15
zj 0 0 0 0 0
z=0
cj – zj 20 45 0 0 0

Inicialmente la tabla presenta, en su cuerpo central, los coeficientes del sistema Ax = b para
la solución básica factible original. En correspondencia con dicho sistema, se adicionan:
 En fila 1, los coeficientes de la función objetivo.
 En fila 2, los rótulos de los vectores que integran la matriz A.
 En columna 1, los coeficientes económicos de las variables básicas.
 En columna 2, los rótulos de los vectores básicos.
Observemos que comenzando con una base igual a la matriz identidad , xB es coincidente
con b (penúltima columna de la tabla).
Los restantes valores se calculan a partir de los existentes:
 En la celda inferior derecha se coloca el valor actual de la función objetivo.
 z 
ci xi se obtiene sumando los productos de los coeficientes de la columna 1 por
iI B
los respectivos valores de las variables básicas en la penúltima columna. En este primer
paso, z = 0.
 Las últimas dos filas contendrán los coeficientes zj y cj – zj que nos permitirán la
verificación de la condición de optimización.
 Los z j  
ci yij resultan de efectuar la suma de los productos de los coeficientes de la
iI B
columna 1 por las respectivas componentes de cada columna Aj (notemos que al ser B
= I es Y = N). Luego, restando cada zj al correspondiente cj ubicado en fila 1 tendremos
los valores cj – zj.
 La Tabla 3-1 nos indica que debe ingresar a la base el vector A2.
 La última columna está destinada a la obtención de los cocientes xi/yij que posibilitarán
la determinación del vector que sale de la base (condición de factibilidad).
 Dividimos cada xi de la penúltima columna por el correspondiente yij > 0 en la columna
del vector que entra a la base (en este caso A2). Seleccionando el mínimo de tales
cocientes, en la última columna, sabremos cuál es el vector saliente.
 En Tabla 3-1 vemos que sale A5.

54 Norma Torrent
 El Método Simplex

Primera iteración
La sencillez de los cálculos precedentes reside en la base inicial igual a la matriz identidad.
Como expresáramos anteriormente, al ser B = I resulta Y = N.
La nueva base estará ahora constituida por los vectores A2, A3 y A4. Si lográramos convertir
esta base en una matriz identidad, el proceso de cálculo sería idéntico al descrito. Para ello
bastará con transformar el sistema de ecuaciones de Tabla 3 -1 en un sistema equivalente que
0 
 
contenga  0  en A2. Utilizaremos el método de eliminación de Gauss–Jordan.12
 1
 
En la intersección de la columna del vector que entra a la base con la fila del vector que
sale, se encuentra el elemento pivote (el que queremos que asuma el valor 1). Si entra Ak y sale
Ar, el pivote será yrk. Luego:
 Dividimos la ecuación “r” por yrk.
 Para i = 1, 2, …, m, con i  r , actualizamos la i–ésima ecuación sumándole –yik veces la
nueva r–ésima ecuación.
En nuestro ejemplo el pivote es y52 = 1, por tanto la tercera ecuación de la Tabla 3-2 será
idéntica a la tercera ecuación de la Tabla 3-1. Luego,
 A la primera ecuación de Tabla 3-1 le restamos la tercera ecuación de Tabla 3-2
multiplicada por 2.
 A la segunda ecuación de Tabla 3-1 le restamos la tercera ecuación de Tabla 3-2
multiplicada por 1,5.
Actualizamos la Tabla 3-2 con los rótulos correspondientes a los vectores básicos (A2
sustituye a A5) y los respectivos coeficientes económicos de las variables básicas (c2 sustituye a
c5), y efectuamos los restantes cálculos.
Tabla 3-2
20 45 0 0 0 xi/yij
ci Ai A1 A2 A3 A4 A5 xi (yij>0)
0 A3 1 0 1 0 –2 10 10
0 A4 3 0 0 1 –3/2 105/2 35/2
45 A2 0 1 0 0 1 15
zj 0 45 0 0 45
z = 675
cj – zj 20 0 0 0 –45
En la Tabla 3-2 vemos que entra A1 y sale A3. Los cálculos necesarios para la
transformación del sistema de ecuaciones de la Tabla 3-1 al equivalente de la Tabla 3-2 pueden
simplificarse aún más procediendo como se indica a continuación.
 En una tabla cualquiera identificamos el elemento pivote. Si entra Ak y sale Ar, el pivote será
yrk. Dividimos la fila (ecuación) asociada a Ar por yrk y completamos los restantes ceros
correspondientes al vector Ak. Los demás valores de la nueva tabla se obtienen operando
directamente sobre la tabla anterior, aplicando la siguiente regla práctica.
 Para obtener el valor de un yij de la nueva tabla trazamos, en la tabla anterior, un rectángulo
que tenga por vértices los coeficientes yij, yrk (elemento pivote, en el vértice opuesto por la
diagonal), yik e yrj (Figura 3-1).

12
Véase Ejemplo 2-1 en Capítulo 2.

55
Capítulo 3

 El valor buscado será entonces igual al valor anterior menos el producto de los vértices en
y
la diagonal opuesta al pivote dividido el pivote. Es decir, yij'  yij  ik y rj .
y rk
Figura 3-1

y 'ij

y 'ij  y ij  y ik y rj
y rk

Así por ejemplo, el valor del coeficiente y31 en la Tabla 3-2 será igual a
y 2 y 1,5
y '31  y 31  32 y 51  1  0  1 . En forma similar, y '45  y 45  42 y 55  0  1  1,5 .
y 52 1 y 52 1
El procedimiento precedente se basa en las denominadas fórmulas de cambio de base que
se desarrollan a continuación.
En una iteración dada cualquier vector no básico puede escribirse como A j  yij Ai . Si 
iI B
en dicha iteración hemos determinado que entra Ak y sale Ar, Ak verificará la relación
Ak   yik Ai  y rk Ar . Luego, dado que yrk > 0, resulta
iI B
ir

1 y ik
Ar 
y rk
Ak  
iI B y rk
Ai (3-8)
ir
con lo cual se tienen los yir que permiten expresar al vector Ar en función de la nueva base.
Ahora, si queremos representar Aj en términos de la nueva base, bastará con reemplazar el vector
Ar por su equivalente expresión. En efecto,
 
 1 y ik 
Aj  
iI B
y ij A i  
iI B
y ij A i  y rj A r 
iI B

y ij A i  y rj 
 y rk
Ak  
iI B y rk
Ai 

ir ir  ir 

 y ik  y rj
Aj    y ij - y rj A i  Ak (3-9)
iI B y rk  y rk
ir

Las fórmulas 3-8 y 3-9 demuestran la validez del procedimiento aplicado.

Observemos que la regla práctica se utiliza también para calcular los nuevos valores de las
variables básicas puesto que,
y x
x i'  x i  x r ik para todo i  I B con i  k ; x 'k  r
y rk y rk
56 Norma Torrent
 El Método Simplex

Análogamente, dicha regla puede emplearse para valuar los nuevos cj – zj. En efecto, en la
próxima tabla, para todo Aj no básico resultará
   
    y ik  y rj


 iIB 

(c j  z j ) '  c j   c i y ij'  c k y 'kj   c j   c i  y ij - y rj
 iIB  y rk 
  c k 
y rk 

 ik   ik 
 
 y rj y rj   y rj 

 c j   c i y ij 
 iIB y rk iIB c i y ik  c k   c j   z j 
y rk   y rk
(c k  z k ) 


 i  k i  k 
por lo cual se verifica
y rj
(c j  z j ) '  (c j  z j )  (c k  z k ) para todo j  I N
y rk
Segunda iteración
A partir de la Tabla 3-2, repitiendo los pasos descritos, obtenemos la Tabla 3-3. La misma
corresponde a la solución óptima ya que c j  z j  0  Aj.
Tabla 3-3
20 45 0 0 0 xi/yij
ci Ai A1 A2 A3 A4 A5 xi (yij>0)
20 A1 1 0 1 0 –2 10
0 A4 0 0 –3 1 9/2 45/2
45 A2 0 1 0 0 1 15
zj 20 45 20 0 5
z = 875
cj – zj 0 0 –20 0 –5

¿CÓMO IDENTIFICAR B-1 EN UNA TABLA SIMPLEX?

Teniendo en cuenta el método para obtener la inversa de una matriz descrito en el Ejemplo 2 -2
del Capítulo 2 y observando que el proceso de transformar la base de las sucesivas tablas en una
matriz identidad es equivalente a premultiplicar dicha base por B-1 en la tabla inicial, resulta
evidente que: la inversa de la base aparecerá siempre en todas las tablas debajo de las variables
que se toman como base inicial.
 1 0  2
Así por ejemplo, de Tabla 3-2  A3 , A4 , A2    0 1  3/2  y, de Tabla 3-3
1
0 0 1 

 1 0  2
 A1 , A4 , A2     3 1 9 /2  .
1
 0 0 1 


3.4 COEFICIENTES DE SUSTITUCIÓN Y COSTOS REDUCIDOS

Para cualquier solución básica factible las variables básicas pueden representarse en términos de
las no básicas como se indica a continuación.
Bx B  Nx N  b

57
Capítulo 3

x B  B 1b  B 1 Nx N
 B 1b  Yx N
 B 1b  
Yj x j
jI N

De esta forma, la variación que sufrirán las variables básicas frente al ingreso de una
x B
variable no básica cualquiera xj estará dada por  Y j . Concretamente, si las m variables
x j
básicas de xB son x1, x2, …, xm, el ratio esperado de cambio de cada una de ellas cuando la
x1 x x
variable no básica xj se incrementa en una unidad será   y1j , 2   y 2j , ..., m   y mj .
x j x j x j
Los yij que componen el cuerpo de la tabla se denominan tasas marginales (o coeficientes) de
sustitución.13
Si xj ingresa a la base el nuevo valor de la función objetivo estará dado por
z  z 0  x j (c j  z j )
luego, la variación en z frente a incrementos unitarios en la variable xj será
z
 cj  zj
x j

Los valores cj – zj correspondiente a las variables no básicas reciben el nombre de costos

reducidos.
Para ejemplificar los conceptos precedentes volvamos a la Tabla 3 -2. La columna A1 nos
dice que por cada vasija que se fabrique x3 y x4 disminuirán en 1 y 3 unidades respectivamente,
en tanto que x2 no experimentará variación alguna (una unidad de x1 sustituye a 1 unidad de x3, 3
de x4 y 0 de x2). A su vez,
si x1 se incrementa en 1 unidad, z se incrementa en $20 pero:
x3 disminuye en 1 unidad  z disminuye en $0∙1 = $0
x4 disminuye en 3 unidades  z disminuye en $0∙3 = $0
x2 disminuye en 0 unidades  z disminuye en $45∙0 = $0
en consecuencia, por cada vasija que se fabrique el incremento efectivo en z será
z  c1  c y
iI B
i i1  20  0  $20

Un razonamiento similar sobre la columna A5 de la Tabla 3-3 nos permitiría concluir que
por cada unidad de x5 que ingrese a la base z* disminuirá en $5.

3.5 LAS VARIABLES FICTICIAS

Hemos visto que el punto de partida para la aplicación del Simplex es una solución básica
factible. Sin duda, la mejor base inicial es la matriz identidad.

13
Si la tabla corresponde a una solución básica factible degenerada, cuando alguna de las variables no básicas se
incrementa (manteniendo las restantes variables no básicas a nivel cero), al menos una de las variables básicas puede
asumir valores negativos destruyéndose la factibilidad de la solución. En tal caso los respectivos coeficientes de
sustitución no son practicables puesto que conducirían a soluciones inadmisibles.

58 Norma Torrent
 El Método Simplex

En el ejemplo anterior, dado que el problema original estaba en forma canónica con todos
sus términos independientes no negativos, la conversión a formato estándar (mediante el
agregado de las variables de holgura) nos proporcionó una solución de arranque inmediata con B
= I. No obstante, tal situación no siempre ocurre.
Cuando las restricciones del modelo son ecuaciones o desigualdades de ≥ con términos
independientes no negativos, la determinación de una solución básica inicial deja de ser
inmediata. En estos casos, para obtener una solución básica de arranque con base igual a la
matriz identidad se introducen en el programa lineal las denominadas variables ficticias o
artificiales.
Veamos, en su forma estándar, el programa planteado en el Ejemplo 1-13.
Max z  30 x 1  40 x 2  0 x 3  0 x 4
s. a
x 1  x 2  1x 3  0 x 4  7
x 1  2 x 2  0 x 3  1x 4  4
x 1  0x 2  0x 3  0x 4  5
x j  0 j  1, 2, ..., 4
Como puede apreciarse, no disponemos de una solución básica factible que resulte
inmediata. Agregamos entonces al sistema de restricciones anterior las variables ficticias x5 y x6
de modo que A5 y A6 junto con A3, completen la matriz identidad.
x 1  x 2  1x 3  0 x 4  0x 5  0x 6  7
x 1  2 x 2  0 x 3  1x 4  1x 5  0x 6  4
x 1  0 x 2  0 x 3  0 x 4  0x 5  1x 6  5
x j  0 j  1, 2, ..., 6

Así, tenemos un modelo aumentado que difiere del original en las variables artificiales.
Para el nuevo modelo el punto x = (0; 0; 7; 0; 4; 5)T es una solución básica factible. El
“artificio” de introducir las variables ficticias para generar la solución inicial recibe el nombre de
técnica de la base artificial.
Las variables ficticias carecen de significado físico o real y, lógicamente, si el problema
original tiene solución, en la misma deberán ser nulas.
Para resolver modelos lineales a los cuales se les han adicionado variables ficticias pueden
emplearse dos métodos: el de penalización o el de las dos fases. Ambos utilizan el método
Simplex con algunas variantes en el inicio.
Observación. Es evidente que la base inicial igual a la matriz identidad provista por las
variables de holgura y/o ficticias proporciona una solución muy alejada de la que nos dará el z
óptimo, sin embargo dicha solución tiene la ventaja de permitir sistematizar los cálculos.

EL MÉTODO DE PENALIZACIÓN
Consiste sencillamente en resolver mediante el método Simplex el modelo aumentado,
penalizando en la función objetivo a cada variable ficticia con un coeficiente económico,
generalmente denotado por M, que garantice su nulidad en la solución final.
Si el objetivo es maximizar, dicho coeficiente será igual a –M, en tanto que para
minimización será igual a M. En ambos casos M es positivo y, en concepto, mucho más grande
que el mayor valor absoluto de los coeficientes económicos de las variables reales del modelo.
De esta forma el Simplex, en la búsqueda de mejores soluciones, hará que las variables
ficticias abandonen la base en las sucesivas iteraciones.
59
Capítulo 3

Durante la resolución puede ocurrir que:

 Se verifique la condición de optimización y la base final no esté integrada por ninguna
variable ficticia, en cuyo caso habremos encontrado la solución óptima del problema
original.
 Se verifique la condición de optimización y la base final esté integrada por a lguna o
algunas variables ficticias con valor nulo, en cuyo caso habremos encontrado la
solución óptima del problema original y la misma es una solución degenerada.
 Se verifique la condición de optimización y la base final esté integrada por al menos
una variable ficticia con valor estrictamente positivo, en cuyo caso el problema original
es no factible.
 Se concluye que la solución no está acotada en cuyo caso:
 Si todas las variables ficticias son nulas, la solución del problema original no está
acotada.
 Si al menos una variable ficticia es distinta de cero, el problema original es no factible.

Ejemplo 3-2 Método de penalización

Un criadero de pollos sabe que la ración diaria a suministrar al comedero debe contener, al
menos, 0,8kg de calcio y 22kg de proteínas como mínimo.
Los ingredientes disponibles para preparar dicha ración son: carbonato de calcio ( CO3Ca),
maíz y harina de soja; cuyos costos y contenidos por kilogramo se dan en la siguiente tabla.
Calcio Proteínas Costo
CO3Ca 0,380 0,32
Maíz 0,001 0,09 0,70
Soja 0,002 0,50 1,20
Se desea determinar la ración de costo mínimo.
Formulación del modelo y resolución aplicando el método de penalización.
xj: kg del ingrediente j que componen la ración diaria; j = 1 (CO3Ca), 2 (maíz), 3 (harina de
soja)
Min w  0,32x 1  0,7x 2  1,2x 3
s. a
0,38x 1  0,001x 2  0,002 x 3  0,8
0,09x 2  0,5x 3  22
x1 , x 2 , x 3  0
Min w  0,32x 1  0,7x 2  1,2x 3  0 x 4  0 x 5  Mx 6  Mx 7
s. a
0,38x 1  0,001x 2  0,002 x 3  1x 4  0 x 5  1x 6  0x 7  0,8
0,09x 2  0,5x 3  0 x 4  1x 5  0x 6  1x 7  22
x j  0 j  1, 2, ...,7
0,32 0,7 1,2 0 0 M M
ci Ai A1 A2 A3 A4 A5 A6 A7 xi xi/yij
M A6 0,38 0,001 0,002 –1 0 1 0 0,8 400
M A7 0 0,09 0,5 0 –1 0 1 22 44
zj 0,38M 0,091M 0,502M –M –M M M
0,32– 0,7– 1,2– w = 22,8M
cj – zj M M 0 0
0,38M 0,091M 0,502M

60 Norma Torrent
 El Método Simplex

0,32 0,7 1,2 0 0 M M

ci Ai A1 A2 A3 A4 A5 A6 A7 xi xi/yij
M A6 0,38 0,0006 0 –1 0,004 1 -0,004 0,712 1,874
1,2 A3 0 0,18 1 0 –2 0 2 44
0,216 + –2,4 + 2,4 –
zj 0,38M 1,2 –M M
0,0006M 0,004M 0,004M w = 52,8 +
0,32 – 0,484 – 2,4 – –2,4 + 0,712M
cj – zj 0 M 0
0,38M 0,0006M 0,004M 1,004M

0,32 0,7 1,2 0 0 M M

ci Ai A1 A2 A3 A4 A5 A6 A7 xi xi/yij
0,32 A1 1 0,0015 0 –2,63 0,011 2,63 -0,011 1,874
1,2 A3 0 0,18 1 0 –2 0 2 44
zj 0,32 0,216 1,2 –0,84 –2,4 0,84 2,4
–0,84 –2,4 + w =53,4
cj – zj 0 0,484 0 0,84 2,4
+M M
Al ser cj – zj > 0 para cada variable no básica, esta última tabla nos da la solución óptima.
Notemos que al ser M positivo y muy grande, toda variable ficticia que en una iteración
cualquiera salga de la base no volverá a ingresar nunca más (para dicha variable cj – zj = M – zj >
0). Por tal motivo las variables artificiales pueden eliminarse a medida que abandonan la base, es
decir, no resulta necesaria su inclusión en las subsiguientes iteraciones.

EFECTO ESPEJO
Un detalle importante que se observa en las tres tablas anteriores es que los vectores A4 y A5
correspondientes a las variables de exceso son iguales a los vectores A6 y A7, correspondientes a
las variables artificiales, multiplicados por –1, ocurriendo lo mismo con sus respectivos zj. Esta
característica se denomina efecto espejo y se presenta en los modelos siempre que se adicionan
variables artificiales en las restricciones de tipo ≥ con términos independientes no negativos.
En base a lo anterior, si así lo dispusiésemos, podríamos eliminar de la tabla las columnas
de las variables artificiales dado que la información en ellas contenida aparece en las columnas
de las variables de exceso a las cuales sustituyeron en la base inicial, multiplicada por –1.

Ejemplo 3-3 Método de penalización

Considerando el Ejemplo 1-13 tendremos
Max z  30 x 1  40 x 2  0 x 3  0 x 4  Mx 5  Mx 6
s. a
x 1  x 2  1x 3  0 x 4  0x 5  0x 6  7
x 1  2 x 2  0 x 3  1x 4  1x 5  0x 6  4
x 1  0 x 2  0 x 3  0 x 4  0x 5  1x 6  5
x j  0 j  1, 2, ..., 6
30 40 0 0 –M –M xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
0 A3 1 1 1 0 0 0 7 7
–M A5 1 –2 0 –1 1 0 4 4
–M A6 1 0 0 0 0 1 5 5
zj –2M 2M 0 M –M –M
z = –9M
cj – zj 30+2M 40–2M 0 –M 0 0

61
Capítulo 3

30 40 0 0 –M –M xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
0 A3 0 3 1 1 –1 0 3 1
30 A1 1 –2 0 –1 1 0 4
–M A6 0 2 0 1 –1 1 1 1/2
zj 30 –60–2M 0 –30–M 30+M –M
z = 120–M
cj – zj 0 100+2M 0 30+M –30–2M 0

30 40 0 0 –M –M xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
0 A3 0 0 1 –1/2 1/2 –3/2 3/2
30 A1 1 0 0 0 0 1 5
40 A2 0 1 0 1/2 –1/2 1/2 1/2
zj 30 40 0 20 –20 50
z = 170
cj – zj 0 0 0 –20 20–M –50–M
Puesto que cj – zj < 0 para cada variable no básica, la última tabla nos da la solución ó ptima.

EL MÉTODO DE LAS DOS FASES

En su desarrollo original el método de penalización fue concebido como un método de
aplicación manual. Su principal desventaja radica en la implementación computacional.
En efecto, al asignar un valor grande a M los cj de las variables de decisión resultan
insignificantes frente a los zj que contienen términos en M lo cual, sumado a los errores de
redondeo inherentes a cualquier computador, puede causar que la solución resulte insensible a
los valores de los coeficientes económicos originales, es decir, se corre el riesgo que tales
coeficientes sean tratados como si tuviesen igual valor en la función objetivo.
El método de las dos fases evita las dificultades anteriores divid iendo el problema en dos
etapas:
En la Fase I se resuelve el modelo aumentado reemplazando la función objetivo del
problema original por la suma de las variables ficticias. La nueva función objetivo será
siempre de minimización.
Si el problema original tiene solución factible, el mínimo valor de la función objetivo del
modelo ampliado será igual a cero, lo que indica que la o las variables ficticias son nulas. En
caso contrario el problema original es no factible.
En la Fase II, se utiliza la solución óptima de la Fase I como solución de comienzo para el
problema original. Para ello, a partir de la tabla de óptimo anterior construimos una nueva
tabla eliminando las columnas correspondientes a las variables ficticias, reemplazando los cj
por los coeficientes económicos de la función objetivo del problema original y recalculando
los valores zj, cj – zj y z. A partir de allí continuamos con la resolución del Simplex en la
forma usual.
Durante la resolución puede ocurrir que:
 En la Fase I se verifique la condición de optimización y el valor de la función objetivo
sea distinto de cero. En este caso, como ya se indicara, el problema original es no
factible.
 En la Fase I se verifique la condición de optimización y la base final no esté integrada
por ninguna variable ficticia, en cuyo caso se continúa con la Fase II según lo explicado
previamente.

62 Norma Torrent
 El Método Simplex

 En la Fase I se verifique la condición de optimización y la base final es té integrada por

al menos una variable ficticia con valor nulo. En este caso, procedemos de la siguiente
forma.
 Si xf es una variable ficticia básica y xj una variable no básica y no ficticia del modelo
con yfj  0, se utiliza yfj como pivote para ingresar a la base a xj, es decir reemplazamos
xf por xj (notemos que aquí yfj puede ser negativo ya que al ser xi = 0, resulta xi/yfj = 0).
Cuando mediante este proceso podemos intercambiar todas las variables artificiales
básicas, se genera una solución básica factible inicial degenerada para el modelo
original y se continúa con la Fase II en la manera habitual.
 Si xf es una variable ficticia básica y todos los yfj correspondientes a las variables no
básicas y no ficticias del modelo son nulos, xf seguirá integrando la base con valor nulo
durante la Fase II.
y fe
 Para cualquier cambio de base en el que entre Ae y salga As, x'f  x f  x s seguirá
y se
siendo nula puesto que y fe  0 y x f  0 , por lo que la restricción asociada a xf es
analíticamente redundante.14 Se eliminan entonces de la tabla la columna y la fila
correspondientes a xf, y se continúa con la Fase II en la forma habitual.

Ejemplo 3-4 Método de las dos fases

Aplicaremos el método al Ejemplo 1-13.
Max z  30 x 1  40 x 2  0 x 3  0 x 4
s. a
x 1  x 2  1x 3  0 x 4  7
x 1  2 x 2  0 x 3  1x 4  4
x 1  0x 2  0x 3  0x 4  5
x j  0 j  1, 2, ..., 4
Fase I
Min f  x 5  x 6
s. a
x 1  x 2  1x 3  0 x 4  0x 5  0x 6  7
x 1  2 x 2  0 x 3  1x 4  1x 5  0x 6  4
x 1  0 x 2  0 x 3  0 x 4  0x 5  1x 6  5
x j  0 j  1, 2, ..., 6
0 0 0 0 1 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
0 A3 1 1 1 0 0 0 7 7
1 A5 1 –2 0 –1 1 0 4 4
1 A6 1 0 0 0 0 1 5 5
zj 2 –2 0 –1 1 1
f=9
cj – zj –2 2 0 1 0 0

14
Véase el apartado 1-8 en Capítulo 1.
63
Capítulo 3

0 0 0 0 1 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
0 A3 0 3 1 1 –1 0 3 1
0 A1 1 –2 0 –1 1 0 4
1 A6 0 2 0 1 –1 1 1 1/2
zj 0 2 0 1 –1 1
f=1
cj – zj 0 –2 0 –1 2 0

0 0 0 0 1 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
0 A3 0 0 1 –1/2 1/2 –3/2 3/2
0 A1 1 0 0 0 0 1 5
0 A2 0 1 0 1/2 –1/2 1/2 1/2
zj 0 0 0 0 0 0
f=0
cj – zj 0 0 0 0 1 1

Fase II
30 40 0 0 xi/yij
ci Ai A1 A2 A3 A4 xi (yij>0)
0 A3 0 0 1 –1/2 3/2
30 A1 1 0 0 0 5
40 A2 0 1 0 1/2 1/2
zj 30 40 0 20
z = 170
cj – zj 0 0 0 –20
T
La solución óptima es x*  5; 0,5; 1,5; 0  ; z *  170.
Notemos que podríamos haber prescindido de la última tabla de la Fase I. En efecto, en la
segunda tabla vemos que x6 abandona la base por lo que estamos en condiciones de asegurar que
la próxima tabla será la de óptimo de la Fase I (todas las ficticias resultarán no básicas y por lo
tanto f* tendrá valor nulo).
Comenzamos entonces directamente la Fase II con el ingreso de x2 y la salida de x6.

3.6 TIPOS DE SOLUCIÓN

A continuación resolveremos algunos modelos sencillos a los efectos de analizar distintas
situaciones y tipos de solución que se pueden presentan durante la ejecución del método
Simplex.

Ejemplo 3-5 Problema con múltiples soluciones óptimas

Veamos el Ejemplo 1-14.
Min w  10 x 1  20 x 2  0 x 3  0 x 4  0 x 5  0 x 6
s. a
 x 1  x 2  1x 3  0 x 4  0 x 5  0 x 6  3
x 1  x 2  0 x 3  1x 4  0 x 5  0 x 6  5
x 1  2 x 2  0 x 3  0 x 4  1x 5  0 x 6  2
0,5x 1  x 2  0 x 3  0 x 4  0 x 5  1x 6  0,5
x j  0 j  1, 2, ...,6

64 Norma Torrent
 El Método Simplex

Fase I
Min f  x 7  x 8
s. a
 x 1  x 2  1x 3  0 x 4  0 x 5  0 x 6  0 x 7  0 x 8  3
x 1  x 2  0 x 3  1x 4  0 x 5  0 x 6  0 x 7  0 x 8  5
x 1  2 x 2  0 x 3  0 x 4  1x 5  0 x 6  1x 7  0 x 8  2
0,5x 1  x 2  0 x 3  0 x 4  0 x 5  1x 6  0 x 7  1x 8  0,5
x j  0 j  1, 2, ...,8
0 0 0 0 0 0 1 1
ci Ai A1 A2 A3 A4 A5 A6 A7 A8 xi xi/yij
0 A3 –1 1 1 0 0 0 0 0 3
0 A4 1 1 0 1 0 0 0 0 5 5
1 A7 1 2 0 0 –1 0 1 0 2 2
1 A8 1/2 –1 0 0 0 –1 0 1 1/2 1
zj 3/2 1 0 0 –1 –1 1 1
f = 5/2
cj – zj –3/2 –1 0 0 1 1 0 0

0 0 0 0 0 0 1 1
ci Ai A1 A2 A3 A4 A5 A6 A7 A8 xi xi/yij
0 A3 0 –1 1 0 0 –2 0 2 4
0 A4 0 3 0 1 0 2 0 –2 4 4/3
1 A7 0 4 0 0 –1 2 1 –2 1 1/4
0 A1 1 –2 0 0 0 –2 0 2 1
zj 0 4 0 0 –1 –2 1 –2
f=1
cj – zj 0 –4 0 0 1 2 0 3
Fase II
10 20 0 0 0 0
ci Ai A1 A2 A3 A4 A5 A6 xi xi/yij
0 A3 0 0 1 0 –1/4 –3/2 17/4
0 A4 0 0 0 1 3/4 1/2 13/4
20 A2 0 1 0 0 –1/4 1/2 1/4
10 A1 1 0 0 0 –1/2 –1 3/2
zj 10 20 0 0 –10 0
w = 20
cj – zj 0 0 0 0 10 0
T
La solución óptima es x*  1,5; 0,25; 4,25; 3,25; 0; 0  ; w*  20 .
Inspeccionando la tabla de óptimo vemos que c6 – z6 =0, por lo tanto existe una solución
básica alternativa que se obtiene ingresando el vector A6.
10 20 0 0 0 0
ci Ai A1 A2 A3 A4 A5 A6 xi xi/yij
0 A3 0 3 1 0 –1 0 5
0 A4 0 –1 0 1 1 0 3
0 A6 0 2 0 0 –1/2 1 1/2
10 A1 1 2 0 0 –1 0 2
zj 10 20 0 0 –10 0
w = 20
cj – zj 0 0 0 0 10 0
T
La nueva solución óptima es x*  2; 0; 5; 3; 0; 0,5  ; w*  20 .

65
Capítulo 3

Dadas dos soluciones básicas óptimas cualquier combinación convexa de ellas nos permite
obtener las múltiples (infinitas) soluciones no básicas que también serán óptimas. 15
Matemáticamente la familia de estas soluciones estará dada por :
x *  3 / 2; 1/4; 17/4; 13/4; 0; 0 T  1   2; 0; 5, 3; 0; 1/2 T ; 0  λ  1
Ejemplo 3-6 Problema con solución no acotada
Resolveremos el Ejemplo 1-16.
Max z  40 x 1  80 x 2  0 x 3  0 x 4  0 x 5
s. a
3x 1  5x 2  1x 3  0 x 4  0 x 5  15
x 1  2 x 2  0 x 3  1x 4  0 x 5  4
 4 x 1  3x 2  0 x 3  0 x 4  1x 5  12
x j  0 j  1, 2, ..., 5
Fase I
Min f  x 6
s. a
3x 1  5x 2  1x 3  0 x 4  0 x 5  1x 6  15
x 1  2 x 2  0 x 3  1x 4  0 x 5  0 x 6  4
 4 x 1  3x 2  0 x 3  0 x 4  1x 5  0 x 6  12
xj x j  0 j  1, 2, ..., 6
0 0 0 0 0 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
1 A6 3 5 –1 0 0 1 15 3
0 A4 1 –2 0 1 0 0 4
0 A5 –4 3 0 0 1 0 12 4
zj 3 5 –1 0 0 1
f = 15
cj – zj –3 –5 1 0 0 0
Fase II
40 80 0 0 0 xi/yij
ci Ai A1 A2 A3 A4 A5 xi (yij>0)
80 A2 3/5 1 –1/5 0 0 3
0 A4 11/5 0 –2/5 1 0 10
0 A5 –29/5 0 3/5 0 1 3 5
zj 48 80 –16 0 0
z = 240
cj – zj –8 0 16 0 0

40 80 0 0 0 xi/yij
ci Ai A1 A2 A3 A4 A5 xi (yij>0)
80 A2 –4/3 1 0 0 1/3 4
0 A4 –5/3 0 0 1 2/3 12
0 A3 –29/3 0 1 0 5/3 5
zj –320/3 80 0 0 80/3
z = 320
cj – zj 440/3 0 0 0 –80/3

Puesto que yi1 < 0  i IB concluimos que la solución no está acotada. 16

15
Véase la solución gráfica del Ejemplo 1-14 en el Capítulo1.
16
Véase la solución gráfica del Ejemplo 1-16 en el Capítulo1.

66 Norma Torrent
 El Método Simplex

Ejemplo 3-7 Problema con solución básica factible degenerada y óptimo no degenerado
Sea el siguiente programa lineal y su correspondiente solución gráfica.

Max z  2 x1  x 2
s. a
4 x1  3x 2  12

z=2
4 x1  x2  8

x
1+
x 2=
x1  2

z0
x1 ; x 2  0

Resolviendo por tabla tendremos.

2 1 0 0 0 xi/yij
ci Ai A1 A2 A3 A4 A5 xi (yij>0)
0 A3 4 3 1 0 0 12 3
0 A4 4 1 0 1 0 8 2
0 A5 1 0 0 0 1 2 2
zj 0 0 0 0 0
z=0
cj – zj 2 1 0 0 0
Dado que el mínimo de los xi/yi1 (con yi1 > 0) se produce para x4/y41 = x5/y51 podremos optar
por remover la columna A4 o la A5 de la base actual. Conforme a lo convenido hacemos salir al
vector de mayor subíndice, es decir A5. Notemos además que al ingresar x1 con valor 1 = x5/y51
= 2 se anularán simultáneamente x5 y x4 por lo que tendremos una solución degenerada.
2 1 0 0 0 xi/yij
ci Ai A1 A2 A3 A4 A5 xi (yij>0)
0 A3 0 3 1 0 –4 4 4/3
0 A4 0 1 0 1 –4 0 0
2 A1 1 0 0 0 1 2
zj 2 0 0 0 2
z=4
cj – zj 0 1 0 0 –2

Al ser 2 = x4/y42 = 0 la próxima solución seguirá siendo degenerada y z mantendrá su valor.

2 1 0 0 0 xi/yij
ci Ai A1 A2 A3 A4 A5 xi (yij>0)
0 A3 0 0 1 –3 8 4 1/2
1 A2 0 1 0 1 –4 0
2 A1 1 0 0 0 1 2 2
zj 2 1 0 1 –4
z=4
cj – zj 0 0 0 –1 4

5 = x3/y35 = 1/2 por lo tanto el problema sale de su estado degenerado.

2 1 0 0 0 xi/yij
ci Ai A1 A2 A3 A4 A5 xi (yij>0)
0 A5 0 0 1/8 –3/8 1 1/2
1 A2 0 1 1/2 –1/2 0 2
2 A1 1 0 –1/8 3/8 0 3/2
zj 2 1 1/4 1/4
z=5
cj – zj 0 0 –1/4 –1/4
67
Capítulo 3

T
La solución óptima es x*  1,5; 2; 0; 0; 0,5  ; z *  5. Como mencionáramos en el
desarrollo teórico, en las distintas aplicaciones que se presentan puede ocurrir que al cabo de
algunas iteraciones la solución degenerada resulte la óptima o bien, como acabamos de ver, se
salga de la degeneración y la solución óptima sea no degener ada.
Por último cabe acotar que cuando más restricciones que las necesarias determinan un punto
extremo, el mismo es degenerado. En efecto, en la solución gráfica de este ejemplo podemos
observar que las restricciones x2 ≥ 0, 4x1 + x2  8 y x2  2 pasan por el punto (2; 0) que queda
determinado con sólo dos de ellas.

Ejemplo 3-8 Problema con redundancia analítica

Recordemos que una restricción es analíticamente redundante cuando puede expresarse como
una combinación lineal de las otras restricciones del modelo. Veamos el siguiente ejemplo.
Max z  3x 1  x 2  x 3
s. a
2x 1  2x 3  6
 x 1  2x 2  x3  2
2x 2  2x 3  5
x1 , x 2 , x 3  0
Fase I
Min f  x 4  x 5  x 6
s. a
2x 1  2 x 3  1x 4  0 x 5  0 x 6  6
 x 1  2x 2  x 3  0 x 4  1x 5  0 x 6  2
2x 2  2 x 3  0 x 4  0 x 5  1x 6  5
x j  0 j  1, 2, ..., 6
0 0 0 1 1 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
1 A4 2 0 2 1 0 0 6 3
1 A5 –1 2 1 0 1 0 2 2
1 A6 0 2 2 0 0 1 5 5/2
zj 1 4 5 1 1 1
f = 13
cj – zj –1 –4 –5 0 0 0

0 0 0 1 1 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
1 A4 4 –4 0 1 –2 0 2 1/2
0 A3 –1 2 1 0 1 0 2
1 A6 2 –2 0 0 –2 1 1 1/2
zj 6 –6 0 1 –4 1
f=3
cj – zj –6 6 0 0 5 0

0 0 0 1 1 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
1 A4 0 0 0 1 2 –2 0 0
0 A3 0 1 1 0 0 1/2 5/2
0 A1 1 –1 0 0 –1 1/2 1/2
zj 0 0 0 1 2 –2
f=0
cj – zj 0 0 0 0 –1 3
68 Norma Torrent
 El Método Simplex

Si bien f ha alcanzado su valor óptimo no se ha verificado la condición de optimización.

0 0 0 1 1 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
1 A5 0 0 0 1/2 1 –1 0
0 A3 0 1 1 0 0 1/2 5/2
0 A1 1 –1 0 1/2 0 –1/2 1/2
zj 0 0 0 1/2 1 –1
f=0
cj – zj 0 0 0 1/2 0 2
Hemos llegado al óptimo de la Fase I, x5 integra la base con valor cero y el coeficiente y52 es
nulo (x2 es la única variable no básica y no ficticia en la tabla), por lo tanto la restricción
asociada a x5 es analíticamente redundante (en efecto, la segunda restricción del modelo es una
combinación lineal de la tercer restricción menos la primera multiplicada por 1/2).
Eliminamos la fila y la columna correspondiente a x5 y continuamos con la Fase II en la
forma habitual.
Fase II
3 1 1 xi/yij
ci Ai A1 A2 A3 xi (yij>0)
1 A3 0 1 1 5/2
3 A1 1 –1 0 1/2
zj 3 2 1
z = 14
cj – zj 0 –1 0
T
La solución óptima es x*  0,5; 0; 2,5  ; z *  14 .

Ejemplo 3-9 Problema con redundancia analítica y solución óptima degenerada

Sea el siguiente programa lineal y su correspondiente solució n gráfica.
x2
Max z  2x 1  x 2
6
s. a
x1  x 2  2
z=2

n c2=1
2x1  x 2  4
x 1+

c1=2
x 2=

3x1  x 2  6 2
z0

x2  2 ÓPTIMO
x1 ; x 2  0
0 2 3 x1

Fase I
Min f  x 4  x 5  x 6
s. a
x 1  2x 2  0 x 3  1x 4  0 x 5  0 x 6  2
2 x 1  x 2  0 x 3  0 x 4  1x 5  0 x 6  4
3x 1  x 2  0 x 3  0 x 4  0 x 5  1x 6  6
x 2  1x 3  0 x 4  0 x 5  0 x 6  2
x j  0 j  1, 2, ..., 6

69
Capítulo 3

0 0 0 1 1 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
1 A4 1 2 0 1 0 0 2 2
1 A5 2 –1 0 0 1 0 4 2
1 A6 3 1 0 0 0 1 6 2
0 A3 0 1 1 0 0 0 2
zj 6 2 0 1 1 1
f = 12
cj – zj –6 –2 0 0 0 0

0 0 0 1 1 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
1 A4 0 5/3 0 1 0 –1/3 0
1 A5 0 –5/3 0 0 1 –2/3 0
0 A1 1 1/3 0 0 0 1/3 2
0 A3 0 1 1 0 0 0 2
zj 0 0 0 1 1 –1
f=0
cj – zj 0 0 0 0 0 2
Hemos llegado al óptimo de la Fase I y las variables ficticias x4 y x5 integran la base con
valor nulo. Podemos reemplazar A4 por A2 (A2 es no básico y no ficticio) utilizando como pivote
y42 = 5/3 (también hubiésemos podido reemplazar A5 por A2 utilizando como pivote y42 = –5/3).
0 0 0 1 1 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
0 A2 0 1 0 3/5 0 –1/5 0
1 A5 0 0 0 1 1 –1 0
0 A1 1 0 0 –1/5 0 3/5 2
0 A3 0 0 1 –3/5 0 1/5 2
zj 0 0 0 1 1 –1
f=0
cj – zj 0 0 0 0 0 2
La variable ficticia x5 es básica a nivel cero. Dado que ya no es posible efectuar un cambio
de base, x5 seguirá siendo nula por lo que su respectiva restricción asociada es analíticamente
redundante (la segunda restricción del modelo se obtiene como diferencia entre las restricciones
tercera y primera). Eliminamos la fila y la columna correspondiente a x5.
Fase II
2 1 0 xi/yij
ci Ai A1 A2 A3 xi (yij>0)
1 A2 0 1 0 0
2 A1 1 0 0 2
0 A3 0 0 1 2
zj 2 1 0
z=4
cj – zj 0 0 0
T
La solución óptima es x*  2; 0; 2  ; z *  4.
Ejemplo 3-10 Problema no factible
Resolveremos el Ejemplo 1-17.
Max w  105x 1  78x 2  0 x 3  0 x 4  0 x 5
s. a
x 1  x 2  1x 3  0 x 4  0 x 5  50
x 1  2 x 2  0 x 3  1x 4  0 x 5  40
3x 1  2 x 2  0 x 3  0 x 4  1x 5  60
x j  0 j  1, 2, ..., 5
70 Norma Torrent
 El Método Simplex

Fase I
Min f  x 6
s. a
x 1  x 2  1x 3  0 x 4  0 x 5  1x 6  50
x 1  2 x 2  0 x 3  1x 4  0 x 5  0 x 6  40
3x 1  2 x 2  0 x 3  0 x 4  1x 5  0 x 6  60
x j  0 j  1, 2, ..., 6
0 0 0 0 0 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
1 A6 1 1 –1 0 0 1 50 50
0 A4 1 2 0 1 0 0 40 40
0 A5 3 2 0 0 1 0 60 20
zj 1 1 –1 0 0 1
f = 50
cj – zj –1 –1 1 0 0 0
Dado que c1 – z1 = c2 – z2 = –1, en base a lo convenido optamos por introducir el vector A2.
0 0 0 0 0 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
1 A6 0 1/3 –1 0 –1/3 1 30 90
0 A4 0 4/3 0 1 –1/3 0 20 15
0 A1 1 2/3 0 0 1/3 0 20 30
zj 0 1/3 –1 0 –1/3 1
f = 30
cj – zj 0 –1/3 1 0 1/3 0

0 0 0 0 0 1 xi/yij
ci Ai A1 A2 A3 A4 A5 A6 xi (yij>0)
1 A6 0 0 –1 –1/4 –1/4 1 25
0 A2 0 1 0 3/4 –1/4 0 15
0 A1 1 0 0 –1/2 1/2 0 10
zj 0 0 –1 –1/4 –1/4 1
f = 25
cj – zj 0 0 1 1/4 1/4 0
Se ha llegado al óptimo de la Fase I y x6 integra la base con valor mayor que cero, en
consecuencia el problema original es no factible. 17

3.7 MÉTODOS DE PUNTO INTERIOR PARA PROGRAMAS LINEALES

En 1984 el matemático hindú Narendra Karmarkar de AT&T Bell Laboratories, publicó un
artículo presentando esquemáticamente un algoritmo de puntos interiores para la resolución de
programas lineales de gran tamaño. Cuatro años después la comunidad científica logró un
conocimiento general del método, iniciándose así el área de los métodos de punto interior, y
AT&T desarrolló en sus laboratorios una versión para su distribución comercial bajo el nombre
AT&T KORBX Linear Programming System.
El Método de Karmarkar, al igual que el Simplex, es un procedimiento iterativo pero a
diferencia de éste se mueve a través de los puntos interiores de la región factible hasta obtener la
mejor solución en un punto extremo o en un punto perteneciente a una arista de dicha región,
logrando para problemas de gran dimensión una significativa reducción en el tiempo de cálculo
con respecto al Simplex. Sin embargo, tal ventaja no se extiende a programas lineales de menor
tamaño.
17
Véase la solución gráfica del Ejemplo 1-17 en el Capítulo1.

71
Capítulo 3

Para problemas que puedan resolverse en una computadora personal o un ordenador portátil
mediante software de aplicación, el Simplex sigue siendo la mejor opción. A modo de ejemplo,
LINDO (Linear, INteractive and Discrete Optimizer) desarrollado por LINDO Systems, Inc.
permite manjar problemas de hasta 64.000 restricciones y 100.000 variables.

72 Norma Torrent