2

Tema 2
El m´etodo simplex
Los modelos lineales con dos o tres variables se pueden resolver gr´aficamente. En
el Tema 1 hemos visto la soluci´on gr´afica de modelos lineales de dos variables.
Sin embargo, este m´etodo no puede ser utilizado en modelos que tengan m´as de
tres variables. Para resolver modelos m´as grandes se necesita un procedimiento
algebr´aico como el algoritmo simplex, publicadoen 1949 por George B. Dantzig,
para dar soluciones num´ericas a problemas de programaci´on lineal.
El desarrollo de la teor´ıa de la programaci´on lineal se basa en la siguiente
forma de escribir el modelo.
Forma est´andar. Un modelo lineal est´a escrito en forma est´andar si todas las
restricciones son del tipo = y todas las variables del modelo y las componentes
del vector b son no negativas. Elmodelo en forma matricial:
max(min) z = cT x
sujeto a
Ax = b
x≥0
Si el objetivo es maximizar, entonces se tiene la forma est´andar de maximizaci´on y, si el objetivo es minimizar, la forma est´andar de minimizaci´on.

2.1 Cambios en el modelo
El primer paso en el proceso de encontrar la soluci´on o´ ptima de un modelo lineal es escribir el modelo en forma est´andar. La mayor´ıa de los modeloslineales
19

20

Tema 2. El m´etodo simplex

no estan inicialmente escritos en esta forma pero se pueden hacer cambios en la
funci´on objetivo, en las restricciones y en las variables del modelo para obtener la
forma est´andar.
1. Funci´on objetivo. Calcular el m´ınimo de la funci´on z es equivalente a
calcular el m´aximo de la funci´on −z.
n

min z =

n

cj xj

⇐⇒

max (−z) =

j=1

−cj xj .
j=1Por ejemplo, calcular el min z = 3x1 − 5x2 es equivalente a calcular el
max (−z) = −3x1 + 5x2 . Es decir, los valores de las variables x1 y x2
que dan a z el valor m´ınimo son los mismos que los que dan a −z el valor
m´aximo, de forma que
min z = − max (−z).
2. Restricciones.
(a) Todas las restricciones del modelo lineal se pueden escribir en el mismo
sentido dado que se verifica
n

n

aij xj ≥ bi−aij xj ≤ −bi .

⇐⇒
j=1

j=1

Por ejemplo, dada la restricci´on 2x1 +3x2 ≤ −2, multiplicando por −1
los dos miembros de la desigualdad, se puede escribir −2x1 −3x2 ≥ 2.
(b) Las restricciones se pueden escribir con igualdad de la siguiente manera:
n

n

aij xj ≤ bi

⇐⇒

aij xj + y = bi ,

j=1

j=1

n

n

aij xj ≥ bi
j=1

⇐⇒

aij xj − y = bi .
j=1

La variable y utilizada en los dos cambios anterioresse llama variable
de holgura; en ambos casos la variable y es mayor o igual que cero.
Por ejemplo, la restricci´on x1 − 4x2 ≤ 4 es equivalente a la restricci´on
x1 − 4x2 + y = 4, donde y es una variable no negativa.

OpenCourseWare, UPV/EHU

2.1. Cambios en el modelo

21

(c) Una restricci´on con igualdad es equivalente a escribir dos restricciones
con desigualdad de la siguiente manera:
n

naij xj = bi ⇐⇒
j=1

n

aij xj ≤ bi

aij xj ≥ bi .

y

j=1

j=1

Por ejemplo, la restricci´on −2x1 + x2 = 2 es equivalente a escribir las
dos siguientes:
−2x1 + x2 ≤ 2

y

− 2x1 + x2 ≥ 2.

3. Variables.
Las variables deben satisfacer la restricci´on de no negatividad. Para garantizar que se cumple dicha restricci´on se tienen los siguientes cambios:
• Si xj ≤ 0, entonces se puede hacer el siguientecambio de variable
xj = −x′j , donde x′j ≥ 0.
• Si xj no tiene restricci´on de signo, se puede escribir como diferencia
de 2 variables positivas de la siguiente forma:
xj = x′j − x′′j , donde x′j , x′′j ≥ 0.
– Si x′j > x′′j , entonces xj > 0.
– Si x′j < x′′j , entonces xj < 0.
– Si x′j = x′′j , entonces xj = 0.
Ejemplo. Escribir el siguiente modelo lineal en forma est´andar de maximizaci´on.
min z= x1 + 2x2 + x3
sujeto a
x1 + x2 − x3 ≥ 2
x1 − 2x2 + 5x3 ≤ −1
x1 + x2 + x3 = 4
x1 ≥ 0 , x2 ≤ 0, x3 : no restringida

Investigaci´on Operativa. Programaci´on Lineal

22

Tema 2. El m´etodo simplex

• Funci´on objetivo. La forma est´andar de maximizaci´on es
− max (−z) = −x1 − 2x2 − x3 .
• Cambios en las restricciones. En la primera restricci´on restamos una variable de holgura x4 ,
x1 + x2 −...