Capı́tulo 2

Análisis teórico del problema

En este capı́tulo se analiza el problema de programación lineal desde un pun-

to de vista geométrico. En el capı́tulo anterior se observaba cómo en un mismo
problema, variando los coeficientes de la función objetivo, se obtenı́an distin-
tas soluciones; sin embargo, en el caso en que exista solución óptima, siempre
hay una solución óptima en un ”vértice”del conjunto S de soluciones factibles.
La idea de ”vértice”se corresponde con el concepto de punto extremo de un
conjunto convexo.
Se definen los conceptos de conjunto convexo y de punto extremo. Se carac-
terizan los puntos extremos del conjunto convexo S. Se demuestra asimismo que
siempre que exista alguna solución factible, existirá al menos un punto extremo.
La solución factible asociada a un punto extremo de S se denominará solución
básica.
Para el caso en que S no esté acotado, se introducen los conceptos de direc-
ción y dirección extrema en un conjunto convexo, ası́ como la correspondiente
caracterización de las direcciones extremas de S.
Termina el capı́tulo con el teorema de representación del conjunto S y sus
implicaciones en el problema de programación lineal. Todos los resultados con-
ducentes a la demostración de este teorema, incluida la propia demostración, se
detallan en una sección independiente.
I.O. Introducción 28 Análisis teórico del problema

2.1. El conjunto de soluciones factibles (S). Solu-

ción básica factible
Dado un problema de programación lineal en su forma estándar

M in ct x
Ax =b
x ≥0

El análisis geométrico del conjunto de soluciones factibles

S = {x ∈ IRn / Ax = b, x ≥ 0}

se basa en considerar la matriz A ∈ Mm×n de restricciones como un conjunto

de n vectores del espacio vectorial IRm :

A = {a1 , a2 , . . . , an }

donde ⎛ ⎞
a1j
⎜ ⎟
⎜ a2j ⎟
⎜ ⎟
aj = ⎜ . ⎟ ∀j ∈ {1, . . . , n}
⎜ .. ⎟
⎝ ⎠
amj

Observación 2.1. Se supondrá que no hay redundancia en el sistema de ecua-

ciones asociado a la matriz A, es decir

rg(A) = m

En el capı́tulo 4 se analizará el caso general, que debe incluir la posible

redundancia del sistema de ecuaciones.

Por ser rg(A) = m, existe una submatriz cuadrada B ∈ Mm×m no singular,

es decir, |B| =
 0. A dicha submatriz cuadrada se la denomina base por identificar
un conjunto de m vectores linealmente independientes del espacio vectorial IRm .
En consecuencia, cualquier vector de IRm , y en particular, cualquier vector
columna de A, aj con j ∈ {1, . . . , n}, puede ser obtenido como combinación
lineal de los vectores columna de una base B.
El conjunto de soluciones factibles (S). Solución básica
I.O. Introducción
factible 29

Tiene sentido, pues, el denotar como B ⊂ A la selección de una base B for-

mada por m columnas de la matriz A ∈ Mm×n . Se determina ası́ una partición
de la matriz A según:

A = (B, N ) B ∈ Mm×m N ∈ Mm×(n−m)

Considerando que a cada una de las n columnas de la matriz A se asocia

una componente del vector x ∈ IRn , cualquier subconjunto de columnas de la
matriz A determina un subconjunto de componentes de x. Por consiguiente,
al seleccionar una base B ⊂ A, la descomposición A = (B, N ) determina una
partición del vector x ∈ IRn según

xB
x=
xN

donde a las componentes de xB ∈ IRm se las denomina básicas y a las de

xN ∈ IRn−m se las denomina secundarias o no básicas.
Con el siguiente ejemplo se ilustra la descomposición de la matriz A.

Ejemplo 2.1. Sea A la matriz de restricciones de un problema de programación

lineal con n = 5 variables y m = 3 restricciones :
⎛ ⎞
2 3 1 −1 0
⎜ ⎟
A=⎜
⎝ 0 0 0 −2 −2 ⎟
⎠
3 3 0 −2 −2

Se puede comprobar que rg(A) = 3, de forma que si se elige como base

⎛ ⎞
2 0 1
⎜ ⎟
B = (a1 , a5 , a3 ) = ⎜
⎝ 0 −2 0 ⎟
⎠
3 −2 0

se ha determinado la descomposición A = (B, N ), siendo

⎛ ⎞
3 −1
⎜ ⎟
N = (a2 , a4 ) = ⎜
⎝ 0 −2 ⎟
⎠
3 −2

De esta forma, el vector solución xt = (x1 , x2 , x3 , x4 , x5 ) se descompone

I.O. Introducción 30 Análisis teórico del problema

según
xt = (xtB , xtN )

siendo
xtB = (x1 , x5 , x3 ) xtN = (x2 , x4 )

Por comodidad de notación, se supondrá que las columnas de B son las m

primeras

xtB = (x1 , . . . , xm ) xtN = (xm+1 , . . . , xn )

Esta hipótesis no supone ninguna restricción real, puesto que siempre se

pueden reordenar las columnas de la matriz A de forma apropiada.
A partir de la partición de las columnas de la matriz A = (B, N ), tiene sen-
tido definir un tipo particular de soluciones para el problema de Programación
lineal.

Definición 2.1. Dado el problema de programación lineal:

M in ct x
Ax =b
x ≥0

se dice que x ∈ IRn es una solución básica cuando existe una base B ⊂ A, tal
que las variables secundarias son nulas, es decir:
 
xB B −1 b
x= =
xN 0

Conviene observar que en esta definición no se ha exigido que las componen-

tes básicas sean mayores o iguales que cero, por lo que una solución básica no
es necesariamente una solución factible. Hay que exigirlo adicionalmente y tiene
sentido, pues, la siguiente definición.

Definición 2.2. Dado un problema de programación lineal en su forma estándar,

fijada una base B ⊂ A, la solución básica asociada es una solución básica factible
si verifica, además, que B −1 b ≥ 0.
Puntos extremos de S I.O. Introducción 31

2.2. Puntos extremos de S

Una propiedad fundamental del conjunto S ∈ IRn es la de ser convexo.

Definición 2.3. Un conjunto C ⊂ IRn , C = ∅, es un conjunto convexo si

λx + (1 − λ)y ∈ C ∀x, y ∈ C ∀λ ∈ [0, 1].

La combinación lineal no negativa cuyos coeficientes suman 1 se denomina

combinación lineal convexa.

Por inducción se demuestra que la combinación lineal convexa de k puntos

de un convexo C pertenece al conjunto, es decir, dados {x1 , . . . , xk } ⊂ C, para

k
cualquier (λ1 , . . . , λk ) tal que λj ≥ 0 ∀j ∈ {1, . . . , k} y j=1 λj = 1, se verifica:

k

λj x j ∈ C
j=1

A continuación se demuestra que el conjunto de soluciones factibles de un

problema de programación lineal es convexo.

Proposición 2.1. El conjunto S = {x ∈ IRn / Ax = b, x ≥ 0} es convexo.

Demostración:
Dados x1 , x2 ∈ S y dado un λ ∈ (0, 1) se define el vector x = λx1 +(1−λ)x2 .
Para demostrar que x ∈ S es suficiente comprobar que x ≥ 0, lo que se
concluye al serlo x1 y x2 y, por otra parte, hay que comprobar que Ax = b :

Ax = A(λx1 + (1 − λ)x2 ) = λAx1 + (1 − λ)Ax2 = λb + (1 − λ)b = b

Por definición de convexidad, dados dos puntos de un convexo, cualquier

punto situado en el segmento que los une, debe pertenecer al conjunto. Dicho
de otra forma, el punto que resulta de la combinación es ”soportado”por sus
extremos. ¿Existen puntos que no son ”soportados”por ningún otro punto? En
un cuadrado en IR2 , por ejemplo, cualquiera de sus vértices no se puede poner
como combinación lineal convexa de puntos diferentes del cuadrado.
Con esta idea se introduce el concepto de punto extremo.
I.O. Introducción 32 Análisis teórico del problema

Definición 2.4. Dado un conjunto convexo C ⊂ IRn , se dice que x ∈ C es un

punto extremo de C si verifica lo siguiente:

x = λy + (1 − λ)z, 0 < λ < 1, y, z ∈ C ⇒ x=y=z

A continuación se caracterizan los puntos extremos del conjunto de solucio-

nes factibles del problema de programación lineal, que coinciden con las solu-
ciones básicas factibles.

Teorema 2.1. Dado S = {x ∈ IRn / Ax = b, x ≥ 0}, donde A es una matriz

m × n y rg(A) = m, entonces,

x̄ es punto extremo de S ⇐⇒
 
x̄B B −1 b
 0, B −1 b ≥ 0 tal que x̄ =
∃B ⊂ A tal que |B| = =
x̄N 0

Demostración :
 
x̄B B −1 b
 0 y B −1 b ≥ 0 y x̄ =
⇐ Sea A = (B, N ), donde |B| = =
x̄N 0
Según se comentó anteriormente, las componentes básicas son las m pri-
meras.
Supongamos que x̄ = λx̄1 + (1 − λ)x̄2 x̄1 , x̄2 ∈ S, siendo 0 < λ < 1.
Descomponiendo x̄1 y x̄2 en las componentes básicas y secundarias, se
tiene:

   
x̄B B −1 b x̄1B x̄2B
x̄ = = =λ + (1 − λ)
x̄N 0 x̄1N x̄2N

Al ser x̄1N , x̄2N ≥ 0 y λ, (1 − λ) > 0, se deduce que x̄1N = x̄2N = 0 ∈ IRn−m

Por otra parte, x̄1 y x̄2 son soluciones y, por consiguiente,


1 x̄1B
Ax̄ = (B, N ) = Bx̄1B + N 0 = b
0

2 x̄2B
Ax̄ = (B, N ) = Bx̄2B + N 0 = b
0
Puntos extremos de S I.O. Introducción 33

de donde se deduce que

x̄1B = x̄2B = B −1 b

Se ha demostrado ası́ que x̄ = x̄1 = x̄2 y que, por tanto, x̄ es un punto

extremo.

⇒ Sea x̄ un punto extremo de S. Sin pérdida de generalidad, se puede suponer

que las coordenadas positivas son las k primeras, de forma que

x̄t = (x̄1 , . . . , x̄k , 0, . . . , 0) x̄j > 0 ∀j = 1, . . . , k 0≤k≤n

No se excluye la posibilidad de que k = 0, es decir x̄ = 0. En este caso,

sin embargo, el resultado que sigue es obvio al considerar que el conjunto
{aj , j = 1, . . . , k} = ∅.
Los vectores {aj , j = 1, . . . , k}, asociados a dichas componentes positivas,
son linealmente independientes, puesto que, en caso contrario, existirı́a un
conjunto de coeficientes {λ1 , . . . , λk } no todos nulos tales que

k

λj aj = 0
j=1

y a partir de estos coeficientes, si se construye el vector

λt = (λ1 , . . . , λk , 0, . . . , 0) ∈ IRn

siempre se podrı́a determinar una cantidad α > 0 suficientemente pequeña

para que, con los vectores x̄ y λ, se construyeran dos soluciones factibles
x̄1 y x̄2 :

x̄1 = x̄ + αλ ≥ 0 Ax̄1 = Ax̄ + αAλ = b

x̄2 = x̄ − αλ ≥ 0 Ax̄2 = Ax̄ − αAλ = b

Por tanto, x̄1 , x̄2 ∈ S. Además, al ser α > 0 y λ = 0, x̄1 = x̄2 , y

I.O. Introducción 34 Análisis teórico del problema

1 1 1 2
x̄ = x̄ + x̄
2 2

serı́a una combinación lineal convexa no trivial, lo que es imposible por

ser x̄ un punto extremo.
Se ha llegado a una contradicción y queda demostrado ası́ que el conjunto
{aj , j = 1, . . . , k} es linealmente independiente.

Al ser {aj , j = 1, . . . , k} linealmente independiente, se deduce que k ≤ m

y, recordando que rg(A) = m, siempre se puede encontrar un conjunto de
m − k vectores adicionales aj elegidos del conjunto {ak+1 , . . . , an } para
completar una base B. El resto de vectores columna forman la matriz N .
Al reordenar las componentes de x̄ según x̄B y x̄N , siendo

x̄tB = (x̄1 , . . . , x̄k , 0, m−k

. . . , 0)t ≥ 0 x̄tN = (0, . . . , 0)

Al ser x̄ solución factible, se verifica:


x̄B
Ax = (B, N ) =b
0

Se concluye ası́ que:

 
x̄B B −1 b
x̄ = =
x̄N 0

El número de puntos extremos es finito, ya que está acotado por


n n!
=
m m!(n − m)!

que es el máximo número de bases B ⊂ A que se pueden determinar.

Se concluye ası́ que las soluciones básicas factibles de un problema de progra-
mación lineal son los puntos extremos del conjunto convexo S de sus soluciones
factibles.
Puntos extremos de S I.O. Introducción 35

Otra cuestión interesante es si se puede garantizar la existencia de, al menos,

un punto extremo. En la proposición siguiente se asegura la existencia de puntos
extremos cuando el conjunto de soluciones factibles sea no vacı́o. Considerando,
según se ha visto en el teorema 2.1, que un punto extremo de S tiene al menos
n − m componentes nulas, la demostración de la proposición siguiente parte de
una solución factible x̄ que se va transformando en otra solución factible con
una componente nula más, y este proceso se repite hasta conseguir al menos
n − m componentes nulas y determinar ası́ un punto extremo.

Proposición 2.2. Si S = {x ∈ IRn / Ax = b, x ≥ 0} = ∅, donde A es una

matriz m × n y rg(A) = m, entonces, existe al menos un punto extremo.

Demostración :
Al ser S no vacı́o, sea x̄ ∈ S una solución factible. Siempre se pueden reor-
denar las coordenadas de forma que las k primeras, siendo 0 ≤ k ≤ n, sean
positivas: x̄t = (x̄1 , . . . , x̄k , 0, . . . , 0).
Sea p = rg(a1 , . . . , ak ) el rango de los vectores columna de A asociados a
estas componentes positivas. Hay dos opciones:

p = k En este caso, {a1 , . . . , ak } es linealmente independiente, por lo que k ≤ m

y, al ser el rg(A) = m, se puede ampliar el conjunto anterior hasta formar
una base B. La solución factible x̄ es, pues, un punto extremo por el
teorema 2.1 y terminarı́a la demostración.

p < k En este caso, {a1 , . . . , ak } es linealmente dependiente y existe una combi-

nación lineal no nula (α1 , . . . , αk ) = (0, . . . , 0) tal que

k

αj aj = 0
j=1

Sea r ∈ {1, . . . , k} un ı́ndice tal que αr > 0. La existencia de este ı́ndice r

está garantizada al ser el vector α = 0 y, en el caso en que αj ≤ 0 ∀j, serı́a
suficiente con multiplicar por −1 todos estos coeficientes para convertirlos
en no negativos y siempre se podrı́a elegir un αr > 0. Posteriormente se
seleccionará el r adecuado.
Al ser x̄ solución, Ax̄ = b, y al sustituir
I.O. Introducción 36 Análisis teórico del problema

k
1 
ar = − α j aj
αr j=1
j=r

se tiene

n
 k
 k
 k
1 
b= aj x̄j = aj x̄j = aj x̄j − αj aj x̄r
j=1 j=1 j=1
αr j=1
j=r j=r

Reagrupando los factores de aj se obtiene:

k
 αj
b= aj (x̄j − x̄r )
j=1
αr
j=r

Observando esta ecuación y denominando

αj
x̄j ≡ (x̄j − x̄r ) ∀j = 1, . . . , k
αr

se deduce que x̄ es una solución con al menos una componente nula más
que x̄, puesto que x̄r = 0. Para garantizar que x̄ sea solución factible hay
que elegir el subı́ndice r adecuadamente; para ello, basta observar las dos
posibilidades respecto los αj :

• αj > 0

αj x̄j x̄r
(x̄j − x̄r ) ≥ 0 ⇐⇒ − ≥0
αr αj αr

Por lo que es suficiente con elegir el subı́ndice r verificando:

x̄r x̄j
≡ M in{ /αj > 0}
αr αj
• αj ≤ 0

αj
x̄j = (x̄j − x̄r ) ≥ x̄j ≥ 0
αr
Ası́ pues, la solución x̄ es factible y tiene menos componentes positivas
que x̄.
Puntos extremos de S I.O. Introducción 37

La demostración continúa considerando x̄ = x̄ y volviendo al principio.

Como en cada uno de los ciclos ası́ formados disminuye, al menos en uno,
el número de coordenadas positivas, el proceso necesariamente terminará
en algún momento en el caso p = k y se obtendrı́a la correspondiente
solución factible que es un punto extremo de S.

Ejemplo 2.2. Determinar los puntos extremos del conjunto de soluciones fac-
tibles asociadas al PPL cuya matriz A de coeficientes y vector b de términos
independientes son:
 
1 −3 −4 5
A= b=
0 2 1 7

Hay tres bases posibles:

 
1 −3 1 3/2
1. B1 = B1−1 =
0 2 0 1/2
 
1 −4 −1 1 4
2. B2 = B2 =
0 1 0 1
 
−3 −4 −1 1/5 4/5
3. B3 = B3 =
2 1 −2/5 −3/5

Hay que comprobar si B −1 b ≥ 0 para ver si las soluciones son factibles:

   
5 31/2 5 33
B1−1 = ≥0 B2−1 = ≥0
7 7/2 7 7
 
5 33/5
B3−1 = ≥ 0
7 −31/5

Sólo los dos primeros vectores tienen todas las componentes mayores o igua-
les que 0 y son, por tanto, soluciones básicas factibles; geométricamente, corres-
ponden a los dos puntos extremos del conjunto de soluciones factibles:
I.O. Introducción 38 Análisis teórico del problema

⎛ ⎞ ⎛ ⎞
31/2 33
⎜ ⎟ ⎜ ⎟
x1 = ⎜ ⎟
⎝ 7/2 ⎠ ; x2 = ⎜ ⎟
⎝ 0 ⎠
0 7

Se puede observar cómo el conjunto de soluciones factibles es un segmento

en IR3 , que es la intersección de los dos planos:

x1 − 3x2 − 4x3 = 5

2x2 + x3 = 7

definidos por cada una de las restricciones. Los extremos de dicho segmento son
los citados puntos extremos y cualquier solución factible se puede expresar como
combinación lineal convexa de ambos.

Directamente de la proposición 2.2 se deduce el siguiente corolario.

Corolario 2.1. Si el conjunto S de soluciones factibles de un problema de

programación lineal no tiene puntos extremos, entonces S = ∅.

Dicho de otra forma, si al analizar todas las soluciones básicas, ninguna de

ellas es factible, el problema de programación lineal no tiene solución factible.

Hay que observar cómo a partir de los puntos extremos del conjunto S se
pueden generar por combinaciones lineales convexas otras soluciones factibles
para el problema P .

2.3. Direcciones extremas de S

El conjunto de soluciones factibles de un problema de programación lineal
no tiene por qué ser acotado. El siguiente ejemplo ilustra esta situación.

Ejemplo 2.3.

M in x1 −x2 −x3
x1 −x2 +x3 = 1
−2x1 −x2 +x3 = 1
xj ≥ 0 ∀i = 1, 2, 3
Direcciones extremas de S I.O. Introducción 39

Al analizar el conjunto de soluciones factibles de este ejemplo, cuya matriz

A de coeficientes y vector b de términos independientes son:
 
1 −1 1 1
A= b=
−2 −1 1 1

se observa que sólo hay un punto extremo

x̄t = (x̄1 , x̄2 , x̄3 ) = (0, 0, 1)

Sin embargo, el conjunto S no es acotado, según se puede observar en la

figura 2.1.

x3

x2
x1

Figura 2.1: Conjunto S del ejemplo 2.3

Además, al existir sólo un punto extremo, difı́cilmente se podrán obtener

más puntos con combinaciones lineales convexas de puntos de S. Es necesario,
pues, introducir el concepto de dirección de un conjunto convexo.

Definición 2.5. Dado un conjunto convexo C ⊂ IRn , C = ∅, un vector d ∈ IRn ,

d = 0 es una dirección de C si se verifica la siguiente propiedad:

∀x ∈ C, ∀μ ≥ 0 x + μd ∈ C

Dos direcciones de C, d1 y d2 , son equivalentes, y se denota por d1 d2

cuando sean los vectores proporcionales con una constante positiva, es decir,
d1 = αd2 , con α > 0.
I.O. Introducción 40 Análisis teórico del problema

Obviamente, si un conjunto C ⊂ IRn admite una dirección, no está acotado.

En el ejemplo 2.3 existe una dirección, dt = (0, 1, 1), que coincide con la
dirección de la semirrecta definida por el conjunto S.

No es difı́cil demostrar que la combinación lineal no negativa de direcciones

de un conjunto convexo C es una dirección de C, es decir, si d1 y d2 son dos
direcciones de C, entonces λ1 d1 +λ2 d2 es también una dirección de C para todo
λ1 , λ2 ≥ 0 y al menos uno de ellos no nulo.
En la siguiente proposición se caracterizan las direcciones del conjunto de
soluciones factibles del problema de programación lineal.

Proposición 2.3. Dado S = {x ∈ IRn / Ax = b, x ≥ 0}, entonces:

d es dirección de S ⇐⇒ d ≥ 0 , d = 0 y Ad = 0

Demostración:

⇒ Al ser d ∈ IRn una dirección de S, debe verificarse que d ≥ 0, ya que,

en caso contrario, si existiera una componente dj < 0, considerando un μ
suficientemente grande, la componente j-ésima xj +μdj < 0 para cualquier
x ∈ S y el vector x + μd ≥ 0, contradiciendo ası́ la definición de dirección.
Por otra parte, si el vector x + μd ∈ S ∀μ ≥ 0, debe verificarse que
A(x + μd) = b ∀μ ≥ 0 y, al ser x ∈ S, Ax = b, necesariamente debe
verificarse Ad = 0.

⇐ Dados x ∈ S y μ ≥ 0, se verifica que

x + μd ≥ 0

A(x + μd) = Ax + μAd = Ax = b

Por lo que el vector d define una dirección de S.

•
Direcciones extremas de S I.O. Introducción 41

Para analizar el caso de múltiples direcciones se introduce el siguiente ejem-

plo, que resulta de modificar el ejemplo 1.7, cuyo recinto de soluciones factibles
está representado en la figura 1.6, al incluir explı́citamente las variables de hol-
gura.
Ejemplo 2.4.

M in 3x1 − x2
sujeto a −x1 + x2 + xh1 = 2
x1 − 2x2 + xh2 = 2
xj , xhi ≥ 0 ∀i, j = 1, 2

Los parámetros que identifican este problema son:

⎛ ⎞
3
  ⎜ ⎟
−1 1 1 0 2 ⎜ −1 ⎟
n=4 m=2 A= b= ⎜
c=⎜ ⎟
−2 ⎟
1 0 1 2 ⎝ 0 ⎠
0

Se puede comprobar que los vectores

⎛ ⎞ ⎛ ⎞
1 2
⎜ ⎟ ⎜ ⎟
⎜ 1 ⎟ ⎜ 1 ⎟
d =⎜
1 ⎟
⎜ 0 ⎟ d =⎜
2 ⎟
⎜ 1 ⎟
⎝ ⎠ ⎝ ⎠
1 0

son direcciones de S, ya que son no nulos, no negativos y verifican Ad = 0.

Cualquier combinación lineal positiva de estas direcciones es otra dirección,
por ejemplo, la dirección
⎛ ⎞
3
⎜ ⎟
⎜ 2 ⎟
d3 = ⎜ ⎟ 1
⎜ 1 ⎟=d +d
2

⎝ ⎠
1

De la misma forma que se introducı́a el concepto de punto extremo de un

conjunto convexo para identificar aquellos puntos del conjunto que no se podı́an
expresar como combinaciones lineales convexas de otros puntos, se introduce
I.O. Introducción 42 Análisis teórico del problema

el concepto de dirección extrema como aquella dirección que no puede ser re-
presentada como combinación lineal positiva de direcciones distintas. Conviene
observar que no se exige en el caso de direcciones extremas que los coeficientes
de la combinación lineal sumen 1, exigiendo sólo que sean no negativos.

Definición 2.6. Dado un conjunto convexo C ⊂ IRn , una dirección d ∈ IRn se

dice que es una dirección extrema de C si al expresarse como:

d = μ1 d 1 + μ2 d 2

siendo μ1 , μ2 > 0 y d1 , d2 direcciones de C, se concluye necesariamente que las

tres direcciones son equivalentes:

d d1 d2

A continuación, se caracterizan las direcciones extremas del conjunto S de

soluciones factibles del problema de programación lineal.

Teorema 2.2. Dado S = {x ∈ IRn / Ax = b, x ≥ 0}, donde A es una matriz

m × n y rg(A) = m, entonces:
d es dirección extrema de S ⇐⇒ ∃B ⊂ A, siendo |B| = 0 tal que A =

 aj ∈ N verificando
(B, N ), y existe un vector columna B −1 aj ≤ 0 de forma que
−B −1 aj
d = αd0 , siendo α > 0 y d0 = .
ej
El vector d0 es de dimensión n y tiene dos partes diferenciadas:

m componentes asociadas a la base, que —por comodidad de notación—

se han situado al principio, pero que en realidad hay que situar en las
posiciones asociadas a las componentes de la base y en el orden correspon-
diente.

n−m componentes complementarias de la base, situadas al final del vector

y que son todas nulas excepto un 1 en la posición j-ésima asociada al vector
aj y que, por esta razón, se ha identificado como el vector ej .

Demostración :

⇐ Sea A = (B, N ), donde |B| =

 0 y sea aj∈ N verificando
B −1 aj ≤ 0 de
−1
−B aj
forma que d = αd0 siendo α > 0 y d0 = .
ej
Direcciones extremas de S I.O. Introducción 43

Se supone, sin pérdida de generalidad, que las componentes de la base B

son las m primeras.
Es trivial comprobar que el vector d ası́ definido es una dirección de S al
verificar, según la proposición 2.3, que Ad = 0 y d ≥ 0. Hay que demostrar
que es una dirección extrema:
Supongamos que d = μ1 d1 + μ2 d2 , siendo μ1 , μ2 > 0 y d1 , d2 ∈ IRn dos
direcciones de S. Cada una de estas direcciones se puede descomponer en
las componentes básicas y secundarias:

   
dB −B −1 aj d1B d2B
d= = = μ1 + μ2
dN ej d1N d2N

Al ser d1N , d2N ≥ 0 y μ1 , μ2 > 0, se deduce que todas las componentes

secundarias, excepto la j-ésima, son nulas, es decir:

d1t 1
N = (0, . . . , dj , . . . , 0) ∈ IR
n−m
d2t 2
N = (0, . . . , dj , . . . , 0) ∈ IR
n−m

Por ser d1 una dirección de S, se verifica que Ad1 = 0, es decir,

⎛ ⎞
d1B
⎜ ⎟
⎜ 0 ⎟
⎜ ⎟
⎜ . ⎟
⎜ .. ⎟
⎜ ⎟
Ad1 = (B, am+1 , . . . , aj , . . . , an ) ⎜ 1 ⎟ = Bd1B + aj d1j = 0
⎜ dj ⎟
⎜ ⎟
⎜ . ⎟
⎜ .. ⎟
⎝ ⎠
0

Al ser B una base y ser 0 ≤ d = 0, se concluye que d1j > 0, puesto que
en caso contrario existirı́a una combinación lineal no nula de los vectores
columna de B igual al vector 0. Se concluye ası́ que

d1B = −d1j B −1 aj

Siguiendo un proceso análogo, se concluye que d2j > 0 y

d2B = −d2j B −1 aj
I.O. Introducción 44 Análisis teórico del problema

por lo que se verifica que

 
1 −B −1 aj −B −1 aj
d d = d1j 2
d = d2j
ej ej

es decir, d es una dirección extrema.

⇒ Sea d una dirección extrema de S. Al ser dirección, d = 0 y, por consi-

guiente, sus k + 1 coordenadas positivas, siendo 0 ≤ k ≤ (n − 1), se pueden
reordenar de forma que k de ellas sean las primeras y la (k + 1)-ésima se
coloca en la posición j, j > m de forma que:

dt = (d1 , . . . , dk , 0, . . . , dj , . . . , 0) dl > 0 ∀l = 1, . . . , k dj > 0

Al ser d dirección, Ad = 0 y, por tanto, el conjunto de vectores {a1 , . . . , ak , aj }

es linealmente dependiente.
Sin embargo, el subconjunto de vectores {a1 , . . . , ak } es linealmente inde-
pendiente. En caso contrario existirı́a un conjunto de coeficientes {λ1 , . . . , λk }
no todos nulos verificando

k

λl al = 0
l=1

y a partir de estos coeficientes se construirı́a el vector

λt = (λ1 , . . . , λk , 0, . . . , 0)

y existirá un α > 0 suficientemente pequeño para el cual los vectores

d1 = d + αλ ≥ 0

d2 = d − αλ ≥ 0

que, además, son no nulos por ser dj > 0 y λj = 0. Por otra parte, al
verificar
Direcciones extremas de S I.O. Introducción 45

Ad1 = Ad + αAλ = 0 + 0 = 0

Ad2 = Ad − αAλ = 0 + 0 = 0
1 1
se concluye que son direcciones de S verificando que d = 2d + 12 d2 ,
contradiciendo la hipótesis de ser d dirección extrema y demostrando que
el conjunto {a1 , . . . , ak } es linealmente independiente.
Se deduce entonces que k ≤ m y siempre se puede encontrar, al ser rg(A) =
m, un conjunto de m − k vectores para completar una base del espacio
vectorial IRm . Esta base B no puede contener al vector aj puesto que,
según se ha visto anteriormente, el conjunto de vectores {a1 , . . . , ak , aj }
es linealmente dependiente.
A partir de B se descompone la matriz A = (B, N ), con la propiedad de
que aj ∈ N . Al ser d una dirección, se verifica que


dB
0 = Ad = (B, N ) = BdB + aj dj
dN

y siguiendo un desarrollo análogo al de la implicación inversa, se obtiene


0 0 −B −1 aj
d = dj d d =
ej

concluyendo ası́ que la dirección extrema d se puede descomponer según

las condiciones del teorema.

Se puede comprobar que en el ejemplo 2.3 existe una dirección extrema ca-
racterizada por la base B = (a1 , a2 ) y por el vector a3 según las condiciones del
teorema anterior. En efecto:

   
1 −1 1/3 −1/3 1 0
B= B −1 = B −1 = ≤0
−2 −1 −2/3 −1/3 1 −1
I.O. Introducción 46 Análisis teórico del problema

y se construye una dirección extrema:

⎛ ⎞
0
⎜ ⎟
d1 = ⎜ ⎟
⎝ 1 ⎠
1

En el ejemplo 2.4, se pueden obtener las siguientes direcciones extremas:


−1 1
A partir de B1 = (a1 , a2 ) =
1 −2
Eligiendo ah2 , se verifica que
  
−2 −1 0 −1
B1−1 ah2 = = ≤0
−1 −1 1 −1

Considerando las componentes de este vector cambiadas de signo como las

coordenadas correspondientes a a1 y a2 respectivamente, y anulando las
componentes no básicas excepto la correspondiente a ah2 , que es igual a
uno, se construye la siguiente dirección extrema
⎛ ⎞
1
⎜ ⎟
⎜ 1 ⎟
d1 = ⎜ ⎟
⎜ 0 ⎟
⎝ ⎠
1


−1 1
A partir de B2 = (a1 , ah1 ) =
1 0
Eligiendo a2 , se verifica que
  
0 1 1 −2
B2−1 a2 = = ≤0
1 1 −2 −1
Teorema de representación de S I.O. Introducción 47

Se construye ası́ la dirección extrema

⎛ ⎞
2
⎜ ⎟
⎜ 1 ⎟
d2 = ⎜
⎜ 1
⎟
⎟
⎝ ⎠
0

Una dirección proporcional a d2 , por tanto, equivalente, se podrı́a haber ob-

tenido considerando la base B1 y el vector ah1 . Otra equivalente se puede deter-
minar con base (a2 , ah1 ) y el vector a1 .

Realmente, cada dirección extrema d está asociada a la combinación lineal de

los vectores de la base y un vector no básico; los coeficientes de esta combinación
lineal son las componentes del vector d, puesto que se verifica Ad = 0.
En consecuencia, se pueden determinar hasta un máximo de m+1 direcciones
extremas, todas ellas equivalentes, sin más que ir variando el elemento de los
m + 1 que sale de la base cuando el coeficiente de la combinación lineal anterior
sea mayor que cero.
Se puede concluir entonces que el número de direcciones extremas es finito
y está acotado por 
n
m+1

que es el número de subconjuntos con m + 1 vectores columna de la matriz A

que, siendo linealmente dependientes al ser un espacio vectorial de dimensión m,
los coeficientes de la correspondiente combinación lineal son todos no negativos.

2.4. Teorema de representación de S

Cuando el conjunto convexo de las soluciones factibles S es no acotado,
las combinaciones lineales convexas de sus puntos extremos no cubren todo el
conjunto. En estos casos, hay que añadir a dicha combinación lineal convexa una
combinación lineal positiva de todas las direcciones extremas. Este resultado es
el teorema de representación que a continuación se enuncia.

Teorema 2.3. Dado el conjunto S = {x ∈ IRn / Ax = b, x ≥ 0}, donde

A es una matriz m × n y rg(A) = m, sean {x1 , x2 , . . . , xk } el conjunto de
I.O. Introducción 48 Análisis teórico del problema

puntos extremos de S y {d1 , d2 , . . . , dl } el conjunto de sus direcciones extremas;

entonces, se verifica que:

k
∃(λ1 , . . . , λk ) λi ≥ 0, ∀i = 1, . . . , k / i=1 λi = 1
x ∈ S ⇐⇒ ∧ de
∃(μ1 , . . . , μl ) μj ≥ 0, ∀j = 1, . . . , l
forma que:

k
 l

x= λi x i + μj d j
i=1 j=1

Observación 2.2. La demostración del teorema de representación, junto con

los resultados previos necesarios, se detallan en la sección 2.5.

En el ejemplo 2.2, hay dos puntos extremos y no hay direcciones, por lo que
el conjunto de soluciones factibles se puede expresar según:
⎧ ⎛ ⎞ ⎛ ⎞ ⎫
⎪
⎪ 31/2 33 ⎪
⎪
⎨ ⎜ ⎟ ⎜ ⎟ ⎬
S= x = λ⎜
⎝ 7/2 ⎟
⎠ + (1 − λ) ⎜
⎝ 0 ⎟
⎠ / 0 ≤ λ ≤ 1⎪
⎪
⎪ ⎪
⎩ 0 7 ⎭

En el ejemplo 2.3, que sólo tiene un punto extremo y una dirección extrema,
el conjunto de soluciones factibles se puede expresar según:
⎧ ⎛ ⎞ ⎛ ⎞ ⎫
⎪
⎪ 0 0 ⎪
⎪
⎨ ⎜ ⎟ ⎜ ⎟ ⎬
S= x=⎜
⎝ 0 ⎟
⎠ + μ⎜
⎝ 1 ⎟
⎠ / μ ≥ 0⎪
⎪
⎪ ⎪
⎩ 1 1 ⎭

En el ejemplo 2.4, hay tres puntos extremos, asociados a las bases (ah1 , ah2 ),
(a1 , ah1 ) y (a2 , ah2 ), y dos direcciones extremas, d1 y d2 , por lo que el conjunto
de soluciones factibles se puede expresar según:

⎧ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎫⎞ ⎛ ⎞ ⎛
⎪
⎪ 0 2 0 ⎪
⎪ 1 2
⎪
⎪ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎪ ⎪
⎨ ⎜ 0 ⎟ ⎜ 0 ⎟ ⎜ 2 ⎟ ⎜ 1 ⎟ ⎜ 1 ⎟⎬
⎜
S = x = λ1 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎪ ⎟ + λ 2 ⎜ 4 ⎟ + λ 3 ⎜ 0 ⎟ + μ 1 ⎜ 0 ⎟ + μ 2 ⎜ 1 ⎟⎪
⎪
⎪ ⎝ 2 ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎪ ⎪
⎪
⎩ ⎪
⎭
2 0 6 1 0
Teorema de representación de S I.O. Introducción 49

siendo todos los coeficientes λ1 , λ2 , λ3 , μ1 , μ2 mayores o iguales a cero y sumando

los lambdas uno.
Proyectando los tres puntos extremos y las dos direcciones extremas sobre
las dos primeras coordenadas se tienen los tres vértices y las dos lı́neas que
delimitan la región factible S del ejemplo 2.4; ver la figura 2.2.

x2 −−−→
(1, 1)

(0, 2)
S

−−−→
(2, 1)

(0, 0) (2, 0) x1

Figura 2.2: Conjunto S del ejemplo 2.4, puntos y direcciones extremas

A partir del Teorema de Representación, y teniendo en cuenta que

k
 l

ct x = λ i ct x i + μ j ct d j
i=1 j=1

se puede analizar la solución del problema de programación lineal:

Corolario 2.2. Si el conjunto de soluciones factibles de un problema de progra-

mación lineal es no vacı́o y tiene una dirección extrema dj verificando ct dj < 0,
entonces el problema tiene solución no acotada.

Demostración: Asignando al coeficiente μj un valor arbitrariamente grande,

se consigue una función objetivo inferior a cualquier cota prefijada.

Corolario 2.3. Si el conjunto de soluciones factibles de un problema de progra-

mación lineal es no vacı́o y no tiene direcciones extremas o teniéndolas, todas
ellas verifican ct dj ≥ 0 , entonces el problema tiene solución óptima, y ésta se
alcanza en un punto extremo del conjunto S.
I.O. Introducción 50 Análisis teórico del problema

Demostración:
El mı́nimo se alcanzarı́a asignando a μj el valor 0, en el caso de que existan
direcciones extremas, y

λs = 1 , λi = 0 ∀i = s

siendo el ı́ndice s el que verifica

ct xs = M in{ct xi /1 ≤ i ≤ k}

2.4.1. Unicidad de la solución óptima

Sea S ∗ ⊂ S el conjunto de soluciones óptimas del problema de programación
lineal. Este conjunto, al igual que S, es también convexo. En los casos de no
existencia de solución factible o solución no acotada, S ∗ = ∅.
Si la solución óptima es única, |S ∗ | = 1; en caso contrario, el conjunto S ∗ es
no numerable y se caracteriza por:
⎧ ⎫
⎨    ⎬
S∗ = x∗ = λi x i + μj dj / λi , μj ≥ 0; λi = 1
⎩ ⎭
i∈I ∗ j∈J ∗ i∈I ∗

siendo

 
I ∗ ≡ s ∈ {1, . . . , k} / ct xs = M in{ct xi /1 ≤ i ≤ k}

 
J ∗ ≡ r ∈ {1, . . . , l} / ct dr = 0

2.4.2. Algoritmo basado en el teorema de representación

Dado el problema de programación lineal en su forma estándar:
Teorema de representación de S I.O. Introducción 51

M in ct x
Ax =b
x ≥0

basándose en la proposición 2.2 y en los corolarios 2.2 y 2.3, del teorema 2.3, se
propone el siguiente algoritmo que determina, si es el caso, una solución óptima:

Determinar el conjunto de puntos extremos de S : {x1 , . . . , xk }

Opciones:
• k = 0 ⇒ (S = ∅) ⇒ NO EXISTE SOLUCIÓN FACTIBLE ⇒ FIN
• k > 0 ⇒ (S = ∅):
Determinar el conjunto de direcciones extremas de S : {d1 , . . . , dl }
Opciones:
• ∃dj 1 ≤ j ≤ l / ct d j < 0
⇒ SOLUCIÓN NO ACOTADA ⇒ FIN
• (l = 0) ó (ct dj ≥ 0 ∀j ∈ {1, . . . , l}): ⇒ SOLUCIÓN ÓPTIMA:
s t s t i
x / c x = M in{c x / 1 ≤ i ≤ k} ⇒ FIN

A continuación se aplica el algoritmo basado en el teorema de representación

al ejemplo 2.4, que tiene tres puntos extremos (k = 3) y dos direcciones extremas
(l = 2):

⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
0 2 0 1 2
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎜ 0 ⎟ ⎜ 0 ⎟ ⎜ 2 ⎟ ⎜ 1 ⎟ ⎜ 1 ⎟
x =⎜
1 ⎟
⎜ 2 ⎟
2 ⎜
x =⎜ ⎟
⎟ x =⎜ 3 ⎟
⎜ 0 ⎟ d =⎜
1 ⎟
⎜ 0 ⎟ d =⎜
2 ⎟
⎜ 1 ⎟
⎝ ⎠ ⎝ 4 ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
2 0 6 1 0

Variando el vector de costes se plantean distintos problemas de programación

lineal:

1. ct = (2, −3, 0, 0)
I.O. Introducción 52 Análisis teórico del problema

⎛ ⎞ ⎛ ⎞
1 2
⎜ ⎟ ⎜ ⎟
⎜ 1 ⎟ ⎜ 1 ⎟
t 1 ⎜
c d = (2, −3, 0, 0) ⎜ ⎟ = −1 < 0 c d = (2, −3, 0, 0) ⎜
t 2 ⎟
⎟ ⎜ 1 ⎟=1≥0
⎝ 0 ⎠ ⎝ ⎠
1 0

Se tiene, por tanto, SOLUCIÓN NO ACOTADA.

2. ct = (4, −3, 0, 0)

⎛ ⎞ ⎛ ⎞
1 2
⎜ ⎟ ⎜ ⎟
⎜ 1 ⎟ ⎜ 1 ⎟
ct d1 = (4, −3, 0, 0) ⎜ ⎟
⎜ 0 ⎟=1≥0 ct d2 = (4, −3, 0, 0) ⎜ ⎟
⎜ 1 ⎟=5≥0
⎝ ⎠ ⎝ ⎠
1 0

Existe solución óptima que se determina en el punto extremo que alcance

el mı́nimo de la función objetivo:

⎛ ⎞ ⎛ ⎞
0 2
⎜ ⎟ ⎜ ⎟
⎜ 0 ⎟ ⎜ 0 ⎟
ct x1 = (4, −3, 0, 0) ⎜ ⎟
⎜ 2 ⎟=0 ct x2 = (4, −3, 0, 0) ⎜ ⎟
⎜ 4 ⎟=8
⎝ ⎠ ⎝ ⎠
2 0
⎛ ⎞
0
⎜ ⎟
⎜ 2 ⎟
ct x3 = (4, −3, 0, 0) ⎜ ⎟
⎜ 0 ⎟ = −6
⎝ ⎠
6

El mı́nimo es único I ∗ = {3}. Al ser J ∗ = ∅, la solución óptima del

problema es el conjunto formado por un único punto:

⎧⎛ ⎞⎫
⎪
⎪ 0 ⎪ ⎪
⎪
⎪ ⎟⎪
⎨⎜⎜ 2 ⎟
⎪
⎬
S∗ = ⎜ ⎟
⎜ 0 ⎟⎪
⎪
⎪ ⎝ ⎠⎪
⎪
⎪ ⎪
⎪
⎩ ⎭
6
Teorema de representación de S I.O. Introducción 53

3. ct = (0, 1, 0, 0)

⎛ ⎞ ⎛ ⎞
1 2
⎜ ⎟ ⎜ ⎟
⎜ 1 ⎟ ⎜ 1 ⎟
ct d1 = (0, 1, 0, 0) ⎜ ⎟
⎜ 0 ⎟=1≥0 ct d2 = (0, 1, 0, 0) ⎜ ⎟
⎜ 1 ⎟=1≥0
⎝ ⎠ ⎝ ⎠
1 0

Existe solución óptima que se determina en el punto extremo que alcance

el mı́nimo de la función objetivo:

⎛ ⎞ ⎛ ⎞
0 2
⎜ ⎟ ⎜ ⎟
⎜ 0 ⎟ ⎜ 0 ⎟
ct x1 = (0, 1, 0, 0) ⎜ ⎟
⎜ 2 ⎟=0 ct x2 = (0, 1, 0, 0) ⎜ ⎟
⎜ 4 ⎟=0
⎝ ⎠ ⎝ ⎠
2 0
⎛ ⎞
0
⎜ ⎟
⎜ 2 ⎟
ct x3 = (0, 1, 0, 0) ⎜ ⎟
⎜ 0 ⎟=2
⎝ ⎠
6

El mı́nimo no es único, siendo I ∗ = {1, 2}. Al ser J ∗ = ∅, la solución

óptima del problema es el conjunto:

⎧ ⎛ ⎞ ⎛ ⎞⎫ ⎧ ⎛ ⎞ ⎫
⎪
⎪ 0 2 ⎪
⎪ ⎪
⎪ 2 − 2λ ⎪
⎪
⎪
⎪ ⎟⎪⎪ ⎪
⎪ ⎜ ⎟ ⎪
⎪
⎨ ⎜ ⎟
⎜ 0 ⎟
⎜
⎜ ⎟
0 ⎟ ⎬ ⎨ ⎜ 0 ⎟ ⎬
S∗ = λ ⎜ ⎟ + (1 − λ) ⎜ = ⎜ ⎟ ; λ ∈ [0, 1]
⎪ ⎜ ⎟ ⎜ ⎟
4 ⎠⎪ ⎪ ⎜ ⎟ ⎪
⎪
⎪ ⎝ 2 ⎠ ⎝ ⎪
⎪
⎪ ⎪⎝ 4 − 2λ ⎠
⎪ ⎪
⎪
⎪
⎪
⎩ ⎭ ⎪ ⎩ ⎭
2 0 2λ

4. ct = (1, −1, 0, 0)

⎛ ⎞ ⎛ ⎞
1 2
⎜ ⎟ ⎜ ⎟
⎜ 1 ⎟ ⎜ 1 ⎟
t 1 ⎜
c d = (1, −1, 0, 0) ⎜ ⎟=0≥0 c d = (1, −1, 0, 0) ⎜
t 2 ⎟
⎟ ⎜ 1 ⎟=1≥0
⎝ 0 ⎠ ⎝ ⎠
1 0
I.O. Introducción 54 Análisis teórico del problema

Hay que observar que existe una dirección extrema d1 verificando ct d1 =

0, por lo que J ∗ = {1}.
El punto extremo óptimo se determina a partir del mı́nimo:

⎛ ⎞ ⎛ ⎞
0 2
⎜ ⎟ ⎜ ⎟
⎜ 0 ⎟ ⎜ 0 ⎟
c x = (1, −1, 0, 0) ⎜
t 1 ⎟
⎜ 2 ⎟=0
t 2 ⎜
c x = (1, −1, 0, 0) ⎜ ⎟=2
⎟
⎝ ⎠ ⎝ 4 ⎠
2 0
⎛ ⎞
0
⎜ ⎟
⎜ 2 ⎟
t 3 ⎜
c x = (1, −1, 0, 0) ⎜ ⎟ = −2
⎟
⎝ 0 ⎠
6

Este mı́nimo es único, I ∗ = {3}, pero al ser J ∗ = {1} = ∅, la solución

óptima del problema es el conjunto:

⎧⎛ ⎞ ⎛ ⎞ ⎧⎛⎫ ⎞ ⎫
⎪
⎪ 0 1 ⎪
⎪ ⎪
⎪ μ1 ⎪
⎪
⎪
⎪ ⎪ ⎪ ⎪
⎨⎜ ⎟
⎜ 2 ⎟
⎜
⎜
⎟
1 ⎟
⎪
⎨ ⎜
⎪
⎬
⎜
⎟
⎟
⎪
⎬
∗
S = ⎜⎜ ⎟ + μ1 ⎜ ⎟ ; μ1 ≥ 0 = ⎜ 2 + μ1 ⎟ ; μ1 ≥ 0
⎪ ⎟ ⎜ ⎟ ⎪ ⎪ ⎜ ⎟ ⎪
⎪
⎪ ⎝ 0 ⎠ ⎝ 0 ⎠ ⎪
⎪ ⎪⎝ 0 ⎠ ⎪
⎪
⎩ ⎪ ⎪
⎭ ⎪
⎩
⎪
⎪
⎭
6 1 6 + μ1

Aunque teóricamente el problema de programación lineal está resuelto con

este algoritmo, en la práctica supone la determinación de todas las posibles
bases B ⊂ A y la posterior comprobación de cuántas de ellas proporcionan
soluciones básicas. Considerando que el número de bases crece exponencialmente
con el numero de variables y ecuaciones, el algoritmo puede ser muy ineficiente
computacionalmente. Por ejemplo, si n = 50 y m = 15, el número de bases a
comprobar es igual a 
50
= 2250829575120
15

es decir, hay que invertir más de 2 billones de matrices con 15 filas y columnas.
En el siguiente capı́tulo se detalla un algoritmo, el algoritmo del simplex,
que de una forma muy eficiente resuelve el problema de programación lineal.
Demostración del teorema de representación (*) I.O. Introducción 55

2.5. Demostración del teorema de representación

(*)
La demostración del teorema de representación requiere de un resultado
previo relativo a la separación de un conjunto cerrado y convexo y un punto
exterior a dicho conjunto. Este resultado requiere, a su vez, la demostración de
otros teoremas y propiedades de conjuntos convexos e hiperplanos separadores
que son introducidos a continuación.

2.5.1. Distancia entre un punto y un conjunto convexo

El siguiente lema se denomina ley del paralelogramo al afirmar que la suma
de los cuadrados de las longitudes de las diagonales de un paralelogramo es igual
al duplo de la suma de los cuadrados de las longitudes de los lados.

Lema 2.1. Dado un espacio normado de dimensión n, en particular IRn , con

la norma euclı́dea 
 a = a21 + . . . + a2n

se verifica la siguiente igualdad:

2 2 2 2
 a + b  +  a − b  = 2 a  + 2 b 

Demostración: Sumando los dos desarrollos siguientes se obtiene el resultado

propuesto:

2 2 2
 a + b  =  a  +  b  + 2at b

2 2 2
 a − b  =  a  +  b  − 2at b

Teorema 2.4. Sea S un conjunto convexo cerrado de IRn y sea y ∈ S, entonces

existe un único punto x ∈ S que hace mı́nima la distancia de S a y.
Además, este punto x se puede caracterizar por la siguiente desigualdad (x−
x)t (x − y) ≥ 0 ∀x ∈ S
I.O. Introducción 56 Análisis teórico del problema

Demostración: Por definición de distancia punto-conjunto,

d(S, y) = Inf { y − x  /x ∈ S} = γ > 0

existe una sucesión {xk } ⊂ S de modo que  y − xk → γ. Se demostrará que

la sucesión {xk } ası́ definida converge al punto x ∈ S.
Algunos aspectos de esta demostración se ilustran en la figura 2.3.

y y

x x

S S

Figura 2.3: Identificación geométrica del punto x̄

Primero se demuestra que la sucesión {xk } es convergente. Para ello es su-

ficiente —al ser IRn espacio de Banach— ver que es sucesión de Cauchy:
Por el lema 2.1, y llamando a = xk − y, b = xm − y:

 xk − xm 2 = 2  xk − y 2 +2  xm − y 2 −  xk + xm − 2y 2 =

xm + xk
= 2  xk − y 2 +2  xm − y 2 −4  − y 2 ≤
2

≤ 2  xk − y 2 +2  xm − y 2 −4γ 2

La última desigualdad es cierta al ser S convexo y poder garantizar que

xm + xk
∈ S,
2
Demostración del teorema de representación (*) I.O. Introducción 57

además, por definición de γ, se verifica que

xm + xk
 − y ≥ γ
2

Si k, m → ∞ se verifica

 xk − y ,  xm − y → γ

y, por la desigualdad obtenida previamente,

 xk − xm → 0

es decir, la sucesión {xk } es de Cauchy y converge a un único punto. Sea x dicho

lı́mite; al ser S cerrado, x ∈ S.
La última parte del teorema permite caracterizar este punto lı́mite:

x es el punto minimizante ⇔ (x − x)t (x − y) ≥ 0 ∀x ∈ S

⇐) Considerando que
x − y = (x − x) + (x − y)

se concluye que

 x−y 2 = x−y 2 +  x−x 2 +2(x−x)t (x−y) ≥ x−y 2 ∀x ∈ S

Por consiguiente, x es el punto que minimiza la distancia entre y y S.

⇒ ) Al ser x un punto minimizante, se verifica

 y − x 2 ≤ y − x 2 ∀x ∈ S

Sea x ∈ S, entonces, para cualquier λ ∈ [0, 1], y considerando que S es

convexo y que x ∈ S, el vector

x + λ(x − x) ∈ S

Aplicando a este punto la inecuación anterior, se obtiene

I.O. Introducción 58 Análisis teórico del problema

 y−x 2 ≤ y−x−λ(x−x) 2 = λ2  x−x 2 +2λ(x−x)t (x−y)+  y−x 2

Se concluye ası́ que

λ2  x − x 2 +2λ(x − x)t (x − y) ≥ 0

Dividiendo los dos miembros de la desigualdad por λ, para que sea cierta
la desigualdad anterior, es necesario que se verifique

(x − x)t (x − y) ≥ 0 ∀x ∈ S

Si fuera negativa esta expresión, bastarı́a considerar un λ > 0 suficiente-

mente pequeño para contradecir la desigualdad previa.

2.5.2. Hiperplano separador

Definición 2.7. Un hiperplano H(p, α) ⊂ IRn es una colección de puntos de la
forma
H(p, α) = {x ∈ IRn /pt x = α}

siendo α ∈ IR y p = 0 el vector normal o caracterı́stico del hiperplano.

A partir del hiperplano H(p, α) se definen dos semiespacios:

H(p, α)+ = {x ∈ IRn /pt x ≥ α} H(p, α)− = {x ∈ IRn /pt x ≤ α}

Definición 2.8. Dados dos conjuntos no vacı́os S1 , S2 ⊂ IRn , un hiperplano

H(p, α) separa ambos conjuntos si se verifica que S1 ⊂ H(p, α)+ y S2 ⊂
H(p, α)−

Teorema 2.5. Dado S ∈ IRn no vacı́o, convexo y cerrado y dado un punto

y ∈ S, existe un hiperplano que los separa.

Demostración:
Demostración del teorema de representación (*) I.O. Introducción 59

Al verificarse las hipótesis del teorema 2.4, existe un único punto x̄ que
minimiza la distancia entre y y S verificándose, además, que x ∈ S, y que
(x − x)t (y − x) ≤ 0 ∀x ∈ S
Esta última desigualdad es equivalente a

(y − x̄)t x ≤ (y − x̄)t x̄ ∀x ∈ S

Introduciendo el vector
p ≡ y − x̄ = 0

y el escalar
α ≡ (y − x̄)t x̄

la desigualdad anterior se expresa

pt x ≤ pt x̄ = α ∀x ∈ S

Al ser p = (y − x̄) = 0, se deduce que

0 < p 2 = pt (y − x̄)

de forma que es cierta la desigualdad

pt y > pt x̄ = α

Encadenando las dos desigualdades, se obtiene

pt y > α ≥ pt x ∀x ∈ S

Ya está demostrado que el hiperplano H(p, α) separa el vector y ∈ S y el

conjunto S.
La figura 2.4 adjunta ilustra la demostración.

2.5.3. Demostración del teorema

Se define el conjunto Λ de todas las combinaciones lineales convexas de pun-
tos extremos de S y combinaciones lineales no negativas de direcciones extremas,
I.O. Introducción 60 Análisis teórico del problema

pt x = α y
p=y−x
x

Figura 2.4: Hiperplano separador pt x = α

es decir

⎧ ⎫
⎨k l
 k
 ⎬
Λ= λi x i + μj dj / λi , μj ≥ 0 ∀i = 1, . . . , k ∀j = 1, . . . , l; λi = 1
⎩ ⎭
i=1 j=1 i=1

Para demostrar el teorema de representación, hay que demostrar que Λ = S.

Al ser S convexo, y por la definición de dirección, se comprueba que Λ ⊂ S.
Es claro que el conjunto Λ = ∅, ya que según se ha demostrado, si S =
∅, existe al menos un punto extremo. También es fácil comprobar que es un
conjunto convexo y cerrado. La inclusión en el otro sentido se demuestra por
contradicción, al suponer que S ⊂ Λ y, por tanto, existe un vector s ∈ S tal que
s ∈ Λ:
Al ser Λ = ∅ cerrado y convexo, por el teorema 2.5 existe un hiperplano
H(p, α) ⊂ IRn que separa el punto s del conjunto Λ, es decir, existen p = 0 ∈ IRn
y α ∈ IR tales que

pt s > α ≥ pt x ∀x ∈ Λ

De esto último se concluye:

1. pt dj ≤ 0 ∀j = 1, . . . , l, ya que si existiera un ı́ndice j0 tal que pt dj0 > 0,

tomando μj0 > 0, suficientemente grande, se obtendrı́a un punto x1 +
Demostración del teorema de representación (*) I.O. Introducción 61

μj0 dj0 ∈ Λ verificando

pt (x1 + μj0 dj0 ) = pt x1 + μj0 pt dj0 > α

lo cual contradirı́a
pt x ≤ α ∀x ∈ Λ

2. pt xi ≤ α ∀i = 1, . . . , k
Sólo hay que considerar λi = 1 y λh = 0 ∀h = i y μj = 0 ∀j = 1, . . . , l.

Sea x el punto extremo que verifica

pt x = máx {pt xi }
1≤i≤k

Al ser x un punto extremo, ∃B ⊂ A tal que, suponiendo que en B están las

primeras m columnas,

B −1 b
x= B −1 b ≥ 0
0

sB
Por ser s ∈ S, se deduce que As = b y s ≥ 0. Sea s = de forma que
sN
As = BsB + N sN = b, y, por consiguiente, sB = B −1 b − B −1 N sN
Por ser pt s > pt x se verifica:

0 < pt s−pt x = ptB (B −1 b−B −1 N sN )+ptN sN −ptB B −1 b = (ptN −ptB B −1 N )sN

Es decir, (ptN − ptB B −1 N )sN > 0, de donde se deduce, al ser s ≥ 0, que


sj > 0
∃j ≥ m + 1 /
pj − ptB B −1 aj > 0.

El vector yj = B −1 aj ≤ 0, puesto que, en caso contrario existirı́a la dirección

extrema: 
−yj
d=
ej
I.O. Introducción 62 Análisis teórico del problema

Y, al ser d dirección extrema, pt d ≤ 0 y, se deducirı́a que

−ptB B −1 aj + pj ≤ 0

en contradicción con la desigualdad obtenida en el párrafo anterior.

Tiene sentido, pues, determinar a partir del vector yj ≤ 0
 
x̄i x̄r
λ = mı́n /yij > 0 ≡ ≥0
1≤i≤m yij yrj

y se define una nueva solución factible x̄ a partir de la anterior x̄:

 
 B −1 b −yj
x̄ = +λ
0 ej

Este vector x̄ ∈ S, ya que x̄ ≥ 0 y Ax̄ = b, en efecto:

 
Ax̄ = B B −1 b − λB −1 aj + λaj = b

Al sustituir en B la columna ar (puesto que x̄r = 0) por aj se tiene una

nueva base
B  = (a1 , . . . , ar−1 , ar+1 , . . . , am , aj )

El que B  sea base se garantiza al ser yrj = 0. Por consiguiente, x̄ es también
un punto extremo de S por el teorema de representación.
Sólo queda, por último, llegar a una contradicción al haber supuesto que
S ⊂ Λ. La contradicción se verifica al comprobar que este nuevo punto extre-
mo x al ser multiplicado escalarmente por p alcanza un valor mayor que el
correspondiente a x, que era, por definición el máximo posible:

t B −1 b − λyj
px= (ptB , ptN ) = ptB B −1 b − λptB yj + λpj =
λej

= pt x + λ(pj − ptB B −1 aj ) > pt x

La última desigualdad se verifica al ser λ > 0 y pj − ptB B −1 aj > 0.

Por consiguiente, S ⊂ Λ y la igualdad de ambos conjuntos ha quedado
demostrada.