Fundamentos matemticos del mtodo smplex

Oscar Eduardo Gmez Rojas

oegrojas@yahoo.com

Trabajo de Grado para Optar por el Ttulo de Matemtico

Director: Pervys Rengifo Rengifo

Ingeniero Universidad Nacional de Colombia

Fundacin Universitaria Konrad Lorenz

Facultad de Matemticas
10 de diciembre de 2004

Tabla de contenido

Resumen_____________________________________________________________ 2
Introduccin__________________________________________________________ 3
Primera Parte_________________________________________________________ 4
1.1 Una motivacin ________________________________________________________ 5
1.2 Conjuntos convexos _____________________________________________________ 7
1.3 Soluciones Bsicas Factibles _____________________________________________ 17
1.4 Teorema de representacin______________________________________________ 21
Segunda Parte ______________________________________________________________ 25
2.1 El mtodo smplex _____________________________________________________ 26
2.2 El mtodo smplex en formato de tabla ____________________________________ 33
2.3 Problemas con solucin bsica factible inmediata ___________________________ 37
2.4 Problemas sin solucin bsica factible inmediata ____________________________ 44
2.5 Degeneracin _________________________________________________________ 51

Conclusiones ________________________________________________________ 53
Bibliografa _________________________________________________________ 54

Resumen
Se presentan algunos resultados de la teora matemtica de Programacin Lineal y se
exponen algunas consecuencia de estos resultados, que generalmente no aparecen en la
literatura que ms se utiliza para ensear estos temas. Se proponen, adems,
modificaciones al algoritmo de penalizacin, con el fin de simplificar su uso.

Abstract
Some results of the Mathematical theory of Linear Programming is presented and so
me of the consequences of these results are exposed; results included are the one that
do not appear in the kind of literature they used most to teach other topics. Besides,
some modification to big M algorithm in order to simplify its use.

Introduccin
Este trabajo trata sobre los fundamentos tericos de la Programacin Lineal. La
Programacin Lineal est comprendida dentro de un campo ms amplio de la
matemtica aplicada conocido como Investigacin de Operaciones. Por lo tanto, antes
de introducir la Programacin Lineal, se aborda el campo que la contiene. De las
definiciones de Investigaciones de Operaciones ms usadas, la que mejor la describe, al
parecer del autor, es la de Churchman, Ackoff y Arnoff, que aparece en la pgina 20 de
[Pra00] y que se transcribe a continuacin: La Investigacin de Operaciones es la
aplicacin, por grupos interdisciplinarios, del mtodo cientfico a problemas
relacionados con el control de las organizaciones o sistemas (hombre-mquina) a fin
de que se produzcan soluciones que mejor sirvan a los objetivos de toda la
organizacin. De esta definicin se concluye que la naturaleza de los problemas a
tratar es tal que hace necesario recurrir a prcticas que son propias de la ciencia, as
como la confluencia de miradas de diversa formacin terica sobre un mismo hecho.
Est ltima afirmacin coincide con lo que dice Taha en la pgina 2 de [Tah95], donde
afirma que: La Investigacin de Operaciones debe visualizarse como una ciencia y
como un arte, sin embargo, en el Tercer Mundo por la condicin de consumidores no
creadores- de Ciencia y Tecnologa, el trabajo en la parte matemtica se limita a la
aplicacin de algoritmos ya existentes y se abandona el estudio de sus fundamentos
tericos. Esta ha sido una constante en el pasado: unos pocos se dedican a producir
algoritmos, y la mayora, luego de recibir una exposicin terica superficial, aprende a
emplearlos en aplicaciones prcticas. Sin embargo, la llegada de los computadores ha
librado al hombre de tener que emplearse en el desarrollo mecnico de algoritmos.
Existen paquetes de software que desarrollan este trabajo algortmico, por lo tanto, la
parte del trabajo interdisciplinario que corresponde a los matemticos, consiste en
comprender los fundamentos a fin de estar en capacidad de producir soluciones nuevas
a problemas que no hayan sido considerados con anterioridad, o a mejorar las
existentes.
Es caracterstica de los modelos matemticos de los problemas de Investigacin de
Operaciones, la existencia de una, o unas, funciones objetivo que se desea optimizar en
presencia de restricciones sobre las variables. La Programacin Lineal se ocupa de los
problemas en los cuales tanto la funcin objetivo como las restricciones son de tipo
lineal. Este trabajo est dirigido ms al porqu, que al cmo, de los algoritmos, por lo
tanto es adecuado, sobre todo, para quienes ya han tenido contacto con el tema y desean
conocer los resultados en los cuales se basa el algoritmo smplex.
Aunque este trabajo es esencialmente de tipo exploratorio, la aplicacin literal de la
teora permiti llegar a desarrollar ejemplos que van ms all de lo usual y a proponer
dos cambios que simplifican la ejecucin del algoritmo de penalizacin.

Este texto y los otros que aparecen citados, se encuentran completamente referenciados en la
bibliografa que aparece al final del trabajo.

Primera Parte
________________

1.1 Una motivacin

El trabajo que se desarrolla en seguida, es una presentacin matemtica formal de las tcnicas
generales de la Programacin Lineal y del mtodo smplex en particular. Por lo tanto, se
comienza ilustrando el mtodo grfico, con un ejemplo particular, para ir as introduciendo unos
conceptos intuitivos que, a continuacin, sern rigurosamente definidos.
Considrese el siguiente problema de optimizacin lineal:
Una compaa fabrica sillas y mesas. Cada silla necesita 5 horas de ensamblado y 2 horas de
acabado, mientras que cada mesa requiere 3 horas de ensamblado y 4 de acabado.
Semanalmente la empresa dispone de 105 horas en la lnea de ensamblado y 70 en la de
acabado. La ganancia por cada silla es de $200 y de $160 por cada mesa. Determine el nmero
de sillas y mesas que deben fabricarse con el fin de maximizar la utilidad total.
Se plantea el problema en forma matemtica:
Primero se define claramente el significado de las variables que se emplearn.
Sean x:= nmero de sillas que se fabricarn.
y:= nmero de mesas que se fabricarn.
El problema se expresa entonces de la forma:
Maximizar la utilidad 200x+160y satisfaciendo las restricciones:
1) 5x + 3y
2) 2x + 4y

105
70

Las restricciones 1) y 2) corresponden, respectivamente, a las horas de ensamblado y acabado

disponibles. Existen adems otras dos restricciones tcitas en este problema: como no tiene
sentido pensar en construir cantidades negativas de ningn producto, se exige adems: x 0 e y
0.
Si se asigna un valor de u a la utilidad, se tiene:
200x+160y = u
despejando y queda

y=

u 200x
160

asignando diversos valores a u se obtienen diferentes rectas paralelas.

Se despeja y en las dos primeras restricciones y se grafica:
1) y

105 5 x
3

2) y

70 2 x
4

3) x 0

4) y 0

El punto (o los puntos) solucin debe(n) satisfacer simultneamente todas las restricciones, por
lo tanto se encontrar(n) en la interseccin de los conjuntos solucin de todas las restricciones.
En la grfica 1.1 la regin sombreada corresponde a esta interseccin (regin factible), por lo
tanto debe buscarse la solucin en ella. Para tal efecto se asignan diversos valores a u y se
grafican las rectas que corresponden a cada una de estas asignaciones. Se puede ver lo que

ocurre cuando u pasa de 0 a 2000: la recta correspondiente a la funcin de utilidad se traslada

paralela en una direccin noreste aproximadamente, incrementndose su valor.

Grfica 1.1 Mtodo grfico

Por lo tanto se debe continuar el traslado en tal direccin mientras se mantenga dentro de la
regin factible. El punto mximo al cual se puede llegar siguiendo este procedimiento es el que
se ha sealado en la grfica 1.1 como punto solucin. Este punto corresponde a la interseccin
de las rectas y=(105-5x)/3 e y=(70-2x)/4, resolviendo este sistema de ecuaciones se encuentra
que la solucin es x = 15 e y=10. Con estos valores se tiene una utilidad de 4600.
En general, para los problemas de programacin lineal en dos variables la regin factible tendr
la forma de un polgono en el plano xy. Al igualar la funcin objetivo (z) a una constante c, su
grfica ser una lnea recta, cambiando el valor de c la recta se desplazar en forma paralela
sobre el plano, existiendo dos sentidos de desplazamiento (uno cuando c se incrementa y el
contrario para decrementos de c). Es intuitivamente obvio que el valor extremo (mximo o
mnimo) de la funcin objetivo dentro de la regin factible se obtendr cuando esta recta pase
por un vrtice (punto extremo) del polgono, puesto que el ltimo punto de contacto con la
regin factible, al moverse en el sentido de crecimiento o decrecimiento, debe ocurrir en uno de
los vrtices. La grfica 1.2 ilustra las afirmaciones anteriores. En la figura (b) las lneas con z
constante son paralelas a un lado del polgono factible, en este caso el valor mximo de z ocurre
cuando la lnea con z constante coincide con tal lado y, por lo tanto, se tienen infinitas
soluciones, todas las cuales se encuentran en el segmento de recta que une dos de los puntos
extremos (vrtices). Aunque no se ilustra en la figura, puede ocurrir que la regin factible no sea
acotada, en tal caso z puede no tener un valor mximo o mnimo finito.
Resumiendo, se tienen ya algunos hechos importantes acerca de los problemas de programacin
lineal: la regin factible es la interseccin de las regiones que determinan cada una de las
restricciones del problema; el punto ptimo se localiza en uno de los puntos extremos de la
regin factible; pueden existir infinitas soluciones; la regin factible puede no ser acotada y por
lo tanto el problema puede no tener una solucin finita; y por ltimo, aunque no se ha
mencionado, la regin factible puede ser vaca, esto es, puede ocurrir que no exista ningn
punto que satisfaga simultneamente todas las restricciones.

Grfica 1.2 Existencia de una o de infinitas soluciones

Los resultados anteriores han sido establecidos de manera intuitiva y han sido motivados con
una grfica bidimensional. Sin embargo, como ocurre en el clculo, los resultados insinuados
por la geometra deben ser establecidos de forma rigurosa, de tal manera que puedan ser
extendidos a ms de tres dimensiones, donde no tiene sentido pensar en hacer un dibujo o una
maqueta. Lo anterior no quiere decir que las interpretaciones geomtricas carezcan de valor,
pues generalmente son ellas las que insinan los resultados que posteriormente se establecen de
forma rigurosa, simplemente que no constituyen una demostracin en el sentido estricto del
trmino. Por lo tanto se seguirn empleando grficas para ilustrar las definiciones y los
resultados que se vayan estableciendo, pero unas y otros se desarrollarn con independencia de
la geometra.

1.2 Conjuntos convexos

La recta que pasa por los puntos


de n se define como el conjunto de puntos
X = {
n /
=
 + (1 )
 , }
El segmento de recta que une


en n se define como el conjunto de puntos
X = {
n /
=
 + (1 )
 ,0 1}
Un hiperplano en n se define como el conjunto de puntos

X = { n /
 =
}
donde

es un vector fila de n componentes y z es un escalar.

Los conjuntos

X = { n /

} y
7

X = { n /

}
se llaman semiespacios cerrados.

Definicin: Un conjunto X es convexo si para dos puntos cualesquiera del conjunto


, el

segmento de recta que los une est tambin dentro del conjunto. En otras palabras, si


 X entonces cada punto

=
 + (1 )

,0 1
debe pertenecer tambin al conjunto. La grfica 1.3 ilustra esta definicin.

Grfica 1.3 Ejemplos de un conjunto convexo y uno no convexo

Definicin: La expresin
+ (1 )
 ,0 1 (para un dado) se llama una

combinacin convexa de


.
Teorema 1.1: Un semiespacio cerrado es un conjunto convexo.
Demostracin: supngase que


estn en el semiespacio cerrado



 si

=
 + (1 )

,0 1
entonces


= 
+ (1 )
 z + (1 ) z = z , (0 1)

y por lo tanto x est en el semiespacio.

Un argumento casi idntico demuestra que un hiperplano tambin es un conjunto convexo.

Teorema 1.2: La interseccin de dos conjuntos convexos tambin es convexa.

Demostracin: sean X 1 , X 2 conjuntos convexos, y sean


X 1 X 2 dos puntos
diferentes (si X 1 X 2 tiene un nico elemento, automticamente es convexo), entonces
y
por lo tanto

 + (1 )
 X 1 ,0 1

 + (1 )
 X 2 ,0 1

 + (1 )
 X 1 X 2 ,0 1 .

Las restricciones en un problema de Programacin Lineal (incluidas las de no negatividad)

tienen la forma de lo que se ha definido como hiperplanos o como semiespacios cerrados, (los
cuales son conjuntos convexos) y la regin factible consiste en la interseccin de un nmero
finito de tales hiperplanos o semiespacios. Y como la interseccin de un nmero finito de
conjuntos convexos es convexa, se puede concluir que: el conjunto de las soluciones factibles
para un problema de Programacin Lineal es un conjunto cerrado y convexo.
Introduciendo variables de holgura o de supervit (holguras que se restan) las restricciones de
las formas " " , " " se transforman en restricciones de la forma =. De lo anterior se
concluye que en los algoritmos de Programacin Lineal se trabaja con sistemas de ecuaciones.
Por lo tanto se necesitar del siguiente resultado: el conjunto de soluciones de un sistema de m
ecuaciones lineales en n incgnitas, Ax=b, es un conjunto convexo y cerrado. Para ver esto,
obsrvese que el conjunto de ecuaciones de puede escribir

   =
 , i=1, . . . ,m.
donde ai es la i-sima fila de A, y para cada i,    =
 representa un hiperplano. El conjunto
de los puntos que satisfacen simultneamente todas las ecuaciones es la interseccin de los m
hiperplanos; que es, como ya se vio, un conjunto convexo y cerrado.
Un punto x es un punto extremo de un conjunto convexo, si, y solo si, no existen en el
conjunto puntos
 
 (

 ) tales que

=
 + (1 )
 , 0 < < 1
La definicin implica que un punto extremo no puede estar entre otros dos puntos del
conjunto, esto es, que no puede estar en el segmento de recta que los une.

Teorema 1.3: Un punto extremo es a su vez un punto frontera.

Demostracin: supngase que x es un punto interior de X, por lo tanto existe una vecindad
de x completamente contenida en X. Sea x1 un punto de la vecindad diferente de x, hagamos x2
= x+(x-x1), se tiene entonces x2-x = x-x1 de donde |x2-x |= |x-x1| y por lo tanto x2 tambin
est en la vecindad y adems para =1/2 se tiene
x1+(1-)x2=(x1+x2)/2=x
por lo tanto x no puede ser un punto extremo. Sin embargo, el recproco no es cierto, no todo
punto frontera es punto extremo, como se ilustra en la grfica 1.4.

Grfica 1.4

La grfica 1.5 permite visualizar un resultado que lleva a la definicin de combinacin convexa
de m puntos. Al prolongar cualquier recta que pase por el punto y esta necesariamente se
encontrar con puntos de la frontera, en este caso los puntos de corte son xa y xb y, por lo tanto,
se tiene que y = xa+(1-)xb, 0 1, pero, a su vez los puntos xa y xb se encuentran entre
x5,x6 y x3,x4 respectivamente, por lo tanto
xa = x5 + (1-)x6, 0 1

xb = x3 + (1-)x4, 0 1

Grfica 1.5 Motivacin de la definicin de combinacin convexa

de donde se tiene

y = xa + (1-)xb
= [x5 + (1-)x6] + (1-)[x3 + (1-)x4]
=x5 + (1-)x6 + (1-)x3 +(1-) (1-)x4

sumando los coeficientes de la combinacin lineal se tiene

+ (1-) + (1-) + (1-) (1-) =
+ + + 1 + = 1
Lo anterior es una motivacin para la siguiente definicin.

Definicin: una combinacin convexa de un numero finito de puntos x1, . . . ,xm se define
como el punto

=

m
i =1

i


i 0, i = 1,..., m,

m
i =1

i = 1.

Entonces se puede afirmar que, cualquier punto de un conjunto convexo acotado se puede
escribir como combinacin convexa de los puntos extremos del conjunto.

Teorema 1.4: El conjunto de todas las combinaciones convexas de un nmero finito de puntos
x1, . . . ,xm, es un conjunto convexo.

10

Es decir, el conjunto
X={


=

i
! ,

i =1

para todos los i 0, i = 1,..., m,

i = 1}

i =1

es convexo.

Demostracin: tmense u y v en X, entonces

m

=

i =1
m

=

i =1

'i 0, i = 1,..., m,

'i
! ""!
' 'i
# $$#

' 'i 0, i = 1,..., m,

' i = 1.

i =1
m

i =1

' ' i = 1.

y hgase la combinacin convexa

u+(1-)v=

m
i =1

'i
% + (1 )

pero

m
i =1

' 'i
& =

m
i =1

( i '+ (1 ) i ' ' )
'

( i '+ (1 ) i ' ' ) 0

y adems
m

( i '+(1 ) i ' ' ) =

i =1

m
i =1

i ' + (1 )

m
i =1

i '' = 1

as que u+(1-)v tambin es una combinacin convexa de los xi y, por lo tanto, el conjunto X
es convexo.

Definicin: Dado un conjunto A, se define la envolvente convexa de A como el conjunto

convexo ms pequeo que contiene a A. Precisando: la envolvente convexa de un conjunto A

es la interseccin de todos los conjuntos convexos que contienen a A.

Teorema 1.5: La envolvente convexa de un nmero finito de puntos x1, . . . , xm es el conjunto

de todas las combinaciones convexas de x1, . . . , xm.

Este teorema afirma que la envolvente convexa de x1, . . . , xm es el conjunto:

X={


=

m
i =1

i
( ))(

para todos los i 0, i = 1,..., m,

m
i =1

i = 1. }

Demostracin: ya se vio que el conjunto de todas las combinaciones convexas de x1, . . . , xm

es un conjunto convexo. Falta demostrar que todo conjunto convexo que contiene a los puntos
x1, . . . , xm tambin contiene X. Se procede por induccin sobre m. Para m=2 el resultado es
inmediato. Supngase el teorema cierto para m-1: esto es que la envolvente convexa de x1, . . . ,
xm-1 es el conjunto:
X1={


=

m 1
i =1

i
( ))(

para todos los i 0, i = 1,..., m,

m
i =1

i = 1. }

Sea X la envolvente convexa de x1, . . . , xm. Obviamente todo punto de X1 est tambin en X y
adems X debe contener tambin a todos los segmentos de recta que unan puntos de X1 con xm,
esto es, todos los puntos:

11

x=

m 1
i =1

si se hace

i
+ + (1 )
*

i = i , i=1, . . . , m-1 y m = (1 )

Entonces, todo i 0 y

m
i =1

i =

m 1
i =1

i + (1 ) = 1

Adems, como i y varan entre 0 y 1, cada i puede tambin tomar cualquier valor entre 0 y
1. As, X es el conjunto de todas las combinaciones convexas de x1, . . . , xm.

Definicin: La envolvente convexa de n puntos se denomina el poliedro convexo engendrado

por estos n puntos.

La grfica 1.6 muestra que dado un conjunto convexo X, y un punto y fuera de l, existe un
hiperplano que los separa, esto es, un hiperplano tal que el punto y est en uno de los
semiespacios que determina el hiperplano, y el conjunto X, en su totalidad, est en el otro.

Grfica 1.6 Existencia y ausencia del hiperplano de separacin.

Teorema 1.6 (o del hiperplano de separacin) : Sea X un conjunto no vaco, cerrado y

convexo y
X . Entonces existe un vector c distinto de cero, y un > 0 tal que cy +
cx para todo x X.
Demostracin: en primer lugar se extrae de X un subconjunto cerrado y acotado, para ello
tomese cualquier xo X y sea r = ||xo-y||, se intersecta la bola cerrada con centro en y y radio r

con el conjunto X, el conjunto resultante, que se denominar X, es convexo, cerrado y acotado,

pues es la interseccin de dos convexos y cerrados, uno de los cuales es acotado. En otras
palabras X est conformado por los puntos de X cercanos a y en el sentido de que estn a
una distancia de, a lo ms, r-. Se define f(x) = ||x-y||, para todo x en X, esta funcin es continua
y como X es compacto, entonces f asume un mnimo en X . Sea w el punto donde la funcin
asume el mnimo. Se ver que este w es nico: supngase que existen w1 y w2 (w1 w2)que
estn a la misma distancia mnima de y, entonces, por la desigualdad triangular se tiene:
||(w1+w2) - y|| = ||(w1-y) + (w2-y)|| < ( || w1-y || + || w2-y ||) = || w1-y ||

La desigualdad estricta vale si w1-y (w2-y) , y este es el caso pues si

Nota: al lector que no conozca esta afirmacin acerca de la desigualdad triangular le sugiero consultar, por ejemplo,
la demostracin de la desigualdad de Cauchy-Schwartz que aparece en la pgina 17 de [Apo77] y la demostracin de
la desigualdad triangular de la pgina 59 del mismo libro.

12

w1-y = (w2-y)

se tendra

||w1-y|| = ||w2-y||

pero, como

||w1-y|| = ||w2-y||

dara como resultado =1, esto implicara que

w1=w2
Lo cual es una contradiccin.
Considrese ahora cualquier punto x en X. Entonces el punto
est en X y cumple
o sea
Aplicando
se tiene
o sea

(1-)w+x, 0 1,
||(1-)w+x - y|| ||w-y||
|| (w - y +x - w) || ||w-y||
||x|| = xx
||w-y|| + 2(w - y )(x - w) + ||x-w|| ||w-y||
2(w - y )(x - w) + ||x-w|| 0

tomando >0 y dividiendo a ambos lados por ,

2(w - y )(x - w) + ||x-w|| 0
tomando el lmite cuando tiende a cero, se obtiene
(w - y )(x - w) 0
se emplea el recurso x w = x - y + y w = x y (w - y) y se reemplaza
o sea
de donde
trasponiendo

(w - y )( x y (w - y)) = (w - y )(x - y) - ||w-y|| 0

(w - y )(x - y) ||w-y||
(w - y )x -(w - y )y ||w-y||
-(w - y )y -(w - y )x + ||w-y||

ahora bien, defnase c = -(w - y ) y = ||w-y|| se tiene entonces

cy cx +
del hecho de ser w y se sigue c 0 y > 0.

13

Hasta el momento se ha hecho nfasis en los resultados referentes a las regiones factibles
acotadas, en las cuales se intuye que todo punto puede ser expresado como combinacin
convexa de sus puntos extremos. Este hecho es muy importante, porque ahora que se vean las
regiones no acotadas, se notar que stas se componen de una parte acotada, que puede ser
generada por sus puntos extremos, y una no acotada, que est ligada al concepto de direccin
extrema, el cual se introduce a continuacin. Sin embargo, cuando un problema tiene solucin
finita, esta se encuentra en la regin acotada, de ah la importancia del trabajo desarrollado hasta
ahora.

Definicin: Dado un conjunto convexo, un vector d, distinto de 0, se llama una direccin del

conjunto si, para cada x en el conjunto, el rayo {x+d / >0} tambin pertenece al conjunto. Es
claro que si el conjunto es acotado, entonces no tiene direcciones. Vase la grfica 1.7.
Considrese el conjunto X={ x / Ax=b,
una direccin de X si, y solo si,

, } no vaco. Entonces un vector d distinto de 0 es

A(x+d)=b
.
/
0
+ para cualquier >0
n
(Observacin: en no existe orden, por lo tanto la notacin
,
componentes del vector x son mayores o iguales que 0)
y

significa que todas las

Grfica 1.7

1
Como Ax=b si X , la ecuacin se reduce a Ad=0. Adems como x+d debe ser no
negativo para arbitrariamente grande, entonces d debe ser no negativo. Resumiendo, d es una
direccin de X si, y solo si,
2 4
3
, , , y Ad=0
2
3
(Nota: de acuerdo a la observacin anterior debe ser claro que las dos condiciones

,
4
, no son equivalentes a d > 0)
Se sabe que, por ejemplo, dados dos vectores linealmente independientes en 2 , el conjunto de
todas sus combinaciones lineales coincide con 2 , se dice entonces que los dos vectores
generan todo el espacio. Pero si se limita a las combinaciones lineales de coeficientes

14

positivos, se obtiene nicamente la regin del espacio comprendida entre las dos rectas
obtenidas al prolongar los vectores. En la grfica 1.8 se ilustra este hecho.

Grfica 1.8 Combinaciones lineales con coeficientes no negativos

Definicin: Una direccin extrema de un conjunto convexo es una direccin del conjunto que
no se puede representar como una combinacin lineal positiva de dos direcciones distintas del
conjunto.

Las direcciones extremas ayudan a completar la base para los conjuntos convexos en el
sentido de que, para el caso de los conjuntos no acotados, se necesitan, adems de los puntos
extremos, para expresar cualquier elemento del conjunto. Se ilustra esto grficamente en la
figura 1.9.

Grfica 1.9
En la figura 1.9 el conjunto tiene 3 puntos extremos x1, x2 y x3, y dos direcciones extremas d1 y
d2. El punto x se puede expresar como y ms una de las direcciones del conjunto. Pero y se
puede expresar como combinacin convexa de x1, x2 y x3 y toda direccin del conjunto se
puede expresar como combinacin lineal no negativa de las direcciones extremas. Resumiendo,
todo punto se puede expresar como combinacin convexa de los puntos extremos ms una
combinacin lineal no negativa de las direcciones extremas. Si el conjunto es acotado no tiene
direcciones y se tendr nicamente la combinacin convexa de los puntos extremos. Este
resultado, que se enunciar formalmente y se demostrar ms adelante, es el teorema de

15

representacin y se usar para demostrar que los ptimos se localizan en los puntos extremos.
Se pospone la demostracin para cuando se hayan reunido todos los elementos que esta
requiere.

Teorema 1.7: Los ptimos locales de la funcin objetivo de un programa lineal, son globales.
Demostracin: supngase que xo es un mximo local de
maximizar z = cx
sujeto a
Ax b
x0
si xo no fuese global, existira x1 tal que cxo < cx1. Entonces usando la notacin
x() = (1-) xo + x1 para 0 < < 1

se tiene

c x() = (1-) cxo + cx1 > (1-) cxo + cxo = cxo

como

lim
( ) =
5
6

se tienen puntos mejores que xo en B(xo, ) para cualquier > 0,

esto estara en contradiccin con el hecho de ser xo un mximo local.

Teorema 1.8: Cuando la funcin objetivo de un programa lineal asume su valor mximo o
mnimo, lo hace en un punto extremo del conjunto de soluciones factibles.

Demostracin: considrese el problema

maximizar z = cx
sujeto a
Ax b
x0
Sea x* un punto factible, entonces, por el teorema de representacin, x* se puede escribir como
combinacin convexa de los puntos extremos del conjunto, ms una combinacin lineal no
negativa de las direcciones extremas, o sea

 =

k
i =1

i  8 +

l
j =1

j
7

donde
i =1

i = 1

y adems

i 0, i = 1,2,..., k y

j 0, j = 1,2,..., l

entonces, el problema se transforma en un problema de las variables i, j y se expresara as:

maximizar z=c  =

k
i =1

i
 : +

sujeto a
k
i =1

i = 1

16

l
j =1

j
 9

i 0, i = 1,2,..., k
j 0, j = 1,2,..., l
como las j se pueden hacer arbitrariamente grandes, si cdj > 0 para alguna j, la funcin objetivo
z puede tomar valores tan grandes como se quiera. Si cdj 0 para toda j, entonces se toman
todas las j = 0. Entonces, para maximizar

k
i =1

i
 ; simplemente se determina el mximo cxi

y se toma su correspondiente = 1 y los restantes se igualan a cero. Si el mximo ocurre en ms

de un punto extremo, entonces, cualquier combinacin convexa de ellos es una solucin ptima.
Esto es, si existen ndices i1, i2, . . . , ip tales que

 ? > =
 ? = = ... =
 ? < = z ptimo
entonces cada combinacin convexa de estos puntos es solucin, pues si

= 1
@ 1 + 2
@ 2 + ... + p
@ p
Entonces
o sea

 = 1
 A 1 + 1
 A 2 + ... + 1
 A p

 = 1 z ptimo + 2 z ptimo + ... + p z ptimo = z ptimo

pues 1+2+ . . . +p = 1. Los libros enfocados a ingeniera y administracin solamente

mencionan el caso para p=2, en la segunda parte se muestra un ejemplo con p=3.

1.3 Soluciones Bsicas Factibles

El lector que ya conoce los algoritmos de Programacin Lineal sabe que stos se basan en el
manejo de matrices y debe estar extraado porque hasta el momento el enfoque ha sido
esencialmente geomtrico. Se ha demostrado ya, que el punto ptimo es un punto extremo, pues
bien, el resultado que sigue a continuacin relaciona los puntos extremos con las matrices y
muestra una manera de encontrarlos.

C
Considrese el sistema Ax=b, B , en donde A es una matriz m n y b es un vector.
Supngase que rango(A,b) = rango(A)=m. Despus de un posible rearreglo de las columnas de
A, sea A=[B,N], en donde B es una matriz invertible m n y N es una matriz m ( n m) .
El punto

E

= D

en donde

 G =  F
y  H =

se llama una solucin bsica del sistema. Si  I
, entonces x se llama una solucin bsica
factible del sistema. Las componentes de
J se llaman variables bsicas, y las componentes

 I >
, entonces x se llama solucin bsica

factible no degenerada, y si al menos una componente de
J es cero, entonces x se llama

de
K

se llaman variables no bsicas. Si

solucin bsica factible degenerada. De hecho, la matriz B es una matriz cuadrada que se

17

forma tomando m columnas de la matriz rectangular A. Si se encuentra que esta matriz es

invertible se le puede asociar una solucin bsica. Por cada matriz B invertible que se extraiga
de A se tiene una solucin bsica.
Ahora se demostrar uno de los resultados ms importantes de esta parte del trabajo.

Teorema 1.9: Un punto x es una solucin bsica factible si, y solo si, x es un punto extremo.
C

B , donde A es una matriz m n de rango m, sea

x un punto extremo de la regin factible. Despus de un posible rearreglo de las componentes
de x y de las columnas de A, supngase que x1,x2, . . . ,xp son positivos y que xp+1, . . . ,xn son
cero. Se ver que a1,a2, . . . ,ap son linealmente independientes, procediendo por contradiccin:
supngase que no son linealmente independientes, entonces deben existir escalares c1, c2, . . . ,

Demostracin: dado el sistema Ax=b,

cp, no todos cero, tales que

c  i =
. A partir de este ltimo resultado se construyen otras

i =1 i

dos soluciones factibles x y x as:

x'j =

x j + c j , j = 1,2,..., p
0, j = p + 1,..., n

x''j =

x j c j , j = 1,2,..., p
0, j = p + 1,..., n

Como x j > 0 para j=1,2, . . . ,p, entonces, independientemente de los valores de c1, c2, . . . , cp
se puede escoger >0 tal que x'>
0 y x''j > 0 para j=1,2,... ,p.
j

Como, adems, los cj no son todos cero entonces x x. Adems:

 =

M
O =N

x'j  L =

M
O =N

( x j + c j ) L =

M
O =N

x jL +

M
O =N

c jL =

De manera anloga Ax =b. Por lo tanto, x y x son soluciones factibles diferentes y

x= 1 x + 1 x
2

esto contradice el hecho de que x es un punto extremo. Por lo tanto, a1, a2, . . . ,ap son
linealmente independientes. Ahora bien, como A es de rango m entonces p m, si p=m ya se
tiene el resultado. Si p < m se extraen m p vectores de ap+1,ap+2, . . . ,an tales que junto con
a1,a2, . . . ,ap formen un conjunto linealmente independiente. Despus de un posible rearreglo de
columnas de A, supngase que son ap+1,ap+2, . . . ,am. Entonces se tiene B=[ a1,a2, . . . ,ap,
ap+1,ap+2, . . . ,am] y con esto concluye la demostracin.
Recprocamente, supngase que x es una solucin bsica factible del sistema Ax=b,
B la base correspondiente a x, por lo tanto

=

R


supngase que x=x+(1-)x, en donde 0<<1 y x y x son factibles.

18

P . Sea

Sean
 =

 T
S



y 

=

R



V
U


se sabe que  W
y   X
y como

 R
 Y

+ (1 )

  R
  Y

0<<1

entonces  Z =   Z =
. Por otra parte, b=Ax=Bx B+Nx N=Bx B de donde,

 \ =  [

Por lo tanto se concluye que x B = xB y como  Z =   Z =
, entonces x=x. Anlogamente
x=x y, como consecuencia, se tiene que x es un punto extremo.
El Teorema 1.8 dice que el punto ptimo se encuentra en uno (o unos) de los puntos extremos y
el Teorema 1.9 dice como encontrarlo(s). Por lo tanto, se est ya en condiciones de resolver
problemas de Programacin Lineal.
De la matriz  ]_^a`

se deben extraer todas las submatrices  ]_^a]

(existen

n
m

de tales

submatrices) y verificar si son invertibles, en caso de serlo se resuelve el sistema Bx=b y si

todos los elementos de la solucin son no negativos entonces se ha encontrado una solucin
bsica factible, y por lo tanto, un punto extremo. Se evala la funcin objetivo en cada uno de
estos puntos y se escoge el ptimo. En el caso de que el punto ptimo se encuentre en ms de un
punto extremo se tienen, como ya se dijo, mltiples soluciones, las cuales coinciden con el
conjunto de todas las combinaciones convexas de tales puntos extremos.
Para ilustrar todo esto, se resolver nuevamente el problema con el cual se hizo la introduccin
en el tema:
maximizar z = 200x1+160x2
sujeto a
5x 1+ 3x2 105
70
2x 1+ 4x2
si se introducen las variables de holgura x3 y x4 se tiene
5x1+ 3x2 + x 3
2x1 + 4x2

+x4

= 105
= 70

Por lo tanto la matriz A y el vector b seran

x1

A =

se debe, por lo tanto, extraer las

2
4
2

x2

3
4

x3

x4

105
70

= 6 submatrices de 2x2 y verificar si son invertibles

19


c =

f =

x1 x2

5 3
2 4

x2

d =

x3

3 1

4 0

g =

x1 x
3

5 1

2 0
x2

e =

x4

3 0
4 1

h =

x1 x4

5 0
2 1

x3 x4

1 0
0 1

en este caso las 6 matrices son invertibles y se tiene por lo tanto, por ejemplo, que el sistema
B1x=b tiene como solucin x=B1 i b, que en este caso da como resultado x1=15, x2=10 para un
x1 = [15,10,0,0] , y similarmente para los otros sistemas se obtiene:
x1=35, x3= -70 para un x2 = [35, 0,-70, 0]
x1=21, x4=28 para un x3 = [21,0,0,28]
x2=17

1
1
1
1
, x3=52 para un x4 = [0, 17 , 52 ,0]
2
2
2
2

x2=35, x4=-70 para un x5 = [0,35,0,-70]

x3=105, x4=70 para un x6 = [0,0,105,70]

en este caso son soluciones bsicas factibles no degeneradas x1, x3, x4 y x6. Tomando las dos
primeras componentes de los vectores se obtienen los puntos extremos en 2 [15,10], [21,0],
[0,17

1
] y [0,0], se pueden verificar estos resultados en la grfica 1.1. Ahora, se evala la
2

funcin objetivo en cada uno de los puntos extremos y se tiene:

z[x1,x2 ] = 200x1+160x2
z[0,0] = 0

z[0,17

1
] = 2800
2

z [21,0] = 4200

z[15,10] = 4600

entonces el punto ptimo es [15,10], esto coincide con el resultado obtenido mediante el mtodo
grfico.
El Teorema 1.9 da un mtodo para encontrar los puntos extremos (soluciones bsicas factibles)
sin embargo, an falta garantizar la existencia de tales puntos extremos, esto se har en el
siguiente teorema.

Teorema 1.10: El conjunto X = {x / Ax=b, x 0 } en donde rango(A)=m y X es no vaco,

tiene al menos una solucin bsica factible.

Demostracin: Sea x una solucin factible de la forma x=(x1, . . . ,xp,xp+1, . . . ,xn) en donde

x1, . . . ,xp > 0 y xp+1= . . . =xn=0. Si a1, . . . ,ap son linealmente independientes entonces se les
pueden agregar m-p vectores columna de A tales que los m vectores sean linealmente
independientes y tener as que x es una solucin bsica factible. De lo contrario, existen
escalares c1, . . . ,cp no todos cero, tales que c1a1+ . . . +cpap = 0. Como hay por lo menos un cj
diferente de cero, si es positivo, no se hace nada, si es negativo, se multiplica la ecuacin por -1,
para tener certeza de que hay al menos un cj positivo. Considrese el siguiente punto x:

x'j =

x j c j , j = 1,..., p
0, j = p + 1,..., n

en donde = mnimo

20

xj
cj

/cj > 0 =

xk
para algn k,
ck

de lo anterior se concluye que x 0 y adems x k = 0, por lo x tanto tiene a lo ms p - 1

componentes positivas. Adems
p

 =

j =1

x'j  j =

p
j =1

( x j   j ) j =

p
j =1

x jj 

 j j =

j =1

por lo tanto se ha construido un punto factible x que tiene a lo ms p - 1 componentes

positivas. Si las columnas correspondientes a estas componentes positivas son linealmente
independientes, entonces x es una solucin bsica factible. En caso contrario, el proceso se
repite. Finalmente se obtendr una solucin bsica factible.
El mtodo smplex, que se desarrollar en la segunda parte del trabajo, busca el ptimo yendo
de una solucin bsica factible a otra. En cada paso, a la matriz B correspondiente a la solucin
actual se le reemplaza una de sus columnas por alguna de las de la matriz N, obteniendo as una
nueva matriz B. Sin embargo, se debe garantizar que B es, a su vez, invertible. El teorema que
se presenta a continuacin da una condicin necesaria y suficiente para que esto ocurra.

Teorema 1.11: Sean a1, a2, . . . ,an una base de n y sea a ai, i=1,2, . . . ,n, por lo tanto

=

n
i =1

i
k

entonces a1,a2, . . . ,aj-1,a,aj+1, . . ,an son linealmente independientes si y solo si, j 0.

Demostracin: supngase que a1,a2, . . . ,aj-1,a,aj+1, . . ,an son linealmente independientes y

que, sin embargo, j = 0. Se tendra, por tanto,
=

n
i =1
i j

i
l de donde

n
i =1
i j

i
m 
= 0 lo cual

contradice que a1,a2, . . . ,aj-1,a,aj+1, . . ,an sean linealmente independientes.

n

Recprocamente, supngase que j 0 y que

i =1
i j
n
i =1
i j

i
p 

n
i =1

i
p =

n
i =1
i j

i
n 
= 0 entonces

( i  i 
p j
o = 0

como los a1, a2, . . . ,an son una base y como j 0 , se tiene =0 y i-i=0 para i j,
entonces i=0 para i j y esto termina la demostracin.
Se finaliza esta parte con la demostracin del teorema de representacin, que fue empleado en la
demostracin del Teorema 1.8 el cual, junto con el Teorema 1.9, constituyen los dos resultados
ms importantes de esta primera parte.

1.4 Teorema de representacin

Teorema 1.12 (Teorema de representacin): Dado el conjunto no vaco X = {x / Ax=b,
x 0 }, sean x1,x2, . . . , xk los puntos extremos y d1,d2, . . . , dl las direcciones extremas.
Entonces x X si y slo si, x se puede representar como una combinacin convexa de los
puntos extremos ms una combinacin lineal no negativa de las direcciones extremas, es decir,

=

k
j =1

jq +

l
j =1

j
q donde

k
j =1

j = 1 , j 0 j = 1,2, ...,k y j 0 j=1,2,...,l (*)

21

Demostracin: supngase primero que x se puede representar segn la expresin anterior,

entonces:

 =

k
j =1

j  r +

j =1

j  r =

por lo tanto x X.
Recprocamente, supngase que el rango(A) = rango(A,B) = m, en caso contrario podemos
eliminar todas las restricciones redundantes. Supngase ahora que x X y que sin embargo,
no puede expresarse segn (*). Considrese el siguiente conjunto
k

S = { =

j =1

jq +

j =1

j
q con

j =1

j = 1 , j 0 j = 1,2, ...,k y j 0 j=1,2,...,l}

Como X es no vaco, por el teorema anterior, tiene al menos un punto extremo, por lo tanto S es
no vaco. Se ver que S es un conjunto convexo. Sean u y w que pertenecen a S. Esto es:

=

k
j =1

=

js +

k
j =1

jt +

l
j =1
l

j =1

entonces u + (1-)w =
=
j =1

j =1

( j + (1 ) j )  t +

jt +
l
j =1

j = 1 , j 0 j = 1,2, ...,k y j 0 j=1,2,...,l

j
t donde

j =1
k

j
s donde

j =1
l
j =1

j = 1 , j 0 j = 1,2, ...,k y j 0 j=1,2,...,l

j
t + (1 )

k
j =1

j  t + (1 )

l
j =1

j
t

( j + (1 ) j )
t

donde se tiene
k
j =1

( j + (1 ) j ) = 1 pues

k
j =1

j =1 y

k
j =1

j = 1 , j + (1 ) j 0 j=1, . . .,k

y adems ( j + (1 ) j ) 0 para j=1, . . .,l. Por lo tanto S es convexo. S es adems

cerrado, y por hiptesis x S. Por el teorema del hiperplano de separacin existe un vector
c 0 y un > 0 tales que

 

k
j =1

ju +

l
j =1

j
u + (1)

Como j puede hacerse arbitrariamente grande se debe tener

cdj 0, j = 1, . . . ,l. (2)
Considrese ahora el punto extremo xp definido por
cxp = mximo
 v (3)
1 j k
Tomando p = 1, j = 0 para j p, j = 0 para todo j, la desigualdad (1) se transforma en
cx cxp + (4)

22

Puesto que xp es un punto extremo, entonces, por el Teorema 1.9, se puede representar como

 w 
en donde B es una submatriz de A de tamao mxm invertible y  x 
. Sin prdida



z
de generalidad, supngase que  x  >
. Descomponiendo x en
se tiene Ax = BxB +

y

NxN = b, de donde xB =  {
-
| NxN. Descomponiendo c en cB y cN, se tiene entonces que

cx = cBxB + cNxN = cB  {
+ (cN - cB
| N) xN y cxp = cB  {
. Sustituyendo en (4) se
tiene
cB  {
+ (cN - cB
| N) xN cB  {
+ o sea
(cN - cB
| N) xN > 0
como cada componente de xN es no negativa debe existir al menos una componente j del vector
cN - cB
| N que es positiva y para la cual x j > 0. Haciendo y j =
| a j se tiene entonces que
xj>0y
cj - cB y j > 0 (5)
Se ver que
} y j 0. Supngase
} que y j 0, sea
d = [-y j ,0,0, . . . ,1, . . . ,0] , en donde el 1 aparece en la j-sima posicin. Entonces



~
0

 = [ ] *

= [
~ +
~ ] = 0 adems d 0, d 0

0
Por lo tanto, d es una direccin de X y, adems

cd = [cB,cN] [-y j ,0,0, . . . ,1, . . . ,0] = -cB y j + cj > 0 por (5)

pero este ltimo resultado se contradice con (2). Por lo tanto y j 0.
Constryase ahora el punto x = xp + d, esto es
x =

 
+ d

haciendo b =
| b se tiene

Nota: en esta parte se ha empleado multiplicacin de matrices por bloques, el lector no familiarizado
puede consultar, por ejemplo, la pgina 45 de [Lip85].

23

x =

b'
1

y1 j

b'
m
0

y mj
0

1
0

Como se requiere que x i 0 y tambin que > 0; para los y i j

positivos se debe tener bi - y i j 0, para todo j, por lo tanto
bi / y i j . Se toma entonces
= mnimo { bi / y i j tal que y i j > 0, 1 i m}.
Sea r tal que = br / y r j

entonces Ax = Axp + Ad = b + 0 = b por lo tanto x es factible. Adems x tiene a lo ms m

componentes positivas pues x r = 0. Hgase que en la submatriz B de A, aj reemplace a ar.
Como yrj 0, entonces, por el teorema 1.12, las columnas de B son linealmente
independientes. Por lo tanto x es un punto extremo de X. Ntese tambin que
cx = cxp + cd
puesto que >ycd >0, entonces cx > cxp, lo cual est en contradiccin con (3). Esta
contradiccin demuestra que x se puede representar como una combinacin convexa de puntos
extremos ms una combinacin lineal no negativa de las direcciones extremas.

24

Segunda Parte
_____________

25

2.1 El mtodo smplex

En la parte 1 se vio un mtodo de solucin para el problema
maximizar z = cx
sujeto a

Ax=b,
en donde A es una matriz m n , b es un vector m-dimensional y c y x son vectores ndimensionales. El mtodo consiste en extraer todas las submatrices B m m de A y verificar si
son invertibles. En caso de serlo, se resuelve el sistema Bx=b y, si todos los elementos de la
solucin son no negativos, entonces se ha encontrado una solucin bsica factible. Se evala la
funcin objetivo en cada una de tales soluciones bsicas factibles y se escoge la ptima. La
dificultad para emplear este procedimiento con problemas reales radica en la cantidad de
submatrices que hay que revisar. Como ya se indic, el nmero de tales submatrices es

n
.
m

Por lo tanto, si se enfrenta un problema en el cual n = 50 y m = 30, el cual es, sin embargo,
bastante moderado, se tendran que revisar

50
30

= 47 129.212 243.960 (donde representa

billones) de matrices de tamao 30x30, lo cual constituye, obviamente, una labor irrealizable. El
mtodo smplex, que se desarrolla a continuacin, y que fue expuesto por primera vez, por su
creador George Dantzig, en 1948, optimiza la bsqueda de la solucin reducindola a unas
dimensiones razonables.
El mtodo es iterativo y consiste, en cada iteracin, en pasar de una solucin bsica factible,
asociada a una matriz B, a otra, asociada a una matriz B, en la cual la funcin objetivo presenta
una mejora con respecto a la anterior. Adems, las matrices B y B difieren nicamente en una
columna.
Antes de abordar el desarrollo del mtodo smplex se llamar la atencin acerca de un resultado,
o mejor de su presentacin, del lgebra lineal: en n , n vectores linealmente independientes
(LI) constituyen una base, esto es, cualquier otro vector de n puede expresarse como
combinacin lineal de los elementos de la base, por ejemplo, para 3 se tiene que si

b11

b12

b13

a1

= b21 ,
= b22 y
= b23 son LI y  = a 2 entonces existen escalares

b31
b32
b33
a3
c1, c2 y c3 tales que a = c1b1+ c2b2+ c3b3. Sin embargo, si b1, b2 y b3 son la base
cannica, entonces c1 = a1, c2 = a2 y c3 = a3. Este hecho es importante porque en el trabajo
con el mtodo smplex siempre se tendr B = I, donde I es la matriz identidad cuyas columnas
coinciden con la base cannica de n . Con este resultado en mente, el desarrollo que se
presenta a continuacin es constructivo, esto es, da una justificacin y al mismo tiempo muestra
la manera de realizar los clculos.
Dado el problema
maximizar z = cx
sujeto a

Ax=b,

26

(1)

Las columnas de A se denotarn como a1, a2, . . . , am. Se considera la matriz Amxn =
[Bmxm,Nmx(n-m)], donde B est constituida por columnas linealmente independientes y est

asociada a una solucin bsica factible, esto es,  =  
(ms adelante se muestra como
obtener esta solucin bsica factible inicial). La idea consiste en reemplazar una columna de B
por alguna de las de N y obtener as una mejora en la funcin objetivo. Por su independencia
lineal las columnas de B constituyen una base para n y esta es la razn por la cual se
denomina base a B. Que B sea invertible es equivalente a que puede convertirse en l mediante
operaciones elementales, por lo tanto, como primer paso, se efectan sobre todo el sistema
Ax=b tales operaciones elementales de manera que se obtiene el sistema equivalente Ax=b
donde A = [I,N]. Como este nuevo sistema es equivalente a (1), por comodidad de notacin,
se seguirn empleando A, B, N y b para referirse a A,I, N y b respectivamente. Es importante
notar tambin que ai=ei para i=1, . . .,m donde ei es la i-sima componente de la base
cannica de n . Como las columnas de I constituyen una base de n , cualquier columna ae
de N (la e es porque las columnas de N son las candidatas para entrar a reemplazar a alguna de
las de B) puede escribirse como

ae = a1ea1+ a2ea2+ . . . + ameam =

m
i =1

aie
(2)

tambin debe ser claro que

x = b (3)
que, como ya se dijo, en adelante se notar simplemente b, sin embargo en (3) se escribe b para
resaltar que esta igualdad se cumple cuando se ha hecho B = I.
Si se supone que el vector que se va a sacar de B es el as, entonces (2) se puede reescribir

ae =

m
i =1
is

aie
+ a se

(4)

como ae reemplazar a as, por el teorema 1.11 necesitamos que la componente ase de ae sea
diferente de cero para que el conjunto

a1,a2, . . . ,as-1,ae,as+1, . . ,am

sea linealmente independiente. Adems (4) insina como hacer el reemplazo: simplemente
despejando as

as =

1


a se

m
i =1
is

a ie

as =

1


a se

m
i =1
is

a ie

.
a se

(5)

Se ver que a1,a2, . . . ,as-1,ae,as+1, . . ,an efectivamente estn asociados a una solucin
bsica. La solucin bsica factible BxB = b puede escribirse como
m
i =1

xi  =

que puede, a su vez, reescribirse

27

m
i =1
is

xi  + x s  =

y teniendo en cuenta (5)

m
i =1
is

xi  + x s (

1

a se

m
i =1
is

aie
 )=

a se

reagrupando
m

 xi x s

i =1
is

aie
x
 + s  =

a se
a se

(6)

si se definen

x'
e =

xs
(7)
a se

x'
i = xi x s

aie
= xi x '
e a ie para 1 i m, i s (8)
a se

se tiene
m
i =1
is

x'
i  + x'
e  =

definiendo adems el vector

x = (x1,x2, . . . ,xs-1,0,xs+1, . . . ,xm,0, . . . ,xe, . . . ,0)

se ve que (6) es equivalente a Ax = b, por lo tanto x efectivamente es una solucin bsica que
reordenando est asociada a la submatriz de A [a1,a2, . . . ,as-1,ae,as+1, . . ,an]. Ahora bien,
est permitido hacer operaciones elementales en la matriz A, pues estas generan sistemas
equivalentes. Ntese que[a1,a2, . . . ,as-1,ae,as+1, . . ,an] difiere de I nicamente en la
columna s que ahora est ocupada por ae y, segn (7), el valor de la variable asociada a la
columna que entra es igual al valor que tena la variable asociada a la columna que sale dividido
entre ase que, como ya se vio, debe ser diferente de cero, por (3) se sabe que esto se obtiene
automticamente dividiendo toda la fila s entre ase. Se obtiene as un 1 en la posicin se. De (8)
y de (3) se ve que para i s el valor de x i se obtiene automticamente restando a la fila i la fila s
multiplicada por aie, esto es equivalente a hacer ceros arriba y abajo del 1 ubicado en la
posicin se. Lo anterior justifica la aplicacin que se hace de la eliminacin de Gauss-Jordan en
la matriz ampliada del sistema. Por otra parte, debe notarse que, luego de la realizacin de estas
operaciones elementales, la columna que entr ha quedado igual a la columna que reemplaz (o
sea con un 1 en la posicin s y ceros en las otras posiciones) pues, al ser el algoritmo de tipo
iterativo las condiciones iniciales para cada iteracin deben ser siempre las mismas y en este
caso se ha supuesto que, despus de un posible rearreglo de las columnas de A, B=I al comienzo
de cualquier iteracin.
Sin embargo, an es necesario establecer las condiciones para que x sea una solucin bsica
factible, esto es para que x 0. Se requiere, por lo tanto, que x e 0 y que x i 0 para 1
i m, i s, o lo que es lo mismo

28

xs
0
a se
lo cual implica que a se > 0 pues x s 0 ,

(9)

xi x s

aie
0 para 1 i m, i s
a se

este ltimo resultado se tiene automticamente si a

requiere xi x s

ie

(10)

< 0. Sin embargo, para los aie 0 se

aie
0 para 1 i m, i s. Lo cual es equivalente a
a se
xs
x
i
para 1 i m, i s (11)
a se aie

En este punto es conveniente recordar que se han empleado los subndices s y e para indicar
que se reemplazar la columna s de B por la e de N, pero hasta el momento no se han fijado,
esto es, pueden ser cualesquiera. Sin embargo, al llegar a (11) aparece el primer criterio de
decisin que se debe emplear, en primer lugar debe verse que la condicin i s se hace
redundante y por lo tanto se puede omitir. En segundo lugar indica que una vez fijado e (ms
adelante se ver con que criterio) s no puede ser cualquiera, debe ser tal que satisfaga (11) y esto
se tiene nicamente si se escoge s de acuerdo a la siguiente regla: s debe ser tal que cumpla

xs
x
= mn i / aie > 0
a se
aie

para 1 i m (12)

Se tiene, por lo tanto, una regla que garantiza que x sea una solucin bsica factible. De (12) y
de (3) se ve que la regla (12) equivale a dividir los elementos de b entre los correspondientes de
ae, siempre y cuando estos ltimos sean positivos, y elegir el ms pequeo de estos cocientes.
Esta solucin est asociada a la matriz B, la cual difiere de B en tan slo una columna. Ahora
se debe fijar el criterio que garantice que x es una mejor solucin que x. El mtodo para ello es,
obviamente, estudiar el valor de la funcin objetivo z en x.
Si en (1) se considera la particin x = [xB,xN] correspondiente a la particin Amxn =
[Bmxm,Nmx(n-m)] se obtiene para Ax = b

[B,N]




=

(13)

desarrollando

BxB + NxN = b (14)

pero como xB 0 y xN = 0 se tiene
o

BxB = b
xB =
b (15)

29

que es una solucin bsica de Ax = b. El vector xB se denomina vector bsico y xN, vector no
bsico. Se parte el vector c en [cB,cN] y la funcion objetivo z = cx puede escribirse


=


z = cB xB + cN xN
z = cB xB (16)

z =[cB,cN]

porque xN = 0. Anlogamente, para x se tiene, despus de un rearreglo (en el cual x pasa de

(7) a x = (x 1, . . . ,x s-1, x s =x e ,x s+1, . . . ,x m,0, . . . ,0))

z = c B x B
Pero, cB y c B difieren nicamente en la s-sima componente, esto es

cB = (c1,c2, . . . , cs, . . . , cm)

c B = (c1,c2, . . . , cs, . . . , cm) donde ci = ci para
entonces

i s y cs = ce

z = c B x B
=
=

m
i =1
m
i =1
is

m
i =1
is

c'
i x'
i
c'
i x'
i + c'
s x'
s
ci x '
i + ce x'
e

teniendo en cuenta (7) y (8) queda

m
i =1
is

ci ( xi x s

En la sumatoria de (17) falta el trmino c s ( x s x s

a ie
x
) + ce s
a se
a se

(17)

a se
) que es igual a cero, por lo tanto puede
a se

agregarse sin afectar la expresin. (17) queda entonces:

m

=
i =1
m

=
i =1
m

=
i =1

ci ( xi x s
ci x i

xs
a se

ci x i (

como z = cx y si se define el escalar

30

m
i =1

aie
x
) + ce s
a se
a se
m
i =1

ci aie + ce

ci aie ce )

xs
a se

xs
a se

(18)

ze = cBae =

m
i =1

ci aie para m < e n

(19)

entonces (18) queda

z = z ( z e ce )

por (9) se sabe que

xs
a se

(20)

xs
0 , por lo tanto, para que z sea mayor que z es necesario que
a se

z e c e < 0 y como el objetivo es obtener el mayor incremento debe escogerse e de tal manera
que z e c e sea el ms negativo. Se tiene por lo tanto la regla para escoger el vector que entra a
la base.
De esta regla se deduce que, siempre que exista algn i tal que z i ci < 0 la solucin actual es
susceptible de ser mejorada. Por lo tanto el proceso se detendr cuando, para todo i, z i ci 0
y esto indicar que se ha encontrado la solucin ptima. Establecer este resultado es el propsito
del siguiente teorema.
Antes de enunciarlo se extender la definicin (19)
para i=1, . . . , m z i = cB a i = cB e i = c

y, por lo tanto

z i c i = 0 para i=1, . . . , m
Teorema 2.1: Se ha llegado a la solucin ptima de (1) cuando z i ci 0 para todo i.
Demostracin: sean x una solucin factible

y x una solucin bsica factible de (1)

respectivamente, x asociada a B, entonces

Ax=b
que puede expandirse como

x1a1+ x2a2+ . . .+ xnan = b (21)

y se tiene entonces

z = c1x1+ c2x2+ . . .+ cnxn (22)

Extendiendo (2) a todas las columnas de A se tiene

aj =

m
i =1

31

aij

reemplazando esto ltimo en (21) queda

x1

m
i =1

ai1
+ x2

m
i =1

ai 2
+ . . .+ xn

m
i =1

ain
= b

y reagrupando
n

a1

i =1

x'
i a1i + a 2

i =1

x'
i a 2i + . . . + a m

n
i =1

x'
i a mi = b (23)

esta ltima igualdad expresa a b como combinacin lineal de a1, a2, . . . , am, que son
linealmente independientes y, por lo tanto, tal representacin es nica, y como adems se tiene
BxB = b, entonces
n

x j=

i =1

x'
i a ji , j=1,2, . . . ,m (24).

Si se supone que z i ci 0 para todo i, se tiene z i ci y esto implica z i x'

ci x'
i
i para todo
i. Sumando todas estas desigualdades se obtiene

z1x1+ z2x2+ . . . + znxn c1x1+ c2x2+ . . . + cnxn = z

Utilizando (19) extendido se tiene

x'
1

m
i =1

ci a i1 + x'
2

m
i =1

ci ai 2 + ... + x'
n

m
i =1

ci a in z '

y reagrupando

c1

n
i =1

x'
i a1i + c 2

n
i =1

x'
i a 2 i + ... + c m

n
i =1

x'
i a mi z '

(25)

Teniendo en cuenta (24) se puede expresar (25) como

c1 x1 + c 2 x 2 + ... + c m x m = z z '
por lo tanto, la solucin bsica factible x, para la cual z i ci para todo i, da a la funcin
objetivo un valor mayor o igual que cualquier otra solucin factible. Esto era lo que se quera
demostrar.
Hasta este momento, la idea central de la exposicin ha sido expresar las columnas de N en
trminos de las de de la base B y aplicar los conceptos y operaciones del algebra lineal, sin
embargo, algunos de estos resultados pueden ser reinterpretados desde una perspectiva ms
intuitiva. Se har esta exposicin a continuacin.
Retomando (8)

32

x'
i = xi x s

aie
= xi x '
e a ie para 1 i m, i s
a se

se ve que por cada unidad en que se incremente x e la variable xi sufre un decremento igual a
aie (si aie es negativa, el efecto ser en realidad un incremento). El efecto neto de estos
decrementos (incrementos) sobre la funcin objetivo z = cx ser, por tanto, igual a

m
i =1

ci aie

que, por (19 ), es igual a - ze. Falta, sin embargo, tener en cuenta el efecto sobre z del
incremento de una unidad de xe, que vendra a ser igual a ce. Por lo tanto, el efecto neto total
sobre z, por cada unidad en que se incremente a xe (desde su actual valor de 0) ser

ce - ze = (ze - ce)
en otras palabras, por cada unidad en que se incremente la variable de entrada la funcin
objetivo tendr un incremento (decremento) de (ze - ce) unidades. Como se trata de
maximizar se toma, como ya se dijo, la e que tenga el ze ce ms negativo con el fin de
mejorar el valor de z. Por otra parte, si todos los ze ce son mayores o iguales a cero y existe
algn e tal que ze ce sea igual a cero el incremento de xe desde su valor actual de cero
conduce a otra solucin que tendr, sin embargo, el mismo valor objetivo.
Supngase que se incrementar una variable no bsica xe tal que ze ce es negativo. Por (8)
para las i, 1 i m, tales que aie > 0 cada unidad de incremento de xe implica un
decremento de xi igual a aie, entonces xe podr incrementarse hasta que para alguna i, x i = 0,
pues incrementos superiores a este implicaran que xi asumira valores negativos, lo cual
constituira una violacin a la factibilidad de las soluciones. La primera variable bsica que se
hace 0 al incrementarse xe se llama variable de bloqueo pues bloquea un incremento adicional
de xe. Entonces se tiene que xe entra a la base y la variable de bloqueo sale de ella.
Supngase, como en el caso anterior, que se tiene una solucin factible con valor objetivo zo y
que hay una variable no bsica xe con ze ce < 0, pero que ai 0 para 1 i m, por lo
tanto, no existe variable de bloqueo pues el incremento de xe se refleja en incrementos en los
valores de las variables bsicas o en que estas conserven su valor actual (en el caso, ai = 0). Al
no existir restriccin para el crecimiento de xe esta variable puede asumir valores tan grandes
como se quiera, sin abandonar la regin factible, por lo tanto, se tendra que la solucin x, en
donde  =  
x e , xe es arbitrariamente grande y todas las otras componentes no
bsicas son cero, es factible y su valor objetivo es z = zo (ze ce)xe que tiende a infinito
cuando xe tiende a infinito.

2.2 El mtodo smplex en formato de tabla

Se han visto algunos resultados referentes al mtodo smplex y se ha insinuado, en su momento,
la forma natural como tales resultados se relacionan con las operaciones elementales que se
pueden hacer a la matriz ampliada del sistema. Sin embargo, hasta ahora, los resultados
referentes a los ze ce no se han relacionado con operaciones elementales.Ha llegado el
momento de hacer todas estas relaciones.

33

Supngase que se tiene una solucin bsica factible inicial x relacionada con la base B. El
problema de programacin lineal (1) puede reescribirse como
Maximizar z
Sujeto a

de (26) se tiene

z cBxB cNxN = 0 (26)

BxB + NxN = b (27)
xB, xN 0
xB + B-1NxN = B-1b (28)

multiplicando (28) por cB y sumando con (26) se obtiene

z + (cBB-1N cN)xN = cB B-1b (29)

como xN = 0 de (28) y de (29) se ve que

xB = B-1b = b

(30)

z = cB B-1b = cB b (31)
si se piensa en z como una variable bsica ms y en (29) como una restriccin adicional, se
puede tabular el problema como aparece en la tabla 2.1, en donde el lado derecho (LD)
contendr los valores de las variables bsicas, incluyendo z. Las variables bsicas se
identificarn en la columna de la extrema izquierda (VB).

xN
LD
VB z xB
-1
z 1 0 cBB N cN cB B-1b
Rengln 0
-1
-1
xB 0 I
B N
B b
Renglones 1 a m
Tabla 2.1
Se muestra el contenido de esta tabla con referencias en el trabajo realizado

Funcin objetivo cB B-1b = cBb vase (31)

Valor de las variables bsicas B-1b = b vase (30)
z j c j en el rengln 0 debajo de xB y xN vase (19)
z j c j = 0 para j=1,2, . . . m.

y tngase en cuenta que

Es deseable tener un procedimiento que haga lo siguiente

1. Actualizar las variables bsicas y sus valores
2. Actualizar los valores z j c j
3. Actualizar las columnas a j
Para ello ejecutamos el siguiente algoritmo
1. Se escoge en el rengln 0 la columna e tal que z e c e sea el ms negativo.

2. Si ae 0 xe puede crecer indefinidamente y, por lo tanto, el objetivo ptimo es no

acotado y se detiene el algoritmo. En caso contrario, segn (12), se dividen las entradas

34

de los renglones 1 a m del lado derecho entre las correspondientes de ae que sean
positivas y se escoge el menor de estos resultados, de esta manera se determina la
variable de bloqueo xs.
(Los pasos que siguen consisten en hacer un pivoteo sobre ase, este es el
procedimiento que se realiza al hacer la eliminacin de Gauss-Jordan)

3. Se divide el rengln s por ase

4. Para i=1,2, . . . ,m, i s, se suma al i-simo rengln el nuevo rengln s multiplicado
por - aie.
5. Se suma al rengln 0 el nuevo rengln s multiplicado por ( z e c e)
Las tablas 2.2 y 2.3 representan la situacin inmediatamente antes y despus del pivoteo.
Antes de pivotear

z
XB1

z XB1
XBs
1 0 ... 0 ...
0 1 ... 0 ...

XBs

0 0 ... 1

...

XBm

0 0 ...

...

XBm
0
...
0
...

z XB1
XBs
1
z ce
0.. e
a se

XB1

a1e
0 1 ... a
se

Xe

0 0 ..

XBm

1j

...
...

...

sj

...

...

mj

...

Xe
zece . .
1e
...
se

me

...
...

LD
cBb
b1
bs
bm

Tabla 2.2

Despus de pivotear

Xj
zjcj

1
a se

a me
0 0... a
se

XBm
...

Xj
zjcj

...

.. .

- ( z e c e)

...

...

...

...

...

...

1j

1e

a sj

a sj
a se

a se

Tabla 2.3

35

me

. ..

a se

a sj

mj -

Xe
0

a sj
a se

...

0 ...

...

1 ...

...

0 ...

LD
cBb b'
(zece) s
a se
b1a
bs 1e
a se

b'
s
a se

bma
bs me
a se

Se examinarn las implicaciones del pivoteo

1. La variable Xe entr a la base y XBs sali de la base. Este cambio queda registrado en
la columna de la izquierda, en la cual Xe reemplaz a XBs.
2. El lado derecho (LD) contiene los valores actualizados de las variables bsicas.
Tnganse en cuenta (30), (31),(7), (8) y (20). Hay que recordar que z se est
considerando como una variable bsica adicional.

3. El valor de z

es cero como corresponde a las variables bsicas.

Hacer evidente que los z j c j de las variables no bsicas tambin fueron actualizados
requiere un poco ms de trabajo. De (19) se tiene

zj = cBaj =

m
i =1

ci aij para m < j n

aplicando esta definicin a la tabla resultante despus del pivoteo se obtiene, para las variables
que siguieron por fuera de la base,
m

z j c j =

i =1
is

ci (aij aie

a sj
a se

) + ce

a sj

-cj

a se

El apstrofe es para diferenciar al z j c j actual del z j c

entrada correspondiente a z j c, de la tabla nueva, aparece

z j c j - ( z e c e)

(32)

anterior. Por otra parte, en la

a sj
a se

que, aplicando (19), queda

m
i =1

m
i =1

ci aij c j

i =1

a sj

ci aij aie

m
i =1
is

a se

ci aij a ie

a sj
a se

a sj

ci a ie ce

c j + ce

a se

a sj
a se

c j + ce

a sj
a se

esta ltima expresin, salvo el orden, es idntica a (32).

Resta verificar el resultado para la variable que abandon la base. Se tiene por (19)
m

z s c s = i =1
is

ci

a ie
1
+ ce
c s (33)
a se
a se

36

y tambin, que en la entrada correspondiente a z s c s aparece

z e ce
a se

(34)

aplicando (19) a (34) se tiene

m

i =1

a se
m

=
=

ci a ie ce

i =1
is

ci a ie + c s a se c e
a se

m
i =1
is

ci

a ie
1
c s + ce
a se
a se

que es idntico a (33) salvo por el orden.

Se ha demostrado, por lo tanto, que si se tiene una solucin bsica factible y se dispone la
informacin segn aparece en la tabla 1, escogiendo las variables de entrada y de salida segn
los criterios dados (si no hay variable de entrada es porque la solucin que se tiene es la ptima
y si no hay variable de salida es porque no existe variable de bloqueo y, por lo tanto, el objetivo
se puede hacer tan grande como queramos) se determina ase. Haciendo un pivoteo sobre l se
llega a una nueva tabla en la cual la informacin esta dispuesta nuevamente segn la tabla 1.
Esta nueva tabla contiene , por lo tanto, una nueva solucin bsica factible y su valor para z es
igual al valor para z en la solucin anterior incrementado en una cantidad igual a ( z j c j )
multiplicado por el valor que asumi la variable que entr a la base. Como la situacin es
equivalente a la inicial, el proceso puede repetirse hasta que no existan variables que entren a la
base, y en ese momento, segn el teorema 2.1, se habr encontrado la solucin ptima.
En todo el desarrollo anterior se ha partido del supuesto de que se dispone de una solucin
bsica factible y con ella, de toda la informacin que requiere la tabla 1.
Se ver que existe una clase de problemas para los cuales la obtencin de una solucin bsica
factible inicial es inmediata. La manera de encontrar una solucin bsica factible para los
problemas que no pertenecen a esta clase se ver ms adelante.

2.3 Problemas con solucin bsica factible inmediata

Un problema de la forma
maximizar z = cx
sujeto a
(35)

Ax b,
Tiene una expresin expandida as

37

maximizar z = c1x1+ c2x2+ . . . + cpxp.

sujeto a

a11 x1 + a12 x 2 + ... + a1 p x p b1

a 21 x1 + a 22 x 2 + ... + a 2 p x p b2
a m1 x1 + a m 2 x 2 + ... + a mp x p bm
Que se transforma, mediante la introduccin de las variables de holgura xp+1, . . . ,xn, en
maximizar z = c1x1+ c2x2+ . . . + cpxp+0xp+1+ . . . +0xn
sujeto a

a11 x1 + a12 x 2 + ... + a1 p x p + x p +1 + 0 x p + 2 +

+ 0 x n = b1

a 21 x1 + a 22 x 2 + ... + a 2 p x p + 0 x p +1 + x p + 2 +

+ 0 x n = b2

a m1 x1 + a m 2 x 2 + ... + a mp x p + 0 x p +1 + 0 x p + 2 +

(36)

(37)

+ x n = bm

se tiene por tanto que x=[xp+1, . . . ,xn] =[b1, . . . ,bm] es una solucin bsica factible
asociada a la matriz B = I para la cual se tiene cB = 0 y z = 0. Las variables x1, . . . ,xp, al no
ser bsicas, tienen todas valor cero y cumplen las condiciones para ser solucin de (35). En otras
palabras, un problema que tenga la forma de (35) permite siempre que el vector x = 0 sea una
solucin. No es este el caso de los problemas que presentan en sus restricciones = o ,
estos casos se discutirn posteriormente.
Se reproduce la tabla 2.1 para ver cmo se tabula la solucin bsica factible que permite iniciar
el ciclo de iteraciones (en esta tabla se han intercambiado las columnas que estn debajo de xB y
xN pues esto se acostumbra en la mayora de los libros y es probable que el lector se sienta ms
cmodo con esta presentacin)

VB z
xN
xB LD
-1
Rengln 0
z 1 cBB N cN 0 cB B-1b
-1
-1
Renglones 1 a m
xB 0
B N
I
B b
Tabla 2.1
Si en (36) se transponen trminos queda

z - c1x1- c2x2- . . . - cpxp-0xp+1- . . . -0xn = 0

que expresado nicamente en trminos de coeficientes se convierte en

1 cN +0 = 0 (37)
como cB = 0 en el rengln 0 la expresin cBB-1N cN se reduce a cN. Adems, se tiene
que cB B-1b = 0, por lo tanto la parte

1 cBB-1N cN 0 cB B-1b
38

del rengln 0 de la tabla 2.1 se reduce a

cN 0 0

que coincide exactamente con (37). Adems, como se tiene que B = I, entonces B-1N = N y
B-1b = b.
Entonces la parte

B-1N I B-1b

de los renglones 1 a m de la tabla 2.1 se reduce a

N I b
que coincide exactamente con los coeficientes de (37). La columna VB almacena el nombre de
la variable bsica correspondiente a cada fila. Reuniendo todas estas conclusiones, se tiene que
la tabla 2.1 para el problema (36), (37) queda como aparece en la tabla 2.4

VB
z
xp+1
xp+2
xn

z
1
0
0

-c1
a11
a21

0 am1

xN
-c2 - . . . -cp
a12 . . . a1p
a22 . . . a2p
...
am2 . . . amp

0
1
0
0

xB
0 ... 0
0 . ..0
1 . ..0
...
0 ...1

LD
0
b1
b2
bm

Tabla 2.4
En este estado de cosas se puede comenzar a ejecutar el algoritmo iterativo.
Ejemplo 1: Resulvase por medio del mtodo smplex el siguiente problema
maximizar z = 5x1 + 3x2
sujeto a
3x1 + 5x2 15
5x1 + 2x2 10
x1,x2 0
trasponiendo trminos y agregando variables de holgura se tiene
z - 5x1 - 3x2
3x1 + 5x2 + x3
5x1 + 2x2
+ x4
x1,x2 x3,x4 0

= 0
= 15
= 10

se tabula la informacin anterior en la tabla 2.5 (se omite la columna z pues las operaciones que
se hacen en el pivoteo no la modifican, se agrega la columna bi/aie para almacenar las razones
que se emplean en la regla (12))

39

VB x1 x2
z -5 -3
x3 3 5
x4 5 2

x3 x4 LD
0 0 0 bi/aie
1 0 15
5
0 1 10
2

Tabla 2.5
En este momento se tiene:
Variables bsicas x3 = 15, x4 =10.
Variables no bsicas x1 = 0, x2 = 0.
z = 0.
Como -5 es el ms negativo de los z j c j de las variables no bsicas (x1, x2) x1 entra a la base
y por lo tanto se tiene e=1. Se calcula, entonces, la columna bi/aie. 15/3=5 y 10/5=2 el valor
mnimo es 2, por lo tanto, x4 es la variable de bloqueo que sale de la base y 2 es el valor que
asumir x1. Como x4 est en la fila 2, s=2 (esto se hace as para evitar los reordenamientos de
los que se habla en el desarrollo de la teora y en los cuales se reservan los subndices 1 a m para
las variables bsicas, en este caso m=2 y se tendra, reordenando, que XB1 = x3 y que XB2 =
x4). Por lo tanto se realiza el pivoteo sobre a21. Se tiene la tabla 2.6

VB
z
x3
x1

x1 x2
0 -1
0 19/5
1 2/5

x3 x4 LD
0 1 10 bi/aie
1 -3/5 9
0 1/5 2
Tabla 2.6

Se llama la atencin acerca de los siguientes hechos:

Se ha eliminado la lnea que separaba las variables bsicas de las no bsicas, pues en la
prctica, como ya se dijo, no se reordenan las columnas. Las variables bsicas se
identifican en la columna VB.
Variables bsicas x3 = 9, x1=2. Ntese que sus respectivos z j-c j = 0.
Variables no bsicas x2 = 0, x4 = 0.
z = 10. Este valor es igual al valor anterior de z (0) menos el z j-c j de la variable que
entr a la base (-5) multiplicado por el valor que asumi esta variable (2), o sea 10 = 0
(-5)*2. Otra forma de verificar este resultado es reemplazar los valores actuales de las
variables en la funcin objetivo z = 5x1 + 3x2 + 0x3 + 0x4 = 5*2 + 3*0 +0*9 + 0*0
= 10.

Como el proceso es iterativo, ste se repite, siguiendo las mismas reglas, hasta cuando ocurra
alguno de los eventos mencionados como posibles terminaciones del algoritmo.
Ejemplo 2: Resolver por el mtodo smplex
Maximizar z = 4x1 + 4x2
Sujeto a
-2x1 + 2x2 2
-x1 + 2x2 4
x1, x2 0

40

trasponiendo trminos, agregando variables de holgura y tabulando se tiene la tabla 2.7.

VB x1 x2
z -4 -4
x3 -2 2
x4 -1
2

x3
0
1
0

x4 LD
0 0 bi/aie
0 2
1
1 4
2

Tabla 2.7
se puede escoger entre x1 y x2 para entrar a la base, escogemos x2, al calcular los bi/aie se
tiene 2/2=1, 4/2= 2. Por lo tanto la variable de bloqueo es x3. Se pivotea sobre a12.y se tiene la
tabla 2.8.

VB x1 x2
z -8
0
x2 -1 1
x4 1
0

x3 x4
2
0
1/2 0
-1
1

LD
4 bi/aie
1
*
2
2

Tabla 2.8
y para la siguiente iteracin

VB x1 x2
z 0
0
x2 0 1
x1 1
0

x3
-6
-1/2
-1

x4 LD
8 20 xi/aie
1 3
*
1 2
*

Tabla 2.9
Para esta ltima tabla se tiene que x3 es candidato para entrar a la base, sin embargo a3 0 y
por lo tanto no existe variable de bloqueo para x3. En otras palabra x3 puede hacerse tan grande
como se quiera.
Segn la teora expuesta se tiene como solucin x, en

donde  =  
xe , xe es arbitrariamente grande y todas las otras componentes no

bsicas son cero y su valor objetivo es z = zo (ze ce)xe que tiende a infinito cuando xe
tiende a infinito. Para este caso, sea x3 = M (en donde M puede ser arbitrariamente grande)
entonces

x2 = 3 +
Se ver que la solucin

M
y x1 = 2 + M
2

2 + M ,3 +

M
, M ,0
2

es factible y se calcular z para ella. Esta solucin cumple las restricciones, pues

-2x1 + 2x2 = -2( 2 + M ) +2( 3 +

y

41

M
)= 2 2
2

-x1 + 2x2 =-( 2 + M ) + 2( 3 +

Adems, se tiene

M
) = 4 4
2

z = z0 (ze ce)xe = 20(-6)M = 20 + 6M

que tambin puede ser calculada haciendo el reemplazo de la solucin en la funcin objetivo

z = 4x1 + 4x2 = 4( 2 + M ) + 4( 3 +

M
) = 20 + 6M
2

Es bueno recordar que la teora recomienda hacer entrar a la base la variable xi, tal que, el zi-ci
correspondiente sea el ms negativo, con el fin de obtener la mayor mejora posible en la funcin
objetivo. Sin embargo, no contradice a la teora hacer entrar a la base cualquier variable que
tenga el correspondiente zi-ci negativo. Por lo tanto, debe ser claro que si en alguna iteracin se
tiene que, para algn i, zi-ci es negativo y, adems, ai 0, entonces, al hacer entrar xi a la
base, el valor de la funcin objetivo puede hacerse tan grande como se quiera. Esta aclaracin se
hace porque en algunos libros (vase, por ejemplo, [Hil02] pg 129) se insina que este

hecho ocurre nicamente cuando se trata de la variable que entra a la base segn el
criterio del zi-ci ms negativo. Esta inexactitud tiene como consecuencia que, en algunos casos,

se realicen ms iteraciones de las necesarias.

Ejemplo 3: Resolver por medio del mtodo smplex

Maximizar z = 3x1 + 2x2 + x3
sujeto a:

2x1 + 3x2 + 5x3 17

3x1 + 2x2 + x3 10
x1 + x2 + 7x3 14
x1 0, x2 0, x3 0

se tiene entonces la tabla 2.10

VB
z
x4
x5
x6

x1
-3
2
3
1

x2
-2
3
2
1

x3
-1
5
1
7

x4
0
1
0
0

x5
0
0
1
0

x6
0
0
0
1

LD
0 bi/aie
17 17/2
10 10/3
14 14

Tabla 2.10
pivoteando en a21 se obtiene la tabla 2.11

VB
z
x4
x1
x6

x1 x2 x3 x4
0 0 0 0
0 5/3 13/3 1
1 2/3 1/3 0
0 1/3 20/3 0

x5 x6
1 0
-2/3 0
1/3 0
-1/3 1

42

LD
10 bi/aie
31/3 31/5
10/3
5
32/3 32

Tabla 2.11
Al no existir en la fila cero cantidades negativas, el algoritmo debera detenerse en este
momento, pues, segn el teorema 2.1, ya se ha encontrado una solucin ptima (10/3, 0, 0, 31/3,
0, 32/3) sin embargo, ntese que en el rengln 0 las variables no bsicas x2 y x3 tienen un 0,
esto indica que al entrar a la base no aportarn nada a z, pero esto permitir encontrar una
solucin alternativa, por ello se hace una nueva iteracin en la cual se hace entrar a x2 a la base.
Por lo tanto pivoteando en a22 se tiene la tabla 2.12

VB x1 x2 x3 x4 x5 x6 LD
z 0 0 0 0 1 0 10 bi/aie
x4 -5/2 0 7/2 1 -3/2 0 2
4/7
x2 3/2 1 1/2 0 1/2 0 5
10
x6 -1/2 0 13/2 0 -1/2 1 9 18/13
Tabla 2.12
En esta ltima tabla se tiene la solucin ptima alternativa (0,5,0,2,0,9). Nuevamente hay dos
variables no bsicas con un cero en el rengln 0: x1 y x3, por lo tanto, se realiza otra iteracin en
la cual x3 entra a la base (si se hiciera entrar x1 se regresara a la tabla anterior). Pivoteando en
a13, se tiene la tabla 2.13

VB x1 x2 x3 x4 x5 x6 LD
z
0 0 0 0 1 0
10 bi/aie
x3 -5/7 0 1 2/7 -3/7 0
4/7
x2 13/7 1 0 -1/7 5/7 0 33/7
x6 29/7 0 0 -13/7 16/7 1 37/7
Tabla 2.13
Se tiene una segunda solucin alternativa (0, 33/7, 4/7, 0, 0, 37/7). Si estas 3 soluciones se
restringen a las variables originales del problema, se tienen las siguientes soluciones:

(10/3, 0, 0), (0,5,0) y (0, 33/7, 4/7)

Todas con un valor de z = 10. Segn la teora vista, todas las combinaciones convexas de estas 3
soluciones son, a su vez, soluciones. Por lo tanto se tiene que el vector x = (x1, x2, x3) tal que

x = 1(10/3, 0, 0) + 2(0,5,0) + 3 (0, 33/7, 4/7) donde 1+2+3 = 1

es tambin una solucin ptima. O, lo que es equivalente, la solucin general queda
determinada por

x1 =

10
33
4
1 , x2 = 5 2 + 3 , x3 = 3 , donde 1 + 2 + 3 = 1
3
7
7

se verificar el valor de z para esta solucin general

z = 3x1 + 2x2 + x3

43

10
33
4
1 + 2( 5 2 + 3 ) + 3
3
7
7
= 10 1 +10 2 + 10 3
= 10(1+2+3)
= 10

= 3*

Ahora se hace la comprobacin de que la solucin general satisface la primera restriccin

2x1 + 3x2 + 5x3 17,

pues se tiene
2*

10
33
4
1 + 3*( 5 2 + 3 ) + 5* 3
3
7
7

20
1 + 152 + 173
3

pero como 3 = 1-2-1, se tiene

= 17 + (

20
17)1 2 2 17
3

la verificacin para las desigualdades restantes es similar.

2.4 Problemas sin solucin bsica factible inmediata

Ya se vio que un problema de la forma
maximizar z = cx
sujeto a

Ax b,
tiene a x = 0 como una solucin factible y, que si adems agregamos las variables de holgura, la
solucin [xB,xN] = [B,0] es una solucin bsica factible asociada a la matriz I, la cual queda
constituida por los coeficientes de stas variables. Los valores que ellas asumen, tienen un
significado en los problemas que se atacan. Puede significar, por ejemplo, la cantidad de un
recurso que se deja sin emplear. Sin embargo, en problemas como el siguiente
maximizar z = x1 2x2
sujeto a

x1 + x2
-x1 + x2
x2
x1, x2

2
1
3
0

es evidente que (x1, x2) = (0, 0) no es una solucin factible pues no satisface las dos primeras
restricciones. Por lo tanto, debe encontrarse, de alguna manera, una solucin bsica factible para
poder comenzar a aplicar el mtodo smplex. En esta clase de problemas se procede de la
siguiente manera: en las dos primeras restricciones que son de la forma , se restan las
variables no negativas x3 y x4, las cuales conservan el nombre de holguras (en algunos textos se
conocen como variables de supervit) y en la ltima sumamos x5, con lo que el problema
quedara
maximizar z = x1 2x2

44

sujeto a

x1 + x2 x3
=2
-x1 + x2
- x4
=1
x2 +
x5 = 3
x1, x2, x3, x4, x5 0

(38)

como los coeficientes de las variables de holgura no forman la matriz identidad se debe extraer
una submatriz invertible, para ello debe verificarse que su determinante sea diferente de cero.
Luego se multiplica el sistema por la inversa de esta submatriz y si el lado derecho es no
negativo se tiene una solucin bsica factible. Se ensaya con las 3 primeras columnas, como

1 1

|B| = 1 1
0 1

1 1

0 = 1 entonces B-1 existe y se tiene B-1 = 0 0 1

0
1 1 2

Multiplicando la matriz aumentada del sistema por B-1 queda

1 1

1 1

0 0 1 * 1 1
1 1 2
0 1

0
0

1 0
0 1

1 0 0 1 1

1 = 0 1 0 0 1
3
0 0 1 1 2

3
3

Como los trminos del lado derecho son no negativos se tiene una solucin bsica factible en la
cual x1=2, x2=3 y x3=6 (ntese que x1=2, x2=3 si es una solucin factible del problema
original). Trasponiendo trminos en la funcin objetivo z (z - x1 + 2x2 = 0) el sistema queda
tabulado como aparece en 2.14

VB x1 x2
z -1 2
x1 1 0
x2 0 1
x3 0 0

x3
0
0
0
1

x4
0
1
0
1

x5
0
1
1
2

LD
0 bi/aie
2
3
3

Tabla 2.14
Sin embargo los zj-cj de las variables bsicas x1 y x2 no son cero, por lo tanto mediante
operaciones elementales con los unos de las filas 1 y 2 se hacen ceros en la fila cero y
finalmente se tiene 2.15

VB x1 x2
z 0 0
x1 1 0
x2 0 1
x3 0 0

x3
0
0
0
1

x4
1
1
0
1

x5 LD
-1 -4 bi/aie
1 2
2
1 3
3
2 3 1.5

Tabla 2.15
Ahora si se estn cumpliendo las condiciones para ejecutar el mtodo smplex. Pivoteando en

a35 se obtiene la tabla 2.16

45

VB
z
x1
x2
x3

x1 x2 x3
x4 x5 LD
0 0 1/2 1/2 0 -5/2 bi/aie
1 0 -1/2 1/2 0 1/2
0 1 -1/2 -1/2 0 3/2
0 0 1/2 1/2 1 3/2
Tabla 2.16

y se ha llegado a la solucin.
Este mtodo, sin embargo, resulta bastante engorroso, pues a pesar de que en este caso la
submatriz que se escogi result no singular y, adems, al resolver el sistema se obtuvieron
valores no negativos - por esto no fue necesario hacer ms ensayos-, este no ser siempre el caso
y, por lo tanto, el mtodo empleado no resulta eficiente.
Un mtodo ms eficiente para encontrar una solucin bsica factible inicial consiste en emplear
el propio mtodo smplex para tal efecto. Para ello se introducen las llamadas variables
artificiales, llamadas as porque, a diferencia de las de holgura, no representan nada en el
problema que se est resolviendo, sino que, simplemente se utilizan para encontrar la solucin
bsica factible inicial y luego se eliminan. Uno de los mtodos empleados para hacer salir las
variables artificiales de la base, consiste en penalizarlas en la funcin objetivo con un
coeficiente que en valor absoluto tiende a infinito y, que ser negativo si el problema es de
maximizacin y positivo en el caso de minimizacin. La solucin bsica factible obtenida en la
iteracin en la cual sale la ltima variable artificial queda en trminos de las variables originales
y de las de holgura y, por lo tanto, es una solucin bsica factible para el problema original, que
era lo que se estaba buscando. Se ilustra esta teora resolviendo nuevamente el ejercicio anterior.
Si en (38) se agregan las variables artificiales para completar la base y se penalizan estas nuevas
variables en la funcin objetivo se tiene
maximizar z = x1 2x2 Mx5 Mx6
sujeto a

x1 + x2 x3 +
x5
=2
-x1 + x2
- x4+ x6
=1
x7 = 3
x2 +
x1, x2,x3, x4, x5, x6, x7 0

en donde por esttica se ha renombrado la variable de holgura x5 como x7.

Trasponiendo trminos en la funcin objetivo y tabulando se obtiene la tabla 2.17

VB
z
x5
x6
x7

x1
-1
1
-1
0

x2 x3
2 0
1 -1
1 0
1 0

x4
0
0
-1
0

x5
M
1
0
0

x6
M
0
1
0

x7 LD
0 0 bi/aie
0 2
0 1
1 3

Tabla 2.17
Haciendo ceros en la fila cero para las variables bsicas x5 y x6 queda la tabla 2.18

46

VB
z
x5
x6
x7

x1 x2
-1 2-2M
1 1
-1 1
0 1

x3
M
-1
0
0

x4
M
0
-1
0

x5 x6 x7 LD
0 0 0 -3M bi/aie
1 0 0
2
2
0 1 0
1
1
0 0 1 3
3
Tabla 2.18

En este momento, las variables artificiales x5 y x6 estn en la base y, por sta razn, el punto
(x1,x2) = (0,0) no pertenece a la regin factible del problema original.
Como 2-2M es el coeficiente ms negativo de la fila cero entra x2 y como 1 es la razn mnima
sale x6. Pivoteando en a22 se tiene 2.19

VB
z
x5
x2
x7

x1
1-2M
2
-1
1

x2
0
0
1
0

x3
x4 x5
M 2 -M 0
-1 1
1
0 -1
0
0
1
0

x6
2M-2
-1
1
-1

x7 LD
0 -3M bi/aie
0
1
1/2
0
1
*
1
2
2

Tabla 2.19
La variable artificial x5 an permanece en la base y, por lo tanto, el punto (x1,x2) = (0,1) no es
factible en el problema original, (ntese que no satisface la restriccin 1).
Como 1-2M es el coeficiente ms negativo de la fila cero entra x1 y como 1/2 es la razn
mnima sale x5. Entonces se pivotea en a11 para obtener la tabla 2.20

VB
z
x1
x2
x7

x1
0
1
0
0

x2
0
0
1
0

x3
x4
x5
x6
x7
1/2 3/2 M-1/2 M-3/2 0
-1/2 1/2 1/2
-1/2
0
-1/2 -1/2 1/2
1/2
0
1/2 1/2 -1/2
-1/2
1

LD
-5/2 bi/aie
1/2
3/2
3/2

Tabla 2.20
En este momento las variables artificiales x5 y x6 han abandonado la base y, por lo tanto, el
punto (x1,x2) = (1/2,3/2) pertenece a la regin factible del problema original. Mas an,
(1/2,3/2,3/2) es una solucin bsica factible asociada a la matriz I cuyas columnas aparecen
debajo de las variables bsicas x1,x2 y x7. Se est, segn la teora expuesta, en condicin de
aplicar el mtodo smplex para resolver el problema original, esto se consigue simplemente
suprimiendo las columnas correspondientes a las variables artificiales y aplicando a la tabla
resultante el algoritmo smplex. En todos los libros que consult el autor de este trabajo, no
eliminan estas columnas, sino que continan el proceso con la tabla completa. Cuando se
desarrolla el algoritmo a mano, esto obviamente implica realizar un trabajo superfluo. Es
probable que la razn de obrar as sea que al programar el algoritmo en un computador, no es
necesario hacer que este tenga en cuenta el momento en el cual sali la ltima variable artificial
y, simplemente, contina iterando con la tabla completa.

47

En el ejercicio que se est desarrollando, coincidencialmente, todos los coeficientes de la fila

cero son no negativos y por lo tanto el algoritmo se detiene aqu dando como solucin ptima
x1 = 1/2 x2 = 3/2 y z = -5/2.
En la grfica 2.1 se ven los distintos valores que asumen x1 y x2 hasta alcanzar el punto factible

Grfica 2.1 Trayectoria seguida hasta alcanzar la solucin bsica factible

Se ha reiterado que cuando en un problema de programacin lineal todas las restricciones son de
la forma entonces 0 es una solucin bsica factible asociada a I, la cual queda constituida
por las columnas que corresponden a las variables de holgura. Tambin se ilustr uno de los
mtodos que se emplean para encontrar una solucin bsica factible cuando no todas las
desigualdades son de la forma . A partir del problema original, se plantea un problema
artificial en el cual a las restricciones originales que no son de la forma se suman variables
artificiales para tener as una solucin bsica factible del problema artificial, asociado a la
matriz I, la cual estar constituida por las columnas correspondientes a las holguras que se
suman y a las variables artificiales. Estas variables artificiales se penalizan en la funcin
objetivo de tal manera que el algoritmo smplex las obligue a salir de la base. Cuando en la base
no queden variables artificiales la solucin bsica factible que en ese momento se tenga para el
problema artificial tambin lo ser del original.
Este mtodo busca una solucin bsica factible, que en particular es un punto factible, y lo
encuentra cuando ha salido la ltima variable artificial de la base. Pero qu ocurre cuando el
algoritmo se detiene antes de que hayan salido todas las variables artificiales de la base y ests
tengan un valor positivo?. Lo que sucede es que no existen puntos factibles, esto es, no existe
ningn punto que satisfaga simultneamente todas las restricciones. Ms formalmente

Teorema 2.2: Si [x,xa], donde xa es el vector de variables artificiales, es solucin ptima del
problema artificial y si xa 0, entonces el problema original no tiene puntos factibles.
Demostracin: Supngase que x es una solucin factible del problema original y, por lo
tanto, [x,0] lo es del artificial. Por la optimalidad de [x,xa] se tiene que
cx cx Mxa
pero como se puede tomar M tan grande como se quiera y como adems xa 0 y xa 0 esta
desigualdad no tiene sentido y por lo tanto x no puede ser una solucin factible del problema
original.

48

El mtodo de penalizacin tiene la ventaja de tener un fundamento intuitivo y de consistir, luego

de haber penalizado las variables artificiales y de hacer cero su correspondiente entrada en el
rengln 0, esencialmente en la aplicacin del mtodo smplex ya conocido. Sin embargo, tiene
su taln de Aquiles en el hecho de que para ejecutarse en un computador se asigna un valor
grande a la M y este valor, al hacerse varias iteraciones, puede conducir a la acumulacin de
errores de redondeo. Taha (pgina 88 de [Tah95]) ilustra esta situacin con el siguiente ejemplo:
maximizar z = 0.2x1 +0.5x2
sujeto a

3x1 + 2x2 6
x1 + 2x2 4
x1, x2 0

y afirma que si se resuelve empleando un M = 10 se obtiene la respuesta correcta x1 = 1, x2 =

1.5 con un z = 0.95. Pero que para M = 999 999 da la respuesta incorrecta x1 = 4, x2 = 0 con
un z = 1.18, este ltimo valor ni siquiera es consistente con los valores de x1 y x2. Existe
adems otro inconveniente que se presenta cuando se ejecutan los algoritmos a mano, y es lo
dispendiosa que se vuelve la manipulacin de la M. Para evitar estos inconvenientes, se ha
desarrollado otro mtodo para la eliminacin de las variables artificiales de la base. Este mtodo
se conoce como el de las dos fases y consiste, como su nombre lo indica, en realizar dos fases,
en la primera de las cuales se ignora la funcin objetivo del problema original y se minimiza la
suma de las variables artificiales que, en caso de que la regin factible no sea vaca, llegar a ser
cero y conducir a la salida de las variables artificiales de la base, este hecho implicar que se
ha encontrado una solucin bsica factible y por lo tanto ahora se puede entrar a resolver el
problema original. Este mtodo tambin presenta desventajas: por una parte, como en la primera
fase se ignora la funcin objetivo del problema original, el algoritmo busca una solucin bsica
factible cualquiera, no necesariamente una buena solucin, esto trae como consecuencia que,
probablemente, con este mtodo sea necesario hacer ms iteraciones que con el de la M. Por
otra parte, en la transicin de la fase uno a la dos hay que cambiar de funcin objetivo y por lo
tanto hacer los ajustes necesarios en el rengln 0 para tener los z j c j de las variables bsicas
iguales a cero, adicionalmente se suprimen las columnas de las variables artificiales, pero este
paso, como ya se indic, tambin debera llevarse a cabo al aplicar el mtodo de la M.
Para eliminar los inconvenientes que presenta el mtodo de la M, principalmente el de los
errores de redondeo que llev a la concepcin del mtodo de las dos fases, en este trabajo se
propone una forma de tabulacin alternativa que, por una parte, permite trabajar sin la engorrosa
manipulacin de las M y, por otra, permite programar un algoritmo en el cual no se asignan
valores numricos grandes a la M sino que opera exactamente igual a cuando se desarrolla el
algoritmo de forma manual. La propuesta consiste en emplear dos filas para el rengln 0, la
primera conteniendo los coeficientes de las M, y la segunda para los trminos independientes.
De esta manera, al hacer el pivoteo, cada fila se trata de forma independiente. Para escoger la
variable de entrada se sigue el siguiente procedimiento: mientras existan nmeros negativos en
la fila de los coeficientes de las M se toma el ms negativo de ellos, en caso de presentarse
algn empate, se emplean los nmeros de la fila de trminos independientes, correspondientes a
los coeficientes empatados, para disolverlo. Si el empate continua, se escoge la variable entrante
de forma arbitraria. Cuando ya no hayan cantidades negativas en la fila de los coeficientes de las
M, se busca el ms negativo de entre las cantidades de la fila de los trminos independientes,
correspondientes a las columnas en las cuales la fila de los coeficientes de las M tenga valores
iguales a cero.
Se justifica nicamente la equivalencia del pivoteo al descomponer la fila 0 en dos filas, pues la
regla de entrada, si se examina detenidamente, es idntica a la que se sigue sin la
descomposicin de la fila 0.

49

La tabla 2.21

aM+b cM+d
1
e
Tabla 2.21

representa una situacin simplificada, en la cual slo aparecen, el pivote y una entrada
cualquiera de la misma fila del pivote, con sus correspondientes entradas en la fila cero. Para
hacer un 0, encima del pivote, se multiplica su fila por (aM+b) y se la suma a la fila cero para
obtener 2.22

aM+b(aM+b) cM+de(aM+b)
1
e
Tabla 2.22
que simplificando queda

0 (c-ea)M+deb
1
e
Tabla 2.23
si se aplica la descomposicin de la fila 0 en lugar de la tabla 2.21 se tiene la tabla 2.24

a c
b d
1 e
Tabla 2.24
En la cual la primera fila corresponde a los coeficientes de las M y la segunda a los trminos
independientes. Se hacen ceros en las posiciones ocupadas por a y b, para obtener 2.25

0 c-ea
0 d-eb
1
e
Tabla 2.25
si se compara esta ltima tabla con la tabla 2.23 se ve que los resultados son equivalentes.
Est nueva forma de tabulacin para el mtodo de la M, como ya se dijo, permite que el trabajo
sea puramente numrico y evita los errores de redondeo provenientes de asignar valores
grandes a la M. Por lo tanto, se tiene que, con la nueva tabulacin, el mtodo de la M es ms
eficiente que el de las dos fases y por esta razn, no tiene sentido dedicar esfuerzos a aprender
este ltimo.

50

2.5 Degeneracin
Se presenta degeneracin cuando alguna de las variables bsicas asume el valor cero. La
degeneracin indica la existencia de restricciones redundantes como ilustra el siguiente ejemplo
maximizar z = 3x1 +9x2
sujeto a

x1 + 4x2 8
x1 + 2x2 4
x1, x2 0

que tiene la siguiente grfica 2.2.

Grfica 2.2 Presencia de restricciones redundantes

Y la siguiente sucesin de tablas smplex

VB x1 x2 x3
z -3 -9
x3 1
4
x4 1
2

x4 LD
0 0 0 bi/aie
1 0 8
2
0 1 4
2

Tabla 2.26
VB x1 x2
z -3/4
x2 1/4
x4 1/2

x3 x4 LD
0 9/4 0 18 bi/aie
1 1/4 0 2
8
0 -1/2 1 0
4
Tabla 2.27

VB x1 x2 x3 x4 LD
z 0 0 3/2 3/2 18 bi/aie
x2 0 1 1/2 -1/2 2
x4 1 0 -1
2 0
Tabla 2.28
51

esta ltima es la tabla ptima.

Se tienen las siguientes observaciones

La degeneracin surge por la presencia de restricciones redundantes, esto es,

restricciones que pueden eliminarse sin que cambie la regin factible. De esto se deduce
que puede replantearse el problema, eliminando la restriccin redundante y con ello la
degeneracin, sin embargo, en problemas de ms de tres dimensiones es difcil
determinar las restricciones redundantes.

En la tabla 2.26 se ve que hay un empate entre las variables que entran a la base,
siempre que esto ocurre la tabla siguiente tiene una solucin bsica factible degenerada,
pues al existir, al menos dos variables de bloqueo, una sale de la base y la otra
permanece, pero con un valor de 0.

En la tabla 2.28 se llega a una solucin ptima degenerada despus de que apareciera la
degeneracin en la tabla 2.27, sin embargo, esto no es una constante pues existen
problemas como:
maximizar z = 3x1 + 2x2
sujeto a

4x1 + 3x2 12
4x1 + x2 8
4x1 - x2 8
x1,x2 0

el cual, luego de pasar por una degeneracin temporal en la primera iteracin llega, en
la segunda, a la solucin ptima no degenerada:

x1 = 3/2,

x2 = 2

z = 17/2

Generalmente cada iteracin del smplex lleva a un nuevo valor de z mejor que el
anterior, sin embargo, este no es el caso cuando hay degeneracin, como se puede ver
en las tablas 2.27 y 2.28. Este hecho, el de que no exista modificacin para z en
sucesivas iteraciones, puede llevar al caso extremo del ciclado, el cual consiste en que,
luego de algunas iteraciones, se llega a una tabla que ya se haba tenido en el proceso, lo
cual, si se siguen los mismos pasos, llevara a un ciclo infinito. Aunque existen mtodos
para evitar el ciclado (vase, por ejemplo, [Baz96] pgina 170 y siguientes) una forma
menos complicada de hacerlo es elegir de manera diferente la variable de entrada que
llev al ciclado (vase, por ejemplo, [Hil02] pgina 129).

52

Conclusiones
Detrs de todo algoritmo matemtico, desde la multiplicacin de nmeros de varias
cifras, hasta el entrenamiento de redes neuronales, existe un teora que justifica cada
uno de los pasos. El conocimiento de sta teora no es necesario para ejecutar los
algoritmos, una demostracin contundente de esta afirmacin son todos los que ejecutan
los computadores. Sin embargo, el desconocimiento de la teora s impide mejorar, o
adaptar, los algoritmos existentes o crear nuevos algoritmos.
En la comprensin del algoritmo smplex, que fue el propsito de este trabajo, hay que
resaltar la importancia de resultados como el teorema 1.9, que relaciona el enfoque
geomtrico con las matrices, mediante la definicin de soluciones bsicas factibles. El
hecho de que los libros enfocados a la Ingeniera no presenten este resultado, y algunos
otros, como algunas conclusiones sobre convexidad y el teorema de representacin (aun
sin demostracin) es la causa, al parecer del autor, de que tales libros no logren ser
convincentes en los intentos que hacen de presentar una justificacin terica. Tampoco
ayuda el proceso de decremento en la enseanza del Algebra Lineal que estamos
viviendo, pues aunque las demostraciones vistas en este trabajo son sencillas en esencia,
a pesar de que algunas puedan resultar extensas, es necesario poseer conocimientos
elementales como: los conceptos de independencia lineal, base etc., y el producto de
matrices por bloques.
La programacin lineal es la puerta de entrada al extenso campo de la Investigacin de
Operaciones, que constituye una de las reas de la matemtica aplicada ms interesantes
y tiles de la actualidad. Por alguna razn, en este momento los trabajos de grado de la
Fundacin se estn enfocando hacia esta rea y esto me parece bueno, porque la
situacin futura del pas nos llevar a enfrentarnos con naciones que aplican este tipo de
conocimientos a cada una de las empresas en las cuales se comprometen, y han
demostrado que constituye una herramienta efectiva.
El terreno ganado en comprensin terica es pequeo, pero desde l se puede continuar
la exploracin de los grandes espacios que an falta conquistar. El matrimonio
matemticas-informtica que est en las fundamentos de la concepcin de la carrera de
matemticas en la Fundacin, puede encontrar en la Investigacin de Operaciones un
rico filn, y puede constituirse en el fuerte del perfil del futuro profesional. Adems,
esto estara en consonancia con el postgrado que ofrece la Fundacin en esta rea.

53

Bibliografa

1. [Apo77] Apostol Tom, Anlisis matemtico, Barcelona Espaa: Revert

(1977).
2. [Baz96] Bazaraa Mokhtar, Programacin lineal y flujo en redes, Mjico,
D.F.: Limusa (1996).
3. [Hil02] Hillier Frederick, Investigacin de Operaciones, Mjico, D.F.:
McGraw-Hill (2002).
4. [Lip85] Lipschutz Seymour, lgebra lineal, Naucalpan de Jurez, Edo. de
Mjico: McGraw-Hill (1985).
5. [Pra00] Prawda Juan, Mtodos y modelos de Investigacin de Operaciones,
Mjico, D.F.: Limusa (2000).
6. [Tah95] Taha Hamdy, Investigacin de Operaciones, Mjico, D.F.:
Alfaomega (1995).

54