ProgM El método símplex Curso 2024-2025

3.1 PUNTOS EXTREMOS Y OPTIMALIDAD

En la figura 1.3 se observó que cuando existe una solución óptima de un problema de
programación lineal, entonces también existe un punto extremo óptimo. Como se demostrará
enseguida, esta observación siempre es cierta.

Sea el siguiente problema de programación lineal:

Minimizar 𝒄𝒄𝒄𝒄
D

Sujeta a
ep

𝐴𝐴𝒙𝒙 = 𝒃𝒃
ar

𝒙𝒙 ≥ 𝟎𝟎.
ta

Sean 𝒙𝒙1 , 𝒙𝒙2 , … , 𝒙𝒙𝑘𝑘 los puntos extremos de la región factible, y 𝒅𝒅1 , 𝒅𝒅2 , … , 𝒅𝒅𝑙𝑙 las
m

direcciones extremas de la región factible. Recordad que cualquier punto 𝒙𝒙 en la región

en

factible se puede representar como 𝒙𝒙 = ∑𝑘𝑘𝑗𝑗=1 𝜆𝜆𝑗𝑗 𝒙𝒙𝑗𝑗 + ∑𝑙𝑙𝑗𝑗=1 𝜇𝜇𝑗𝑗 𝒅𝒅𝑗𝑗 , ∑𝑘𝑘𝑗𝑗=1 𝜆𝜆𝑗𝑗 = 1, 𝜆𝜆𝑗𝑗 ≥ 0 𝑗𝑗 =
to

1,2, … , 𝑘𝑘 y 𝜇𝜇𝑗𝑗 ≥ 0 𝑗𝑗 = 1,2, … , 𝑙𝑙.

de

Por consiguiente, el problema de programación lineal se puede transformar en un

Es

problema en las variables 𝜆𝜆1 , 𝜆𝜆2 , … , 𝜆𝜆𝑘𝑘 , 𝜇𝜇1 , 𝜇𝜇2 , … , 𝜇𝜇𝑙𝑙 , el cual se puede expresar como el
ta

siguiente programa lineal:

dí
st

Minimizar ∑𝑘𝑘𝑗𝑗=1 𝜆𝜆𝑗𝑗 (𝒄𝒄𝒙𝒙𝑗𝑗 ) + ∑𝑙𝑙𝑗𝑗=1 𝜇𝜇𝑗𝑗 (𝒄𝒄𝒅𝒅𝑗𝑗 )

ic
a

Sujeta a ∑𝑘𝑘𝑗𝑗=1 𝜆𝜆𝑗𝑗 = 1, 𝜆𝜆𝑗𝑗 ≥ 0 𝑗𝑗 = 1,2, … , 𝑘𝑘 y 𝜇𝜇𝑗𝑗 ≥ 0 𝑗𝑗 = 1,2, … , 𝑙𝑙.

e
I.

Puesto que las 𝜇𝜇𝑗𝑗 pueden hacerse arbitrariamente grandes, entonces el mínimo es −∞ si
O

𝒄𝒄𝒅𝒅𝑗𝑗 < 0 para algún 𝑗𝑗 = 1,2, … , 𝑙𝑙. Si 𝒄𝒄𝒅𝒅𝑗𝑗 ≥ 0 para toda 𝑗𝑗 = 1,2, … , 𝑙𝑙, entonces las 𝜇𝜇𝑗𝑗
.y

correspondientes se pueden hacer cero. Ahora, bien, para minimizar ∑𝑘𝑘𝑗𝑗=1 𝜆𝜆𝑗𝑗 (𝒄𝒄𝒙𝒙𝑗𝑗 ),
D

sobre las variables 𝜆𝜆1 , 𝜆𝜆2 , … , 𝜆𝜆𝑘𝑘 tales que ∑𝑘𝑘𝑗𝑗=1 𝜆𝜆𝑗𝑗 = 1 y 𝜆𝜆𝑗𝑗 ≥ 0 𝑗𝑗 = 1,2, … , 𝑘𝑘
.M

simplemente se determina el mínimo 𝒄𝒄𝒙𝒙𝑗𝑗 , por ejemplo 𝒄𝒄𝒙𝒙𝑝𝑝 , se toma 𝜆𝜆𝑝𝑝 = 1 y todas las
.U

otras 𝜆𝜆𝑗𝑗 iguales a cero.

ni

Resumiendo, la solución óptima del problema lineal es finita si y sólo si 𝒄𝒄𝒅𝒅𝑗𝑗 ≥ 0 para
ve

todas las direcciones extremas. Además, si este es el caso, entonces el punto mínimo se
rs

determina seleccionando el mínimo valor objetivo de entre todos los puntos extremos.
id

Lo anterior demuestra que, si existe una solución óptima, entonces debe ser posible
ad

encontrar un punto extremo óptimo. Por supuesto, si el mínimo 𝒄𝒄𝒙𝒙𝑗𝑗 ocurre en más de
de

un índice, entonces todo punto extremo correspondiente es un punto extremo óptimo

y toda combinación convexa de estos puntos es solución óptima. De hecho, todo el
O
vi

conjunto de soluciones óptimas alternativas está dado por el conjunto de las

ed

combinaciones convexas de tales puntos más una combinación lineal no negativa de las
o

direcciones extremas 𝒅𝒅𝑗𝑗 que satisfacen 𝒄𝒄𝒅𝒅𝑗𝑗 = 0.

Ejemplo.- Considerad la región definida por las siguientes restricciones:

−𝑥𝑥1 + 𝑥𝑥2 ≤ 2
−𝑥𝑥1 + 2𝑥𝑥2 ≤ 6

1
 ProgM El método símplex Curso 2024-2025

𝑥𝑥1 , 𝑥𝑥2 ≥ 0
Observad que esta región tiene tres puntos extremos 𝒙𝒙1 , 𝒙𝒙2 y 𝒙𝒙3 y dos direcciones extremas 𝒅𝒅1
0 0 2 1 2
y 𝒅𝒅2 (ved la figura 3.1). Estos son 𝒙𝒙1 = � �, 𝒙𝒙2 = � �, 𝒙𝒙3 = � �, 𝒅𝒅1 = � � y 𝒅𝒅2 = � �.
0 2 4 0 1
D
ep
ar
ta
m
en
to
de
Es

Ahora suponed que se quiere minimizar 𝑥𝑥1 − 3𝑥𝑥2 en la región dada. De la figura 3.1a se
ta

observa que el problema es no acotado y tiene un valor de −∞. En este caso, se tiene
dí

𝒄𝒄𝒙𝒙1 = 0, 𝒄𝒄𝒙𝒙2 = −6, 𝒄𝒄𝒙𝒙3 = −10, 𝒄𝒄𝒅𝒅1 = 1 y 𝒄𝒄𝒅𝒅2 = −1.

st
ic

El problema es equivalente al siguiente

a
e

Minimizar 0𝜆𝜆1 − 6𝜆𝜆2 − 10𝜆𝜆3 + 𝜇𝜇1 − 𝜇𝜇2

I.

Sujeta a
O

𝜆𝜆1 + 𝜆𝜆2 + 𝜆𝜆3 = 1 𝜆𝜆1 , 𝜆𝜆2 , 𝜆𝜆3 , 𝜇𝜇1 , 𝜇𝜇2 ≥ 0.

.y

Puesto que 𝒄𝒄𝒅𝒅2 = −1 < 0 y 𝜇𝜇2 se puede hacer arbitrariamente grande sin violar las
D

restricciones anteriores, entonces el valor objetivo puede hacerse igual a −∞ tomando

.M

𝜇𝜇2 = ∞. Luego, 𝜇𝜇1 se puede tomar igual a cero. Cualquier conjunto de variables no
.U

negativas 𝜆𝜆1 , 𝜆𝜆2 , 𝜆𝜆3 cuya suma sea igual a 1 satisface las restricciones anteriores. Lo
anterior ilustra la condición necesaria y suficiente para no acotamiento de un programa
ni
ve

lineal factible; a saber, 𝒄𝒄𝒄𝒄 < 0 para alguna dirección extrema 𝒅𝒅.
rs

Considerad ahora el problema de minimizar 4𝑥𝑥1 − 𝑥𝑥2 en la misma región. De la figura

id

0
3.1b se observa que la solución óptima es el punto extremo 𝒙𝒙2 = � �. En este caso se
a

2
d

tiene 𝒄𝒄𝒙𝒙1 = 0, 𝒄𝒄𝒙𝒙2 = −2, 𝒄𝒄𝒙𝒙3 = 4, 𝒄𝒄𝒅𝒅1 = 4 y 𝒄𝒄𝒅𝒅2 = 7.

de

En consecuencia, el problema es equivalente al siguiente

O
vi

Minimizar 0𝜆𝜆1 − 2𝜆𝜆2 + 4𝜆𝜆3 + 4𝜇𝜇1 + 7𝜇𝜇2

ed

Sujeta a
o

𝜆𝜆1 + 𝜆𝜆2 + 𝜆𝜆3 = 1 𝜆𝜆1 , 𝜆𝜆2 , 𝜆𝜆3 , 𝜇𝜇1 , 𝜇𝜇2 ≥ 0.

Como los coeficientes de 𝜇𝜇1 y 𝜇𝜇2 en la función objetivo son positivos, se toma 𝜇𝜇1 = 𝜇𝜇2 =
0. Para minimizar la expresión 0𝜆𝜆1 − 2𝜆𝜆2 + 4𝜆𝜆3 , sujeta a 𝜆𝜆1 + 𝜆𝜆2 + 𝜆𝜆3 = 1
𝜆𝜆1 , 𝜆𝜆2 , 𝜆𝜆3 ≥ 0, se hace 𝜆𝜆2 = 1, y 𝜆𝜆1 = 𝜆𝜆3 = 0. Lo anterior demuestra que la solución
0
óptima es el punto extremo 𝒙𝒙2 = � �.
2

2
 ProgM El método símplex Curso 2024-2025

3.2 SOLUCIONES BÁSICAS FACTIBLES

En la sección anterior se obtuvo una condición necesaria y suficiente para tener una
solución no acotada. Asimismo, se demostró que, si existe una solución óptima,
entonces también existe un punto extremo óptimo. El concepto de punto extremos es
un concepto geométrico, aunque para poder usarlo desde un punto de vista
computacional es necesaria una caracterización algebraica de los puntos extremos.
D

En esta sección se presentan las soluciones básicas factibles y se demuestra que

ep

corresponden a los puntos extremos. Esta caracterización permitirá describir

ar

algebraicamente el método símplex.

ta

Definición (Soluciones básicas factibles)

m
en

Considere el sistema 𝐴𝐴𝒙𝒙 = 𝒃𝒃 y 𝒙𝒙 ≥ 𝟎𝟎, en donde 𝐴𝐴 es una matriz 𝑚𝑚 × 𝑛𝑛 y 𝒃𝒃 es un 𝑚𝑚 vector.

to

Suponed que rango (𝐴𝐴, 𝒃𝒃) = rango (𝐴𝐴) = 𝑚𝑚. Después de un posible reordenamiento de las
columnas de 𝐴𝐴, sea 𝐴𝐴 = [𝐵𝐵, 𝑁𝑁], en donde 𝐵𝐵 es una matriz 𝑚𝑚 × 𝑚𝑚 regular y 𝑁𝑁 es una matriz 𝑚𝑚 ×
de

𝒙𝒙𝐵𝐵
(𝑛𝑛 − 𝑚𝑚). La solución 𝒙𝒙 = �𝒙𝒙 � del sistema 𝐴𝐴𝒙𝒙 = 𝒃𝒃, en donde 𝒙𝒙𝐵𝐵 = 𝐵𝐵−𝟏𝟏 𝒃𝒃 y 𝒙𝒙𝑁𝑁 = 𝟎𝟎 se denomina
Es

𝑁𝑁
solución básica del sistema. Si 𝒙𝒙𝐵𝐵 ≥ 𝟎𝟎, entonces 𝒙𝒙 se denomina solución básica factible del
ta

sistema. Aquí, 𝐵𝐵 se denomina la matriz básica (o simplemente la base) y 𝑁𝑁 se denomina matriz

dí

no básica. Las componentes de 𝒙𝒙𝐵𝐵 se denominan variables básicas (o variables dependientes),

st

y las componentes de 𝒙𝒙𝑁𝑁 se denominan variables no básicas (o variables independientes). Si

ic

𝒙𝒙𝐵𝐵 > 𝟎𝟎, entonces 𝒙𝒙 se denomina solución básica factible no degenerada, y si por lo menos una
a

componente de 𝒙𝒙𝐵𝐵 es igual a cero, entonces 𝒙𝒙 se denomina solución básica factible degenerada.
e
I.

El concepto de solución básica factible se ilustra en los dos ejemplos siguientes.

O
.y

Ejemplo 3.2 (Soluciones básicas factibles)

D

Considerad el conjunto poliédrico definido por las siguientes desigualdades y que se ilustra en
.M

la figura 3.2:
.U

𝑥𝑥1 + 𝑥𝑥2 ≤ 6
ni

𝑥𝑥2 ≤ 3
ve
rs

𝑥𝑥1 , 𝑥𝑥2 ≥ 0
id
ad
de
O
vi
ed
o

3
 ProgM El método símplex Curso 2024-2025

Introduciendo las variables de holgura 𝑥𝑥3 y 𝑥𝑥4 , el problema se puede escribir en la siguiente
forma estándar:

𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 = 6

𝑥𝑥2 + 𝑥𝑥4 = 3
𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ≥ 0
D

1 1 1 0
Observad que la matriz de restricciones es 𝐴𝐴 = [𝒂𝒂1 , 𝒂𝒂2 , 𝒂𝒂3 , 𝒂𝒂4 ] = � �. Por la
ep

0 1 0 1
definición anterior, las soluciones básicas factibles corresponden a encontrar una matriz básica
ar

𝐵𝐵 de 2 × 2 con 𝐵𝐵 −𝟏𝟏 𝒃𝒃 no negativa. A continuación se muestran las formas posibles en que 𝐵𝐵 se

ta

puede obtener a partir de 𝐴𝐴.

m
en

1 1 1 −1 6 3 𝑥𝑥3 0
1. 𝐵𝐵 = [𝒂𝒂1 , 𝒂𝒂2 ] = � �, 𝒙𝒙 = 𝐵𝐵−𝟏𝟏 𝒃𝒃 = � � � � = � �, 𝒙𝒙𝑁𝑁 = �𝑥𝑥 � = � �.
0 1 𝐵𝐵 0 1 3 3 𝟒𝟒 0
to

1 0 −𝟏𝟏 1 0 6 6 𝑥𝑥2 0
2. 𝐵𝐵 = [𝒂𝒂1 , 𝒂𝒂4 ] = � �, 𝒙𝒙 = 𝐵𝐵 𝒃𝒃 = � � � � = � �, 𝒙𝒙𝑁𝑁 = �𝑥𝑥 � = � �.
1 𝐵𝐵
de

0 0 1 3 3 𝟑𝟑 0
1 1 −𝟏𝟏 0 1 6 3 𝑥𝑥1 0
3. 𝐵𝐵 = [𝒂𝒂2 , 𝒂𝒂3 ] = � �, 𝒙𝒙 = 𝐵𝐵 𝒃𝒃 = � � � � = � �, 𝒙𝒙𝑁𝑁 = �𝑥𝑥 � = � �.
0 𝐵𝐵
Es

1 1 −1 3 3 𝟒𝟒 0
1 0 −𝟏𝟏 1 0 6 6 𝑥𝑥1 0
4. 𝐵𝐵 = [𝒂𝒂2 , 𝒂𝒂4 ] = � �, 𝒙𝒙 = 𝐵𝐵 𝒃𝒃 = � � � � = � �, 𝒙𝒙𝑁𝑁 = �𝑥𝑥 � = � �.
ta

1 1 𝐵𝐵 −1 1 3 −3 𝟑𝟑 0
1 0 1 0 6 6 𝑥𝑥1 0
dí

−𝟏𝟏
5. 𝐵𝐵 = [𝒂𝒂3 , 𝒂𝒂4 ] = � �, 𝒙𝒙 = 𝐵𝐵 𝒃𝒃 = � � � � = � �, 𝒙𝒙𝑁𝑁 = �𝑥𝑥 � = � �.
0 1 𝐵𝐵 0 1 3 3 0
st

𝟐𝟐
ic

Observad que los puntos correspondientes a los casos 1, 2, 3 y 5 son soluciones básicas factibles.
a

El punto que se obtiene en el caso 4 es una solución básica, pero no es factible porque viola las
e

restricciones de no negatividad. En otras palabras, se tienen cuatro soluciones básicas factibles;

I.

3 6 0 0
O

a saber, 𝒙𝒙1 = � �, 𝒙𝒙2 = � �, 𝒙𝒙3 = � � y 𝒙𝒙4 = �0�.

3 0 3
.y

0 0 3 6
0 3 0 3
D
.M

Estos puntos pertenecen a ℝ4 , ya que después de introducir las variables de holgura se

.U

tienen 4 variables. Al proyectar estas soluciones básicas factibles sobre ℝ2 se obtienen

3 6 0 0
ni

los cuatro puntos siguientes: � �, � �, � � y � �. Esos cuatro puntos se ilustran en la figura

3 0 3 0
ve

3.2. Observad que estos puntos son precisamente los puntos extremos de la región
rs

factible.
id
a

En este ejemplo, el número posible de soluciones básicas factibles está acotado por el
d

número de formas en que es posible obtener dos de las cuatro columnas para formar la
de

base. Por consiguiente, el número de soluciones básicas factibles es menor o igual que
O

�42� = 6. De estas seis posibilidades, un punto viola la no negatividad de 𝐵𝐵−𝟏𝟏 𝒃𝒃. Además,
vi

𝒂𝒂1 y 𝒂𝒂3 no hubieran podido usarse para formar una base. Esto deja sólo cuatro
ed

soluciones básicas factibles. En general, el número de soluciones básicas factibles es

o

𝑛𝑛
menor o igual que �𝑚𝑚 �.

Hay otra forma intuitiva de visualizar las soluciones básicas y las soluciones básicas
factibles. Cada restricción, incluyendo las restricciones de no negatividad, se pueden
asociar de forma única con una cierta variable. Así, 𝑥𝑥1 ≥ 0 se puede asociar con la
variable 𝑥𝑥1 , y la recta 𝑥𝑥1 = 0 es la frontera del semiespacio 𝑥𝑥1 ≥ 0. De forma semejante,

4
 ProgM El método símplex Curso 2024-2025

𝑥𝑥1 + 𝑥𝑥2 ≤ 6 se puede asociar con la variable 𝑥𝑥3 , 𝑥𝑥3 = 0 es la frontera del semiespacio
𝑥𝑥1 + 𝑥𝑥2 ≤ 6. Graficando la frontera de las distintas restricciones se obtiene la gráfica
que se muestra en la figura 3.3. Ahora bien, las soluciones básicas corresponden a la
intersección de dos rectas en esta gráfica; las rectas corresponden a las variables no
básicas. En la gráfica se obtienen cinco intersecciones correspondientes a cinco
soluciones básicas. Observad que las rectas 𝑥𝑥2 = 0 y 𝑥𝑥4 = 0 no intersecan y, por tanto,
no existe ninguna solución básica que corresponda a estas dos variables que son no
D

básicas. Tan pronto como se ha identificado la región factible, es posible distinguir las
ep

soluciones básicas de aquellas que también son las soluciones básicas factibles.
ar
ta
m
en
to
de
Es
ta
dí
st
ic
a
e
I.
O

Ejemplo 3.3 (Soluciones básicas factibles degeneradas)

.y

Considerad el conjunto poliédrico definido por las siguientes desigualdades y que se ilustra en
D

la figura 3.4:
.M

𝑥𝑥1 + 𝑥𝑥2 ≤ 6
.U

𝑥𝑥2 ≤ 3
ni
ve

𝑥𝑥1 + 2𝑥𝑥2 ≤ 9
rs

𝑥𝑥1 , 𝑥𝑥2 ≥ 0
id
a

Introduciendo las variables de holgura 𝑥𝑥3 , 𝑥𝑥4 y 𝑥𝑥5 , el problema se puede escribir en la
d

siguiente forma estándar:

de
O

𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 = 6

vi

𝑥𝑥2 + 𝑥𝑥4 = 3
ed
o

𝑥𝑥1 + 2𝑥𝑥2 + 𝑥𝑥5 = 9

𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 ≥ 0

5
 ProgM El método símplex Curso 2024-2025

1 1 1 0 0
Observad que la matriz de restricciones es 𝐴𝐴 = [𝒂𝒂1 , 𝒂𝒂2 , 𝒂𝒂3 , 𝒂𝒂4 , 𝒂𝒂5 ] = �0 1 0 1 0�.
1 2 0 0 1
𝑥𝑥1 0 −2 1 6 3
Considerad la solución básica factible 𝐵𝐵 = [𝒂𝒂1 , 𝒂𝒂2 , 𝒂𝒂3 ], 𝒙𝒙𝐵𝐵 = �𝑥𝑥2 � = �𝟎𝟎 1 0 � �3� = �3�,
𝑥𝑥3 1 1 −1 9 0
𝑥𝑥4
𝒙𝒙𝑁𝑁 = �𝑥𝑥 �.
5

Observad que esta solución básica factible es degenerada, pues la variable básica 𝑥𝑥3 = 0.
D

Considerad ahora la solución básica factible 𝐵𝐵 = [𝒂𝒂1 , 𝒂𝒂2 , 𝒂𝒂4 ]. Observad que esta base
ep

origina la misma solución básica factible que se obtiene con 𝐵𝐵 = [𝒂𝒂1 , 𝒂𝒂2 , 𝒂𝒂3 ]. También es
ar

posible comprobar que la solución básica factible con la base 𝐵𝐵 = [𝒂𝒂1 , 𝒂𝒂2 , 𝒂𝒂5 ] es la misma.
ta
m

Observad que todas y cada una de tres bases anteriores representan el punto extremo o la
en

solución básica factible (𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 ) = (3,3,0,0,0). Esta solución básica factible es
to

degenerada, pues cada una de las bases asociadas contiene una variable básica en el
nivel cero. Los puntos extremos restantes de la figura 3.4 corresponden a soluciones
de

básicas factibles no degeneradas. También debéis observad que la degeneración no

Es

siempre es el simple resultado de restricciones redundantes. (Ver la figura 2.14, por

ta

ejemplo)
dí
st
ic
a
e
I.
O
.y
D
.M
.U
ni
ve
rs
id
a d
de

Correspondencia entre soluciones básicas factibles y puntos extremos

O
vi

A continuación, se demostrará que la colección de soluciones básicas factibles y la colección de

ed

puntos extremos son equivalentes. En otras palabras, un punto es una solución básica factible
o

si y sólo si es un punto extremo. Puesto que un programa lineal con un valor óptimo finito tiene
una solución óptima en un punto extremo, se observa que para tales problemas siempre es
posible encontrar una solución básica factible.

Sea el siguiente problema de programación lineal:

Minimizar 𝒄𝒄𝒄𝒄

6
 ProgM El método símplex Curso 2024-2025

Sujeta a 𝐴𝐴𝒙𝒙 = 𝒃𝒃

𝒙𝒙 ≥ 𝟎𝟎
donde 𝐴𝐴 es una matriz de 𝑚𝑚 × 𝑛𝑛 de rango 𝑚𝑚. Sea 𝒙𝒙 un punto extremo de la región factible. Se
demostrará que 𝒙𝒙 es también una solución básica factible del sistema 𝐴𝐴𝒙𝒙 = 𝒃𝒃, 𝒙𝒙 ≥ 𝟎𝟎.

Por la definición geométrica, existen 𝑛𝑛 hiperplanos definitorios linealmente independientes

conectantes en 𝒙𝒙. Como 𝐴𝐴𝒙𝒙 = 𝒃𝒃 proporciona 𝑚𝑚 hiperplanos conectantes linealmente
D

independientes, entonces por las restricciones de no negatividad deben existir 𝑝𝑝 = (𝑛𝑛 − 𝑚𝑚)
ep

hiperplanos definitorios conectantes adicionales que junto con 𝐴𝐴𝒙𝒙 = 𝒃𝒃 proporcionan 𝑛𝑛

ar

hiperplanos definitorios linealmente independientes conectantes en 𝒙𝒙. Si tales 𝑝𝑝 hiperplanos

ta

adicionales se denotan por 𝒙𝒙𝑁𝑁 = 𝟎𝟎, entonces es posible concluir que el sistema 𝐴𝐴𝒙𝒙 = 𝒃𝒃, 𝒙𝒙𝑁𝑁 =
m

𝟎𝟎 tiene por solución única a 𝒙𝒙. Ahora, sea 𝑁𝑁 que representa las columnas de las variables 𝒙𝒙𝑁𝑁 en
en

𝐴𝐴, y sea 𝐵𝐵 la matriz integrada por las columnas restantes de 𝐴𝐴, con 𝒙𝒙𝐵𝐵 como las variables
asociadas. Cómo 𝐴𝐴𝒙𝒙 = 𝒃𝒃 puede escribirse como 𝐵𝐵𝒙𝒙𝐵𝐵 + 𝑁𝑁𝒙𝒙𝑁𝑁 = 𝒃𝒃, lo anterior significa que 𝐵𝐵 es
to

una matriz 𝑚𝑚 × 𝑚𝑚 regular; más aún, 𝒙𝒙𝐵𝐵 = 𝐵𝐵−1 𝒃𝒃 ≥ 𝟎𝟎, ya que 𝒙𝒙 = (𝒙𝒙𝐵𝐵 , 𝒙𝒙𝑁𝑁 ) es una solución
de

factible. Por consiguiente, 𝒙𝒙 es una solución básica factible.

Es

Contrariamente, suponed que 𝒙𝒙 es una solución básica factible del sistema 𝐴𝐴𝒙𝒙 = 𝒃𝒃, 𝒙𝒙 ≥ 𝟎𝟎. Se
ta

quiere demostrar que 𝒙𝒙 es un punto extremo. Por definición, 𝒙𝒙 = (𝒙𝒙𝐵𝐵 , 𝒙𝒙𝑁𝑁 ), en donde de
dí

manera correspondiente se tiene que 𝐴𝐴 = (𝐵𝐵, 𝑁𝑁), tal que 𝒙𝒙𝐵𝐵 = 𝐵𝐵−1 𝒃𝒃 ≥ 𝟎𝟎 y 𝒙𝒙𝑁𝑁 = 𝟎𝟎. Sin
st

embargo, esto significa que los 𝑛𝑛 hiperplanos 𝐴𝐴𝒙𝒙 = 𝒃𝒃, 𝒙𝒙𝑁𝑁 = 𝟎𝟎 son conectantes en 𝒙𝒙, y que
ic

además son linealmente independientes, ya que ∃𝐵𝐵−1 . Entonces, por la definición

a

proporcionada en la sección 2.6, 𝒙𝒙 es un punto extremo.

e

Toda solución básica factible es equivalente a un punto extremo. Sin embargo, es posible que
I.
O

exista más de una base correspondiente a la misma solución básica factible o al mismo punto
.y

extremo. Un caso así puede ocurrir en presencia de degeneración, como se ilustró en el ejemplo
3.3. Con respecto a la demostración precedente, este caso corresponde a aquél de un punto
D

extremo en el cual 𝑟𝑟 > 𝑝𝑝 ≡ 𝑛𝑛 − 𝑚𝑚 hiperplanos definitorios desde 𝒙𝒙 ≥ 𝟎𝟎 son conectantes. Así,

.M

para cualquier base asociada, (𝑟𝑟 − 𝑝𝑝) de las 𝒙𝒙𝐵𝐵 variables también son cero. Entonces, el número
.U

de variables positivas es 𝑞𝑞 = 𝑚𝑚 − (𝑟𝑟 − 𝑝𝑝) < 𝑚𝑚. En este caso, toda elección posible de una base
𝐵𝐵 que incluya las columnas de estas 𝑞𝑞 variables mayores que cero representa este punto.
ni
ve

Resulta evidente que, si existe más de una base que representa a un punto extremo, entonces
rs

este punto extremo es degenerado. Sin embargo, la recíproca no necesariamente es verdadera.

id

Considerar el siguiente ejemplo de un conjunto poliédrico.

ad

𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 = 1

de

−𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 = 1

O
vi

𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 ≥ 0.

ed

Considerad la solución 𝒙𝒙
� = (0,1,0). Observad que se trata de un punto extremo o de
o

una solución básica factible con una base correspondiente con 𝑥𝑥1 y 𝑥𝑥2 como variables
básicas. Además, se trata de un punto extremo degenerado. En 𝒙𝒙 � conectan cuatro
hiperplanos definitorios. Además, existen tres formas de elegir tres hiperplanos
linealmente independientes a partir de este conjunto, tales que se obtenga a 𝒙𝒙
� como la
solución única. Sin embargo, la base asociada con 𝒙𝒙
� es única.

7
 ProgM El método símplex Curso 2024-2025

El método símplex es un procedimiento ingenioso que permite moverse de un punto extremo a

otro, mejorando cada vez (o por lo menos, no empeorando) el objetivo. También permite
descubrir si la región factible es vacía o si la solución óptima es no acotada. En la práctica, el
método enumera sólo una pequeña parte de los puntos extremos de la región factible. A
continuación, se presentará la clave de este método.

3.3 CLAVE DEL MÉTODO SÍMPLEX

La clave del método símplex radica en reconocer la optimalidad de un punto extremo solución
D

dado con base a consideraciones locales sin tener que enumerar (globalmente) todos los puntos
ep

extremos o las soluciones básicas factibles.

ar
ta

Sea el siguiente problema de programación lineal:

m

Minimizar 𝒄𝒄𝒄𝒄
en

Sujeta a 𝐴𝐴𝒙𝒙 = 𝒃𝒃
to
de

𝒙𝒙 ≥ 𝟎𝟎
Es

donde 𝐴𝐴 es una matriz de 𝑚𝑚 × 𝑛𝑛 de rango 𝑚𝑚. Suponer que se tiene una solución básica factible
−1
�𝐵𝐵 𝒃𝒃� cuyo valor objetivo 𝑧𝑧0 está dado por
ta

𝟎𝟎
dí

−1 −1
st

𝑧𝑧0 = 𝒄𝒄 �𝐵𝐵 𝒃𝒃� = (𝒄𝒄𝐵𝐵 , 𝒄𝒄𝑁𝑁 ) �𝐵𝐵 𝒃𝒃� = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃 = 𝒄𝒄𝐵𝐵 𝒃𝒃
� (3.1)
ic

𝟎𝟎 𝟎𝟎
a

Luego, sean 𝒙𝒙𝐵𝐵 y 𝒙𝒙𝑁𝑁 que denotan, respectivamente, al conjunto de variables básicas y al
e

conjunto de variables no básicas para la base dada. Entonces, la factibilidad requiere que 𝒙𝒙𝐵𝐵 ≥
I.

𝟎𝟎, 𝒙𝒙𝑁𝑁 ≥ 𝟎𝟎 y que 𝒃𝒃 = 𝐴𝐴𝒙𝒙 = 𝐵𝐵𝒙𝒙𝐵𝐵 + 𝑁𝑁𝒙𝒙𝑁𝑁 . Al multiplicar por 𝐵𝐵−1 el último sistema y reordenando
O

los términos se obtiene

.y

� − ∑𝑗𝑗∈𝑅𝑅(𝒚𝒚 )𝑥𝑥𝑗𝑗
𝒙𝒙𝐵𝐵 = 𝐵𝐵−1 𝒃𝒃 − 𝐵𝐵−1 𝑁𝑁𝒙𝒙𝑁𝑁 = 𝐵𝐵−1 𝒃𝒃 − ∑𝑗𝑗∈𝑅𝑅 𝐵𝐵−1 𝒂𝒂𝑗𝑗 𝑥𝑥𝑗𝑗 = 𝒃𝒃 (3.2)
D

𝑗𝑗
.M

en donde 𝑅𝑅 es el conjunto actual de índices de las variables no básicas. Observando (3.1) y (3.2)
.U

y haciendo que 𝑧𝑧 denote el valor de la función objetivo, se obtiene

ni

� − ∑𝑗𝑗∈𝑅𝑅 �𝒚𝒚 � 𝑥𝑥𝑗𝑗 � = 𝑧𝑧0 − ∑𝑗𝑗∈𝑅𝑅(𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ) 𝑥𝑥𝑗𝑗

𝑧𝑧 = 𝒄𝒄𝒄𝒄 = 𝒄𝒄𝐵𝐵 𝒙𝒙𝐵𝐵 + 𝒄𝒄𝑁𝑁 𝒙𝒙𝑁𝑁 = 𝒄𝒄𝐵𝐵 �𝒃𝒃 (3.3)
ve

𝑗𝑗
rs

en donde 𝑧𝑧𝑗𝑗 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂𝑗𝑗 para toda variable no básica.

id
ad

Aplicando las transformaciones anteriores, el problema de programación lineal PL

puede escribirse nuevamente como
de

Minimizar 𝑧𝑧0 − ∑𝑗𝑗∈𝑅𝑅(𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ) 𝑥𝑥𝑗𝑗

O
vi

�
Sujeta a ∑𝑗𝑗∈𝑅𝑅(𝒚𝒚𝑗𝑗 )𝑥𝑥𝑗𝑗 + 𝒙𝒙𝐵𝐵 = 𝒃𝒃 (3.4)
ed
o

𝑥𝑥𝑗𝑗 ≥ 0, 𝑗𝑗 ∈ 𝑅𝑅 y 𝒙𝒙𝐵𝐵 ≥ 𝟎𝟎.

Sin pérdida de generalidad, se supondrá que ninguna fila del sistema (3.4) tenga sólo ceros en
las columnas de las variables no básicas 𝑥𝑥𝑗𝑗 , 𝑗𝑗 ∈ 𝑅𝑅. En caso contrario, se conoce el valor de la
variable básica en tal fila, y esta fila puede eliminarse del problema. Luego, observad que las
variables 𝒙𝒙𝐵𝐵 simplemente desempeñan el papel de las variables de holgura en el sistema (3.4).

8
 ProgM El método símplex Curso 2024-2025

Por tanto, es posible escribir de manera equivalente PL en el espacio de variables no básicas, es

decir en términos de las variables no básicas como se muestra a continuación

Minimizar 𝑧𝑧0 − ∑𝑗𝑗∈𝑅𝑅(𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ) 𝑥𝑥𝑗𝑗

�
Sujeta a ∑𝑗𝑗∈𝑅𝑅(𝒚𝒚𝑗𝑗 )𝑥𝑥𝑗𝑗 ≤ 𝒃𝒃 (3.5)

𝑥𝑥𝑗𝑗 ≥ 0, 𝑗𝑗 ∈ 𝑅𝑅.
D

Observad que el número de variables no básicas es 𝑝𝑝 = (𝑛𝑛 − 𝑚𝑚) y por tanto PL se ha

ep

representado en algún espacio 𝑝𝑝-dimensional. Lo anterior era de esperarse, ya que en el sistema

ar

de restricciones hay 𝑝𝑝 variables independientes, o 𝑝𝑝 grados de libertad. Los valores (𝑐𝑐𝑗𝑗 − 𝑧𝑧𝑗𝑗 )
ta

algunas veces se denominan coeficientes de coste reducidos, ya que son los coeficientes de las
m

variables (no básicas) en este espacio reducido. La representación (3.4) en que la función
en

objetivo 𝑧𝑧 y las variables básicas 𝒙𝒙𝐵𝐵 han sido resueltas en términos de las variables no básicas
se denomina representación de la solución básica en forma canónica. El resultado clave puede
to

plantearse ahora simplemente como si 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0 para todo 𝑗𝑗 ∈ 𝑅𝑅 entonces la solución básica
de

factible es óptima.
Es

Lo anterior debe resultar evidente si se observa que como 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0 para todo 𝑗𝑗 ∈ 𝑅𝑅,
ta

entonces se tiene que 𝑧𝑧 ≥ 𝑧𝑧0 para cualquier solución factible, y para la solución (básica) factible
dí

actual, se sabe que 𝑧𝑧 = 𝑧𝑧0 , ya que 𝑥𝑥𝑗𝑗 = 0 para todo 𝑗𝑗 ∈ 𝑅𝑅.

st
ic

3.4 MOTIVACIÓN GEOMÉTRICA DEL MÉTODO SÍMPLEX

a
e

Es instructivo analizar las operaciones anteriores desde un punto de vista geométrico. Observad
I.

que en la representación del espacio de variables no básicas, la región factible de PL está definida
O

en términos de 𝑛𝑛 semiespacios que se intersecan, 𝑚𝑚 asociados con las restricciones de

.y

desigualdad del sistema (3.5) y 𝑝𝑝 = (𝑛𝑛 − 𝑚𝑚) asociados con las restricciones de no negatividad.
Con cada uno de tales semiespacios hay asociada cierta variable definitoria que asume un valor
D

de cero sobre el hiperplano definitorio correspondiente y asume valores no negativos sobre el

.M

semiespacio correspondiente. Para las desigualdades del sistema (3.5), estas variables
.U

definitorias son las variables básicas 𝒙𝒙𝐵𝐵 , y para las restricciones de no negatividad, estas
ni

variables definitorias son las variables 𝑥𝑥𝑗𝑗 , 𝑗𝑗 ∈ 𝑅𝑅 mismas.

ve

En la figura 3.5 se ilustra una situación en que 𝑝𝑝 = 2, en donde 𝑛𝑛 = 6, 𝑚𝑚 = 4, 𝑅𝑅 = {1,2} y en

rs

donde 𝒙𝒙𝐵𝐵 = (𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 , 𝑥𝑥6 ). Las variables definitorias asociadas con los 𝑛𝑛 = 6 hiperplanos
id

definitorios se muestran contra los hiperplanos correspondientes en esta figura. Los puntos
ad

extremos o vértices de la región factible están etiquetados como 𝒗𝒗1 , … , 𝒗𝒗5 y 𝒄𝒄� es el vector
de

de coste reducido. Observad que la región factible está definida por las restricciones 𝑥𝑥𝑗𝑗 ≥ 0, 𝑗𝑗 =
1, … , 𝑛𝑛 en este espacio. La solución básica factible actual corresponde al vértice 𝒗𝒗1 , es decir, al
O
vi

origen. Observad también que cualquier otro punto extremo también está definido por
ed

la intersección de 𝑝𝑝 = 2 hiperplanos linealmente independientes, en donde las 𝑝𝑝 variables

o

definitorias correspondientes son las variables no básicas. Así, para el vértice 𝒗𝒗2 definido por
𝑥𝑥1 = 0 y 𝑥𝑥3 = 0, las variables no básicas son 𝑥𝑥1 y 𝑥𝑥3 , y las variables básicas son 𝑥𝑥2 , 𝑥𝑥4 , 𝑥𝑥5
y 𝑥𝑥6 .

9
D ProgM El método símplex Curso 2024-2025
ep
ar
ta
m
en
to
de
Es
ta
dí
st

Ahora considerad el origen 𝒗𝒗1 y analizad los 𝑝𝑝 hiperplanos definitorios asociados con las
ic

variables no básicas correspondientes. Manteniendo conectantes a (𝑝𝑝 − 1) de tales planos y

a

desplazándose en una dirección factible hacia el hiperplano restante se procede a lo largo de un

e
I.

rayo unidimensional con vértice en 𝒗𝒗1 . Existen 𝑝𝑝 de tales rayos. Entonces, en 𝒗𝒗1 , como
O

(𝑝𝑝 − 1) = 1, al mantener 𝑥𝑥2 = 0 e incrementando 𝑥𝑥1 se procede a lo largo del eje de 𝑥𝑥1 ,
.y

en donde la función objetivo cambia a una razón de 𝜕𝜕𝜕𝜕⁄𝜕𝜕𝑥𝑥1 = −(𝑧𝑧1 − 𝑐𝑐1 ) = 𝑐𝑐̅1 < 0. De
manera semejante, al mantener 𝑥𝑥1 = 0 e incrementando 𝑥𝑥2 se procede a lo largo del
D
.M

eje 𝑥𝑥2 , en donde la función objetivo cambia a una razón de 𝜕𝜕𝜕𝜕⁄𝜕𝜕𝑥𝑥2 = −(𝑧𝑧2 − 𝑐𝑐2 ) =
𝑐𝑐̅2 < 0. Por consiguiente, cualquier rayo describe una dirección de movimiento
.U

atractiva. Suponed que se elige la última dirección de movimiento. Como se trata de una
ni

dirección factible, se procede a lo largo de una arista de la región factible. Naturalmente,

ve

hubiera sido conveniente desplazarse tan lejos como fuese posible a lo largo de esta
rs

arista ya que 𝜕𝜕𝜕𝜕⁄𝜕𝜕𝑥𝑥2 < 0. Sin embargo, el movimiento es bloqueado por el hiperplano
id

𝑥𝑥3 = 0, ya que 𝑥𝑥3 se ha disminuido a cero y continuar el desplazamiento volvería a 𝑥𝑥3

ad

negativo. Además, dado que (𝑝𝑝 − 1) hiperplanos linealmente independientes eran

de

conectantes a lo largo de todo el recorrido y fueron bloqueados por un nuevo

hiperplano, ahora se tienen 𝑝𝑝 hiperplanos conectantes linealmente independientes, por
O

lo que se ha llegado a un punto extremo de la región factible. De hecho, éste es un punto

vi
ed

extremo adyacente con respecto al punto extremo previo. En 𝒗𝒗2 las variables no básicas
o

son 𝑥𝑥1 y 𝑥𝑥3 , y las demás variables son básicas.. Ahora se ha completado un paso
denominado iteración o pivoteo del método símplex. En este paso, la variable 𝑥𝑥2 se
denomina variable de entrada porque entró al conjunto de variables básicas, y la
variable 𝑥𝑥3 se denomina variable de bloqueo, o variable de salida, porque bloqueó el
movimiento o salió del conjunto de variables básicas en 𝒗𝒗1 . La base anterior y la base

10
 ProgM El método símplex Curso 2024-2025

nueva difieren sólo por una variable básica, y por consiguiente en una sola variable no
básica. Tales bases se denominan bases adyacentes.
Repitiendo este proceso en 𝒗𝒗2 , por supuesto que sería deseable no ingresar a 𝑥𝑥3 a la
base, ya que de hacerlo solamente se retrocedería a lo largo de la dirección precedente.
Sin embargo, manteniendo 𝑥𝑥3 = 0 e incrementando 𝑥𝑥1 se procede a lo largo de una
arista mejorada. Procediendo en esta dirección, como se muestra en la figura 3.5, se
observa que más de un hiperplano bloquea el movimiento. Suponed que uno de éstos
D

se elige de manera arbitraria como hiperplano de bloqueo; a saber, 𝑥𝑥4 = 0. Entonces,

ep

𝑥𝑥4 es la variable de salida, y para la base actual que representa a 𝒗𝒗3 , se tiene que 𝑥𝑥3 y
ar

𝑥𝑥4 son las variables no básicas. Luego, si se mantiene 𝑥𝑥4 = 0 y se realiza un

ta

desplazamiento en una dirección a lo largo de la cual aumenta 𝑥𝑥3 , entonces el valor de

m
en

la función objetivo decrece, ya que esta dirección forma un ángulo agudo con −𝒄𝒄�. Sin
embargo, esta dirección no es factible. El hiperplano 𝑥𝑥5 = 0 impide el movimiento aun antes
to

de empezar a efectuarlo. Es decir, 𝑥𝑥5 sale de la base, con lo que se obtienen a 𝑥𝑥4 y 𝑥𝑥5
de

como nuevas variables no básicas, mientras que se permanece todavía en el mismo

Es

vértice 𝒗𝒗3 . Tal paso, en el que se cambia de una base a una base adyacente, ambas
representando el mismo punto extremo solución, se denomina iteración degenerada o
ta
dí

pivoteo degenerado.
st

Con 𝑥𝑥4 y 𝑥𝑥5 como variables no básicas en 𝒗𝒗3 , manteniendo 𝑥𝑥5 = 0 e incrementando 𝑥𝑥4
ic
a

se procede en una dirección mejorada sobre una arista factible, y por tanto se obtiene
e

un pivoteo no degenerado. La variable de bloqueo o de salida que se transforma en cero

I.

es 𝑥𝑥6 y las nuevas variables no básicas son 𝑥𝑥5 y 𝑥𝑥6 . Observad que correspondiente a esta
O

base ninguno de los 𝑝𝑝 rayos, definidos manteniendo iguales a cero algunas (𝑝𝑝 − 1)
.y

variables no básicas e incrementando la variable no básica restante, conduce a una

D

mejora en la función objetivo, y por tanto el “resultado clave” declara que 𝒗𝒗4 es óptimo
.M

en el cono poliédrico formado por los semiespacios que tienen como variables
.U

definitorias a las variables no básicas actuales que en efecto contiene a la región factible.
Una ruta seguida por el método símplex a lo largo de aristas del conjunto poliédrico (de
ni

𝒗𝒗1 a 𝒗𝒗2 a 𝒗𝒗3 a 𝒗𝒗4 en el ejemplo anterior) se denomina ruta símplex.

ve
rs

Tal vez el lector observe que cuando el método símplex se implementa algebraicamente,
id

en cada iteración se representa el programa lineal en el espacio de variables no básicas,

ad

justamente como se hizo en el punto extremo 𝒗𝒗1 . Lo anterior proporcionará de manera

de

conveniente la razón de cambio en el valor de la función objetivo a lo largo de cada uno

de los 𝑝𝑝 rayos que inciden directamente en el vector de coste reducido, y por tanto en
O

cada iteración se planteará la pregunta de si el origen actual es óptimo o si es necesario

vi

considerar el movimiento a lo largo de una de las direcciones de los “ejes” actuales.

ed
o

3.5 ÁLGEBRA DEL MÉTODO SÍMPLEX

A continuación, se traducirá al álgebra el proceso geométrico descrito en la sección
precedente. A fin de lograr lo anterior, considerad la representación del programa lineal
PL en el espacio de variables no básicas, escrito en forma de igualdad como en el sistema
� es óptimo para PL. En
(3.4). Si 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0 para todo 𝑗𝑗 ∈ 𝑅𝑅, entonces 𝑥𝑥𝑗𝑗 = 0, 𝑗𝑗 ∈ 𝑅𝑅 y 𝒙𝒙𝐵𝐵 = 𝒃𝒃

11
 ProgM El método símplex Curso 2024-2025

caso contrario, mientras (𝑝𝑝 − 1) variables no básicas se mantienen fijas en cero, el método
símplex considera incrementar la variable restante, por ejemplo, 𝑥𝑥𝑘𝑘 . Naturalmente, hubiera
sido deseable que 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 fuese positivo, y quizá el más positivo de todos los 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 .
Ahora, fijando 𝑥𝑥𝑗𝑗 = 0, 𝑗𝑗 ∈ 𝑅𝑅 − {𝑘𝑘}, con base al sistema (3.4) se obtiene que

𝑧𝑧 = 𝑧𝑧0 − (𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 )𝑥𝑥𝑘𝑘 (3.7)

y
D
ep
ar

𝑥𝑥𝐵𝐵1 𝑏𝑏� 𝑦𝑦1𝑘𝑘

⎡ 𝑥𝑥𝐵𝐵 ⎤ ⎡ 1 ⎤ ⎡ 𝑦𝑦 ⎤
ta

�
⎢ ⋮ ⎥ ⎢ 𝑏𝑏2 ⎥ ⎢ ⋮ ⎥
2 2𝑘𝑘
m

⎢ ⎥ = ⎢ ⋮ ⎥−⎢ ⎥ 𝑥𝑥𝑘𝑘 (3.8)

⎢ 𝑥𝑥𝐵𝐵𝑟𝑟 ⎥ ⎢ 𝑏𝑏�𝑟𝑟 ⎥ ⎢ 𝑦𝑦𝑟𝑟𝑟𝑟 ⎥
en

⎢ ⋮ ⎥ ⎢ ⋮ ⎥ ⎢ ⋮ ⎥
to

⎣𝑥𝑥𝐵𝐵𝑚𝑚 ⎦ ⎣𝑏𝑏�𝑚𝑚 ⎦ ⎣𝑦𝑦𝑚𝑚𝑚𝑚 ⎦

de

Si 𝑦𝑦𝑖𝑖𝑖𝑖 ≤ 0, entonces 𝑥𝑥𝐵𝐵𝑖𝑖 crece cuando 𝑥𝑥𝑘𝑘 crece y así 𝑥𝑥𝐵𝐵𝑖𝑖 continua siendo no negativo. Si 𝑦𝑦𝑖𝑖𝑖𝑖 >
Es

0, entonces 𝑥𝑥𝐵𝐵𝑖𝑖 decrece cuando 𝑥𝑥𝑘𝑘 crece. A fin de satisfacer la no negatividad, 𝑥𝑥𝑘𝑘 se
ta

incrementa hasta el primer punto en que una variable básica 𝑥𝑥𝐵𝐵𝑖𝑖 desciende a cero. Al
dí

analizar el sistema (3.8), resulta entonces evidente que la primera variable básica que se vuelve
st

cero corresponde al mínimo de 𝑏𝑏�𝑖𝑖 �𝑦𝑦𝑖𝑖𝑖𝑖 para 𝑦𝑦𝑖𝑖𝑖𝑖 positivo. Más precisamente, es posible
ic

incrementar 𝑥𝑥𝑘𝑘 hasta

a
e

𝑥𝑥𝑘𝑘 = 𝑏𝑏� 𝑟𝑟 ⁄𝑦𝑦𝑟𝑟𝑟𝑟 = min {𝑏𝑏�𝑖𝑖 ⁄𝑦𝑦𝑖𝑖𝑖𝑖 : 𝑦𝑦𝑖𝑖𝑖𝑖 > 0} (3.9)

I.

1≤𝑖𝑖≤𝑚𝑚
O

Cuando no hay degeneración, 𝑏𝑏�𝑟𝑟 > 0 y entonces 𝑥𝑥𝑘𝑘 = 𝑏𝑏� 𝑟𝑟 ⁄𝑦𝑦𝑟𝑟𝑟𝑟 > 0. Por la ecuación (3.7) y con
.y

base al hecho de que 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0, se concluye que 𝑧𝑧 < 𝑧𝑧0 y la función objetivo mejora
D

estrictamente. Cuando 𝑥𝑥𝑘𝑘 crece desde el nivel 0 hasta 𝑏𝑏�𝑟𝑟 �𝑦𝑦𝑟𝑟𝑟𝑟 se obtiene una nueva solución
.M

factible. Al sustituir 𝑥𝑥𝑘𝑘 = 𝑏𝑏� 𝑟𝑟 ⁄𝑦𝑦𝑟𝑟𝑟𝑟 en el sistema (3.8) se obtiene el punto siguiente
.U

𝑦𝑦𝑖𝑖𝑖𝑖
𝑥𝑥𝐵𝐵𝑖𝑖 = 𝑏𝑏�𝑖𝑖 − 𝑏𝑏� , 𝑖𝑖 = 1,2, … 𝑚𝑚
ni

𝑦𝑦𝑟𝑟𝑟𝑟 𝑟𝑟
ve

𝑏𝑏�
rs

𝑥𝑥𝑘𝑘 = 𝑦𝑦 𝑟𝑟 (3.10)
id

𝑟𝑟𝑟𝑟
ad

Todas las demás 𝑥𝑥𝑗𝑗 son cero.

de

En base al sistema (3.10) 𝑥𝑥𝐵𝐵𝑟𝑟 = 0 y entonces como mucho 𝑚𝑚 variables son positivas. Las
columnas correspondientes en 𝐴𝐴 son 𝒂𝒂𝐵𝐵1 , … , 𝒂𝒂𝐵𝐵𝑟𝑟−1 , 𝒂𝒂𝑘𝑘 , 𝒂𝒂𝐵𝐵𝑟𝑟+1 , … , 𝒂𝒂𝐵𝐵𝑚𝑚 . Observad que estas
O

columnas son linealmente independientes ya que 𝑦𝑦𝑟𝑟𝑟𝑟 ≠ 0. (Recordad que si

vi
ed

𝒂𝒂𝐵𝐵1 , … , 𝒂𝒂𝐵𝐵𝑟𝑟 , … , 𝒂𝒂𝐵𝐵𝑚𝑚 son linealmente independientes, y si 𝒂𝒂𝑘𝑘 reemplaza a 𝒂𝒂𝐵𝐵𝑟𝑟 , entonces
o

las nuevas columnas son linealmente independientes si y sólo si 𝑦𝑦𝑟𝑟𝑟𝑟 ≠ 0; ved la sección
2.1). Por consiguiente, el punto dado por el sistema (3.10) es una solución básica
factible.
Resumiendo, se ha descrito algebraicamente una iteración; es decir, el proceso de
transformación de una base a una base adyacente. Lo anterior se lleva a cabo
incrementando el valor de una variable no básica 𝑥𝑥𝑘𝑘 con 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0 y ajustando las
12
 ProgM El método símplex Curso 2024-2025

variables básicas actuales. En el proceso, la variable 𝑥𝑥𝐵𝐵𝑟𝑟 se hace cero. Por tanto, la variable
𝑥𝑥𝑘𝑘 entra a la base y 𝑥𝑥𝐵𝐵𝑟𝑟 sale de la base. Cuando no hay degeneración, el valor de la función
objetivo decrece estrictamente y así las soluciones básicas factibles son distintas. Dado que sólo
existe un número finito de soluciones básicas factibles, entonces el procedimiento debe
terminar en un número finito de pasos.

Ejemplo 3.4
D

Minimizar 𝑥𝑥1 + 𝑥𝑥2

ep

Sujeta a 𝑥𝑥1 + 2𝑥𝑥2 ≤ 4

ar
ta

𝑥𝑥2 ≤ 1
m

𝑥𝑥1 , 𝑥𝑥2 ≥ 0
en
to

Se introducen las variables de holgura 𝑥𝑥3 y 𝑥𝑥4 a fin de plantear el problema en forma
estándar. Lo anterior conduce a la siguiente matriz de restricciones 𝐴𝐴 =
de

1 2 1 0
[𝒂𝒂1 , 𝒂𝒂2 , 𝒂𝒂3 , 𝒂𝒂4 ] = � �.
Es

0 1 0 1
ta

Considerad la solución básica factible correspondiente a 𝐵𝐵 = [𝒂𝒂1 , 𝒂𝒂2 ]. En otras palabras,

dí

𝑥𝑥1 y 𝑥𝑥2 son las variables básicas y 𝑥𝑥3 y 𝑥𝑥4 son las variables no básicas. La representación
st

del problema en este espacio de variables no básicas como en el sistema (3.4) con 𝑅𝑅 =
ic

{3,4} se puede obtener como se muestra a continuación.

a
e

1 2 −1 1 −2
Primero se calcula 𝐵𝐵 −1 = � �, 𝒄𝒄𝐵𝐵 𝐵𝐵−1 = (1,1) �1 −2� = (1, −1).
I.

� =�
0 1 0 1 0 1
O
.y

1 −2 1 1 1 −2 0 −2
Por tanto, 𝒚𝒚3 = 𝐵𝐵 −1 𝒂𝒂3 = � � � � = � �, 𝒚𝒚4 = 𝐵𝐵 −1 𝒂𝒂4 = � �� � = � � y
0 1 0 0 0 1 1 1
D

𝒃𝒃 −1
� = 𝐵𝐵 𝒃𝒃 = �1 −2 4 2
� � � = � �.
.M

0 1 1 1
.U

2 1
También, 𝑧𝑧0 = 𝒄𝒄𝐵𝐵 𝒃𝒃� = (1,1) � � = 3, 𝑧𝑧3 − 𝑐𝑐3 = 𝒄𝒄𝐵𝐵 𝒚𝒚3 − 𝑐𝑐3 = (1,1) � � − 0 = 1 y 𝑧𝑧4 −
1 0
ni

−2
𝑐𝑐4 = 𝒄𝒄𝐵𝐵 𝒚𝒚4 − 𝑐𝑐4 = (1,1) � � − 0 = −1.
ve

1
rs

Así, la representación requerida del problema es

id
ad

Minimizar 3 − 𝑥𝑥3 + 𝑥𝑥4

de

Sujeta a 𝑥𝑥3 − 2𝑥𝑥4 + 𝑥𝑥1 =2

O

𝑥𝑥4 + 𝑥𝑥2 = 1
vi
ed

𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥1 , 𝑥𝑥2 ≥ 0

o

La región factible de este problema se muestra en la figura 3.7, en el espacio original

(𝑥𝑥1 , 𝑥𝑥2 ) y en el espacio actual (𝑥𝑥3 , 𝑥𝑥4 ). Como 𝑧𝑧3 − 𝑐𝑐3 > 0, entonces el objetivo mejora
con el incremento de 𝑥𝑥3 . La solución modificada está dada por 𝒙𝒙𝐵𝐵 = 𝒃𝒃 � − 𝒚𝒚 𝑥𝑥3 ; o sea,
3
𝑥𝑥1 2 1
�𝑥𝑥 � = � � − � � 𝑥𝑥3 .
2 1 0

13
D ProgM El método símplex Curso 2024-2025
ep
ar
ta
m
en
to
de

El valor máximo de 𝑥𝑥3 es 2 (cualquier valor mayor de 𝑥𝑥3 obliga a que 𝑥𝑥1 sea negativo).
Por consiguiente, la nueva solución básica factible es (𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ) = (0,1,2,0). Aquí
Es

𝑥𝑥3 entra en la base y 𝑥𝑥1 sale de la base. Observad que el nuevo punto tiene un valor
ta

objetivo igual a 1, lo cual es una mejora con respecto al valor objetivo previo de 3. La
dí

mejora es precisamente (𝑧𝑧3 − 𝑐𝑐3 )𝑥𝑥3 = 2. Continuad el proceso de mejoramiento

st
ic

empezando en el nuevo punto.

a

Interpretación de entrar y salir de la base

e
I.

Ahora se considerará más a fondo el proceso de entrar y salir de la base, así como su
O

interpretación.
.y

INTERPRETACIÓN DE 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘

D
.M

A lo largo del curso se usará una y otra vez el criterio 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0 para que una variable
.U

no básica 𝑥𝑥𝑘𝑘 entre en la base. En este momento es de utilidad revisar la definición de 𝑧𝑧𝑘𝑘
y hacer algunos comentarios sobre el significado del criterio de entrada 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0.
ni

Recordad que 𝑧𝑧 = 𝒄𝒄𝐵𝐵 𝒃𝒃� − (𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 )𝑥𝑥𝑘𝑘 , en donde

ve
rs

𝑧𝑧𝑘𝑘 = 𝒄𝒄𝐵𝐵 𝒚𝒚𝑘𝑘 = ∑𝑚𝑚

𝑖𝑖=1 𝑐𝑐𝐵𝐵𝑖𝑖 𝑦𝑦𝑖𝑖𝑖𝑖 (3.11)
id
a

Y 𝑐𝑐𝐵𝐵𝑖𝑖 es el coste de la 𝑖𝑖-ésima variable básica. Observad que si la variable 𝑥𝑥𝑘𝑘 asciende
d

desde el nivel cero mientras las restantes variables no básicas se mantienen en el nivel
de

cero, entonces las variables básicas 𝑥𝑥𝐵𝐵1 , … , 𝑥𝑥𝐵𝐵𝑚𝑚 deben modificarse según la ecuación (3.8).
O

En otras palabras, si 𝑥𝑥𝑘𝑘 se incrementa en una unidad, entonces 𝑥𝑥𝐵𝐵1 , … , 𝑥𝑥𝐵𝐵𝑚𝑚 disminuirán
vi

respectivamente por 𝑦𝑦1𝑘𝑘 , … , 𝑦𝑦𝑚𝑚𝑚𝑚 unidades (si 𝑦𝑦𝑖𝑖𝑖𝑖 < 0, entonces 𝑥𝑥𝐵𝐵𝑖𝑖 se incrementa). Por
ed

consiguiente, el ahorro (un ahorro negativo significa más costo) que resulta de la modificación
o

de las variables básicas, como resultado del incremento de 𝑥𝑥𝑘𝑘 en una unidad, es ∑𝑚𝑚
𝑖𝑖=1 𝑐𝑐𝐵𝐵𝑖𝑖 𝑦𝑦𝑖𝑖𝑖𝑖 ,
que es 𝑧𝑧𝑘𝑘 (ver la ecuación 3.11). Sin embargo, el coste de incrementar 𝑥𝑥𝑘𝑘 en una unidad es
𝑐𝑐𝑘𝑘 . Por tanto, 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 es el ahorro menos el coste de incrementar 𝑥𝑥𝑘𝑘 en una unidad.
Naturalmente, si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0, entonces será ventajoso incrementar 𝑥𝑥𝑘𝑘 . Por cada unidad
de 𝑥𝑥𝑘𝑘 , el coste se reducirá por una cantidad 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 , y así será ventajoso incrementar 𝑥𝑥𝑘𝑘
tanto como sea posible. Por otra parte, si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 < 0, entonces al incrementar 𝑥𝑥𝑘𝑘 el
14
 ProgM El método símplex Curso 2024-2025

ahorro neto que se obtiene es negativo y esta acción da por resultado un mayor coste.
Así, esta acción está prohibida. Finalmente, si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 = 0, entonces incrementar 𝑥𝑥𝑘𝑘
conduce a una solución diferente con el mismo coste. Entonces, si 𝑥𝑥𝑘𝑘 se mantiene en el
nivel cero o se incrementa, no ocurre ningún cambio en el coste.
Ahora, suponed que 𝑥𝑥𝑘𝑘 es una variable básica. En particular, suponed que 𝑥𝑥𝑘𝑘 es la 𝑡𝑡-
ésima variable básica; es decir, 𝑥𝑥𝑘𝑘 = 𝑥𝑥𝐵𝐵𝑡𝑡 , 𝑐𝑐𝑘𝑘 = 𝑐𝑐𝐵𝐵𝑡𝑡 y 𝒂𝒂𝑘𝑘 = 𝒂𝒂𝐵𝐵𝑡𝑡 . Recordad que 𝑧𝑧𝑘𝑘 =
𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂𝑘𝑘 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂𝐵𝐵𝑡𝑡 . Sin embargo, 𝐵𝐵−1 𝒂𝒂𝐵𝐵𝑡𝑡 es un vector de ceros, excepto el de la 𝑡𝑡-
D
ep

ésima posición que es un uno. Por consiguiente, 𝑧𝑧𝑘𝑘 = 𝑐𝑐𝐵𝐵𝑡𝑡 , y por tanto 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 = 0.
ar

Ejemplo 3.5
ta
m

Minimizar 2𝑥𝑥1 − 𝑥𝑥2

en

Sujeta a −𝑥𝑥1 + 𝑥𝑥2 ≤ 2

to

2𝑥𝑥1 + 𝑥𝑥2 ≤ 6
de

𝑥𝑥1 , 𝑥𝑥2 ≥ 0
Es

Se introducen las variables de holgura 𝑥𝑥3 y 𝑥𝑥4 . Lo anterior conduce a las siguientes
ta
dí

restricciones:
st

−𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 = 2

ic
a

2𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥4 = 6

e
I.

𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ≥ 0

O

Considerad la solución básica factible con base 𝐵𝐵 = [𝒂𝒂1 , 𝒂𝒂2 ] = �−1 1� y 𝐵𝐵 −1 =

.y

2 1
D

1 1
−3
.M

3
� 2 1�, 𝒙𝒙𝐵𝐵 = 𝐵𝐵−1 𝒃𝒃 − 𝐵𝐵−1 𝑁𝑁𝒙𝒙𝑁𝑁
.U

3 3
ni

1 1 1 1 4 1 1
𝑥𝑥𝐵𝐵 𝑥𝑥1 − 3 2
−3 3 1 0� �𝑥𝑥3 � = � 3 � − �− 3� 𝑥𝑥 − �3� 𝑥𝑥
ve

�𝑥𝑥 1 � = �𝑥𝑥 � = � 2 3 1� �6�

−� 2 1� �0 3 1 4
(3.12)
𝐵𝐵2 2 1 𝑥𝑥4 10 2
rs

3 3 3 3 3 3 3
id

4 10
Actualmente, 𝑥𝑥3 = 𝑥𝑥4 = 0, 𝑥𝑥1 = 3 y 𝑥𝑥2 = . Observad que 𝑧𝑧4 − 𝑐𝑐4 = 𝒄𝒄𝐵𝐵 𝐵𝐵 −1 𝒂𝒂4 − 𝑐𝑐4 =
ad

3
1 1
−3
de

3 0 1
(2, −1) � 2 1� �1� − 0 = 3 > 0. Por tanto, el objetivo mejora manteniendo como no
O

3 3
vi

básica a 𝑥𝑥3 e introduciendo a 𝑥𝑥4 en la base. Luego, 𝑥𝑥3 se mantiene en el nivel cero, 𝑥𝑥4
ed

se incrementa y 𝑥𝑥1 y 𝑥𝑥2 se modifican según el sistema (3.12). Se observa que 𝑥𝑥4 se puede
o

incrementar hasta 4 en cuyo instante 𝑥𝑥1 se hace cero. Cualquier incremento adicional
de 𝑥𝑥4 hace que 𝑥𝑥1 viole la restricción de no negatividad, y así 𝑥𝑥1 es la variable de
bloqueo. Con 𝑥𝑥4 = 4 y 𝑥𝑥3 = 0, los valores modificados de 𝑥𝑥1 y 𝑥𝑥2 son 0 y 2,
respectivamente. La nueva solución básica factible es (𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ) = (0,2,0,4).

15
 ProgM El método símplex Curso 2024-2025

En la figura 3.8 se ilustra el movimiento de la solución básica factible anterior a la

solución básica factible nueva en el espacio original (𝑥𝑥1 , 𝑥𝑥2 ).
D
ep
ar
ta
m
en
to
de
Es
ta

3.6 TERMINACIÓN: OPTIMALIDAD Y NO ACOTAMIENTO

dí
st

Se ha analizado un procedimiento mediante el cual, introduciendo una variable en la

ic

base y sacando otra variable de la base, el proceso se mueve de una base a otra
a

adyacente. Los criterios para entrar y salir de la base son los siguientes.
e
I.

1. Entrada: 𝑥𝑥𝑘𝑘 puede entrar si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0.

O

2. Salida: 𝑥𝑥𝐵𝐵𝑟𝑟 puede salir si 𝑏𝑏�𝑟𝑟 �𝑦𝑦𝑟𝑟𝑟𝑟 = min {𝑏𝑏�𝑖𝑖 �𝑦𝑦𝑖𝑖𝑖𝑖 : 𝑦𝑦𝑖𝑖𝑖𝑖 > 0}.
.y

1≤𝑖𝑖≤𝑚𝑚

De inmediato surgen dos preguntas lógicas. En primer lugar, ¿qué ocurre si todas las
D
.M

variables no básicas 𝑥𝑥𝑗𝑗 tienen 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0? En este caso, como se vio en la sección 3.3,
.U

se ha obtenido una solución básica factible óptima. En segundo lugar, suponga que 𝑧𝑧𝑘𝑘 −
𝑐𝑐𝑘𝑘 > 0, de modo que 𝑥𝑥𝑘𝑘 es elegible para entrar a la base, pero 𝒚𝒚𝑘𝑘 ≤ 𝟎𝟎. En este caso, el
ni

valor de la solución óptima es no acotado. En esta sección se estudiarán los dos casos con mayor
ve

detalle.
rs
id

Terminación con una solución óptima

d a

Sea el siguiente problema donde 𝐴𝐴 es una matriz de 𝑚𝑚 × 𝑛𝑛 de rango 𝑚𝑚.

de

Minimizar 𝒄𝒄𝒄𝒄
O

Sujeta a 𝐴𝐴𝒙𝒙 = 𝒃𝒃
vi
ed

𝒙𝒙 ≥ 𝟎𝟎
o

−1
Suponer que 𝒙𝒙∗ es una solución básica factible con base 𝐵𝐵; es decir, 𝒙𝒙∗ = �𝐵𝐵 𝒃𝒃�. Denotar por
𝟎𝟎
𝑧𝑧 ∗ el valor objetivo en 𝒙𝒙∗ , o sea, 𝑧𝑧 ∗ = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃. Además, suponed que 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0 para todas
las variables no básicas, de modo que ninguna variable no básica es elegible para entrar
en la base. Sea 𝒙𝒙 cualquier solución factible con valor objetivo 𝑧𝑧. Entonces, por la ecuación
(3.3) se tiene

16
 ProgM El método símplex Curso 2024-2025

𝑧𝑧 ∗ − 𝑧𝑧 = ∑𝑗𝑗∈𝑅𝑅(𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ) 𝑥𝑥𝑗𝑗 (3.13)

Puesto que 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0 y 𝑥𝑥𝑗𝑗 ≥ 0 para todas las variables, entonces 𝑧𝑧 ∗ ≤ 𝑧𝑧 y por tanto, 𝒙𝒙∗
es una solución básica óptima.

Soluciones óptimas únicas y alternativas

Es posible obtener más información de la ecuación (3.13). Si 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 < 0 para todas las
componentes no básicas, entonces la solución óptima actual es única. Para ver lo
D

anterior, sea 𝒙𝒙 cualquier solución factible distinta de 𝒙𝒙∗ . Luego, existe por lo menos una
ep

componente no básica 𝑥𝑥𝑗𝑗 que es positiva, porque si todas las componentes no básicas son
ar

cero, entonces 𝒙𝒙 no podría ser distinta de 𝒙𝒙∗ . Así, de la ecuación (3.13) se concluye que 𝑧𝑧 ∗ < 𝑧𝑧
ta

y, por consiguiente 𝒙𝒙∗ es la única solución óptima.

m
en

Considerad ahora el caso en que 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0 para todas las componentes no básicas, pero
to

𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 = 0 para al menos una variables no básica 𝑥𝑥𝑘𝑘 . Al incrementar 𝑥𝑥𝑘𝑘 (y suponiendo
de

que no hay degeneración), se obtienen puntos distintos de 𝒙𝒙∗ pero que tienen el mismo
valor objetivo. Si 𝑥𝑥𝑘𝑘 se incrementa hasta ser bloqueada por una variable básica, entonces
Es

se obtiene una solución básica factible óptima alternativa. El proceso de incrementar 𝑥𝑥𝑘𝑘
ta

desde el nivel cero hasta que es bloqueada genera una infinidad de soluciones óptimas.
dí
st

Ejemplo 3.6
ic
a

Minimizar −3𝑥𝑥1 + 𝑥𝑥2

e

Sujeta a 𝑥𝑥1 + 2𝑥𝑥2 + 𝑥𝑥3 =4

I.
O

−𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥4 = 1

.y

𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ≥ 0

D
.M

Considerad la solución básica factible con base 𝐵𝐵 = [𝒂𝒂1 , 𝒂𝒂4 ] = � 1 0� y 𝐵𝐵−1 = �1 0�.
−1 1 1 1
.U

El punto correspondiente está dado por

ni

𝑥𝑥1 1 0 4 4 𝑥𝑥2 0
ve

𝒙𝒙𝐵𝐵 = �𝑥𝑥 � = � � � � = � �, 𝒙𝒙𝑁𝑁 = �𝑥𝑥 � = � �

4 1 1 1 5 3 0
rs

y el valor objetivo es −12. A fin de ver si es posible mejorar esta solución, se calculan
id
a

𝑧𝑧2 − 𝑐𝑐2 y 𝑧𝑧3 − 𝑐𝑐3 como se muestra a continuación, observando que 𝒄𝒄𝐵𝐵 𝐵𝐵−1 = (−3,0), en
d

donde 𝒄𝒄𝐵𝐵 = (−3,0).

de

2
𝑧𝑧2 − 𝑐𝑐2 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂2 − 𝑐𝑐2 = (−3,0) � � − 1 = −7
O

1
vi

1
ed

𝑧𝑧3 − 𝑐𝑐3 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂3 − 𝑐𝑐3 = (−3,0) � � − 0 = −3

0
o

Puesto que ambos 𝑧𝑧2 − 𝑐𝑐2 < 0 y 𝑧𝑧3 − 𝑐𝑐3 < 0 se concluye que la solución básica factible
(𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ) = (4,0,0,5) es el único punto óptimo. En la figura 3.9a se ilustra esta
solución óptima única. Considérese ahora el problema de minimizar la función objetivo
−2𝑥𝑥1 − 4 𝑥𝑥2 en la misma región. De nuevo, considerad el mismo punto (𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ) =

17
 ProgM El método símplex Curso 2024-2025

(4,0,0,5). El valor objetivo es −8 y el nuevo 𝒄𝒄𝐵𝐵 = (−2,0), 𝒄𝒄𝐵𝐵 𝐵𝐵−1 = (−2,0), 𝑧𝑧2 − 𝑐𝑐2 y 𝑧𝑧3 −
𝑐𝑐3 se calculan como sigue
2
𝑧𝑧2 − 𝑐𝑐2 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂2 − 𝑐𝑐2 = (−2,0) � � + 4 = 0
1
1
𝑧𝑧3 − 𝑐𝑐3 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂3 − 𝑐𝑐3 = (−2,0) � � − 0 = −2
0
En este caso, la solución básica factible dada es óptima pero ya no es una solución
D
ep

óptima única. Se ve que al incrementar 𝑥𝑥2 se obtiene toda una familia de soluciones
óptimas. De hecho, si se incrementa 𝑥𝑥2 , se mantiene 𝑥𝑥3 = 0 y se modifican 𝑥𝑥1 y 𝑥𝑥4 , se
ar
ta

obtiene
m

𝑥𝑥1 4 2
en

�𝑥𝑥 � = 𝐵𝐵−1 𝒃𝒃 − 𝐵𝐵−1 𝒂𝒂2 𝑥𝑥2 = � � − � � 𝑥𝑥2

4 5 3
to

Para cualquier 𝑥𝑥2 ≤ 5⁄3, la solución es una solución óptima con objetivo −8. En
de

particular, si 𝑥𝑥2 = 5⁄3, entonces se obtiene una solución básica factible alternativa, en
donde 𝑥𝑥4 sale de la base. Lo anterior se ilustra en la figura 3.9b.
Es
ta
dí
st
ic
a
e
I.
O
.y
D
.M
.U
ni
ve
rs

No acotamiento
id

Suponed que se tiene una solución básica factible del sistema 𝐴𝐴𝒙𝒙 = 𝒃𝒃, 𝒙𝒙 ≥ 𝟎𝟎 con valor objetivo
ad

𝑧𝑧0 . Ahora se considerará el caso en que se encuentra una variable no básica

de

correspondiente 𝑥𝑥𝑘𝑘 , con 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0 y 𝒚𝒚𝑘𝑘 ≤ 𝟎𝟎. Esta variable es elegible para entrar a la
base, ya que al incrementar su valor se mejora la función objetivo. De la ecuación (3.3)
O

se tiene 𝑧𝑧 = 𝑧𝑧0 − (𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 )𝑥𝑥𝑘𝑘 . Como se desea minimizar el objetivo 𝑧𝑧 y ya que 𝑧𝑧𝑘𝑘 −
vi
ed

𝑐𝑐𝑘𝑘 > 0, conviene incrementar indefinidamente el valor de 𝑥𝑥𝑘𝑘 , lo cual hará que 𝑧𝑧 se vaya
o

a −∞. La razón por la cual no fue posible hacer esto antes es que el incremento en el
valor de 𝑥𝑥𝑘𝑘 estaba bloqueado por una variable básica. Lo anterior impone un tope a 𝑥𝑥𝑘𝑘 , más
allá del cual una variable básica se hace negativa. Sin embargo, cuando no hay bloqueo
no existe ninguna razón por la cual se deba detener el crecimiento de 𝑥𝑥𝑘𝑘 . Este es
precisamente el caso cuando 𝒚𝒚𝑘𝑘 ≤ 𝟎𝟎. Recordad que de la ecuación (3.8) se tiene 𝒙𝒙𝐵𝐵 =
� − 𝒚𝒚 𝑥𝑥𝑘𝑘 de modo que si 𝒚𝒚𝑘𝑘 ≤ 𝟎𝟎, entonces 𝑥𝑥𝑘𝑘 se puede incrementar indefinidamente
𝒃𝒃 𝑘𝑘

18
 ProgM El método símplex Curso 2024-2025

sin que ninguna de las variables básicas se haga negativa. Por tanto, la solución 𝒙𝒙 (en
� − 𝒚𝒚 𝑥𝑥𝑘𝑘 , 𝑥𝑥𝑘𝑘 es arbitrariamente grande y todas las demás componentes no
donde 𝒙𝒙𝐵𝐵 = 𝒃𝒃 𝑘𝑘
básicas son cero) es factible y su valor objetivo es 𝑧𝑧 = 𝑧𝑧0 − (𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 )𝑥𝑥𝑘𝑘 , el cual tiende
a −∞ cuando 𝑥𝑥𝑘𝑘 tiende a +∞.
Resumiendo, si se tiene una solución básica factible con 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0 para alguna
variable no básica 𝑥𝑥𝑘𝑘 y además 𝒚𝒚𝑘𝑘 ≤ 𝟎𝟎, entonces el óptimo es no acotado con objetivo
−∞. Este valor se obtiene al incrementar 𝑥𝑥𝑘𝑘 indefinidamente y ajustar los valores de las
D
ep

variables básicas actuales; esto, a su vez, es equivalente a efectuar un desplazamiento a

lo largo del rayo
ar
ta

𝐵𝐵−1 𝒃𝒃 −𝒚𝒚𝑘𝑘
m

⎧⎡ ⎤ ⎡ 0 ⎤ ⎫
⎪⎢ 0 ⎥ ⎪
en

⋮ ⎢ ⋮ ⎥
⎢ ⎥ + 𝑥𝑥𝑘𝑘 ⎢ : 𝑥𝑥 ≥ 0
1 ⎥ 𝑘𝑘
to

⎨⎢ 0 ⎥ ⎬
⎪⎢ ⋮ ⎥ ⎢ ⋮ ⎥ ⎪
de

⎩⎣ 0 ⎦ ⎣ 0 ⎦ ⎭
Es

−1
Observad que el vértice del rayo es la solución básica factible actual �𝐵𝐵 𝒃𝒃� y que la
𝟎𝟎
ta

dirección del rayo es

dí
st

−𝒚𝒚𝑘𝑘
ic

⎡ 0 ⎤
a

⎢ ⋮ ⎥
𝒅𝒅 = ⎢
e

1 ⎥
⎢ ⋮ ⎥
I.

⎣ 0 ⎦
O
.y

en donde el 1 aparece en la 𝑘𝑘-ésima posición. Se puede observar que 𝒄𝒄𝒄𝒄 = −𝒄𝒄𝐵𝐵 𝒚𝒚𝑘𝑘 +
D

𝑐𝑐𝑘𝑘 = −𝑧𝑧𝑘𝑘 + 𝑐𝑐𝑘𝑘 . Pero como −𝑧𝑧𝑘𝑘 + 𝑐𝑐𝑘𝑘 < 0 (puesto que 𝑥𝑥𝑘𝑘 es elegible para entrar en la
.M

base), entonces 𝒄𝒄𝒄𝒄 < 0.

.U

Ejemplo 3.7
ni

Minimizar −𝑥𝑥1 − 3 𝑥𝑥2

ve
rs

Sujeta a 𝑥𝑥1 − 2𝑥𝑥2 ≤ 4

id

−𝑥𝑥1 + 𝑥𝑥2 ≤ 3
ad

𝑥𝑥1 , 𝑥𝑥2 ≥ 0
de

Es claro que el problema, ilustrado en la figura 3.10, tiene una solución óptima no acotada.
O
vi

Después de introducir las variables de holgura 𝑥𝑥3 y 𝑥𝑥4 , se obtiene la matriz de restricciones
ed

1 −2 1 0
𝐴𝐴 = � �.
o

−1 1 0 1

19
D ProgM El método símplex Curso 2024-2025
ep
ar
ta
m
en
to

Considerad ahora la solución básica factible cuya base es 𝐵𝐵 = [𝒂𝒂3 , 𝒂𝒂4 ] = �1 0�.
de

0 1
Es

𝑥𝑥3 1 0 4 4 𝑥𝑥1 0
𝒙𝒙𝐵𝐵 = �𝑥𝑥 � = � � � � = � �, 𝒙𝒙𝑁𝑁 = �𝑥𝑥 � = � �.
ta

4 0 1 3 3 2 0
dí

𝑧𝑧1 − 𝑐𝑐1 y 𝑧𝑧2 − 𝑐𝑐2 se calculan como se muestra enseguida, observando que 𝒄𝒄𝐵𝐵 𝐵𝐵−1 =
st

(0,0):
ic
a

𝑧𝑧1 − 𝑐𝑐1 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂1 − 𝑐𝑐1 = −𝑐𝑐1 = 1

e
I.

𝑧𝑧2 − 𝑐𝑐2 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂2 − 𝑐𝑐2 = −𝑐𝑐2 = 3

O

De modo que 𝑥𝑥2 se incrementa con el valor más positivo de 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 . Observad que 𝒙𝒙𝐵𝐵 =
.y

𝐵𝐵−1 𝒃𝒃 − 𝐵𝐵−1 𝒂𝒂2 𝑥𝑥2 , y por tanto

D

𝑥𝑥3
.M

4 −2
�𝑥𝑥 � = � � − � � 𝑥𝑥2
4 3 1
.U

El valor máximo de 𝑥𝑥2 es 3, en cuyo instante 𝑥𝑥4 se vuelve cero. Por consiguiente, la
ni

nueva solución básica factible es (𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ) = (0,3,10,0). La nueva base 𝐵𝐵 =
ve

[𝒂𝒂3 , 𝒂𝒂2 ] = �1 −2� con inversa �

1 2
�. Como 𝒄𝒄𝐵𝐵 = (0, −3), se obtiene 𝒄𝒄𝐵𝐵 𝐵𝐵−1 = (0, −3) y
rs

0 1 0 1
id

𝑧𝑧1 − 𝑐𝑐1 y 𝑧𝑧4 − 𝑐𝑐4 se calculan como sigue:

a d

1
𝑧𝑧1 − 𝑐𝑐1 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂1 − 𝑐𝑐1 = (0, −3) � �+1= 4
de

−1
O

0
𝑧𝑧4 − 𝑐𝑐4 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒂𝒂4 − 𝑐𝑐4 = (0, −3) � � − 0 = −3
vi

1
ed

−1 0
Se observa que 𝑧𝑧1 − 𝑐𝑐1 > 0 y 𝒚𝒚1 = 𝐵𝐵−1 𝒂𝒂1 = �� ≤ � �. Por tanto, la solución óptima
o

−1 0
es no acotada. En este caso, si se incrementa 𝑥𝑥1 y se mantiene fijo 𝑥𝑥4 , se obtiene la
siguiente solución:

𝒙𝒙𝐵𝐵 = 𝐵𝐵−1 𝒃𝒃 − 𝐵𝐵−1 𝒂𝒂1 𝑥𝑥1

20
 ProgM El método símplex Curso 2024-2025

𝑥𝑥3 10 −1 10 + 𝑥𝑥1
�𝑥𝑥 � = � � − � � 𝑥𝑥1 = � �
2 3 −1 3 + 𝑥𝑥1
𝑥𝑥4 = 0
Observad que esta solución es factible para todo 𝑥𝑥1 ≥ 0. En particular,
𝑥𝑥1 − 2𝑥𝑥2 + 𝑥𝑥3 = 𝑥𝑥1 − 2(3 + 𝑥𝑥1 ) + 10 + 𝑥𝑥1 = 4
y
D
ep

−𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥4 = −𝑥𝑥1 + 3 + 𝑥𝑥1 + 0 = 3.

ar

Además, 𝑧𝑧 = −9 − 4𝑥𝑥1 , que tiende a −∞ cuando 𝑥𝑥1 tiende a +∞. Por consiguiente, la
ta
m

solución óptima es no acotada al efectuarse un movimiento a lo largo del rayo

en

{(0,3,10,0) + 𝑥𝑥1 (1,1,1,0): 𝑥𝑥1 ≥ 0}.

to

3.7 EL MÉTODO SÍMPLEX

de

Se ha construido toda la maquinaria necesaria para describir el algoritmo del símplex y

Es

demostrar su convergencia en un número finito de iteraciones (en ausencia de

ta

degeneración). Dadas una solución básica factible y una base correspondiente, entonces
dí

es posible mejorar la solución si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0 para alguna variable no básica 𝑥𝑥𝑘𝑘 , o bien,
st

el proceso se detiene en un punto óptimo si 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0 para todas las variables no
ic
a

básicas. Si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0 y el vector 𝒚𝒚𝑘𝑘 contiene por lo menos una componente positiva,
e

entonces el incremento de 𝑥𝑥𝑘𝑘 será bloqueado por una de las variables básicas actuales,
I.

la cual se vuelve cero y sale de la base. Por otra parte, si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0 y 𝒚𝒚𝑘𝑘 ≤ 𝟎𝟎, entonces
O

𝑥𝑥𝑘𝑘 se puede incrementar indefinidamente y la solución óptima es no acotada con valor

.y

−∞. Esto que se ha descrito es precisamente lo que hace el método símplex.

D

A continuación se proporcionará un resumen del método símplex para resolver el

.M

siguiente problema de programación lineal.

.U

Minimizar 𝒄𝒄𝒄𝒄
ni
ve

Sujeta a 𝐴𝐴𝒙𝒙 = 𝒃𝒃
rs

𝒙𝒙 ≥ 𝟎𝟎
id
a

donde 𝐴𝐴 es una matriz de 𝑚𝑚 × 𝑛𝑛 de rango 𝑚𝑚 (en el tema 4 no se aplicará estrictamente la

d

condición de que el rango (𝐴𝐴) sea igual a 𝑚𝑚.

de

El algoritmo del símplex

O
vi

PASO INICIAL
ed
o

Seleccionar una solución básica factible inicial con base 𝐵𝐵. En el tema 4 se describirán varios
procedimientos para determinar una base inicial.

PASO PRINCIPAL
�). Sean 𝒙𝒙𝐵𝐵 = 𝒃𝒃
1. Resolver el sistema 𝐵𝐵𝒙𝒙𝐵𝐵 = 𝒃𝒃 (con solución única 𝒙𝒙𝐵𝐵 = 𝐵𝐵−1 𝒃𝒃 = 𝒃𝒃 �,
�.
𝒙𝒙𝑁𝑁 = 𝟎𝟎 y 𝑧𝑧 = 𝒄𝒄𝐵𝐵 𝒃𝒃

21
 ProgM El método símplex Curso 2024-2025

2. Resolver el sistema 𝒘𝒘𝐵𝐵 = 𝒄𝒄𝐵𝐵 (con solución única 𝒘𝒘 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 ). (El vector 𝒘𝒘 se
denomina vector de multiplicadores símplex porque sus componentes son los
multiplicadores de las filas de 𝐴𝐴 que se suman a la función objetivo a fin de llegar
a la forma canónica). Para todas las variables no básicas, calcular 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 =
𝒘𝒘𝒂𝒂𝑗𝑗 − 𝑐𝑐𝑗𝑗 . Sea
𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 = max 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗
𝑗𝑗∈𝑅𝑅
D

en donde 𝑅𝑅 es el conjunto actual de índices asociados con las variables no

ep

básicas. Si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 ≤ 0, entonces el proceso se detiene con las solución básica
ar

factible actual como una solución óptima. En caso contrario, se continúa con el
ta

paso 3, con 𝑥𝑥𝑘𝑘 como variable de entrada.

m
en

3. Resolver el sistema 𝐵𝐵𝒚𝒚𝑘𝑘 = 𝒂𝒂𝑘𝑘 (con solución única 𝒚𝒚𝑘𝑘 = 𝐵𝐵−1 𝒂𝒂𝑘𝑘 ). Si 𝒚𝒚𝑘𝑘 ≤ 𝟎𝟎,
entonces el proceso se detiene con la conclusión de que la solución óptima es no
to

acotada a lo largo del rayo

de

−1 −𝒚𝒚𝑘𝑘
��𝐵𝐵 𝒃𝒃� + 𝑥𝑥𝑘𝑘 � 𝑘𝑘 �: 𝑥𝑥𝑘𝑘 ≥ 0�
Es

𝟎𝟎 𝒆𝒆
𝑘𝑘
en donde 𝒆𝒆 es un (𝑛𝑛 − 𝑚𝑚)-vector de ceros excepto por un 1 en la 𝑘𝑘-ésima
ta

posición. Si 𝒚𝒚𝑘𝑘 ≰ 𝟎𝟎, se continua con el paso 4.

dí

4. Ahora, 𝑥𝑥𝑘𝑘 entra en la base. El índice 𝑟𝑟 de la variable de bloqueo 𝑥𝑥𝐵𝐵𝑟𝑟 , que sale de
st
ic

la base, se determina mediante el siguiente criterio (o prueba) de la razón mínima:

a

𝑏𝑏�𝑟𝑟 𝑏𝑏�𝑖𝑖
e

= min { : 𝑦𝑦𝑖𝑖𝑖𝑖 > 0}.

I.

𝑦𝑦𝑟𝑟𝑟𝑟 1≤𝑖𝑖≤𝑚𝑚 𝑦𝑦𝑖𝑖𝑖𝑖

O

Se actualiza la base 𝐵𝐵, en donde 𝒂𝒂𝐵𝐵𝑟𝑟 se sustituye por 𝒂𝒂𝑘𝑘 , se actualiza el conjunto 𝑅𝑅 de
.y

índices, y se repite el paso 1.

D

Modificación para un problema de maximización

.M
.U

Un problema de maximización se puede transformar en un problema de minimización

multiplicando por −1 los coeficientes de la función objetivo. Un problema de maximización
ni

también se puede manejar directamente procediendo como sigue. A diferencia del caso de
ve

minimización, sea ahora 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 = min 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ; el criterio para detener el proceso es que
rs

𝑗𝑗∈𝑅𝑅
id

𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 ≥ 0. En caso contrario, los pasos son como antes.

d a

Convergencia finita del método símplex en ausencia de degeneración

de

Observad que en cada iteración (es decir, un desarrollo de todo el paso principal) se
O

efectúa una de las tres acciones siguientes. EL proceso se detiene en un punto extremo
vi

óptimo si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 ≤ 0; el proceso se detiene con una solución no acotada si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 >
ed

0 y 𝒚𝒚𝑘𝑘 ≤ 𝟎𝟎; o bien, se genera una nueva solución básica factible si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 > 0 y 𝒚𝒚𝑘𝑘 ≰
o

𝑏𝑏 �
𝟎𝟎. Cuando no hay degeneración, 𝑏𝑏�𝑟𝑟 > 0 y entonces 𝑥𝑥𝑘𝑘 = 𝑦𝑦 𝑟𝑟 > 0. Por consiguiente, la
𝑟𝑟𝑟𝑟
diferencia entre los valores objetivos de la iteración anterior y los de la iteración presente es
𝑥𝑥𝑘𝑘 (𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 ) > 0. En otras palabras, la función objetivo decrece estrictamente en cada
iteración y por tanto las soluciones básicas factibles generadas por el método símplex
son distintas. Puesto que sólo hay un número finito de soluciones básicas factibles,

22
 ProgM El método símplex Curso 2024-2025

entonces el método se detendrá en un número finito de pasos, ya sea con una solución
óptima finita o bien, con una solución óptima no acotada. Con base en esta
argumentación, el siguiente teorema resulta evidente.
Teorema 3.5
Cuando no hay degeneración (y suponiendo factibillidad), el método símplex se detiene
en un número finito de iteraciones, ya sea con una solución básica factible óptima o
D

bien, con la conclusión de que el valor óptimo es no acotado.

ep

Cuando hay degeneración, como ya se vio, es posible que haya ciclado en un circuito
ar

infinito. Esta cuestión se analizará con mayor detalle en el tema 4.

ta
m

Ejemplo 3.8
en

Minimizar −𝑥𝑥1 − 3 𝑥𝑥2

to
de

Sujeta a 2𝑥𝑥1 + 3𝑥𝑥2 ≤ 6

Es

−𝑥𝑥1 + 𝑥𝑥2 ≤ 1
ta

𝑥𝑥1 , 𝑥𝑥2 ≥ 0
dí

El problema se ilustra en la figura 3.11. Después de introducir las las variables de holgura 𝑥𝑥3 y
st
ic

2 3 1 0
𝑥𝑥4 , se obtiene la matriz de restricciones 𝐴𝐴 = � �.
a

−1 1 0 1
e
I.
O
.y
D
.M
.U
ni
ve
rs
id
ad
de
O
vi

Iteración 1
ed

Sea 𝐵𝐵 = [𝒂𝒂3 , 𝒂𝒂4 ] = �1 0� y 𝑁𝑁 = [𝒂𝒂1 , 𝒂𝒂2 ] = � 2 3�. Resolviendo el sistema 𝐵𝐵𝒙𝒙𝐵𝐵 = 𝒃𝒃 se

o

0 1 −1 1
obtiene 𝑥𝑥𝐵𝐵1 = 𝑥𝑥3 = 6 y 𝑥𝑥𝐵𝐵2 = 𝑥𝑥4 = 1. Las variables no básicas son 𝑥𝑥1 y 𝑥𝑥2 , y el objetivo
6
es 𝑧𝑧 = 𝒄𝒄𝐵𝐵 𝒙𝒙𝐵𝐵 = (0,0) � � = 0. Para determinar cuál es la variable que entra a la base, se
1
−1
calcula 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 = 𝒄𝒄𝐵𝐵 𝐵𝐵 𝒂𝒂𝑗𝑗 − 𝑐𝑐𝑗𝑗 = 𝒘𝒘𝒂𝒂𝑗𝑗 − 𝑐𝑐𝑗𝑗 . Primero se encuentra 𝒘𝒘 resolviendo el
sistema 𝒘𝒘𝐵𝐵 = 𝒄𝒄𝐵𝐵 :

23
 ProgM El método símplex Curso 2024-2025

1 0 0
(𝑤𝑤1 , 𝑤𝑤2 ) � � = � �⇒𝑤𝑤1 = 𝑤𝑤2 = 0
0 1 0
𝑧𝑧1 − 𝑐𝑐1 = 𝒘𝒘𝒂𝒂1 − 𝑐𝑐1 = 1
𝑧𝑧2 − 𝑐𝑐2 = 𝒘𝒘𝒂𝒂2 − 𝑐𝑐2 = 3
Por consiguiente, se incrementa 𝑥𝑥2 . Para determinar 𝑥𝑥2 es necesario calcular 𝒚𝒚2
resolviendo el sistema 𝐵𝐵𝒚𝒚2 = 𝒂𝒂2 :
D

1 0 𝑦𝑦12
ep

3
� � � � = � �⇒𝑦𝑦12 = 3 y 𝑦𝑦22 = 1
0 1 𝑦𝑦22 1
ar
ta

La variable 𝑥𝑥𝐵𝐵𝑟𝑟 que sale de la base se determina mediante la siguiente prueba de la razón
m

mínima:
en

𝑏𝑏� 𝑏𝑏� 6 1
Mínimo �𝑦𝑦 1 , 𝑦𝑦 2 � = Mínimo �3 , 1� = 1
to

12 22
de

Por tanto, el índice 𝑟𝑟 = 2, es decir, 𝑥𝑥𝐵𝐵2 = 𝑥𝑥4 sale de la base. Esto también resulta
evidente observando que
Es

𝑥𝑥𝐵𝐵
ta

𝑥𝑥3 6 3
� 𝑥𝑥 1 � = � 𝑥𝑥 � = � � − � � 𝑥𝑥2 (3.14)
dí

𝐵𝐵2 4 1 1
st

y 𝑥𝑥4 es la primera variable básica que se hace cero cuando 𝑥𝑥2 = 1.

ic
a

Iteración 2
e
I.

La variable 𝑥𝑥2 entra a la base y la variable 𝑥𝑥4 sale de ella:

O

1 3� y 𝑁𝑁 = [𝒂𝒂 , 𝒂𝒂 ] = � 2 0�
.y

𝐵𝐵 = [𝒂𝒂3 , 𝒂𝒂2 ] = � 1 4
0 1 −1 1
D

Ahora, 𝒙𝒙𝐵𝐵 se puede determinar resolviendo 𝐵𝐵𝒙𝒙𝐵𝐵 = 𝒃𝒃, o bien, simplemente observando
.M

que 𝑥𝑥2 = 1 en la ecuación (3.14)

.U

𝑥𝑥𝐵𝐵 𝑥𝑥3 3 𝑥𝑥1 0

� 𝑥𝑥 1 � = � 𝑥𝑥 � = � � � 𝑥𝑥 � = � �
ni

𝐵𝐵2 2 1 4 0
ve

El valor objetivo es 𝑧𝑧 = −3. 𝒘𝒘 se calcula mediante 𝒘𝒘𝐵𝐵 = 𝒄𝒄𝐵𝐵 :

rs
id

1 3 0
(𝑤𝑤1 , 𝑤𝑤2 ) � � = � �⇒𝑤𝑤1 = 0 y 𝑤𝑤2 = −3
a

0 1 −3
d
de

2
𝑧𝑧1 − 𝑐𝑐1 = 𝒘𝒘𝒂𝒂1 − 𝑐𝑐1 = (0, −3) � �+1 =4
−1
O

La variable 𝑥𝑥4 salió de la base en la iteración anterior y no puede entrar a la base en esta
vi
ed

iteración, ya que 𝑧𝑧4 − 𝑐𝑐4 < 0. Por consiguiente, se incrementa 𝑥𝑥1 . Resolviendo el sistema
𝐵𝐵𝒚𝒚1 = 𝒂𝒂1 :
o

1 3 𝑦𝑦11 2
� � � � = � �⇒𝑦𝑦11 = 5 y 𝑦𝑦21 = −1
0 1 𝑦𝑦21 −1
Puesto que 𝑦𝑦21 < 0, entonces 𝑥𝑥𝐵𝐵1 = 𝑥𝑥3 sale de la base cuando 𝑥𝑥1 crece. Esto también resulta
evidente observando que

24
 ProgM El método símplex Curso 2024-2025

𝑥𝑥𝐵𝐵 𝑥𝑥3 3 5
� 𝑥𝑥 1 � = � 𝑥𝑥 � = � � − � � 𝑥𝑥 (3.14)
𝐵𝐵2 2 1 −1 1
3
y 𝑥𝑥3 se vuelve cero cuando 𝑥𝑥1 = 5.

Iteración 3
Ahora 𝑥𝑥1 entra en la base y 𝑥𝑥3 sale de ella:
D

𝐵𝐵 = [𝒂𝒂1 , 𝒂𝒂2 ] = � 2 3� y 𝑁𝑁 = [𝒂𝒂 , 𝒂𝒂 ] = �1 0�

ep

3 4
−1 1 0 1
ar

3
𝑥𝑥𝐵𝐵 𝑥𝑥1 𝑥𝑥3 0
ta

� 𝑥𝑥 1 � = � 𝑥𝑥 � = �58� � 𝑥𝑥 � = � �
0
m

𝐵𝐵2 2 4
5
en

−27
El valor objetivo es 𝑧𝑧 = . Se calcula 𝒘𝒘 mediante 𝒘𝒘𝐵𝐵 = 𝒄𝒄𝐵𝐵 :
to

5
de

2 3 −1 −4 −3
(𝑤𝑤1 , 𝑤𝑤2 ) � � = � �⇒𝑤𝑤1 = 5 y 𝑤𝑤2 = 5
−1 1 −3
Es

La variable 𝑥𝑥3 salió de la base en la iteración anterior y no puede entrar a la base en esta
ta

iteración, ya que 𝑧𝑧3 − 𝑐𝑐3 < 0.

dí
st

−4 −3 0 −3
ic

𝑧𝑧4 − 𝑐𝑐4 = 𝒘𝒘𝒂𝒂4 − 𝑐𝑐4 = � , � � � − 0 =

5 5 1 5
a
e

Por tanto, 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0 para todas las variables no básicas, de modo que el punto actual
I.

3 8
es óptimo. Luego, la solución óptima es (𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ) = (5 , 5 , 0,0) con valor objetivo
O
.y

−27
5
. En la figura 3.11 se describe la ruta símplex, es decir, la sucesión de pasos que
D

efectúo el método símplex para alcanzar el punto óptimo.

.M

3.8 EL MÉTODO SÍMPLEX EN FORMATO DE TABLA

.U

En cada iteración es necesario resolver los siguientes sistema de ecuaciones lineales: 𝐵𝐵𝒙𝒙𝐵𝐵 = 𝒃𝒃,
ni

𝒘𝒘𝐵𝐵 = 𝒄𝒄𝐵𝐵 y 𝐵𝐵𝒚𝒚𝑘𝑘 = 𝒂𝒂𝑘𝑘 . Varios procedimientos para resolver y actualizar estos sistemas
ve

llevarán a diferentes algoritmos, comprendidos todos dentro del modelo general del
rs

método símplex ya descrito. En esta sección se describirá el método símplex en formato

id
ad

de tabla.
de

Suponed que se tiene una solución básica factible inicial 𝒙𝒙 con base 𝐵𝐵. El problema de
programación lineal se puede representar como sigue
O
vi

Minimizar 𝑧𝑧
ed

Sujeta a 𝑧𝑧 − 𝒄𝒄𝐵𝐵 𝒙𝒙𝐵𝐵 − 𝒄𝒄𝑁𝑁 𝒙𝒙𝑁𝑁 = 0 (3.15)

o

𝐵𝐵𝒙𝒙𝐵𝐵 + 𝑁𝑁𝒙𝒙𝑁𝑁 = 𝒃𝒃 (3.16)

𝒙𝒙𝐵𝐵 , 𝒙𝒙𝑁𝑁 ≥ 𝟎𝟎
Por la ecuación (3.16) se tiene

25
 ProgM El método símplex Curso 2024-2025

𝒙𝒙𝐵𝐵 + 𝐵𝐵−1 𝑁𝑁𝒙𝒙𝑁𝑁 = 𝐵𝐵−1 𝒃𝒃 (3.17)

Multiplicando (3.17) por 𝒄𝒄𝐵𝐵 y sumando el resultado a la ecuación (3.15) se obtiene
𝑧𝑧 − 𝟎𝟎𝒙𝒙𝐵𝐵 + ( 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝑁𝑁 − 𝒄𝒄𝑁𝑁 )𝒙𝒙𝑁𝑁 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃 (3.18)

En este momento, 𝒙𝒙𝑁𝑁 = 𝟎𝟎, y de las ecuaciones (3.17) y (3.18) se obtiene 𝒙𝒙𝐵𝐵 = 𝐵𝐵−1 𝒃𝒃 y
𝑧𝑧 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃. Asimismo, de (3.17) y (3.18) es posible representar de manera conveniente
la solución básica factible actual con base 𝐵𝐵 en la siguiente tabla. Aquí, se piensa en 𝑧𝑧 como
D
ep

una variable (básica) que debe minimizarse. Se hará referencia a la fila objetivo como la fila 0 y
a las filas restantes como las filas 1 a 𝑚𝑚. La columna del lado derecho (LD) denotará los valores
ar

de las variables básicas (incluyendo el valor de la función objetivo). Las variables básicas se
ta

identificarán en la columna extrema izquierda.

m
en

𝑧𝑧 𝒙𝒙𝐵𝐵 𝒙𝒙𝑁𝑁 LD
to

𝑧𝑧 1 𝟎𝟎 𝒄𝒄𝐵𝐵 𝐵𝐵 𝑁𝑁 − 𝒄𝒄𝑁𝑁 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃 Fila 0

−1

𝒙𝒙𝐵𝐵 𝟎𝟎 𝑰𝑰 𝐵𝐵−1 𝑁𝑁 𝐵𝐵−1 𝒃𝒃 Filas 1 a 𝑚𝑚

de
Es

Se dice que la tabla en que 𝑧𝑧 y 𝒙𝒙𝐵𝐵 se expresan en términos de 𝒙𝒙𝑁𝑁 está en forma canónica,
ta

y esta tabla no sólo proporciona el valor de la función objetivo 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃 y el de las
dí

variables básicas 𝐵𝐵−1 𝒃𝒃 en el lado derecho, sino que también proporciona toda la
st

información necesaria para proceder con el método símplex. En realidad, la fila cero da
ic
a

𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝑁𝑁 − 𝒄𝒄𝑁𝑁 , que consta de los valores 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 para las variables no básicas. Así, la fila
e

cero dirá si ya se ha llegado a la solución óptima (si todo 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0), y qué variable no
I.

básica se debe incrementar en caso contrario. Si se incrementa 𝑥𝑥𝑘𝑘 , entonces el vector

O

𝒚𝒚𝑘𝑘 = 𝐵𝐵−1 𝒂𝒂𝑘𝑘 , que está representado en las filas 1 a 𝑚𝑚 en la tabla bajo la variable 𝑥𝑥𝑘𝑘 ,
.y

ayudará a determinar qué tanto es necesario incrementar 𝑥𝑥𝑘𝑘 . Si 𝒚𝒚𝑘𝑘 ≤ 𝟎𝟎, entonces 𝑥𝑥𝑘𝑘
D

puede crecer indefinidamente sin ser bloqueada y el objetivo óptimo es no acotado. Por
.M

otra parte, si 𝒚𝒚𝑘𝑘 ≰ 𝟎𝟎, entonces el incremento de 𝑥𝑥𝑘𝑘 será bloqueado por una de las
.U

variables básicas actuales, que se vuelve cero. La prueba de la razón mínima (que es
� y 𝒚𝒚 están en la tabla) determina la variable de
ni

posible efectuar ya que 𝐵𝐵−1 𝒃𝒃 = 𝒃𝒃 𝑘𝑘

ve

bloqueo. Se desearía tener un esquema, o algoritmo, que hiciera lo siguiente.

rs

1. Actualizar las variables básicas y sus valores.

id

2. Actualizar los valores de 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 de las nuevas variables no básicas.

a
d

3. Actualizar las columnas 𝒚𝒚𝑗𝑗 .

de

Pivoteo
O
vi

Todas las operaciones anteriores pueden efectuarse simultáneamente mediante una

ed

sola operación de pivoteo. Si 𝑥𝑥𝑘𝑘 entra a la base, y 𝑥𝑥𝐵𝐵𝑟𝑟 sale de la base, entonces el pivoteo
o

sobre 𝑦𝑦𝑟𝑟𝑟𝑟 se puede plantear como sigue:

1. La fila 𝑟𝑟 se divide entre 𝑦𝑦𝑟𝑟𝑟𝑟 .
2. Para 𝑖𝑖 = 1,2, … , 𝑚𝑚, con 𝑖𝑖 ≠ 𝑟𝑟, la 𝑖𝑖-ésima fila se actualiza sumándole la nueva fila
𝑟𝑟 multiplicada por −𝑦𝑦𝑖𝑖𝑖𝑖 .

26
 ProgM El método símplex Curso 2024-2025

3. La fila cero se actualiza sumándole la nueva fila 𝑟𝑟 multiplicada por 𝑐𝑐𝑘𝑘 − 𝑧𝑧𝑘𝑘 . Las
dos tablas 3.1 y 3.2 representan la situación inmediatamente antes e
inmediatamente después de cada pivoteo.
D
ep
ar
ta
m
en
to
de
Es
ta
dí
st
ic
a
e
I.
O
.y
D
.M
.U
ni
ve
rs
id
ad
de
O
vi
ed
o

A continuación, se analizarán las implicaciones de la operación de pivoteo.

27
 ProgM El método símplex Curso 2024-2025

1. La variable 𝑥𝑥𝑘𝑘 entró a la base y 𝑥𝑥𝐵𝐵𝑟𝑟 salió de la base. Lo anterior e ilustra en el lado
izquierdo extremo de la tabla reemplazando 𝑥𝑥𝐵𝐵𝑟𝑟 por 𝑥𝑥𝑘𝑘 . Para efectos de la siguiente
iteración, el nuevo 𝑥𝑥𝐵𝐵𝑟𝑟 es ahora 𝑥𝑥𝑘𝑘 .
2. El lado derecho de la tabla proporciona los valores actuales de las variables básicas
(revisad la ecuación 3.10). Las variables no básicas se mantienen iguales a cero.
3. Suponed que las columnas originales de las nuevas variables básicas y no básicas son 𝐵𝐵�
�, respectivamente. Mediante una sucesión de operaciones elementales de filas la
y 𝑁𝑁
D

tabla original se reduce a la tabla actual con 𝐵𝐵� reemplazada por 𝐼𝐼. Del tema 2, se sabe
ep

que lo anterior equivale a premultiplicar por 𝐵𝐵�−1. Por tanto, el pivoteo da como
ar

resultado una nueva tabla que proporciona la nueva 𝐵𝐵�−1 𝑁𝑁� bajo las variables no básicas,
ta

un conjunto actualizado de valores 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 para las nuevas variables no básicas, y
m

los valores de las nuevas variables básicas y la función objetivo.

en

El método símplex en formato de tabla

to
de

PASO INICIAL
Es

Se encuentra una solución básica factible inicial con base 𝐵𝐵 y se forma la siguiente tabla
inicial.
ta
dí

𝑧𝑧 𝒙𝒙𝐵𝐵 𝒙𝒙𝑁𝑁 LD
st

𝑧𝑧 1 𝟎𝟎 𝒄𝒄𝐵𝐵 𝐵𝐵 𝑁𝑁 − 𝒄𝒄𝑁𝑁 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃 Fila 0

−1
ic

𝒙𝒙𝐵𝐵 𝟎𝟎 𝑰𝑰 𝐵𝐵−1 𝑁𝑁 𝐵𝐵−1 𝒃𝒃 Filas 1 a 𝑚𝑚

a

PASO PRINCIPAL
e
I.

Sea 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 = max 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 . Si 𝑧𝑧𝑘𝑘 − 𝑐𝑐𝑘𝑘 ≤ 0, entonces el proceso ha terminado; la
O

𝑗𝑗∈𝑅𝑅
.y

solución actual es óptima. En caso contrario, se analiza 𝒚𝒚𝑘𝑘 . Si 𝒚𝒚𝑘𝑘 ≤ 𝟎𝟎, entonces el
proceso ha terminado; la solución óptima es no acotada a lo largo del rayo
D

−1 −𝒚𝒚𝑘𝑘
.M

��𝐵𝐵 𝒃𝒃� + 𝑥𝑥𝑘𝑘 � 𝑘𝑘 �: 𝑥𝑥𝑘𝑘 ≥ 0�

𝟎𝟎 𝒆𝒆
.U

en donde 𝒆𝒆𝑘𝑘 es un (𝑛𝑛 − 𝑚𝑚)-vector de ceros excepto por un 1 en la 𝑘𝑘-ésima posición. Si

ni

𝒚𝒚𝑘𝑘 ≰ 𝟎𝟎, entonces el índice 𝑟𝑟 se determina como sigue

ve
rs

𝑏𝑏�𝑟𝑟 𝑏𝑏�𝑖𝑖
= min { : 𝑦𝑦𝑖𝑖𝑖𝑖 > 0}
id

𝑦𝑦𝑟𝑟𝑟𝑟 1≤𝑖𝑖≤𝑚𝑚 𝑦𝑦𝑖𝑖𝑖𝑖

ad

La tabla se actualiza pivoteando sobre 𝑦𝑦𝑟𝑟𝑟𝑟 . Se actualizan las variables básicas y no básicas,
de

en donde 𝑥𝑥𝑘𝑘 entra a la base y 𝑥𝑥𝐵𝐵𝑟𝑟 sale de la base, y se repite el paso principal.
O

Ejemplo 3.9.-
vi
ed

Minimizad 𝑥𝑥1 + 𝑥𝑥2 − 4𝑥𝑥3

o

Sujeta a 𝑥𝑥1 + 𝑥𝑥2 + 2𝑥𝑥3 ≤ 9

𝑥𝑥1 + 𝑥𝑥2 − 𝑥𝑥3 ≤ 2
−𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 ≤ 4
𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 ≥ 0

28
 ProgM El método símplex Curso 2024-2025

Se introducen las variables de holgura no negativas 𝑥𝑥4 , 𝑥𝑥5 y 𝑥𝑥6 . El problema se convierte
en el siguiente.
Minimizad 𝑥𝑥1 + 𝑥𝑥2 − 4𝑥𝑥3
Sujeta a 𝑥𝑥1 + 𝑥𝑥2 + 2𝑥𝑥3 + 𝑥𝑥4 = 9

𝑥𝑥1 + 𝑥𝑥2 − 𝑥𝑥3 + 𝑥𝑥5 = 2

D

−𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 + 𝑥𝑥6 = 4

ep

𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 , 𝑥𝑥6 ≥ 0

ar
ta

Puesto que 𝒃𝒃 ≥ 𝟎𝟎, entonces la base inicial se puede coger como 𝐵𝐵 = [𝑎𝑎4 , 𝑎𝑎5 , 𝑎𝑎6 ] = 𝐼𝐼3 .
m

Con lo anterior se obtiene la siguiente tabla inicial.

en

Iteración 1
to
de

𝑧𝑧 𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4 𝑥𝑥5 𝑥𝑥6 LD

𝑧𝑧 1 −1 −1 4 0 0 0 0
Es

𝑥𝑥4 0 1 1 2 1 0 0 9
ta

𝑥𝑥5 0 1 1 −1 0 1 0 2
dí

𝑥𝑥6 0 −1 1 𝟏𝟏 0 0 1 4
st
ic

Iteración 2
a
e

𝑧𝑧 𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4 𝑥𝑥5 𝑥𝑥6 LD

I.

𝑧𝑧 1 3 −5 0 0 0 −4 −16
O

𝑥𝑥4 0 𝟑𝟑 −1 0 1 0 −2 1
.y

𝑥𝑥5 0 0 2 0 0 1 1 6
D

𝑥𝑥3 0 −1 1 1 0 0 1 4
.M
.U

Iteración 3
ni

LD
ve

𝑧𝑧 𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4 𝑥𝑥5 𝑥𝑥6

𝑧𝑧 1 0 −4 0 −1 0 −2 −17
rs

𝑥𝑥1 0 1 1 0 1 0 2 1
id

− −
ad

3 3 3 3
𝑥𝑥5 0 0 2 0 0 1 1 6
de

𝑥𝑥3 0 0 2 1 1 0 1 13
3 3 3 3
O
vi
ed

Esta es la tabla óptima, ya que 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≤ 0 para todas las variables no básicas. La solución
o

1 13
óptima está dada por 𝑥𝑥1 = 3, 𝑥𝑥2 = 0, 𝑥𝑥3 = y 𝑧𝑧 = −17. Observad que la base óptima
3
1 0 2
actual consta de las columnas 𝒂𝒂1 , 𝒂𝒂5 y 𝒂𝒂3 ; a saber, 𝐵𝐵 = � 1 1 −1�.
−1 0 1
Interpretación de los elementos en la tabla símplex

29
 ProgM El método símplex Curso 2024-2025

Considerad la siguiente tabla símplex general y suponed que no hay degeneración.

𝑧𝑧 𝒙𝒙𝐵𝐵 𝒙𝒙𝑁𝑁 LD
𝑧𝑧 1 𝟎𝟎 𝒄𝒄𝐵𝐵 𝐵𝐵 𝑁𝑁 − 𝒄𝒄𝑁𝑁 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃
−1

𝒙𝒙𝐵𝐵 𝟎𝟎 𝑰𝑰 𝐵𝐵−1 𝑁𝑁 𝐵𝐵−1 𝒃𝒃

La tabla puede considerarse como una representación de las variables básicas y de la

variable coste 𝑧𝑧, ambas en términos de las variables no básicas 𝒙𝒙𝑁𝑁 . Por tanto, es posible pensar
D

que las variables no básicas son variables independientes, mientras que 𝒙𝒙𝐵𝐵 y 𝑧𝑧 son variables
ep

dependientes. De la fila cero se tiene

ar
ta

𝑧𝑧 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃 − (𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝑁𝑁 − 𝒄𝒄𝑁𝑁 )𝒙𝒙𝑁𝑁 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃 − ��𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 �𝑥𝑥
𝑗𝑗
m

𝑗𝑗∈𝑅𝑅
en

y por tanto la razón de cambio de 𝑧𝑧 como función de una variable no básica cualquiera 𝑥𝑥𝑗𝑗 , es
to

decir 𝜕𝜕𝑧𝑧⁄𝜕𝜕𝑥𝑥𝑗𝑗 , es simplemente 𝑐𝑐𝑗𝑗 − 𝑧𝑧𝑗𝑗 . A fin de minimizar 𝑧𝑧, es necesario incrementar 𝑥𝑥𝑗𝑗 , si
de

𝜕𝜕𝑧𝑧⁄𝜕𝜕𝑥𝑥𝑗𝑗 < 0, es decir, si 𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 > 0. (A partir de este momento y en lo que resta del
Es

curso, todas las derivadas parciales se definen en el sentido usual de razón de cambio,
ta

manteniendo constantes en sus valores actuales a las demás variables independientes.)

dí
st

Así mismo, las variables básicas se pueden representar en términos de las variables no
ic

básicas como sigue:

a
e

𝒙𝒙𝐵𝐵 = 𝐵𝐵−1 𝒃𝒃 − 𝐵𝐵−1 𝑁𝑁𝒙𝒙𝑁𝑁 = 𝐵𝐵−1 𝒃𝒃 − � 𝐵𝐵−1 𝒂𝒂𝑗𝑗 𝑥𝑥𝑗𝑗 = 𝐵𝐵−1 𝒃𝒃 − � 𝒚𝒚𝑗𝑗 𝑥𝑥𝑗𝑗 .
I.
O

𝑗𝑗∈𝑅𝑅 𝑗𝑗∈𝑅𝑅
.y

Por consiguiente, 𝜕𝜕𝒙𝒙𝐵𝐵 ⁄𝜕𝜕𝑥𝑥𝑗𝑗 = −𝒚𝒚𝑗𝑗 es la razón de cambio de las variables básicas como función
D

de la variable no básica 𝑥𝑥𝑗𝑗 . En otras palabras, si 𝑥𝑥𝑗𝑗 se incrementa en una unidad, entonces
.M

la 𝑖𝑖-ésima variable básica 𝑥𝑥𝐵𝐵𝑖𝑖 decrece en una cantidad 𝑦𝑦𝑖𝑖𝑖𝑖 , o simplemente, 𝜕𝜕𝑥𝑥𝐵𝐵𝑖𝑖 ⁄𝜕𝜕𝑥𝑥𝑗𝑗 =
.U

−𝑦𝑦𝑖𝑖𝑖𝑖 . Alternativamente, una columna 𝒚𝒚𝑗𝑗 se puede interpretar como sigue. Recordad que
ni

𝐵𝐵𝒚𝒚𝑗𝑗 = 𝒂𝒂𝑗𝑗 y, por tanto, 𝒚𝒚𝑗𝑗 representa la combinación lineal de las columnas básicas requeridas
ve

para representar 𝒂𝒂𝑗𝑗 . Más específicamente, 𝒂𝒂𝑗𝑗 = ∑𝑚𝑚 𝑖𝑖=1 𝒂𝒂𝐵𝐵𝑖𝑖 𝑦𝑦𝑖𝑖𝑖𝑖 .
rs
id

La tabla símplex también proporciona una forma conveniente para predecir la razón de cambio
ad

de la función objetivo y el valor de las variables básicas como una función del vector del lado
derecho 𝒃𝒃. Puesto que el vector de lado derecho suele representar escasos recursos, entonces
de

la razón de cambio de la función objetivo se puede predecir si se hace variar la disponibilidad de

O

los recursos. En particular, 𝑧𝑧 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝒃𝒃 − ∑𝑗𝑗∈𝑅𝑅�𝑧𝑧𝑗𝑗 − 𝑐𝑐𝑗𝑗 �𝑥𝑥𝑗𝑗 , y por tanto, 𝜕𝜕𝑧𝑧⁄𝜕𝜕𝒃𝒃 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 . Si la
vi

identidad original consiste de variables de holgura con coste cero, entonces los elementos de la
ed

fila cero en la tabla final, bajo las variables de holgura, dan 𝒄𝒄𝐵𝐵 𝐵𝐵−1 𝐼𝐼 − 𝟎𝟎 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1, que es
o

𝜕𝜕𝑧𝑧⁄𝜕𝜕𝒃𝒃. Más específicamente, si 𝒘𝒘 = 𝒄𝒄𝐵𝐵 𝐵𝐵−1 , entonces 𝜕𝜕𝑧𝑧⁄𝜕𝜕𝑏𝑏𝑖𝑖 = 𝑤𝑤𝑖𝑖 .

De manera semejante, la razón de cambio de las variables básicas como una función del vector
del lado derecho 𝒃𝒃 está dada por 𝜕𝜕𝒙𝒙𝐵𝐵 ⁄𝜕𝜕𝒃𝒃 = 𝐵𝐵−1 . En particular, 𝜕𝜕𝑥𝑥𝐵𝐵𝑖𝑖 ⁄𝜕𝜕𝒃𝒃 es la 𝑖𝑖-ésima fila de
𝐵𝐵−1, 𝜕𝜕𝑥𝑥𝐵𝐵𝑖𝑖 ⁄𝜕𝜕 𝑏𝑏𝑗𝑗 es el elemento (𝑖𝑖, 𝑗𝑗) de 𝐵𝐵−1 .

30
 ProgM El método símplex Curso 2024-2025

Observad que si la tabla corresponde a una solución básica factible degenerada, entonces al
incrementar realmente una variable no básica 𝑥𝑥𝑗𝑗 , por lo menos una de las variables básicas
puede hacerse inmediatamente negativa (ved la ecuación 3.8), destruyendo así la factibilidad.
En este caso, la razón de cambio indicada en el valor objetivo respecto a 𝑥𝑥𝑗𝑗 no es realizable,
debido a que cuando 𝑥𝑥𝑗𝑗 crece manteniendo las demás variables no básicas en cero, los puntos
resultantes no son factibles. Observaciones semejantes se tienen para las otras derivadas
parciales. En particular, si 𝜕𝜕𝑧𝑧⁄𝜕𝜕𝑏𝑏𝑖𝑖 = 𝑤𝑤𝑖𝑖 en optimalidad, entonces aunque esta razón de cambio
es válida en el sentido acostumbrado de la derivada parcial, puede no ser el cambio realizable
D
ep

actual en el valor óptimo de la función objetivo cuando 𝑏𝑏𝑖𝑖 se incrementa en el caso de

degeneración. Como se verá más tarde en el capítulo 5, en tal caso la función objetivo 𝑧𝑧 como
ar

una función de 𝑏𝑏𝑖𝑖 puede no ser diferenciable, y entonces 𝑤𝑤𝑖𝑖 puede ser sólo la pendiente de un
ta

soporte tangencial posible de esta función en el valor actual de 𝑏𝑏𝑖𝑖 .

m
en

Identificación de 𝑩𝑩−𝟏𝟏 en la tabla símplex

to

La matriz inversa de la base se puede identificar en la tabla símplex de la siguiente manera.

de

Suponer que la tabla original tiene la matriz identidad. El proceso de reducir la matriz básica 𝐵𝐵
Es

de la tabla original a una matriz identidad en la tabla actual equivale a premultiplicar por 𝐵𝐵−1
ta

las filas de la 1 a la 𝑚𝑚 de la tabla original, a fin de obtener la tabla actual. Lo anterior también
dí

transforma la matriz identidad de la tabla original en 𝐵𝐵−1. Por tanto, 𝐵𝐵−1 se puede extraer de la
st

tabla actual como la submatriz de las filas de la 1 a la 𝑚𝑚 que está bajo las columnas de la
ic

identidad original.
a
e

Ejemplo 3.10
I.

Para ilustrar las interpretaciones de los elementos en la tabla símplex, considerad el ejemplo 3.9
O

en la iteración 2. Entonces,
.y

𝜕𝜕𝑧𝑧 𝜕𝜕𝑧𝑧 𝜕𝜕𝑧𝑧

D

𝜕𝜕𝑥𝑥1
= −3, 𝜕𝜕𝑥𝑥 = 5, 𝜕𝜕𝑥𝑥 = 4
.M

2 6

𝜕𝜕𝑥𝑥4 𝜕𝜕𝑥𝑥5 𝜕𝜕𝑥𝑥3

.U

= −3, = 0, = −1
𝜕𝜕𝑥𝑥1 𝜕𝜕𝑥𝑥1 𝜕𝜕𝑥𝑥1
ni
ve

𝜕𝜕𝒙𝒙𝐵𝐵 1
= �−2�
rs

𝜕𝜕𝑥𝑥2
−1
id
ad

𝜕𝜕𝑧𝑧 𝜕𝜕𝑧𝑧 𝜕𝜕𝑧𝑧

= = 0, = −4
𝜕𝜕𝑏𝑏1 𝜕𝜕𝑏𝑏2 𝜕𝜕 𝑏𝑏3
de

𝜕𝜕𝑥𝑥5 𝜕𝜕𝑥𝑥4
O

= 1, = −2
𝜕𝜕𝑏𝑏2 𝜕𝜕 𝑏𝑏3
vi
ed

1 0 −2
o

𝐵𝐵−1 = �0 1 1�
0 0 1
El vector 𝒂𝒂2 puede representarse como una combinación lineal de las columnas básicas como
se muestra enseguida: 𝒂𝒂2 = −1𝒂𝒂4 + 2𝒂𝒂5 + 𝒂𝒂3 .

31
 ProgM El método símplex Curso 2024-2025

EJERCICIOS

1. Considerad el programa lineal Minimizar 𝒄𝒄𝒄𝒄 sujeta a 𝐴𝐴𝒙𝒙 = 𝒃𝒃, 𝒙𝒙 ≥ 𝟎𝟎, en donde 𝒄𝒄 ≠
𝟎𝟎. Suponed que el punto 𝒙𝒙0 es tal que 𝐴𝐴𝒙𝒙0 < 𝒃𝒃 y 𝒙𝒙0 > 𝟎𝟎. Demostrar que 𝒙𝒙0 no
puede ser una solución óptima.
2. Considerad un programa lineal de maximización con puntos extremos 𝒙𝒙1 , 𝒙𝒙2 , 𝒙𝒙3 y
𝒙𝒙4 , direcciones extremas 𝒅𝒅1 , 𝒅𝒅2 y 𝒅𝒅3 , y con un gradiente 𝒄𝒄 de la función objetivo tal
que 𝒄𝒄𝒄𝒄1 = 5, 𝒄𝒄𝒄𝒄2 = 7, 𝒄𝒄𝒄𝒄3 = 4, 𝒄𝒄𝒄𝒄4 = 7, 𝒄𝒄𝒄𝒄1 = 0, 𝒄𝒄𝒄𝒄2 = −3 y 𝒄𝒄𝒄𝒄3 = 0.
D

Caracterizad el conjunto de soluciones óptimas alternativas de este problema.

ep

3. Considerad el siguiente problema de programación lineal.

ar

Maximizar 2𝑥𝑥1 + 𝑥𝑥2 − 𝑥𝑥3

ta

sujeta a 𝑥𝑥1 + 𝑥𝑥2 + 2𝑥𝑥3 ≤ 6

m
en

𝑥𝑥1 + 4𝑥𝑥2 − 𝑥𝑥3 ≤ 4

𝑥𝑥1 , 𝑥𝑥2 ≥ 0
to

Determinad la solución óptima evaluando la función objetivo en todos los puntos

de

extremos del conjunto de restricciones. Demostrar que este método es válido en

Es

este problema. Suponed ahora que la primera restricción se sustituye por 𝑥𝑥1 + 𝑥𝑥2 −
ta

2𝑥𝑥3 ≤ 6. ¿Es posible aplicar el mismo método para determinar el punto óptimo?
dí

Explicad por qué.

st
ic

4. Considerad el siguiente problema de programación lineal

a

Maximizar 2𝑥𝑥1 + 𝑥𝑥2 + 4𝑥𝑥3 + 5𝑥𝑥5 + 𝑥𝑥6

e

sujeta a 3𝑥𝑥1 + 6𝑥𝑥2 + 3𝑥𝑥3 + 2𝑥𝑥4 + 3𝑥𝑥5 + 4𝑥𝑥6 ≤ 60

I.

𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 , 𝑥𝑥6 ≥ 0

O
.y

Determinad todas las soluciones básicas factibles del problema y calculad el óptimo
comparando todas estas soluciones básicas factibles.
D
.M

5. Considerad las siguientes restricciones: 𝑥𝑥1 + 𝑥𝑥2 ≤ 3, −2𝑥𝑥1 + 𝑥𝑥2 ≤ 2, 𝑥𝑥1 − 2𝑥𝑥2 ≤ 0
.U

y 𝑥𝑥1 , 𝑥𝑥2 ≥ 0.
ni

a. Dibujar la región factible.

ve

b. Identificad los puntos extremos y en cada uno de tales puntos identificad

rs

todas las variables básicas y no básicas posibles.

id

c. Suponed que, en el espacio (𝑥𝑥1 , 𝑥𝑥2 ) el proceso se mueve del punto extremo
ad

(2,1) al punto extremo (0,0). Especificad las posibles variables de entrada y

de salida.
de

6. Resolved el siguiente problema de programación lineal aplicando el método símplex,

O

empezando con la solución básica factible (𝑥𝑥1 , 𝑥𝑥2 ) = (4,0). Graficar la región
vi

factible en el espacio de las variables no básicas.

ed

Maximizar −𝑥𝑥1 + 2 𝑥𝑥2

o

Sujeta a 3𝑥𝑥1 + 4𝑥𝑥2 = 12

2𝑥𝑥1 − 𝑥𝑥2 ≤ 12
𝑥𝑥1 , 𝑥𝑥2 ≥ 0
7. Resolved el siguiente problema de programación lineal aplicando el método símplex.
Maximizad 𝑥𝑥1 − 2𝑥𝑥2 + 𝑥𝑥3
sujeta a 𝑥𝑥1 + 2𝑥𝑥2 + 𝑥𝑥3 ≤ 12

32
 ProgM El método símplex Curso 2024-2025

2𝑥𝑥1 + 𝑥𝑥2 − 𝑥𝑥3 ≤ 6

−𝑥𝑥1 + 3𝑥𝑥2 ≤9
𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 ≥ 0
8. Considerad el siguiente problema
Maximizad 2𝑥𝑥1 + 𝑥𝑥2 + 5𝑥𝑥3 − 3𝑥𝑥4
sujeta a 𝑥𝑥1 + 2𝑥𝑥2 + 4𝑥𝑥3 − 𝑥𝑥4 ≤ 6
2𝑥𝑥1 + 3𝑥𝑥2 − 𝑥𝑥3 + 𝑥𝑥4 ≤ 12
D

𝑥𝑥1 + 𝑥𝑥3 + 𝑥𝑥4 ≤ 4

ep

𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ≥ 0

ar

Determinad una solución básica factible con las variables básicas 𝑥𝑥1 , 𝑥𝑥2 y 𝑥𝑥4 . ¿Es
ta

óptima esta solución? En caso de no serlo, entonces empezando por esta solución
m

determinar la solución óptima.

en
to

9. Un molino agrícola produce alimento para ganado. El alimento para ganado consta
de tres ingredientes principales: maíz, cal y harina de pescado. Estos ingredientes, a
de

su vez, contienen tres nutrientes: proteínas, calcio y vitaminas. En la tabla siguiente

Es

se proporcionan los contenidos de nutrientes para cada libra de ingrediente.

ta

INGREDIENTE
dí

NUTRIENTE MAÍZ CAL HARINA DE PESCADO

st

Proteínas 25 15 25
ic

Calcio 15 30 20
a

Vitaminas 5 12 8
e

Los contenidos de proteínas, calcio y vitaminas por cada libra del alimento para
I.

ganado deben estar, respectivamente, en los siguientes intervalos: [18,22], [20, ∞)

O
.y

y [6,12]. Si los precios de venta por cada libra de maíz, cal y harina de pescado son
$0.10, $0.08 y $0.12, respectivamente, calcular la mezcla menos costosa.
D
.M

10. Una empresa elabora los productos 1, 2 y 3. Cada producto requiere de un tiempo
.U

de producción en tres departamentos, como se muestra en la siguiente tabla .

PRODUCTO DEPTO. 1 DEPTO.2 DEPTO.3
ni

3h/unidad 2 h/unidad 1 h/unidad

ve

1
2 4 h/unidad 1 h/unidad 3 h/unidad
rs

3 2 h/unidad 2 h/unidad 3 h/unidad

id

En cada uno de los tres departamentos se dispone de 600, 400 y 300 horas de
a d

tiempo de producción, respectivamente. Si cada unidad de producto 1, 2 y 3

de

contribuye con una ganancia de $2, $4 y $2.5, respectivamente, determinad la

combinación óptima de productos.
O
vi

11. Considerad el siguiente problema.

ed

Maximizad −3𝑥𝑥1 + 2𝑥𝑥2 − 𝑥𝑥3 + 𝑥𝑥4

o

sujeta a 2𝑥𝑥1 − 3𝑥𝑥2 − 𝑥𝑥3 + 𝑥𝑥4 ≤ 8

−𝑥𝑥1 + 2𝑥𝑥2 + 2𝑥𝑥3 − 3 𝑥𝑥4 ≤ 10
−𝑥𝑥1 + 𝑥𝑥2 − 4𝑥𝑥3 + 𝑥𝑥4 ≤ 3
𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 ≥ 0

33
 ProgM El método símplex Curso 2024-2025

Aplicad el método símplex para verificar que la solución óptima es no acotada. Usad
la tabla símplex final para obtener una solución factible con un objetivo mayor o
igual que 3000. Usad la tabla final para construir una dirección 𝒅𝒅 tal que 𝒄𝒄𝒄𝒄 > 0.
12. Demostrad que en el método símplex, si una variable 𝑥𝑥𝑗𝑗 sale de la base, entonces no
puede entrar a la base en la siguiente iteración.
13. Determinad una solución óptima factible no básica del siguiente problema.
Maximizad 11𝑥𝑥1 + 2𝑥𝑥2 − 𝑥𝑥3 + 3𝑥𝑥4 + 4𝑥𝑥5 + 𝑥𝑥6
D
ep

sujeta a 5𝑥𝑥1 + 𝑥𝑥2 − 𝑥𝑥3 + 2𝑥𝑥4 + 𝑥𝑥5 = 12

−14𝑥𝑥1 − 3𝑥𝑥2 + 3𝑥𝑥3 − 5𝑥𝑥4 + 𝑥𝑥6 = 2
ar

1 1 1 5
ta

2𝑥𝑥1 + 𝑥𝑥2 − 𝑥𝑥3 + 𝑥𝑥4 ≤

m

2 2 2 2
1 1 3
en

3𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 + 𝑥𝑥4 ≤3

2 2 2
to

𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 , 𝑥𝑥6 ≥ 0

de

14. El siguiente planteamiento matemático describe el problema que tiene una empresa
para asignar tres recursos a la producción anual de tres artículos. Denotad por 𝑥𝑥1 , 𝑥𝑥2
Es

y 𝑥𝑥3 las cantidades que se producirán de los tres artículos. La función objetivo refleja
ta

la contribución (en pesos) de tales artículos a la ganancia.

dí

Maximizar 10𝑥𝑥1 + 15𝑥𝑥2 + 5𝑥𝑥3

st

sujeta a 2𝑥𝑥1 + 𝑥𝑥2 ≤ 6000

ic
a

3𝑥𝑥1 + 3𝑥𝑥2 + 𝑥𝑥3 ≤ 9000

e

𝑥𝑥1 + 2𝑥𝑥2 + 2𝑥𝑥3 ≤ 4000

I.

𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 ≥ 0

O

a. Sin aplicar el método símplex, comprobad que la base óptima consta de la

.y

variable de holgura de la primera restricción, de 𝑥𝑥1 y de 𝑥𝑥2 .

b. Usad la información obtenida en el apartado a. para escribir la tabla óptima.
D
.M

c. El departamento de investigación y desarrollo propone un nuevo artículo

cuyos coeficientes de producción están representados por [2,4,1]𝑡𝑡 . Si la
.U

contribución a la ganancia de este nuevo artículo es de $12 por unidad,

ni

¿debe producirse tal artículo? Si se produce, ¿cuál es el nuevo programa

ve

óptimo?
rs

d. ¿Cuál es la contribución mínima a la ganancia que es de esperar antes de que

id

la producción de este nuevo artículo incremente, de hecho, el valor de la

a d

función objetivo?
de

15. Considerad el siguiente programa lineal

Minimizar −𝑥𝑥1 − 2𝑥𝑥2 + 𝑥𝑥3
O
vi

sujeta a: 2𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 ≤ 6

ed

2𝑥𝑥2 − 𝑥𝑥3 ≤ 3
𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 ≥ 0.
o

a. Determinad la solución óptima aplicando el método símplex. En cada iteración,

identificar 𝐵𝐵, 𝑁𝑁, 𝐵𝐵−1 𝑁𝑁, 𝑐𝑐𝐵𝐵𝑡𝑡 𝐵𝐵−1 y 𝑐𝑐̅𝑗𝑗 .
𝜕𝜕𝑥𝑥 𝜕𝜕𝑥𝑥 𝜕𝜕𝑧𝑧 𝜕𝜕𝒙𝒙
b. En la tabla óptima, determinar 𝜕𝜕𝑥𝑥1, 𝜕𝜕𝑥𝑥2 , y 𝜕𝜕𝒙𝒙𝐵𝐵 , en donde 𝑥𝑥4 y 𝑥𝑥5 son las variables
3 4 𝜕𝜕𝑥𝑥5 𝑁𝑁
de holgura. Interpretad estos valores.

34
 ProgM El método símplex Curso 2024-2025

c. Suponed que 𝑐𝑐1 se cambia de −1 a −1 + ∆1 y que 𝑐𝑐2 se cambia de −2 a −2 + ∆2 .

Calcular la región de (∆1 , ∆2 ) que conserva la optimalidad de la solución obtenida
en el apartado a).
d. Suponed que se considera una nueva actividad al nivel 𝑥𝑥6 , con 𝑐𝑐6 = −3, 𝑎𝑎16 = 3 y
𝑎𝑎26 = 3. ¿Conviene producir esta actividad? Si la respuesta es afirmativa,
determinad la nueva solución óptima.
e. Suponed que 𝑏𝑏1 se cambia de 6 a 6 + ∆. Calcular el rango de ∆ que mantiene la
optimalidad de la base obtenida en el apartado a. Dar la solución óptima si 𝑏𝑏1 fuese
D

igual a 4.
ep

16. Considerad el siguiente problema de programación lineal.

ar

Maximizad 2𝑥𝑥1 + 12𝑥𝑥2 + 7𝑥𝑥3

ta

sujeta a 𝑥𝑥1 + 3𝑥𝑥2 + 2𝑥𝑥3 ≤ 10000

m

2𝑥𝑥1 + 2𝑥𝑥2 + 𝑥𝑥3 ≤ 4000

en

𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 ≥ 0

to

A continuación se muestra la solución óptima, en donde 𝑧𝑧 es la función objetivo, y

de

𝑥𝑥4 y 𝑥𝑥5 son las variables de holgura.

𝑧𝑧 𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4 𝑥𝑥5 LD
Es

𝑧𝑧 1 12 2 0 0 7 28000
ta

𝑥𝑥4 0 −3 −1 0 1 −2 2000
dí

𝑥𝑥3 0 2 2 1 0 1 4000
st

a. ¿Cuáles son las razones de incremento del objetivo como una función del
ic

lado derecho de las restricciones primera y segunda, respectivamente?

a

b. Suponed que el lado derecho de la 2ª restricción cambia a 4000 + ∆. ¿Cuál

e
I.

es el rango de ∆ que mantiene óptima la base de la tabla anterior?

O

c. Determinar explícitamente el valor óptimo 𝑧𝑧 como una función de ∆.

.y

17. Resolver por el método símplex el siguiente problema de PL:

Minimizar 𝑧𝑧 = 𝑥𝑥1 + 2𝑥𝑥2 + 4𝑥𝑥3
D

s.a. 𝑥𝑥1 + 𝑥𝑥2 ≤ 10

.M

𝑥𝑥1 + 2𝑥𝑥2 + 𝑥𝑥3 = 14

.U

𝑥𝑥1 ≥ 0, 𝑥𝑥2 ≤ 0, 𝑥𝑥3 libre.

ni

18. Dado el problema de PL:

ve

Maximizar 𝑧𝑧 = 𝑐𝑐1 𝑥𝑥1 + 2𝑥𝑥2 + 𝑥𝑥3

s.a. 𝑥𝑥1 + 2𝑥𝑥2 + 𝑎𝑎13 𝑥𝑥3 ≤ 8
rs

2𝑥𝑥1 + 4𝑥𝑥3 ≤ 𝑏𝑏2

id
a

𝑥𝑥𝑖𝑖 ≥ 0, ∀𝑖𝑖;
d

con 𝑏𝑏2 ≥ 0, y conociendo los siguientes valores de la tabla símplex óptima:

de

Básicas 𝑧𝑧 𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑠𝑠1 𝑠𝑠2 Lado derecho

𝑥𝑥1 0 3
O

𝑥𝑥2 0 1/2
vi

𝑧𝑧 1 7 1 1
ed

Hallar los valores de 𝑐𝑐1 , 𝑎𝑎13 y 𝑏𝑏2 y completar la tabla.

o

35