Capı́tulo 4

Algoritmo del simplex.

Inicialización

El algoritmo del simplex parte de una solución básica factible asociada a una
base B ⊂ A. Salvo casos particulares, la determinación de esta base inicial no
es una tarea trivial desde el punto de vista computacional, ya que implicarı́a la
inversión de matrices de 
dimensión
 m×m y el número de estas inversiones puede
n
alcanzar el valor lı́mite cuando el problema de programación lineal no
m
admita soluciones factibles.
El método de las dos fases y el de las penalizaciones son dos procedimientos
eficientes para determinar una solución básica factible inicial.
Ambos procedimientos detectan el caso de no existencia de solución facti-
ble sin necesidad de enumerar todas las bases. Además, en el caso en que haya
redundancia del sistema, es decir, cuando rg(A) < m, identifican la fila redun-
dante y la combinación lineal de filas asociada, permitiendo su eliminación y la
solución del problema.

4.1. Solución básica inicial. Variables artificiales

En algunos problemas de programación lineal concretos la base inicial B
aparece explı́citamente. Serı́a el caso, por ejemplo, de un problema con restric-
ciones de desigualdad ≤ y con el vector de términos independientes b ≥ 0; la
base inicial estarı́a formada por todas las columnas asociadas a las variables de
I.O. Introducción 96 Algoritmo del simplex. Inicialización

holgura; es decir,
B = {ah1 , . . . , ahm }

Ejemplo 4.1. Sea el problema de programación lineal

M in x1 −3x2 −x3
x1 +4x2 +3x3 ≤ 12
x1 +2x2 −x3 ≤4
xj ≥ 0 ∀j = 1, 2, 3

Introduciendo las variables de holgura xh1 y xh2 se obtiene

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

En este ejemplo se observa que, al elegir como base B = {ah1 , ah2 } = I, se

verifica que B −1 = I y, por consiguiente, las magnitudes relevantes se obtienen
fácilmente

x̄B = b z̄ = 0 yj = aj ∀j ∈ I ∪ J zj − cj = −cj ∀j ∈ I ∪ J

y la tabla inicial del simplex es

··· −cj ··· 0

.. ..
. aj . b

Continuando con el ejemplo 4.1, la tabla inicial serı́a:

1 −3 −1 0 0
x1 x2 x3 xh1 xh2
−1 3 1 0 0 0
0 xh1 1 4 3 1 0 12
0 xh2 1 2 −1 0 1 4
Solución básica inicial. Variables artificiales I.O. Introducción 97

En general, sin embargo, la determinación de esta base inicial B no es una

tarea trivial.

En lo que sigue, y para que la existencia de una submatriz identidad I ⊂

A proporcione una solución básica factible inicial, se exigirá que el vector de
términos independientes sea no negativo, es decir,

b≥0

Esta hipótesis no supone pérdida de generalidad ya que en caso contrario,

si existiera un bi < 0 para algún i ∈ {1, . . . , m}, se multiplicarı́a la restricción
correspondiente por −1, invirtiendo el sentido de la desigualdad si fuera una
inecuación.

En el caso general, cuando la existencia de una submatriz I ⊂ A no esté

garantizada, se forzará su inclusión añadiendo nuevas variables al problema,
denominadas variables artificiales, que se incorporan a cada una de las restric-
ciones de igualdad ampliando la región factible inicial, que pasa de ser

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

a
  
a x n+m a a
S = ∈ IR / Ax + Ix = b x, x ≥ 0
xa

donde
⎛ ⎞
xa1
⎜ . ⎟
xa = ⎜ . ⎟
⎝ . ⎠≥0
xam

es el vector de variables artificiales de dimensión m.

Es fácil verificar que

x∈S ⇐⇒ (x, 0) ∈ S a

En el caso en que haya alguna inecuación ≤ con el término independiente no

negativo, no serı́a necesario introducir una variable artificial para dicha inecua-
I.O. Introducción 98 Algoritmo del simplex. Inicialización

ción, puesto que el vector unitario de la correspondiente variable de holgura

podrı́a incluirse en la base inicial junto con las otras variables artificiales del
resto de restricciones. No obstante, y sin pérdida de generalidad, se considera
que se parte del modelo estándar de programación lineal y se añaden tantas
variables artificiales como restricciones.

Ejemplo 4.2. Sea el problema de programación lineal:

M in x1 +2x2 −x3 −2x4 +2x5 +3x6

x1 +x3 +x4 −x5 +2x6 =2
−x1 +x2 +2x3 +x5 −x6 =1
2x1 −x2 +3x3 +2x4 +x5 =5
xj ≥ 0 ∀j = 1, . . . , 6

introduciendo tres variables artificiales se define el recinto S a ⊂ IR9 :

x1 +x3 +x4 −x5 +2x6 +xa1 =2

−x1 +x2 +2x3 +x5 −x6 +xa2 =1
2x1 −x2 +3x3 +2x4 +x5 +xa3 =5
xj ≥ 0 ∀j = 1, . . . , 6
xai ≥ 0 ∀i = 1, . . . , 3

La base inicial formada por los vectores columna unitarios asociados a las
variables artificiales

B = {aa1 , . . . , aam } = I

es la matriz identidad y proporciona como solución básica factible —para el

problema ampliado— el vector

(0, b) ∈ S a

El objetivo es intentar anular las variables artificiales para obtener una so-
lución básica factible para el problema original. Dos procedimientos generales
son: el método de las dos fases y el método de las penalizaciones.
Método de las dos fases I.O. Introducción 99

4.2. Método de las dos fases

El método de las dos fases resuelve el problema de programación lineal
⎧
⎪
⎪ ct x
⎨ M in
P Ax =b
⎪
⎪
⎩ x ≥0

Sólo se supone, sin pérdida de generalidad, que b ≥ 0.

1. Fase 1
Se introducen las variables artificiales según se ha detallado anteriormente
y se fuerza su salida mediante el algoritmo del simplex a partir de la
base inicial formada por los vectores asociados a las variables artificiales
resolviendo el siguiente problema:

⎧
⎪
⎪ 1t xa
⎨ M in
1
P Ax +Ixa =b
⎪
⎪
⎩ x, xa ≥0

donde 1t = (1, . . . , 1) es un vector de dimensión m. El objetivo de la fase 1

es la determinación de una base inicial que proporcione una solución básica
factible para el problema P . Por lo explicado previamente, si al aplicar el
algoritmo del simplex, se consigue sacar de la base a todas las variables
artificiales —es la idea de minimizar su suma— se habrá conseguido este
propósito.
El problema P 1 siempre tiene solución óptima, puesto que la función ob-
jetivo está acotada inferiormente y existe al menos una solución factible
(0, b) ∈ S a = ∅. Sea B ∗ la base óptima del problema P 1 .
El análisis de la existencia de solución factible del problema P y el análisis
de la redundancia del sistema de ecuaciones asociado Ax = b requiere
distinguir si las variables artificiales pertenecen o no a la base B ∗ . Sea I ∗
el conjunto de ı́ndices asociados a la base B ∗ , entonces

I ∗ = Io∗ ∪ Ia∗

donde
I.O. Introducción 100 Algoritmo del simplex. Inicialización

Io∗ ⊂ {1, . . . , n} Ia∗ ⊂ {1, . . . , m}

son los conjuntos de ı́ndices asociados a B ∗ entre las variables originales

y las variables artificiales respectivamente:

s ∈ Io∗ ⇐⇒ as ∈ B ∗ i ∈ Ia∗ ⇐⇒ aai ∈ B ∗

Análogamente se definen Jo∗ y Ja∗ para las variables secundarias.

Se tienen las siguientes posibilidades:

a) Ia∗ = ∅
Necesariamente, todas las variables artificiales se anulan, por lo que
se eliminan de la tabla del simplex óptima. La primera fase ha ter-
minado. IR A LA FASE 2.
b) Ia∗ = ∅
Hay dos opciones:
∃i ∈ Ia∗ tal que x̄ai > 0
En este caso, no existe solución factible para el problema P . Ver
proposición 4.1.
NO EXISTE SOLUCIÓN FACTIBLE. FIN.
x̄ai = 0 ∀i ∈ Ia∗
En este caso, para cada fila i ∈ Ia∗ se distinguen dos casos:
• ∃j ∈ Jo∗ / yia j = 0
Sale de la base B ∗ el vector aai pivotando en el elemento
yia j = 0 obteniendo la misma solución con una base distinta
que no la incluye.
Para pivotar, al ser solución degenerada, no es preciso que
yia j > 0, pudiendo ser negativo.
Se actualiza la base B ∗ = B ∗ ∪ {aj } − {aai }.
• yia j = 0 ∀j ∈ Jo∗
En este caso, la fila ia -ésima puede ser suprimida al ser re-
dundante. Ver proposición 4.2.
En ambos casos, después de pivotar o suprimir filas redundantes
hasta eliminar todas las variables artificiales en la base con valor
Método de las dos fases I.O. Introducción 101

0, IR A LA FASE 2.

2. Fase 2
Se resuelve el problema P partiendo de la tabla del simplex óptima de la
Fase 1 y con la base inicial B ∗ . Al haber modificado los coeficientes de la
función objetivo, hay que volver a calcular la fila de los zj − cj y z̄.
Las dos posibles salidas para el problema P son ahora SOLUCIÓN NO
ACOTADA y SOLUCIÓN ÓPTIMA.

Aplicando el método de las dos fases al ejemplo 4.2, se obtiene la siguiente

secuencia de tablas del simplex:
Fase 1:

0 0 0 0 0 0 1 1 1
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
2 0 6 3 1 1 0 0 0 8
1 xa1 1 0 1 1 −1 2 1 0 0 2
1 xa2 −1 1 2 0 1 −1 0 1 0 1
1 xa3 2 −1 3 2 1 0 0 0 1 5

0 0 0 0 0 0 1 1 1
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
5 −3 0 3 −2 4 0 −3 0 5
1 xa1 3/2 −1/2 0 1 −3/2 5/2 1 −1/2 0 3/2
0 x3 −1/2 1/2 1 0 1/2 −1/2 0 1/2 0 1/2
1 xa3 7/2 −5/2 0 2 −1/2 3/2 0 −3/2 1 7/2

0 0 0 0 0 0 1 1 1
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
0 −4/3 0 −1/3 3 −13/3 −10/3 −4/3 0 0
0 x1 1 −1/3 0 2/3 −1 5/3 2/3 −1/3 0 1
0 x3 0 1/3 1 1/3 0 1/3 1/3 1/3 0 1
1 xa3 0 −4/3 0 −1/3 3 −13/3 −7/3 −1/3 1 0
I.O. Introducción 102 Algoritmo del simplex. Inicialización

0 0 0 0 0 0 1 1 1
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
0 0 0 0 0 0 −1 −1 −1 0
0 x1 1 −7/9 0 5/9 0 2/9 −1/9 −4/9 1/3 1
0 x3 0 1/3 1 1/3 0 1/3 1/3 1/3 0 1
0 x5 0 −4/9 0 −1/9 1 −13/9 −7/9 −1/9 1/3 0

Y se termina ası́ la fase 1, con

Io∗ = {1, 5, 3} Ia∗ = ∅ Jo∗ = {2, 4, 6} Ja∗ = {1, 2, 3}

La base inicial para la fase 2 es

B ∗ = {a1 , a3 , a5 }

Fase 2:
Después de eliminar las columnas asociadas a las variables artificiales, hay
que volver a calcular la primera fila siguiendo los siguientes pasos:

1. Sustituir los coeficientes de la función objetivo, que eran 0 en la Fase 1,

por el vector c. En la columna correspondiente, se especifica el vector cB .

2. Evaluar zj − cj = ctB yj − cj ∀j ∈ Jo∗

Obviamente, zs − cs = 0 ∀s ∈ Io∗

3. Evaluar z̄ = ctB x̄∗B

La tabla inicial del simplex en la fase 2 es la siguiente:

1 2 −1 −2 2 3
x1 x2 x3 x4 x5 x6
0 −4 0 2 0 −6 0
1 x1 1 −7/9 0 5/9 0 2/9 1
−1 x3 0 1/3 1 1/3 0 1/3 1
2 x5 0 −4/9 0 −1/9 1 −13/9 0

Pivotando en y14 = 5/9 se obtiene la siguiente tabla:

Método de las dos fases I.O. Introducción 103

1 2 −1 −2 2 3
x1 x2 x3 x4 x5 x6
−18/5 −6/5 0 0 0 −34/5 −18/5
−2 x4 9/5 −7/5 0 1 0 2/5 9/5
−1 x3 −3/5 4/5 1 0 0 1/5 2/5
2 x5 1/5 −3/5 0 0 1 −7/5 1/5

que proporciona la solución óptima:

x̄1 = 0 x̄2 = 0 x̄3 = 2/5 x̄4 = 9/5 x̄5 = 1/5 z̄ = −18/5

Observación 4.1. Dada una base B que proporciona una solución básica fac-
tible, la tabla del simplex se construye multiplicando el sistema Ax = b por su
inversa B −1 y completando la primera fila de los zj − cj y z̄.
Recı́procamente, dada una tabla del simplex, la base B se construye a partir
de los vectores aj asociados a los vectores unitarios es de la tabla en el orden
canónico s = 1, 2, . . . , m.
Además, si la tabla inicial del simplex incorporaba una submatriz identidad
bien porque I ⊂ A o bien porque se hubieran añadido variables artificiales, se
puede recuperar de forma instantánea la inversa de la base B −1 sin más que
reproducir los yj de la tabla asociados a los vectores unitarios de la submatriz
identidad que originó la base inicial.
Para comprobar este resultado, y suponiendo que se han añadido las m va-
riables artificiales, es suficiente con observar que las últimas m columnas de la
tabla del simplex son el producto del sistema de ecuaciones ampliado por B −1 .
Concretamente, la tabla del simplex con variables artificiales es

xt xat
zj − c j zia − cai z̄
−1 −1
B A B I x̄B
Con el fin de identificar en cada iteración del simplex la inversa de la base
asociada, se pueden mantener las columnas de las variables artificiales en la Fase
2. Estos vectores nunca entrarán en ninguna base en la Fase 2.

El método de las dos fases no sólo proporciona una base inicial, sino que
I.O. Introducción 104 Algoritmo del simplex. Inicialización

permite detectar la situación de no existencia de solución factible y la redun-

dancia algebraica del sistema de ecuaciones que definen el recinto de soluciones
factibles. Ambas cuestiones se estudiarán en las secciones 4.2.1 y 4.2.2 respecti-
vamente.

Integrando el método de las dos fases para determinar una solución básica
inicial, se propone el siguiente esquema del algoritmo del simplex:
Método de las dos fases I.O. Introducción 105

Io = ∅ , Ia = {1, . . . , m} ; I = Io ∪ Ia Jo = {1, . . . , n} , Ja = ∅ ; J = Jo ∪ Ja
m m
zj − cj = i=1 aij ∀j ∈ Jo , zs − cs = 0 ∀s ∈ Ia , z̄ = i=1 bi
yj = aj ∀j ∈ Jo ys = es ∀s ∈ Ia x̄ = b
fase=1
do
J + ≡ {j ∈ J / zj − cj > 0}
if (J + = ∅) then
if (fase = 1) then
if (Ia = ∅) then ! Eliminar Variables artificiales de la tabla
zj − cj = ctB yj − cj ∀j ∈ Jo zs − cs = 0 ∀s ∈ Io z̄ = ctB x̄
fase = 2
else
Ia+ ≡ {i ∈ Ia / x̄ai > 0}
if (Ia+ = ∅) then
NO EXISTE SOLUCIÓN FACTIBLE. FIN.
else
do while (i ∈ Ia / x̄ai = 0)
Joi ≡ {j ∈ Jo / yia j = 0}
if (Joi = ∅) then
Eliminar la ecuación ia -ésima y la variable xai de la Tabla.
else
Sea j ∈ Joi .
Ia = Ia − {i} ; Ja = Ja ∪ {i} Jo = Jo − {j} ; Io = Io ∪ {j}
Pivotar la Tabla en yia j
endif
enddo
endif
endif
else ! Fase 2
SOLUCIÓN ÓPTIMA: x̄∗s = x̄s ∀s ∈ Io , x̄∗j = 0 ∀j ∈ Jo , z̄ ∗ = z̄. FIN.
endif
else ! ( J + = ∅)
if ( ∃k ∈ J + / yk ≤ 0) then
SOLUCIÓN NO ACOTADA. FIN.
else ! (∀k ∈ J + yk ≤ 0)
Criterio Entrada: Determinar k ∈ J tal que zk − ck = máxj∈J + {zj − cj }
 
Criterio Salida: Determinar l ∈ I tal que yx̄lkl = M in yx̄sks / ysk > 0
I = I ∪ {k} − {l} J = J ∪ {l} − {k}. Actualizar Io , Ia , Jo , Ja .
Pivotar la Tabla en ylk
endif
endif
enddo
I.O. Introducción 106 Algoritmo del simplex. Inicialización

Para ilustrar el caso i ∈ Ia∗ tal que existe un j ∈ Jo∗ verificando yia j = 0 se
propone el siguiente ejemplo.

Ejemplo 4.3. Sea el problema de programación lineal siguiente:

⎧
⎪
⎪ M in 3x1 +2x2
⎪
⎪
⎨ x1 +x2 =1
P
⎪
⎪ 2x1 +x2 =2
⎪
⎪
⎩
xj ≥0 ∀j = 1, 2

La tabla del simplex inicial de la Fase 1 es la siguiente:

0 0 1 1
x1 x2 xa1 xa2
3 2 0 0 3
1 xa1 1 1 1 0 1
1 xa2 2 1 0 1 2

Al pivotar se obtiene la siguiente tabla óptima de la Fase 1:

0 0 1 1
x1 x2 xa1 xa2
0 −1 −3 0 0
0 x1 1 1 1 0 1
1 xa2 0 -1 −2 1 0

Esta tabla identifica las condiciones anteriores, es decir, aa2 ∈ B ∗ , x̄a2 = 0

y existe un elemento y22a = −1 = 0. Al elegir como pivote dicho elemento,
se obtiene siguiente tabla, que también es óptima para la Fase 1, pero con la
ventaja de no tener variables artificiales en la base:

0 0 1 1
x1 x2 xa1 xa2
0 0 −1 −1 0
0 x1 1 0 −1 1 1
0 x2 0 1 2 −1 0

Al sustituir los coeficientes de la función objetivo de la Fase 1 por los origi-

nales, se obtiene, en este ejemplo, la tabla óptima de la Fase 2:
Método de las dos fases I.O. Introducción 107

3 2 − −
x1 x2 xa1 xa2
0 0 − − 3
3 x1 1 0 −1 1 1
2 x2 0 1 2 −1 0

Las columnas de las variables artificiales identifican la inversa de la base

óptima, ver observación 4.1.

4.2.1. No existencia de solución factible

Proposición 4.1. Si en la solución óptima de P 1 existe una variable artificial
en la base con un valor positivo, es decir, ∃i ∈ Ia∗ tal que x̄ai > 0, entonces no
existe solución factible para P .

Demostración
Sea (x∗ , xa∗ ) la solución óptima de P 1 . Al verificar las hipótesis de la pro-
posición, el valor de la función objetivo de esta solución en el problema P 1 serı́a
positivo.
Si existiera solución factible de P , sea por ejemplo x0 , la solución (x0 , 0) serı́a
una solución del problema P 1 , y serı́a mejor que (x∗ , xa∗ ) puesto que el valor
de la función objetivo serı́a nulo. Por consiguiente, no puede existir solución
factible para P .

Con el siguiente ejemplo se ilustra la detección de no existencia de solución

factible con el método de las dos fases.

Ejemplo 4.4. Sea el problema de programación lineal

⎧
⎪
⎪ M in 2x1 +2x2 −x3 +3x4
⎪
⎪
⎪
⎪
⎪
⎨ x1 +2x2 −x3 +2x4 =3
P x1 −x2 +2x3 −3x4 =4
⎪
⎪
⎪
⎪ −x1 −5x2 +4x3 −7x4 =2
⎪
⎪
⎪
⎩ xj ≥ 0 ∀j = 1, 2, 3, 4

Fase 1:
I.O. Introducción 108 Algoritmo del simplex. Inicialización

⎧
⎪
⎪ M in xa1 +xa2 +xa3
⎪
⎪
⎪
⎪ −x3 +xa1
⎪
⎪
x1 +2x2 +2x4 =3
⎪
⎨ x1 −x2 +2x3 −3x4 +xa2 =4
P1
⎪
⎪ −x1 −5x2 +4x3 −7x4 +xa3 =2
⎪
⎪
⎪
⎪
⎪
⎪ xj ≥ 0 ∀j = 1, 2, 3, 4
⎪
⎩
xai ≥ 0 ∀i = 1, 2, 3

Aplicando el algoritmo del simplex se obtienen las siguientes tablas:

0 0 0 0 1 1 1
x1 x2 x3 x4 xa1 xa2 xa3
1 −4 5 −8 0 0 0 9
1 xa1 1 2 −1 2 1 0 0 3
1 xa2 1 −1 2 −3 0 1 0 4
1 xa3 −1 −5 4 −7 0 0 1 2

0 0 0 0 1 1 1
x1 x2 x3 x4 xa1 xa2 xa3
9/4 9/4 0 3/4 0 0 −5/4 13/2
1 xa1 3/4 3/4 0 1/4 1 0 1/4 7/2
1 xa2 3/2 3/2 0 1/2 0 1 −1/2 3
0 x3 −1/4 −5/4 1 −7/4 0 0 1/4 1/2

La tabla óptima de la fase 1 es:

0 0 0 0 1 1 1
x1 x2 x3 x4 xa1 xa2 xa3
0 0 0 0 0 −3/2 −1/2 2
1 xa1 0 0 0 0 1 −1/2 1/2 2
0 x1 1 1 0 1/3 0 2/3 −1/3 2
0 x3 0 −1 1 −5/3 0 1/6 1/6 1

En esta tabla óptima, se observa que B ∗ = {aa1 , a1 , a3 }, de forma que

Io∗ = {1, 3} Ia∗ = {1} Jo∗ = {2, 4} Ja∗ = {2, 3}

Método de las dos fases I.O. Introducción 109

En este ejemplo, 1 ∈ Ia∗ = ∅ y se verifica que x̄a1 = 2 > 0, por lo que no

existe solución factible para el problema planteado.

4.2.2. Redundancia del sistema de ecuaciones

En los desarrollos teóricos del problema de programación lineal, se suponı́a
que rg(A) = m. Para un problema de grandes dimensiones, la comprobación de
esta hipótesis puede ser muy ineficiente desde un punto de vista computacional.
El método de las dos fases permite analizar directamente la redundancia del
sistema de ecuaciones determinando explı́citamente la combinación lineal de las
ecuaciones implicadas.
Concretamente, siempre que exista una variable artificial en una base con va-
lor nulo y no se pueda pivotar para que sea sustituida por una variable original,
la ecuación asociada a dicha variable artificial es redundante y puede ser elimi-
nada. La siguiente proposición formaliza esta propiedad para la base óptima B ∗
del problema P 1 .

Proposición 4.2. Si en la solución óptima de P 1 existe una variable artificial

en la base x̄ak = 0 para algún k ∈ Ia∗ verificando, además, que ykj = 0 ∀j ∈
Jo∗ , entonces el sistema de ecuaciones Ax = b es redundante y la ecuación
correspondiente a esta variable se puede suprimir.

Demostración
Sea ai , con i ∈ {1, . . . , m}, el vector cuyos elementos son los de la fila i-ésima
de la matriz A de restricciones del problema P , es decir,
⎛ ⎞ ⎛ ⎞
(a1 )t ai1
⎜ .. ⎟ ⎜ . ⎟
A=⎜
⎝ .
⎟
⎠ ai = ⎜ . ⎟
⎝ . ⎠ ∀i ∈ {1, . . . , m}
m t
(a ) ain

El sistema de ecuaciones Ax = b es redundante si, y sólo si, existe una

combinación lineal no trivial entre las filas de la matriz A:

m

λi ai = 0 ∈ IRn
i=1

siendo
I.O. Introducción 110 Algoritmo del simplex. Inicialización

λ = 0, λ ∈ IRm

y verificando, para que el sistema de ecuaciones sea compatible, que

m

λi bi = 0
i=1

El vector λ que identifica la combinación lineal de las ecuaciones se determina

a partir del ı́ndice k ∈ Ia∗ y de la inversa de la base óptima B ∗ del problema P 1
de la fase 1:

λt = etk (B ∗ )−1

donde ek ∈ IRm es el vector unitario con un 1 en la componente k-ésima y ceros

en el resto.
Por consiguiente, λ es el vector de la fila k-ésima de la inversa de la base
óptima y verifica las siguientes propiedades:

1. λ = 0
Ya que el vector λ coincide con la fila de una matriz que se puede invertir.
m
2. i=1 λi ai = 0 ∈ IRn
En efecto,

m

λi ai = λt A = etk (B ∗ )−1 A = etk (. . . , ei , . . . , yj , . . .)
i=1

donde ei son vectores unitarios para todo i ∈ Io∗ , y los vectores yj =

(B ∗ )−1 aj para j ∈ Jo∗ .
Al ser i = k para cualquier i ∈ Io∗ , se verifica que

etk ei = 0 ∀i ∈ Io∗

Por la hipótesis de la proposición, para el ı́ndice k ∈ Ia∗ verificando ykj =

0 ∀j ∈ Jo∗ , se tiene que

etk yj = 0 ∀j ∈ Jo∗
Método de las dos fases I.O. Introducción 111

m
3. i=1 λ i bi = 0
Por definición del vector λ, se verifica

m

λi bi = λt b = etk (B ∗ )−1 b = etk x̄B ∗ = x̄ak = 0
i=1

Se concluye ası́ la demostración.

En la demostración de esta proposición se identifica la combinación lineal de

las ecuaciones del sistema Ax = b a partir de la fila k-ésima de la inversa de la
base óptima para la Fase 1, siendo xak la variable artificial que pertenece a dicha
base con valor 0.
Una demostración alternativa se basa en considerar los vectores yj∗ como
los coeficientes de la dependencia lineal del vector aj respecto de la base B ∗ .
∗
Entonces, bajo las condiciones de la proposición 4.2, se tiene que si ykj = 0 para
todo j ∈ Jo∗ , ninguno de los vectores aj depende linealmente del vector asociado
a xak y, por consiguiente, el rango de la matriz A no serı́a m, sino m − 1.

A continuación se ilustra esta proposición con un ejemplo.

Ejemplo 4.5. Sea el problema de programación lineal

⎧
⎪
⎪ M in 2x1 +x2 −x3 +3x4
⎪
⎪
⎪
⎪
⎪
⎨ x1 +2x2 −x3 +2x4 =1
P x1 −x2 +2x3 −3x4 =4
⎪
⎪
⎪
⎪ −x1 −5x2 −7x4
⎪
⎪
+4x3 =2
⎪
⎩ xj ≥ 0 ∀j = 1, 2, 3, 4

Fase 1:

⎧
⎪
⎪ M in xa1 +xa2 +xa3
⎪
⎪
⎪
⎪ −x3 +xa1
⎪
⎪
x1 +2x2 +2x4 =1
⎪
⎨ x1 −x2 +2x3 −3x4 +xa2 =4
P1
⎪
⎪ −x1 −5x2 +4x3 −7x4 +xa3 =2
⎪
⎪
⎪
⎪
⎪
⎪ xj ≥ 0 ∀j = 1, 2, 3, 4
⎪
⎩
xai ≥ 0 ∀i = 1, 2, 3
I.O. Introducción 112 Algoritmo del simplex. Inicialización

Por el método de las dos fases, en la Fase 1, tendrı́amos la siguiente secuen-

cia de tablas:

0 0 0 0 1 1 1
x1 x2 x3 x4 xa1 xa2 xa3
1 −4 5 −8 0 0 0 7
1 xa1 1 2 −1 2 1 0 0 1
1 xa2 1 −1 2 −3 0 1 0 4
1 xa3 −1 −5 4 −7 0 0 1 2

0 0 0 0 1 1 1
x1 x2 x3 x4 xa1 xa2 xa3
9/4 9/4 0 3/4 0 0 −5/4 9/2
1 xa1 3/4 3/4 0 1/4 1 0 1/4 3/2
1 xa2 3/2 3/2 0 1/2 0 1 −1/2 3
0 x3 −1/4 −5/4 1 −7/4 0 0 1/4 1/2

0 0 0 0 1 1 1
x1 x2 x3 x4 xa1 xa2 xa3
0 0 0 0 −3 0 −2 0
1 x1 1 1 0 1/3 4/3 0 1/3 2
1 xa2 0 0 0 0 −2 1 −1 0
0 x3 0 −1 1 −5/3 1/3 0 1/3 1

En esta última tabla, la óptima, la base es:

B ∗ = {a1 , aa2 , a3 }

es decir, Ia∗ = {2} = ∅ y, además, x̄a2 = 0 verificando y2∗a j = 0 ∀j ∈ Jo∗ . Es la

situación descrita en la proposición 4.2.
El vector λ en este ejemplo se evalúa a partir de la inversa de la base óptima:
⎛ ⎞
4/3 0 1/3
⎜ ⎟
λt = et2 (B ∗ )−1 = (0, 1, 0) ⎜
⎝ −2 1 −1 ⎟⎠ = (−2, 1, −1)
1/3 0 1/3

que, como se puede comprobar, define la combinación lineal del sistema de ecua-
Método de las dos fases I.O. Introducción 113

ciones y es la segunda fila de la inversa de la base óptima.

Observación 4.2. Observando la tabla del simplex anterior se puede aportar

una demostración más intuitiva de la redundancia del sistema de ecuaciones sin
más que observar que son nulos todos los coeficientes de las variables normales,
las originales más las de holgura, y que, por tanto, la ecuación lineal asociada
a la tercera fila identifica una combinación de variables artificiales que es igual
a cero (1xa1 − 1/2xa2 + 1/2xa3 = 0).
Si se sustituyen en esta ecuación los valores de las variables artificiales por
el resto de las ecuaciones donde se introdujeron, se obtiene de forma natural
una combinación lineal no trivial de las ecuaciones que se anula.

Una vez tachadas la tercera fila de la tabla, la asociada a xa1 , y las columnas
asociadas a las variables artificiales, se pasa a la siguiente fase.
Fase 2:
Volviendo a calcular la primera fila a partir de los coeficientes de la función
objetivo del problema original, se obtiene la tabla del simplex:

2 1 −1 3
x1 x2 x3 x4
0 2 0 −2/3 3
2 x1 1 1 0 1/3 2
−1 x3 0 −1 1 −5/3 1

Pivotando en el elemento y12 = 1 se obtiene la tabla óptima del simplex

2 1 −1 3
x1 x2 x3 x4
−2 0 0 −4/3 −1
1 x2 1 1 0 1/3 2
−1 x3 1 0 1 −4/3 3

que corresponde a la solución óptima

x̄1 = 0 x̄2 = 2 x̄3 = 3 x̄4 = 0 z̄ = −1

Observación 4.3. Si el problema de programación lineal P es de maximiza-

ción, el problema P 1 asociado a la Fase 1 no varı́a, puesto que en esta fase
I.O. Introducción 114 Algoritmo del simplex. Inicialización

hay que construir una solución factible anulando las variables artificiales que
inicialmente están en la base. En la Fase 2 hay que considerar el problema de
máximo, bien multiplicando por −1 los coeficientes de la función objetivo para
convertir el problema de máximo en uno de mı́nimo o bien alterando el criterio
de entrada del algoritmo del simplex según se vio en la observación 3.2.

4.3. Método de las penalizaciones

Dado el problema de programación lineal P , y una vez ampliado con las va-
riables artificiales, el método de las penalizaciones plantea un problema asociado
de programación lineal en el que se penalizan fuertemente los valores no nulos
de las variables artificiales en la función objetivo. La aplicación del algoritmo
del simplex a este nuevo problema forzará la salida de la base óptima de las va-
riables artificiales —y su consiguiente anulación en la solución básica asociada—
para recuperar ası́ una solución factible del problema original y poder llegar al
óptimo.
Formalmente, dado el problema de programación lineal:
⎧
⎪
⎪ ct x
⎨ M in
P Ax = b
⎪
⎪
⎩ x ≥ 0

introduciendo una constante positiva M > 0 arbitrariamente grande y el vector

Mt = (M, . . . , M ) de m componentes se define el problema ”penalizado”:
⎧
⎪
⎪ ct x Mt x a
⎨ M in +
M
P Ax + Ixa = b
⎪
⎪
⎩ x, x a
≥ 0

Al igual que con el método de las dos fases, la base inicial B está formada
por los vectores unitarios asociados a las variables artificiales, por lo que la tabla
del simplex inicial se obtiene fácilmente.
Es fácil demostrar que si (x∗ , xa∗ ) es la solución óptima de P M , x∗ será
la solución óptima de P si, y sólo si, xa∗ = 0. Esta situación se ilustra con el
siguiente ejemplo.

Aplicando el método de las penalizaciones al ejemplo 4.2, se define el si-

Método de las penalizaciones I.O. Introducción 115

guiente problema

⎧
⎪
⎪ M in x1 +2x2 −x3 −2x4 +2x5 +3x6 +M xa1 +M xa2 +M xa3
⎪
⎪
⎪
⎪ −x5 +xa1
⎪
⎪
x1 +x3 +x4 +2x6 =2
⎪
⎨ −x1 +x2 +2x3 +x5 −x6 +xa2 =1
PM
⎪
⎪ 2x1 −x2 +3x3 +2x4 +x5 +xa3 =5
⎪
⎪
⎪
⎪
⎪
⎪ xj ≥ 0 ∀j = 1, . . . , 6
⎪
⎩
xai ≥ 0 ∀i = 1, . . . , 3

La tabla del simplex inicial asociada a la base B = {aa1 , aa2 , aa3 } es la siguiente

1 2 −1 −2 2 3 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
2M − 1 −2 6M + 1 3M + 2 M −2 M −3 0 0 0 8M
M xa1 1 0 1 1 −1 2 1 0 0 2
M xa2 −1 1 2 0 1 −1 0 1 0 1
M xa3 2 −1 3 2 1 0 0 0 1 5

Para aplicar el criterio de entrada, todos los zj − cj con coeficiente mayor

que 0 multiplicando a la constante M son positivos, el mayor será el de mayor
coeficiente y, en caso de empate, se compara el término constante. En este caso,

zk − ck = M ax{(2M − 1), (6M + 1), (3M + 2), (M − 2), (M − 3)} = (6M + 1)

y, por consiguiente, entra en la base a3 .

Aplicando el criterio de salida,

x̄l 2 1 5 1
= M in{ ; ; }=
yl3 1 2 3 2

sale de la base aa2 .

La nueva tabla al pivotar en y32a = 2 es
I.O. Introducción 116 Algoritmo del simplex. Inicialización

1 2 −1 −2 2 3 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
5M... −3M... 0 3M... −2M... 4M... 0 −3M... 0 5M − 1/2
M xa1 3/2 −1/2 0 1 −3/2 5/2 1 −1/2 0 3/2
−1 x3 −1/2 1/2 1 0 1/2 −1/2 0 1/2 0 1/2
M xa3 7/2 −5/2 0 2 −1/2 3/2 0 −3/2 1 7/2

Pivotando en y11a = 3/2 se obtiene

1 2 −1 −2 2 3 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
0 −4/3M... 0 −1/3M... 3M... −12/3M... −10/3M... −4/3M... 0 0
1 x1 1 −1/3 0 2/3 −1 5/3 2/3 −1/3 0 1
−1 x3 0 1/3 1 1/3 0 1/3 1/3 1/3 0 1
M xa3 0 −4/3 0 −1/3 3 −13/3 −7/3 −1/3 1 0

Pivotando en y53a = 3 se obtiene

1 2 −1 −2 2 3 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
0 −4 0 +2 0 −6 −M... −M... −M... 0
1 x1 1 −7/9 0 5/9 0 2/9 −1/9 −4/9 1/3 1
−1 x3 0 1/3 1 1/3 0 1/3 1/3 1/3 0 1
2 x5 0 −4/9 0 −1/9 1 −13/9 −7/9 −1/9 1/3 0

Pivotando en y14 = 5/9 se obtiene la tabla óptima

Método de las penalizaciones I.O. Introducción 117

1 2 −1 −2 2 3 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
−18/5 −6/5 0 0 0 −34/5 −M... −M... −M... −18/5
−2 x4 9/5 −7/5 0 1 0 2/5 −1/5 −4/5 3/5 9/5
−1 x3 −3/5 4/5 1 0 0 1/5 2/5 3/5 −1/5 2/5
2 x5 1/5 −3/5 0 0 1 −7/5 −4/5 −1/5 2/5 1/5

La solución óptima es

x̄1 = 0 x̄2 = 0 x̄3 = 2/5 x̄4 = 9/5 x̄5 = 1/5 z̄ = −18/5

De forma análoga al método de las dos fases, el método de las penalizaciones

identifica la no existencia de soluciones factibles cuando a la base óptima del
problema P M pertenezca un vector columna asociado a una variable artificial y
ésta tome un valor positivo.
El caso de redundancia en el sistema de ecuaciones Ax = b también se puede
detectar. Aplicando el método de las penalizaciones al ejemplo 4.5 se obtiene la
siguiente secuencia de tablas del simplex:

2 1 −1 3 M M M
x1 x2 x3 x4 xa1 xa2 xa3
M −2 −4M − 2 5M + 1 −8M − 3 0 0 0 7M
M xa1 1 2 −1 2 1 0 0 1
M xa2 1 −1 2 −3 0 1 0 4
M xa3 −1 −5 4 −7 0 0 1 2

2 1 −1 3 M M M
x1 x2 x3 x4 xa1 xa2 xa3
9M/4.. 9M/4.. 0 3M/4.. 0 0 −5M/4.. 9M/2..
M xa1 3/4 3/4 0 1/4 1 0 1/4 3/2
M xa2 3/2 3/2 0 1/2 0 1 −1/2 3
−1 x3 −1/4 −5/4 1 −7/4 0 0 1/4 1/2
I.O. Introducción 118 Algoritmo del simplex. Inicialización

2 1 −1 3 M M M
x1 x2 x3 x4 xa1 xa2 xa3
−1 0 0 −19/12 −3M.. 0 −2M.. −1
1 x2 1 1 0 1/3 4/3 0 1/3 2
M xa2 0 0 0 0 −2 1 −1 0
−1 x3 1 0 1 −3/4 5/3 0 2/3 3

En esta tabla, que es la óptima, se elimina la segunda fila por ser redundante
y se obtiene directamente la solución óptima

x̄1 = 0 x̄2 = 2 x̄3 = 3 x̄4 = 0 z̄ = −1

El caso en el que se detecte no acotación en P M requiere de un análisis más

detallado; más concretamente, supongamos que tenemos una solución básica
factible x̄∗ de P M para la que se verifica:

zk − ck = máx{zj − cj } > 0 , yk ≤ 0
j

entonces se pueden dar dos casos:

x̄a∗ = 0.
En este caso, P es no acotado. En efecto, si P M es no acotado es que
existe una dirección de S a

dt = (do t , da t ) ≥ (0t , 0t )

verificando

Ado + Ida = 0

ct d o + M t d a < 0

Como M es arbitrariamente grande y da ≥ 0, necesariamente debe verifi-

carse
Método de las penalizaciones I.O. Introducción 119

da = 0 , ct do < 0

Pero do es una dirección de S ya que Ado = 0 y, por tanto, P es no

acotado.

En el ejemplo 3.2 del capı́tulo 3, se obtiene la siguiente tabla del simplex:

6 5 −2 2 −1 1 M M M
x1 x2 x3 x4 x5 x6 xa1 xa2 xa3
−3 0 1 0 −6 0 −M.. −M.. −M..
5 x2 0 1 0 0 −2 0 5/4 −1/2 −3/4 5/4
2 x4 1 0 0 1 2 0 −1 1 1 1
1 x6 1 0 −1 0 −1 1 3/4 −1/2 −1/4 3/4

que identifica un problema con solución no acotada al existir un k = 3 ∈ J

tal que z3 − c3 = 1 > 0 y verificar que y3 ≤ 0.
La dirección asociada en el recinto S a ⊂ IR9 es

dt = (0, 0, 1, 0, 0, 1, 0, 0, 0)

cuyas 6 primeras componentes identifican la dirección del recinto S

dto = (0, 0, 1, 0, 0, 1) ct do = −1 < 0

∃s ∈ Ia∗ tal que x̄a∗

s > 0.

En este caso P es no factible.

Para comprobarlo, veamos, en primer lugar, que


ysj ≤ 0 , ∀j ∈ J ∗
s∈Ia∗

En efecto, ∀j ∈ J ∗ se verifica
I.O. Introducción 120 Algoritmo del simplex. Inicialización

 
zj − c j = cs ysj + M ysj − cj
s∈Io∗ s∈Ia∗

Considerando el ı́ndice k ∈ J ∗ , determinado por:

zk − ck = máx∗ {zj − cj } yk ≤ 0
j∈J

se deduce que


ysk = 0
s∈Ia∗

En caso contrario, si existiera un ysk < 0 para algún s ∈ Ia∗ , no podrı́a ser
zk − ck > 0, al ser M > 0 arbitrariamente grande.

Tampoco puede existir ningún j ∈ J ∗ tal que s∈I ∗ ysj > 0; en caso a

contrario, al multiplicar por la constante M se obtendrı́a un zj −cj superior

a zk − ck , que ha sido elegido por ser el máximo.

En segundo lugar, a partir de las ecuaciones del sistema explı́cito asociadas

a las variables artificiales


xs = x̄∗s − ysj xj , s ∈ Ia∗
j∈J ∗

se obtiene al sumarlas:

   
xs = x̄∗s − xj ( ysj )
s∈Ia∗ s∈Ia∗ j∈J ∗ s∈Ia∗

Si P tuviera solución factible, deberı́an existir unos valores para los paráme-
tros xj , con j ∈ J ∗ , que anulasen todas las componentes de la variable
artificial y, en consecuencia, la suma anterior, o lo que es lo mismo,

  
x̄∗s = xj ( ysj )
s∈Ia∗ j∈J ∗ s∈Ia∗

Pero el lado izquierdo es positivo, ya que tenemos una variable artificial en

la base que es distinta de cero, mientras que el lado derecho serı́a menor o
Método de las penalizaciones I.O. Introducción 121

igual que cero, según acabamos de ver. Esta contradicción prueba que P
es no factible.

El método de las penalizaciones, al igual que el método de las dos fases,

no sólo proporciona una base inicial, sino que permite detectar la situación de
no existencia de solución factible y la redundancia algebraica del sistema de
ecuaciones que definen el recinto de soluciones factibles.
Integrando el método de las penalizaciones para determinar una solución
básica inicial, se propone el siguiente esquema del algoritmo del simplex:
I.O. Introducción 122 Algoritmo del simplex. Inicialización

Io = ∅ , Ia = {1, . . . , m} ; I = Io ∪ Ia Jo = {1, . . . , n} , Ja = ∅ ; J = Jo ∪ Ja
m m
zj − cj = M · i=1 aij − cj ∀j ∈ Jo , zs − cs = 0 ∀s ∈ Ia , z̄ = M · i=1 bi
yj = aj ∀j ∈ Jo ys = es ∀s ∈ Ia x̄ = b
do
zk − ck = máxj∈J {zj − cj }
if (zk − ck ≤ 0) then
if (Ia = ∅) then
Ia+ ≡ {i ∈ Ia / x̄ai > 0}
if (Ia+ = ∅) then
NO EXISTE SOLUCIÓN FACTIBLE. FIN.
else
do while (i ∈ Ia / x̄ai = 0)
Joi ≡ {j ∈ Jo / yia j = 0}
if (Joi = ∅) then
Eliminar la ecuación ia -ésima y la variable xai de la Tabla.
else
Sea j ∈ Joi .
Ia = Ia − {i} ; Ja = Ja ∪ {i} Jo = Jo − {j} ; Io = Io ∪ {j}
Pivotar la Tabla en yia j
endif
enddo
endif
endif
SOLUCIÓN ÓPTIMA: x̄∗s = x̄s ∀s ∈ Io , x̄∗j = 0 ∀j ∈ Jo , z̄ ∗ = z̄. FIN.
else
if ( yk ≤ 0) then
if (∃i ∈ Ia tal que x̄ai > 0) then
NO EXISTE SOLUCIÓN FACTIBLE. FIN.
else
SOLUCIÓN NO ACOTADA. FIN.
endif
else
Criterio Entrada: Entra ak
 
x̄l x̄s
Criterio Salida: Determinar l ∈ I tal que ylk = M in ysk / ysk > 0
I = I ∪ {k} − {l} J = J ∪ {l} − {k}. Actualizar Io , Ia , Jo , Ja .
Pivotar la Tabla en ylk
endif
endif
enddo
Método de las penalizaciones I.O. Introducción 123

Observación 4.4. Si el problema de programación lineal P es de máximo, la

función objetivo para el problema P M serı́a:

M ax{ct x − Mt xa }

o su equivalente

M in{−ct x + Mt xa }